webmaster: Sven Koenig

Learn all about Multi-Agent Path Finding (MAPF)


E. Boyarski, A. Felner, G. Sharon and R. Stern. Don't Split, Try To Work It Out: Bypassing Conflicts in Multi-Agent Pathfinding. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pages 47-51, 2015.

Abstract: Conflict-Based Search (CBS) is a recently introduced algorithm for Multi-Agent Path Finding (MAPF) whose runtime is exponential in the number of conflicts found between the agents’ paths. We present an improved version of CBS that bypasses conflicts thereby reducing the CBS search tree. Experimental results show that this improvement reduces the runtime by an order of magnitude in many cases.

Download the paper in pdf.

(last updated in 2022)