The Speed vs Quality Spectrum in MAPF: A Unified Review of Suboptimal and Bounded-Suboptimal Pathfinding Solvers

Abstract

The Multi-Agent Pathfinding (MAPF) problem, a core challenge in robotics and logistics, seeks collision-free paths for multiple agents while minimizing aggregated cost. Given the NP-hard nature of MAPF, optimal solvers often fail to scale to large or highly dense environments. This review focuses exclusively on the efficient alternatives: bounded-suboptimal and suboptimal algorithms. We trace the origin of these approaches to the computational intractability of the joint state space. We classify algorithms by their solution quality guarantees, detailing bounded methods like Enhanced CBS (ECBS) and Anytime Repairing A∗ (ARA∗), which offer guaranteed performance bounds. We also review purely suboptimal and heuristic methods, such as Priority-Based Search (PBS) and Optimal Reciprocal Collision Avoidance (ORCA), which prioritize speed and scalability over global guarantees. This analysis provides a structured overview of the current state-of-the-art in scalable MAPF solving.