Conflict-Based Search for Optimal Multi-Agent Path Finding Conference Paper uri icon


  • We present a new two-level search algorithm for optimal multi-agent path finding called Conflict Based Search (CBS). At the high level, a search is performed on a tree based on conflicts between agents. At the low level, a search is performed only for a single agent at a time. Experimental results on various problems shows a speedup of up to a full order of magnitude over previous approaches.

published proceedings

  • Proceedings of the International Symposium on Combinatorial Search

author list (cited authors)

  • Sharon, G., Stern, R., Felner, A., & Sturtevant, N.

citation count

  • 1

complete list of authors

  • Sharon, Guni||Stern, Roni||Felner, Ariel||Sturtevant, Nathan

publication date

  • December 2012