Publication

X. Wu, S. Zhao and Z. Ren. BCBS-AA: Bounded Sub-Optimal Conflict-Based Search for Multi-Agent Path Finding with Asynchronous Actions. In International Symposium on Combinatorial Search (SoCS), 2026.

Abstract: This paper develops bounded-suboptimal search for Multi-Agent Path Finding with asynchronous, non-unit-time actions. It shows that directly adapting recent MAPF bound-distribution techniques can perform poorly when action durations are heterogeneous and asynchronous. The proposed method distributes suboptimality bounds while accounting for action timing and agent speeds, and prioritizes high-level search nodes using conflict intensity. Experiments report higher success rates and fewer search expansions than existing approaches.

Download the paper in pdf.