/Anytime Guaranteed Search using Spanning Trees

Anytime Guaranteed Search using Spanning Trees

Geoffrey Hollinger, Athanasios Kehagias, Sanjiv Singh, David Ferguson and Siddhartha Srinivasa
Tech. Report, CMU-RI-TR-08-36, Robotics Institute, Carnegie Mellon University, August, 2008

Download Publication (PDF)

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.


This technical report presents an anytime algorithm for solving the multi-robot guaranteed search problem. Guaranteed search requires a team of robots to clear an environment of a potentially adversarial target. In other words, a team of searchers must generate a search strategy guaranteed to find a target. This problem is known to be NP-complete on arbitrary graphs but can be solved in linear-time on trees. Our proposed algorithm reduces an environment to a graph representation and then randomly generates a spanning tree of the graph. Guards are then placed on nodes in the graph to eliminate non-tree edges, and a search strategy for the remaining tree is found using a linear-time algorithm from prior work. To reduce the number of guards, our algorithm takes advantage of the temporal characteristics of the search schedule to reuse guards no longer necessary at their previous locations. Many spanning trees are analyzed prior to search to determine the tree that yields the best search strategy. At any time, spanning tree generation can be stopped yielding the best strategy thus far. Our proposed algorithm is demonstrated on two complex graphs derived from physical environments, and several methods for generating candidate spanning trees are compared.

BibTeX Reference
author = {Geoffrey Hollinger and Athanasios Kehagias and Sanjiv Singh and David Ferguson and Siddhartha Srinivasa},
title = {Anytime Guaranteed Search using Spanning Trees},
year = {2008},
month = {August},
institution = {Carnegie Mellon University},
address = {Pittsburgh, PA},
number = {CMU-RI-TR-08-36},
keywords = {graph search, multi-robot coordination},