Minimizing Makespan with Conflict-Based Search for Optimal Multi-Agent Path Finding
Published in
Adaptive Agents and Multi-Agent Systems(2025)External Links:
TL
TL;DR
It is shown that CBS can be redefined as a framework that can be fine-tuned to different objectives, and an instantiation of this framework for minimizing MKS is introduced, which can significantly outperform previous algorithms for MKS.
Abstract
Conflict-based search (CBS) is a prominent algorithm that optimally solves the Multi-Agent Path Finding problem (MAPF). There are two common objective functions for MAPF: Makespan (MKS), the time elapsed until the task ends, and Sum-Of-Costs (SOC), the sum of costs of all paths. Most existing MAPF algorithms, including CBS, were not designed particularly for minimizing MKS. In this paper, we show that CBS can be redefined as a framework that can be fine-tuned to different objectives. We introduce an instantiation of this framework for minimizing MKS. Its low-level solves a new search setting which we call Extended Bounded-Cost Search. Our experiments show that our new algorithm can significantly outperform previous algorithms for MKS. Moreover, we discuss two extensions of MKS which are also members of our general framework.