Adaptive-Horizon Conflict-Based Search for Closed-Loop Multi-Agent Path Finding

📄 arXiv: 2602.12024v1 📥 PDF

作者: Jiarui Li, Federico Pecora, Runyu Zhang, Gioele Zardini

分类: cs.RO

发布日期: 2026-02-12

💡 一句话要点

提出自适应时域冲突搜索算法ACCBS，解决闭环多智能体路径规划问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 多智能体路径规划 闭环控制 冲突搜索 自适应时域 机器人集群

📋 核心要点

  1. 现有MAPF方法要么是开环规划，难以处理扰动，要么是闭环启发式算法，缺乏可靠的性能保证。
  2. ACCBS通过动态调整规划时域，并复用约束树，实现了在计算资源限制下快速生成高质量可行解的能力。
  3. 实验表明，ACCBS在保证性能的同时，对扰动具有良好的适应性，提升了大规模机器人部署的鲁棒性。

📝 摘要（中文）

本文提出了一种名为ACCBS的闭环多智能体路径规划算法，该算法基于有限时域的冲突搜索（CBS）变体，并采用了一种受模型预测控制（MPC）中迭代加深启发的时域调整机制。ACCBS能够根据可用的计算资源动态调整规划时域，并复用单个约束树，从而实现时域之间的无缝过渡。因此，该算法能够快速生成高质量的可行解，并且随着计算资源的增加，渐近达到最优解，表现出随时可用的特性。大量的案例研究表明，ACCBS兼具对扰动的灵活性和强大的性能保证，有效地弥合了大规模机器人部署中理论最优性和实际鲁棒性之间的差距。

🔬 方法详解

问题定义：多智能体路径规划（MAPF）是自动化仓库和物流中大规模机器人集群协调的核心问题。现有的方法要么是开环规划器，生成固定的轨迹，难以处理扰动；要么是闭环启发式算法，没有可靠的性能保证，限制了它们在安全关键部署中的应用。因此，需要一种既能保证性能，又能适应环境扰动的闭环MAPF算法。

核心思路：ACCBS的核心思路是结合有限时域的冲突搜索（CBS）和模型预测控制（MPC）中的迭代加深思想。通过有限时域CBS，可以保证在一定时域内的最优性。借鉴MPC的迭代加深，ACCBS能够根据计算资源动态调整规划时域，从而在保证性能的同时，提高对环境变化的适应性。

技术框架：ACCBS的整体框架基于CBS。首先，使用有限时域的CBS进行初始规划。然后，根据可用的计算资源，动态调整规划时域。如果检测到冲突或者环境发生变化，ACCBS会重新规划当前时域内的路径。为了提高效率，ACCBS复用之前的约束树，避免了每次重新规划都从头开始。

关键创新：ACCBS的关键创新在于其自适应时域调整机制。传统的CBS算法通常使用固定的规划时域，难以适应动态变化的环境。ACCBS通过动态调整规划时域，能够在保证性能的同时，提高对环境变化的适应性。此外，ACCBS复用约束树的设计也提高了算法的效率。

关键设计：ACCBS的关键设计包括：1）有限时域CBS的实现，需要定义合适的冲突检测和解决策略；2）时域调整策略，需要根据可用的计算资源和环境变化情况，动态调整规划时域；3）约束树的复用机制，需要有效地存储和更新约束树，避免重复计算。

📊 实验亮点

实验结果表明，ACCBS算法在保证性能的同时，对扰动具有良好的适应性。与传统的CBS算法相比，ACCBS能够更快地找到可行解，并且随着计算资源的增加，能够渐近达到最优解。在多个测试场景中，ACCBS都表现出了优于其他基线算法的性能。

🎯 应用场景

ACCBS算法适用于自动化仓库、物流、交通运输等需要多智能体协同作业的场景。它可以提高机器人集群的运行效率和鲁棒性，降低运营成本，并提升安全性。未来，该算法有望应用于更复杂的机器人协作任务，例如自动驾驶、无人机编队等。

📄 摘要（原文）

MAPF is a core coordination problem for large robot fleets in automated warehouses and logistics. Existing approaches are typically either open-loop planners, which generate fixed trajectories and struggle to handle disturbances, or closed-loop heuristics without reliable performance guarantees, limiting their use in safety-critical deployments. This paper presents ACCBS, a closed-loop algorithm built on a finite-horizon variant of CBS with a horizon-changing mechanism inspired by iterative deepening in MPC. ACCBS dynamically adjusts the planning horizon based on the available computational budget, and reuses a single constraint tree to enable seamless transitions between horizons. As a result, it produces high-quality feasible solutions quickly while being asymptotically optimal as the budget increases, exhibiting anytime behavior. Extensive case studies demonstrate that ACCBS combines flexibility to disturbances with strong performance guarantees, effectively bridging the gap between theoretical optimality and practical robustness for large-scale robot deployment.