Pursuit-Evasion Game
Overview
|
|
In Pursuit-Evasion Games (PEGs) multiple robots (the pursuers) collectively determine the location of one or more evaders, and try to corral them. The game terminates when every evader has been corralled by one or more robots. PEGs have motivated interesting research directions in multi-robot coordination. Pursuers may not have line-of-sight visibility to evaders, and a sensor network can help detect and track evaders.
PEG is an application case study of Tenet, a software architecture for Wireless Sensor Network. Tenet architecture provides a wireless subtract for pursuer to communicate and collect sensor data. Tenet simplifies the development of the wireless sensor applications, since it is not necessary to worry about reliability, mobility, routing tree and other issues.
Experiments
Architectural Design
Environment
We evaluate our PEG in RTH building, using Tutornet testbed, which represents a realistic setting for examining network performance as well as for evaluating PEGs. The false ceiling is heavily obstructed, so the wireless communication that we see is representative of harsh environments. The environment is also visually obstructed and is precisely the kind in which a sensor network would be used to aid the robotic search for survivors in, say, a building after a disaster, an application of pursuit-evasion.
For our experiments, lacking a magnetometer sensor, we use an "RSSI" sensor. The evader periodically sends radio beacons and sensors detect the existence of the evader by the receipt of the beacons. The beacon’s RSSI value is used as an indication of the intensity of the sensed data. Since multiple nodes can detect the evader beacon, its effect is similar to that of having a real magnetometer.
The RSSI is used to implicitly localize the evader and since we only require coarsegrain localization, it is a reasonable choice for our experiments as well.Figure 2 plots the empirically measured radio signal strength readings at various nodes in our testbed when the evader is at varying positions in the topological map. As the figure shows, the fraction of nodes detecting the radio signal is relatively small; in practice, we have observed at most a one-node error in localization using this simple technique.
|
|
Robots
|
|
Our pursuers are robots running USC’s Player/Stage software on a Linux-based platform. The robots have an 802.11 wireless interface, which they use to join the Tenet master network. They continuously convey their current position to the coordinator using IP routing on the master network.
We are working with the iRobot Create, a Roomba robot version without any vacumm cleaner capability.Here is our newer platform.
Publications
Marcos A. M. Vieira, Ramesh Govindan, Gaurav S. Sukhatme, Scalable and Practical Pursuit-Evasion with Networked Robots, Journal of Intelligent Service Robotics Special Issue on Networked Robots, August 2009. [PDF]
Marcos A. M. Vieira, Ramesh Govindan, Gaurav S. Sukhatme, Scalable and Practical Pursuit-Evasion, In Second International Conference on Robot Communication and Coordination, March 2009. [PDF]
Marcos A. M. Vieira, Ramesh Govindan, Gaurav S. Sukhatme, Optimal Policy in Discrete Pursuit-Evasion Games, No. 08-900, January 2008. [Technical Report] [HTML] [PDF]
Marcos A. M. Vieira, Ramesh Govindan, Gaurav S. Sukhatme, Scalable and Practical Pursuit-Evasion, No. 09-902, March 2009. [Technical Report] [HTML] [PDF]
Students
Faculty
Acknowledgements
This work is supported in part by the grant 2229/03-0 from CAPES - BRAZIL.
This material is based upon work supported by the National Science Foundation under Grant No. 0820230. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).