Anytime Guaranteed Search using Spanning Trees

Abstract

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.