Abstract
Cooperative pathfinding, or Multi-Agent Pathfinding (MAPF), is a PSPACE-hard problem where multiple agents must navigate to their goals without colliding. This paper presents a practical, complete, and admissible algorithm that achieves optimal solutions by combining two novel techniques: Operator Decomposition (OD) and Independence Detection (ID). OD reduces the branching factor by serializing agent moves into intermediate states, while ID decomposes large problems into independent sub-problems. Experimental results on grid worlds demonstrate that this approach solves over 90% of instances with up to 60 agents in under one second, significantly outperforming existing suboptimal methods in both solution quality and completeness.
Introduction
The challenge of multi-agent pathfinding lies in the exponential growth of the state space. While single-agent pathfinding is efficiently handled by A*, $n$ agents moving simultaneously in a grid create a branching factor of $9^n$. This "curse of dimensionality" has historically forced researchers to choose between suboptimal "good enough" solutions or incomplete algorithms that might fail even when a path exists. This research introduces a framework that guarantees optimal, shortest-path solutions while remaining computationally feasible for practical applications like video games or warehouse robotics.
Methodology
The proposed algorithm tames complexity through two primary strategies:
1. Operator Decomposition (OD)
Standard A moves all agents simultaneously, leading to a massive branching factor. OD instead moves agents one by one. A "standard state" (where all agents have moved) transitions to the next standard state through a sequence of "intermediate states" (where only some agents have been assigned their next move). This transformation reduces the branching factor to a constant (e.g., 9 for a grid), making the search tree deeper but much narrower and more manageable for A.
2. Independence Detection (ID)
ID is a meta-algorithm that exploits the spatial sparsity of many problems. It initially plans individual optimal paths for every agent. If collisions occur, the conflicting agents are merged into a group and re-planned cooperatively using OD. This ensures that high-complexity joint planning is only applied to agents that actually interfere with one another, preventing the "mega-group" bottleneck in sparse environments.
Evaluation and Results
The researchers evaluated their approach using 10,000 random 32x32 grid world instances with 20% obstacle density and agent counts ranging from 2 to 60. The combination of OD and ID solved 90.45% of these instances in under one second each.
Key findings include:
- Optimality: The algorithm found true shortest paths, whereas industry-standard suboptimal methods like HCA* produced solutions that were, on average, 12.8 moves longer in 40-agent scenarios.
- Completeness: The algorithm successfully solved 361 difficult instances where HCA* failed to find any solution at all.
- Efficiency: By serializing moves, OD prevents the open list from being flooded with millions of unpromising nodes, while ID recognizes that most agents are physically independent.
Conclusion
By serializing moves and detecting independent agent groups, this work provides a robust solution for optimal MAPF. While performance can degrade if a problem is so congested that all agents must be merged into a single group, the algorithm's ability to handle the majority of cases in milliseconds marks a significant advancement. Future work will explore more sophisticated heuristics to account for agent congestion and dynamic environments where obstacles or goals change in real-time.
Summary updated