Abstract
Conflict-Based Search (CBS) and its enhancements
are among the strongest algorithms for Multi-Agent
Path Finding. 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 dependencies between
agents. Empirically, CBS with either new heuristic
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.