Finding Optimal Solutions to Cooperative Pathfinding Problems

TLDR

Cooperative pathfinding requires planning non‑interfering paths for multiple agents from their current states to their goals. The study introduces the first practical, admissible, and complete algorithm for cooperative pathfinding. The algorithm uses operator decomposition to reduce branching, exploits common independence in instances, and incorporates further improvements to detect additional independent subproblems. Empirical results demonstrate that the combined techniques dramatically speed up the standard admissible algorithm and enable the complete algorithm to optimally solve large cooperative pathfinding problems in milliseconds.

Abstract

In cooperative pathfinding problems, non-interfering paths that bring each agent from its current state to its goal state must be planned for multiple agents. We present the first practical, admissible, and complete algorithm for solving problems of this kind. First, we propose a technique called operator decomposition, which can be used to reduce the branching factors of many search algorithms, including algorithms for cooperative pathfinding. We then show how a type of independence common in instances of cooperative pathfinding problems can be exploited. Next, we take the idea of exploiting independent subproblems further by adding improvements that allow the algorithm to recognize many more cases of such independence. Finally, we show empirically that these techniques drastically improve the performance of the standard admissible algorithm for the cooperative pathfinding problem, and that their combination results in a complete algorithm capable of optimally solving relatively large problems in milliseconds.