Abstract
Multi-Agent Path Finding (MAPF) is a computationally hard problem essential for applications in robotics and gaming. This paper presents ICBS (Improved Conflict-Based Search), which enhances the standard CBS algorithm by prioritizing "cardinal" conflicts and employing a "Merge and Restart" strategy for meta-agents. By focusing on conflicts that necessarily increase solution costs and avoiding redundant work through global search restarts, ICBS achieves up to a 5x speedup over previous state-of-the-art optimal solvers.
Introduction
Multi-Agent Path Finding (MAPF) involves finding collision-free paths for multiple agents from their respective starts to goals while minimizing total travel time. Standard Conflict-Based Search (CBS) uses a two-level approach: a low-level search for individual paths and a high-level search to resolve collisions via constraints. However, CBS often struggles with inefficient conflict selection and redundant work when agents must be merged into "meta-agents" due to high density.
Methodology
ICBS introduces four key enhancements to the CBS framework:
- Prioritizing Conflicts (PC): Utilizing Multi-Value Decision Diagrams (MDDs), ICBS identifies "Cardinal Conflicts"—those where any resolution increases the path cost for at least one agent. Prioritizing these allows the algorithm to prune the search tree more effectively.
- Merge and Restart (MR): When agents are frequently in conflict, they are merged into a meta-agent. ICBS improves on previous methods by restarting the search from the root upon merging, treating the merge as global knowledge rather than a local branch modification.
- Bypassing Conflicts (BP): This technique attempts to find alternative paths of equal cost to resolve conflicts without branching.
- Meta-Agent CBS (MA-CBS): This provides the framework for handling groups of entangled agents as single entities.
Experimental Evaluation
The authors evaluated ICBS on several benchmarks, including 8x8 grids with 15% obstacles, 20x20 empty grids, and complex maps from Dragon Age: Origins (e.g., den520d). These maps test the algorithm's performance in both dense interactions and large open areas.
Results and Discussion
ICBS demonstrated significant improvements in both runtime and success rates. It achieved up to a 5x speedup compared to previous versions of CBS. On the 8x8 grid benchmark, ICBS maintained a near-100% success rate for up to 18 agents, a significant improvement over standard CBS which dropped below 20% at 14 agents.
Key insights from the results include the effectiveness of cardinal conflict prioritization in identifying map bottlenecks and the efficiency of the global "Merge and Restart" strategy in reducing redundant search efforts.
Conclusion
ICBS significantly advances the state-of-the-art in optimal MAPF by focusing on critical conflicts and improving meta-agent management. Future research could focus on more advanced merge policies and extending these techniques to bounded-suboptimal solvers.
Summary updated