ICBS: Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding

Eli Boyarski, Ariel Felner, Roni Stern, Guni Sharon, David Tolpin, Oded Betzalel, Solomon Eyal ShimonyIJCAI 2015

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.
Figure 1: Illustration of the Conflict-Based Search (CBS) high-level tree, showing how conflicts are resolved by adding constraints and branching.

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.

Figure 6: Performance comparison of ICBS components. (a-b) show the impact of Prioritizing Conflicts (PC) and Bypassing (BP) on CBS. (c-d) show the impact of Merge and Restart (MR) on MA-CBS.

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

BibTeX
@inproceedings{boyarski2015icbs,
  author = {Eli Boyarski and Ariel Felner and Roni Stern and Guni Sharon and David Tolpin and Oded Betzalel and Solomon Eyal Shimony},
  title = {{ICBS: Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure