ACBS: A Bounded-Suboptimal Multi-Agent Path Finding Solver for Search-Based Problems

Abstract

Multi-Agent Path Finding (MAPF) represents a critical computational challenge in robotics and logistics, requiring the coordination of multiple agents to reach their destinations while avoiding collisions. Traditional optimal algorithms, such as Conflict-Based Search (CBS), deliver mathematically perfect solutions but demonstrate poor scalability with increasing agent populations. Bounded-suboptimal variants like Enhanced CBS (ECBS) and Explicit Estimation CBS (EECBS) attempt to balance solution quality with computational efficiency, yet encounter significant difficulties in large-scale scenarios. This paper adopts Agile Conflict-Based Search (ACBS), a novel bounded-suboptimal algorithm incorporating goal decomposition, temporal flexibility, multiple conflict resolution strategies, and agile heuristics to enhance scalability. A thorough empirical investigation on established MAPF benchmarks using agent populations from 100 to 2000 has shown that ACBS can yield up to 5× runtime improvements and higher success rates, while maintaining solution quality within a suboptimality bound of 1.2. We have found ACBS to demonstrate excellent performance in dense environments in particular, which positions it as a promising solution for online applications, including warehouse automation, and coordination of autonomous vehicles while maintaining solution quality within a suboptimality bound of while maintaining solution quality within a suboptimality bound of w = 1.2.