GSST: anytime guaranteed search

Geoffrey Hollinger, Athanasios Kehagias and Sanjiv Singh
Journal Article, Carnegie Mellon University, Autonomous Robots, Vol. 29, No. 1, pp. 99 - 118, July, 2010

View Publication

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.


We present Guaranteed Search with Spanning Trees (GSST), an anytime algorithm for multi-robot search. The problem is as follows: clear the environment of any adversarial target using the fewest number of searchers. This problem is NP-hard on arbitrary graphs but can be solved in linear-time on trees. Our algorithm generates spanning trees of a graphical representation of the environment to guide the search. At any time, spanning tree generation can be stopped yielding the best strategy so far. The resulting strategy can be modified online if additional information becomes available. Though GSST does not have performance guarantees after its first iteration, we prove that several variations will find an optimal solution given sufficient runtime. We test GSST in simulation and on a human-robot search team using a distributed implementation. GSST quickly generates clearing schedules with as few as 50% of the searchers used by competing algorithms.

author = {Geoffrey Hollinger and Athanasios Kehagias and Sanjiv Singh},
title = {GSST: anytime guaranteed search},
journal = {Autonomous Robots},
year = {2010},
month = {July},
volume = {29},
number = {1},
pages = {99 - 118},
} 2017-09-13T10:40:41-04:00