This paper presents theoretically proved Agile CBS algorithm, an extension of the traditional Conflict-Based Search which is customized to support bounded-suboptimal solutions for Multi-Agent Pathfinding problems. The method uses flexible assignment of intermediate targets and adaptive resolution of constraints, focusing to improve scalability, especially in environments with high agent density. Unlike conventional CBS, which resolves conflicts reactively, Agile CBS decomposes long-term objectives into incremental sub-goals, enabling progressive planning while maintaining bounded suboptimality guarantees. The algorithm utilizes a constraint tree for high-level search and A* for low-level path computation, thereby reducing planning overhead in scenarios where optimal solvers encounter computational challenges. While theoretical in nature, this framework provides a foundation for developing scalable classical AI-based MAPF solvers.
Khan et al. (Fri,) studied this question.