Efficient, Guaranteed Search with Multi-Agent Teams - Robotics Institute Carnegie Mellon University

Efficient, Guaranteed Search with Multi-Agent Teams

Geoffrey Hollinger, Athanasios Kehagias, and Sanjiv Singh
Conference Paper, Proceedings of Robotics: Science and Systems (RSS '09), July, 2009

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.

BibTeX

@conference{Hollinger-2009-10260,
author = {Geoffrey Hollinger and Athanasios Kehagias and Sanjiv Singh},
title = {Efficient, Guaranteed Search with Multi-Agent Teams},
booktitle = {Proceedings of Robotics: Science and Systems (RSS '09)},
year = {2009},
month = {July},
}