Complete Approximation Algorithms for Cooperative Pathfinding Problems
Trevor Standley and Richard Korf
Problems that require multiple agents to follow non-interfering paths from their current states to their respective goal states are called cooperative pathfinding problems. We present the first complete approximation algorithm for finding these paths that is sufficiently fast for real-time applications. Furthermore, our algorithm offers a trade-off between running time and solution quality. We then refine our algorithm into an anytime algorithm that first quickly finds a solution, and then uses any remaining time to incrementally improve that solution until it is optimal or the algorithm is terminated. We compare our algorithms to those in the literature and show that in addition to completeness, our algorithms offer improved solution quality as well as competitive running time. Finally, we show that techniques similar to those we presented lead to a simple algorithm for computing an accurate lower bound on the cost of any solution to a problem instance.