LaCAM* Variants for Minimizing Makespan in Multi-Agent Path Finding

Abstract

Multi-Agent Path Finding (MAPF) requires conflict-free paths. Optimal MAPF solutions often minimize the sum of the costs of the paths (SOC), or their maximum (makespan, MKS). LaCAM* is a recent anytime MAPF solver, eventually converging to the optimal solution. However, LaCAM* was reported to have a considerably slow convergence speed to the optimum. Although this is true for SOC, in this paper, we show that LaCAM* can quickly find optimal MKS solutions. Additionally, currently, due to its anytime nature, LaCAM* uses a branch-and-bound search mechanism. We introduce a version of LaCAM* that uses IDA* and show that it has superb performance for finding optimal MKS solutions, even with thousands of agents. We explain all these phenomena.