  Conflict-Based Search (CBS) is a popular multi-agent path finding (MAPF)
solver that employs a low-level single agent planner and a high-level
constraint tree to resolve conflicts. The vast majority of modern MAPF solvers
focus on improving CBS by reducing the size of this tree through various
strategies with few methods modifying the low level planner. Typically low
level planners in existing CBS methods use an unweighted cost-to-go heuristic,
with suboptimal CBS methods also using a conflict heuristic to help the high
level search. In this paper, we show that, contrary to prevailing CBS beliefs,
a weighted cost-to-go heuristic can be used effectively alongside the conflict
heuristic in two possible variants. In particular, one of these variants can
obtain large speedups, 2-100x, across several scenarios and suboptimal CBS
methods. Importantly, we discover that performance is related not to the
weighted cost-to-go heuristic but rather to the relative conflict heuristic
weight's ability to effectively balance low-level and high-level work.
Additionally, to the best of our knowledge, we show the first theoretical
relation of prioritized planning and bounded suboptimal CBS and demonstrate
that our methods are their natural generalization. Update March 2024: We found
that the relative speedup decreases to around 1.2-10x depending on how the
conflict heuristic is computed (see appendix for more details).
