提出新算法DECBS，加速多智能体路径规划求解。
Accelerating Focal Search in Multi-Agent Path Finding with Tighter Lower Bounds
- 用最大下界值引导最优优先搜索，扩大早期搜索空间。
- 相比ECBS，高阶节点减少近30%，低阶焦点搜索节点减半。
- 适合中高密度场景，提升23.5%运行效率，兼容现有优化技术。
多智能体路径规划（MAPF）旨在为多个智能体寻找无碰撞路径并最小化代价函数——这是一个NP难问题。基于冲突的有界次优方法如增强型冲突搜索（ECBS）和显式估计算法CBS（EECBS）通过聚焦搜索机制在解的质量与计算效率间取得平衡。然而传统聚焦搜索存在局限：决定节点进入焦点列表的下界值在搜索初期增长缓慢，导致搜索空间受限，延迟找到有效解。本文提出一种新型有界次优算法——双倍ECBS（DECBS），首先确定最大下界值，再以此下界引导最优优先搜索，快速寻得无碰撞路径。实验表明，DECBS在多数测试案例中优于ECBS，且兼容现有优化技术。其可减少近30%的高阶冲突树节点和50%的低阶焦点搜索节点；在中高密度场景下，相同次优性约束与优化条件下，平均运行时间比ECBS提升23.5%。
原文摘要 · Abstract (English)
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% high-level CT nodes and 50% low-level focal search nodes. When agent density is moderate to high, DECBS achieves a 23.5% average runtime improvement over ECBS with identical suboptimality bounds and optimizations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。