Cooperative Graph Search Using Fractal Decomposition
James R. Riehl, João P. Hespanha · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · 2007
We present an algorithm based on hierarchical decomposition that finds close-to-optimal search paths for a cooperative team of agents searching for one or more targets on a graph. The method partitions the graph to create a high-level problem and several lower-level problems. Since the computations on each level are identical, the lower-level problems can be further decomposed. In this way, the problem becomes fractal in nature. We use best-case and worst-case instances of the decomposed problem to establish upper and lower bounds on the optimal search reward, and the bounds are determined with much less computation than what is required to solve the full problem. We show that as the number of decomposition levels increases, the computational complexity approaches O(n) at the expense of looser bounds on the optimal reward. A large-scale test case shows that this method is computationally fast, produces good results, and achieves true cooperation between agents.