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

Here we present an anytime algorithm for clearing an environment using multiple searchers. 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). We introduce an algorithm that combines finite-horizon planning with spanning tree traversal methods to generate plans that clear the environment of a worst-case adversarial target and have good average-case performance considering a target motion model. Our algorithm is scalable to large teams of searchers and yields theoretically bounded average-case performance. We have tested our proposed algorithm through a large number of experiments in simulation and with a team of robot and human searchers in an office building. Our combined search algorithm both clears the environment and reduces average capture times by up to 75% when compared to a purely worst-case approach.

Notes

Associated Center(s) / Consortia: Field Robotics Center

Associated Project(s): EMBER

Number of pages: 8

Text Reference

Geoffrey Hollinger, Athanasios Kehagias, and Sanjiv Singh, "Efficient, Guaranteed Search with Multi-Agent Teams," Robotics: Science and Systems, July, 2009.

BibTeX Reference

@inproceedings{Hollinger_2009_6411,
   author = "Geoffrey Hollinger and Athanasios Kehagias and Sanjiv Singh",
   title = "Efficient, Guaranteed Search with Multi-Agent Teams",
   booktitle = "Robotics: Science and Systems",
   month = "July",
   year = "2009",
}

The Robotics Institute

Menu