file.pdf (431.04 kB)
0/0

Efficient, Guaranteed Search with Multi-agent Teams

Download (431.04 kB)
journal contribution
posted on 01.07.2009 by Geoffrey A. Hollinger, Sanjiv Singh, Athanasios Kehagias

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.

History

Date

01/07/2009

Exports

Keyword(s)

Exports