ENL Publications

Abstract

Marcos A. M. Vieira, Ramesh Govindan, Gaurav S. Sukhatme, Scalable and Practical Pursuit-Evasion, In Second International Conference on Robot Communication and Coordination (ROBOCOMM'09), March 2009. [PDF] [BIB]

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.

@inproceedings{Vieira09a,
	author = {Marcos A. M. Vieira and Ramesh Govindan and Gaurav S. Sukhatme},
	title = {{Scalable and Practical Pursuit-Evasion}},
	booktitle = "Second International Conference on Robot Communication and Coordination (ROBOCOMM'09)",
	year = "2009",
	month = "March",
}