2nd International ICST Conference on Robot Communication and Coordination

Research Article

Scalable and Practical Pursuit-Evasion

Download458 downloads
  • @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},
  • Marcos A. M. Vieira
    Ramesh Govindan
    Gaurav S.Sukhatme
    Year: 2009
    Scalable and Practical Pursuit-Evasion
    DOI: 10.4108/ICST.ROBOCOMM2009.5838
Marcos A. M. Vieira1,*, Ramesh Govindan1,*, Gaurav S.Sukhatme1,*
  • 1: Department of Computer Science University of Southern California
*Contact email: mvieira@usc.edu, ramesh@usc.edu, gaurav@usc.edu


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