Conflict-Based Search for Optimal Multi-Agent Path Finding

In the multi agent path finding problem (MAPF) paths shouldbe found for several agents, each with a different start andgoal position such that agents do not collide. Previous optimalsolvers applied global A*-based searches. We presenta new search algorithm called Conflict Based Search (CBS).CBS is a two-level algorithm. At the high level, a search isperformed on a tree based on conflicts between agents. At thelow level, a search is performed only for a single agent at atime. In many cases this reformulation enables CBS to examinefewer states than A* while still maintaining optimality.We analyze CBS and show its benefits and drawbacks. Experimentalresults on various problems shows a speedup ofup to a full order of magnitude over previous approaches.