Effectively Incorporating Weighted Cost-to-go Heuristic in Suboptimal CBS
Abstract
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 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. All 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. Contrary to prevailing beliefs, we show that the cost-to-go heuristic can be used significantly more effectively by weighting it in a specific manner alongside the conflict heuristic. We introduce two variants of doing so and demonstrate that this change can lead to 2-100x speedups in certain scenarios. Additionally, we show the first theoretical relation of prioritized planning and bounded suboptimal CBS and demonstrate that our methods are their natural generalization.
BibTeX
@conference{Veerapaneni-2022-134558,author = {Rishi Veerapaneni and Tushar Kusnur and Maxim Likhachev},
title = {Effectively Incorporating Weighted Cost-to-go Heuristic in Suboptimal CBS},
booktitle = {Proceedings of 15th International Symposium on Combinatorial Search (SoCS '22)},
year = {2022},
month = {July},
pages = {327 - 328},
keywords = {multi-agent pathfinding, heuristic search, conflict-based search},
}