Graph-Based Approximation Algorithms for Cooperative Routing Problems.

This work focuses on finding good approximations to large scale, computationally complex cooperative routing problems. These optimizations may be defined on a graph, or a continuous domain on which we construct a graph. In the latter case, we show that the construction of the graph is a key step in the approximation algorithm and is vital to its performance. The remainder of this work is a combination of two differing approaches to the approximation of cooperative routing graph optimizations. In each case, the goal is the same: find fast approximation algorithms that generate close-to-optimal solutions. The first method, which we call fractal decomposition, works by recursively partitioning the graph in order to reduce the original large problem to several smaller problems. The solutions to these smaller problems are used to construct bounds on the optimal solution and generate an approximate solution. This general method applies to a wide range of graph optimizations for which the data is static, including shortest path, maximum flow, and graph search. As the number of decomposition levels increases, the computational complexity approaches O(n) at the expense of looser approximation bounds. We demonstrate the fractal decomposition method on three example problems related to cooperative routing: shortest path matrix, maximum flow matrix, and cooperative search. Large-scale simulations show that this fractal decomposition method is computationally fast and can yield good results for practical problems. The second approximation method is a receding horizon approach applied to a search problem, in which multiple agents are cooperatively searching for a mobile target in a bounded continuous region. By sampling the region of interest at locations with high target probability, we reduce the continuous search problem to an optimization on a finite graph. Paths are computed on this graph using a receding horizon approach, in which the horizon is a fixed number of waypoints. To facilitate a fair comparison between paths of varying length on a non-uniform graph, we use an optimization criterion corresponding to the probability of finding the target per unit time. Using this algorithm, we show that the team discovers the target in finite time with probability one. Simulations show that this algorithm makes efficient use of agents and performs quite well compared to previously proposed cooperative search algorithms.