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

By Eli Boyarski, Ariel Felner, Roni Stern, Guni Sharon, Oded Betzalel, David Tolpin, Solomon Eyal Shimony. Symposium on Combinatorial Search, 2015

321 citations recorded by the source corpus.

Conflict-Based Search (CBS) and its generalization, Meta-Agent CBS are amongst the strongest newly introduced algorithms for Multi-Agent Path Finding. This paper introduces ICBS, an improved version of CBS. ICBS incorporates three orthogonal improvements to CBS which are systematically described and studied. Experimental results show that each of these improvements reduces the runtime over basic CBS by up to 20x in many cases. When all three improvements are combined, an even larger improvement is achieved, producing state-ofthe art results for a number of domains.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/e42c6839051d476c32e49989b9eb852277727b1c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Sven Koenig
2. Jiaoyang Li
3. Hang Ma
4. T. K. Satish Kumar
5. Ariel Felner
6. Roni Stern
7. Eli Boyarski
8. Jingjin Yu

In Computer Vision and Pattern Recognition

1. Sven Koenig
2. Jiaoyang Li
3. T. K. Satish Kumar
4. Hang Ma
5. Roni Stern
6. Ariel Felner
7. Jingjin Yu
8. Nathan R Sturtevant

Citations in the corpus

• Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks (2017, methodology): “Optimal dedicated MAPF algorithms include Independence Detection with Operator Decomposition [22], Enhanced Partial Expansion A* [7], Increasing Cost Tree Search [20], M* [29], and ConflictBased Search [19, 1, 3].”
• Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks (2019, methodology): “These columns report the maximal number of agents solved by ICBS in the scenario in which this number was smallest (“Min”) and when it was largest (“Max”).”
• Optimal Multirobot Path Planning on Graphs: Complete Algorithms and Effective Heuristics (2015, background): “recently, increasing cost tree search (ICTS [45]) and conflictbased search (CBS [46]) have further pushed the performance on cycle-free MPP.”