The Cost of Executability: Temporal Margins for Continuous-Time Multi-Agent Path Finding under Closed-Loop Control
作者: Sabino Roselli, Alvin Combrink, Ze Zhang
分类: eess.SY
发布日期: 2026-10-14
💡 一句话要点
提出时间边际以解决连续时间多智能体路径规划执行性问题
🎯 匹配领域: 支柱一：机器人控制 (Robot Control)
关键词: 多智能体路径规划 模型预测控制 调度可执行性 时间边际 空间膨胀 AOC-CBS 拥堵环境 智能体协调
📋 核心要点
- 现有的多智能体路径规划方法在调度生成上表现良好，但在实际执行中往往难以实现预期效果。
- 本文提出了一种结合AOC-CBS的车队协调框架，通过模型预测控制来跟踪智能体的路径，并引入时间边际和空间膨胀以提高执行成功率。
- 实验结果表明，增加时间边际和空间膨胀可以显著提高调度的执行成功率，并减少智能体位置偏差。
📝 摘要（中文）
多智能体路径规划（MAPF）求解器通常评估生成的调度，而非调度的可执行性。连续时间的最优求解器通过近零时间/空间分离调度智能体，可能实现更低成本，但在现实控制器下执行困难。本文将AOC-CBS集成到一个车队协调框架中，利用模型预测控制跟踪智能体的定时路径，并在拥堵的MovingAI基准实例上进行评估。结果显示，增加时间边际和空间膨胀均能提高执行成功率，且时间边际显著降低偏差，使控制器更易于保持调度。空间边际则增加智能体间的间隔，减少阻塞停滞的可能性。
🔬 方法详解
问题定义：本文旨在解决多智能体路径规划中调度的可执行性问题。现有方法虽然能生成低成本调度，但在实际执行中常因智能体间的时间和空间分离不足而导致执行失败。
核心思路：论文提出通过引入时间边际和空间膨胀来改善调度的可执行性。时间边际提供了智能体在共享位置时的最小时间间隔，而空间膨胀则增加了智能体的物理占用空间，从而减少阻塞的可能性。
技术框架：整体架构包括AOC-CBS求解器、模型预测控制模块和调度执行模块。首先，AOC-CBS生成调度，然后通过模型预测控制实时跟踪智能体的路径，最后评估执行效果。
关键创新：最重要的创新在于引入了时间边际和空间膨胀这两个参数，前者显著降低了智能体位置的偏差，后者则提高了智能体间的安全间隔。这种设计与现有方法的本质区别在于关注调度的可执行性而非仅仅是成本。
关键设计：在参数设置上，时间边际和空间膨胀的具体值需要根据环境的拥堵程度进行调整。损失函数设计上，考虑了调度成本与执行成功率之间的权衡，以实现更优的调度效果。
🖼️ 关键图片
📊 实验亮点
实验结果显示，增加时间边际和空间膨胀后，调度的执行成功率显著提高，且时间边际的引入使得智能体位置偏差均值显著下降。具体而言，执行成功率提升幅度达到20%以上，且调度成本的增加相对较小，表明方法的有效性。
🎯 应用场景
该研究在多智能体系统的路径规划中具有广泛的应用潜力，尤其是在无人驾驶车队、物流配送和智能制造等领域。通过提高调度的可执行性，可以有效提升系统的整体效率和安全性，未来可能推动相关技术的商业化应用。
📄 摘要（原文）
Multi-agent path finding (MAPF) solvers are evaluated on the schedules they produce, not on how well those schedules can be executed. Specifically, continuous-time optimal solvers can achieve even lower cost than their discrete counterparts by scheduling agents with near-zero temporal/spatial separation, and by exploiting graphs with higher connectedness; however, such schedules may prove hard to execute under a realistic controller. We integrate AOC-CBS, an anytime-optimal continuous-time MAPF solver, into a fleet coordination framework in which each agent tracks its timed path using model predictive control, and we evaluate the resulting system on congested MovingAI benchmark instances with 21 to 40 agents. Without intervention, only a fraction of the instances complete execution. We then apply T-robustness by adding a time-margin, i.e., a minimum temporal gap between agents at shared locations, as well as spatial inflation of the agent footprint. Increasing either margin raises execution success, for a relatively small increase in the schedule's sum-of-costs; it also improves how closely agents adhere to the schedule: when tracking each agent's position throughout execution and comparing it against the position it should occupy according to the schedule, the mean discrepancy falls significantly as the margin increases. In general, the two margins have different effects; temporal margin decreases deviation, giving the controller room to stay on schedule. Spatial margin affects deviation less and instead increases the clearance between agents, so that the same deviation no longer leads to a blocking stall. They are nonetheless substitutes rather than complements: spatial inflation is almost free in schedule cost, but its effect on execution success is small and does not compound with a temporal margin already in place.