Ariel Felner

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.