The Robotics Institute

Carnegie Mellon Robotics Institute

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

We present an anytime algorithm for coordinating multiple autonomous searchers to find a potentially adversarial target on a graphical representation of a physical environment. This problem is closely related to the mathematical problem of earching for an adversary on a graph. Prior methods in the literature treat multi-agent search as either a worst-case problem (i.e. clear an environment of an adversarial evader with potentially infinite speed), or an average-case problem (i.e. minimize average capture time given a model of the target’s motion). Both of these problems have been shown to be NP-hard, and optimal solutions typically scale exponentially in the number of searchers. We propose treating search as a resource allocation problem, which leads to a scalable anytime algorithm for generating schedules that clear the environment of a worst-case adversarial target and have good average-case performance considering a non-adversarial motion model. Our algorithm yields theoretically bounded average-case performance and allows for online and decentralized operation, making it applicable to real-world search tasks. We validate our proposed algorithm through a large number of experiments in simulation and with a team of robot and human searchers in an office building.

Keywords

multi-robot coordination, autonomous search, pursuit/evasion, decentralized planning

Notes

Sponsor: National Science Foundation

Associated Center(s) / Consortia: Field Robotics Center

Associated Project(s): EMBER

Number of pages: 18

Text Reference

Geoffrey Hollinger, Sanjiv Singh, and Athanasios Kehagias, "Improving the Efficiency of Clearing with Multi-agent Teams," International Journal of Robotics Research, Vol. 29, No. 8, July, 2010, pp. 1088-1105.

BibTeX Reference

@article{Hollinger_2010_6640,
   author = "Geoffrey Hollinger and Sanjiv Singh and Athanasios Kehagias",
   title = "Improving the Efficiency of Clearing with Multi-agent Teams",
   journal = "International Journal of Robotics Research",
   pages = "1088-1105",
   publisher = "Springer",
   month = "July",
   year = "2010",
   volume = "29",
   number = "8",
}

The Robotics Institute

Menu