CADENCE：预测超越成本之和的实际MAPF执行时间

CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs

作者: Abhishek S, Badrikanath Praharaj, Sreeram MV

arXiv: 2606.04746

分类: cs.RO

📝 论文摘要

多智能体路径规划（MAPF）算法日益广泛地被用于规划工业仓库及机器人共享工作空间中机器人团队的运动，然而标准MAPF算法评估指标（如总成本、总完工时间及规划器运行时间）可能掩盖规划方案选择如何转化为实际执行性能的差异。我们提出CADENCE（面向网络化连续执行的协调与行动驱动估计）方法，通过在一个固定7×7工作单元中、使用七台差速驱动机器人进行硬件研究，考察执行前可用的哪些特征能够最优预测最终的实际时钟完成时间。我们比较了总成本、规划总行进代价、基本运动负担（规划所需的基础运动量，如总完工时间、转弯次数、连续移动次数及启停转换次数）以及交互感知协调结构（规划所引发的机器人间协调量，如依赖链接、交互机器人对、依赖深度及拥塞暴露程度）。为进行测试，我们在15个场景（5个空场景、5个中等随机场景、5个瓶颈场景）中生成120个规划，并对每个规划执行四次，从而构成包含480次试验的硬件语料库。通过使用场景留出岭回归模型和试验级混合效应模型，我们发现仅依赖总成本虽然提供一定信息但不全面，而基本运动负担带来的改善最为显著，相较于仅使用总成本的模型，其留出误差在平均绝对误差上降低约48.6%–59.8%，在均方根误差上降低约44.2%–61.4%。交互感知协调特征则带来较小且不一致的增益，在混合效应分析中最为明显。在两个模型及不确定性检验中，基本运动负担是总成本之外最可靠的额外信号，表明在执行开始前的离线规划中，已可明显看出大部分执行时间差距。

📊 核心分析

🎯 研究动机

- 现有**多智能体路径规划(Multi-Agent Path Finding, MAPF)** 算法评估指标（如**总代价(Sum of Costs, SoC)**、makespan和规划器运行时间）无法充分反映实际执行性能。 - 需要研究哪些预执行特征能最好地预测最终**墙钟完成时间(wall-clock completion time)**。

🔧 核心方法

- 构建**CADENCE(Coordination and Action-Driven Estimation for Networked Continuous Execution)** 框架，在固定7x7工作区中使用7台差速驱动机器人。 - 生成120个计划（15个场景，每个执行4次），共480次硬件试验，收集**原始运动负担(primitive motion burden)** （如makespan、转弯、连续移动、启停转换）和**交互感知协调结构(interaction-aware coordination structure)** （如依赖链接、交互机器人对、依赖深度、拥挤暴露）等特征。 - 使用**留出场景的岭回归模型(scenario-held-out ridge model)** 和**试验级混合效应模型(trial-level mixed-effects model)** 比较不同特征组合对执行时间的预测能力。

💡 核心创新

- **系统性实证研究**：首次通过硬件实验系统比较了SoC、原始运动负担和交互感知协调结构对MAPF执行时间的预测能力。 - **发现关键预测指标**：**原始运动负担(primitive motion burden)** 是最可靠的额外信号，相比仅使用SoC，将**平均绝对误差(MAE)** 降低约48.6%-59.8%，**均方根误差(RMSE)** 降低44.2%-61.4%。 - **揭示局限性**：交互感知协调结构贡献较小且不统一，表明运动学因素比协调复杂性更能影响执行时间。

🏆 总体贡献

- 为MAPF领域提供了一种**基于离线特征的执行时间预测方法**，帮助规划者提前评估计划的实际性能。 - 证明了**原始运动负担(primitive motion burden)** 是比SoC更有效的执行时间预测指标，挑战了传统评估指标的充分性。 - 提供了包含480次硬件试验的**开源数据集**，促进社区对MAPF执行性能的进一步研究。