Abstract
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.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.