Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search: Preliminary Results


  • Jiaoyang Li University of Southern California
  • Eli Boyarski Ben-Gurion University of the Negev
  • Ariel Felner Ben-Gurion University of the Negev
  • Hang Ma University of Southern California
  • Sven Koenig University of Southern California



Conflict-Based Search (CBS) and its enhancements are among the strongest algorithms for Multi-Agent Pathfinding. Recent work introduced an admissible heuristic to guide the high-level search of CBS. In this work, we prove the limitation of this heuristic, as it is based on cardinal conflicts only. We then introduce two new admissible heuristics by reasoning about the pairwise dependency between agents. Empirically, CBS with both new heuristics significantly improves the success rate over CBS with the recent heuristic and reduces the number of expanded nodes and runtime by up to a factor of 50, yielding a new state-of-the-art CBS-based algorithm.