Distributed Algorithms for Pursuit Evasion Games

Luca Schenato and Bruno Sinopoli
(Professor S. Shankar Sastry)
(DARPA) BAA 01-06

In the past few years we have been witnessing the explosion of Internet and wireless networking. Computation and communication are becoming ubiquitous and affordable at very large scale. An enormous amount of information becomes readily available to assist any decision process. Centralized algorithms for computation of this information are doomed to fail because of their intrinsic lack of scalability. In this research we propose to develop a framework for the design of distributed algorithms for large wireless sensor networks and evaluate their performance with respect to some predefined metrics. In particular, we propose to integrate a wireless sensor network into the pursuit evasion games (PEGs) framework [1]. In this framework, a group of unmanned pursuers (ground robots and helicopters) monitors an unknown terrain searching for evaders. The pursuers cooperate via radio communication to catch the moving evaders. We propose to extend this framework by deploying, into the environment, a large scale wireless sensor network consisting of about one thousand nodes. Every node in this network is equipped with sensors capable of detecting an object moving nearby, and it is subject to tight power, bandwidth, and communication constraints. Any centralized algorithm to estimate the position and track the motion of the evaders would show poor scalability properties in this modified scenario. In our approach we propose alternative algorithms where computation is distributed among the nodes and then transmitted to the pursuers.

H. J. Kim, R. Vidal, D. H. Shim, O. Shakernia, and S. Sastry, "A Hierarchical Approach to Probabilistic Pursuit-Evasion Games with Unmanned Ground and Aerial Vehicles," IEEE Conf. Decision and Control, Orlando, FL, December 2001.

More information (http://robotics.eecs.berkeley.edu/~sinopoli) or

Send mail to the author : (sinopoli@eecs.berkeley.edu)

Edit this abstract