Efficient, guaranteed search with multi-agent teams

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. Download: Bibtex: @INPROCEEDINGS{ Hollinger-RSS-09, AUTHOR = {G. Hollinger AND S. Singh AND A. Kehagias}, TITLE = {Efficient, guaranteed search with multi-agent teams}, BOOKTITLE = {Proceedings of Robotics: Science and Systems}, YEAR = {2009}, ADDRESS = {Seattle, USA}, MONTH = {June}, DOI = {10.15607/RSS.2009.V.034} }