Research Article
Scalable and Practical Pursuit-Evasion
@INPROCEEDINGS{10.4108/ICST.ROBOCOMM2009.5838, author={Marcos A. M. Vieira and Ramesh Govindan and Gaurav S.Sukhatme}, title={Scalable and Practical Pursuit-Evasion}, proceedings={2nd International ICST Conference on Robot Communication and Coordination}, proceedings_a={ROBOCOMM}, year={2009}, month={5}, keywords={}, doi={10.4108/ICST.ROBOCOMM2009.5838} }
- Marcos A. M. Vieira
Ramesh Govindan
Gaurav S.Sukhatme
Year: 2009
Scalable and Practical Pursuit-Evasion
ROBOCOMM
ICST
DOI: 10.4108/ICST.ROBOCOMM2009.5838
Abstract
In this paper, we consider the design and implementation of practical, yet near-optimal, pursuit-evasion games. In prior work, we developed, using the theory of zero-sum games, minimal completion-time strategies for pursuit-evasion. Unfortunately, those strategies do not scale beyond a small number of robots. In this paper, we design and implement a partition strategy where pursuers capture evaders by decomposing the game into multiple multi-pursuer single-evader games. Our algorithm terminates, has bounded capture time, is robust, and is scalable in the number of robots. In our implementation, a sensor network provides sensing-at-a-distance, as well as a communication backbone that enables tighter coordination between pursuers. Our experiments in a challenging office environment suggest that this approach is near-optimal, at least for the configurations we have evaluated. Overall, our work illustrates an innovative interplay between robotics and communication