How can I speed up multi-agent pathfinding?
Accelerating Focal Search in Multi-Agent Path Finding with Tighter Lower Bounds
This paper introduces DECBS, an improved algorithm for Multi-Agent Path Finding (MAPF), the problem of finding collision-free paths for multiple agents. DECBS optimizes the "focal search" process used in existing MAPF solvers by employing a two-phase "double search." First, a shortest path search determines a maximum lower bound cost. Second, a best-first search uses this bound to find less collision-prone paths more efficiently. This reduces both high-level planning and low-level pathfinding computation, especially in denser multi-agent scenarios. While less impactful in sparse environments, the core idea of using pre-computed bounds for more efficient focal search could potentially be applied to other multi-objective optimization problems, possibly including those relevant to LLM-based multi-agent coordination and planning in web applications.