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

Authors

  • Eli Boyarski Bar-Ilan University
  • Ariel Felner Ben-Gurion University of the Negev
  • Roni Stern Ben-Gurion University of the Negev
  • Guni Sharon Ben-Gurion University of the Negev
  • Oded Betzalel Ben-Gurion University of the Negev
  • David Tolpin Ben-Gurion University of the Negev
  • Eyal Shimony Ben-Gurion University of the Negev

DOI:

https://doi.org/10.1609/socs.v6i1.18343

Keywords:

Heuristic search, Multi-agent, pathfinding, optimal, cbs, ma-cbs

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.

Downloads

Published

2021-09-01