AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Symposium on Combinatorial Search, 8

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

Authors

Eli Boyarski,Ariel Felner,Roni Stern,Guni Sharon,Oded Betzalel,David Tolpin,Eyal Shimony

Bar-Ilan University,Ben-Gurion University of the Negev,Ben-Gurion University of the Negev,Ben-Gurion University of the Negev,Ben-Gurion University of the Negev,Ben-Gurion University of the Negev,Ben-Gurion University of the Negev


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 8

Volume

Issue:

Vol. 8 No. 1 (2015): Eighth Annual Symposium on Combinatorial Search

Track:

Abstracts

Downloads:

Download PDF

Abstract:

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.

DOI:

10.1609/socs.v6i1.18343


SOCS

Vol. 8 No. 1 (2015): Eighth Annual Symposium on Combinatorial Search