Publication

Y. Tang, Z. Yu, J. Li and S. Koenig. Accelerating Focal Search in Multi-Agent Path Finding with Tighter Lower Bounds. In IEEE International Conference on Intelligent Robots and Systems (IROS), pages 14111-14117, 2025.

Abstract: Multi-Agent Path Finding (MAPF) involves finding collision-free paths for multiple agents while minimizing a cost function - an NP-hard problem. Bounded suboptimal methods like Enhanced Conflict-Based Search (ECBS) and Explicit Estimation CBS (EECBS) balance solution quality with computational efficiency using focal search mechanisms. While effective, traditional focal search faces a limitation: the lower bound (LB) value determining which nodes enter the FOCAL list often increases slowly in early search stages, resulting in a constrained search space that delays finding valid solutions. In this paper, we propose a novel bounded suboptimal algorithm, double-ECBS (DECBS), to address this issue by first determining the maximum LB value and then employing a best-first search guided by this LB to find a collision-free path. Experimental results demonstrate that DECBS outperforms ECBS in most test cases and is compatible with existing optimization techniques. DECBS can reduce nearly 30 percent high-level Constraint Tree (CT) nodes and 50 percent low-level focal search nodes. When agent density is moderate to high, DECBS achieves a 23.5 percent average runtime improvement over ECBS with identical suboptimality bounds and optimizations.

Download the paper in pdf.