精读笔记

Problem Setting

Receding Horizon Re-Ordering of Multi-Agent Execution Schedules（IEEE Transactions on Robotics / 2024）关注的是 MAPF plan 的执行阶段，而不是 MAPF 求解本身。输入是一个已规划好的多 AGV roadmap 路径及其原始时序；问题是在执行中机器人被人、第三方车辆或局部障碍大幅延迟后，是否还能安全地改变各机器人通过共享资源/交叉点的顺序。

真正困难不在于检测冲突，而在于“局部换序”和“全局无死锁”之间的矛盾。一个机器人被延迟时，让其它机器人先过在局部看合理，但多个局部换序叠加后可能在 dependency graph 中形成环，执行策略就会进入等待闭环。固定 ADG 可以保守地避免这一点，但代价是把原始 MAPF 时序中隐含的 ordering 当成不可改变的硬约束，导致延迟传播。

所以这篇论文的任务可以概括为：在不改路径、不重新求 MAPF 的条件下，把执行阶段的 ordering 从固定约束变成在线优化变量，同时保持 collision-free 和 deadlock-free 的形式化保证。

Motivation

已有路线缺的是“执行时的全局一致换序能力”。ADG/RMTRACK 类方法能容忍小延迟，但本质上是在维护原始计划的 homotopy/order；robust MAPF 能在规划阶段吸收 bounded delay，但会产生保守计划，而且对大延迟或未建模延迟不经济。局部 repair / pairwise flipping 方法虽然允许换序，但多半依据局部性能指标，无法保证 fleet-level sum-of-costs 改善，也容易把全局环检测问题留到后面。

作者的核心观察是：很多执行损失不是路径规划不好，而是原始 MAPF 的时间顺序在动态环境下过时了。若某个 AGV 因外部障碍停住，让其它 AGV 继续通过同一资源可能更优；但要做到这一点，必须知道哪些 inter-agent dependency 可以被翻转，以及翻转后是否仍保持全局依赖图无环。

因此论文不是试图做更 robust 的 MAPF，而是把 robustness 后移到 execution layer：用在线反馈根据当前进度重排 ordering。这是一个很实际的系统切分：MAPF 负责给路线和初始可行计划，SADG/RHC 负责运行时吸收大扰动。

Core Idea

论文真正的核心是 SADG：把原来的 ADG 从一个固定 directed graph 扩展为一个由 binary decisions 参数化的 graph family。每个可切换冲突依赖都有 forward 和 reverse 两种边，binary 变量决定当前采用哪个 ordering。这样，执行调度问题不再是“是否遵守原计划”，而是“在所有安全可表达的 ordering 中选一个当前代价最低且无环的依赖图”。

这个建模改变很关键。它把 MAPF 执行中的隐含时间顺序显式化为可优化的离散结构，同时保留 ADG 的安全语义：边表示必须先完成的事件，图无环表示不存在等待闭环。MILP 中的时间变量不是为了做精细轨迹规划，而是作为 certificate：如果某组切换导致环，对应的 strict precedence constraints 会不可满足；因此 feasibility 本身就是 deadlock-free 的证明。

和 prior 的本质区别在于，它不是 pairwise heuristic flipping，也不是重新规划路径，而是在 dependency graph 层面对所有候选换序做联合优化。这给了它一个很强的 inductive bias：只搜索原始 MAPF 路径诱导出的可交换 ordering 空间，而不是全 MAPF 空间，因此维度低得多；同时又比固定 ADG 有足够自由度来利用延迟带来的机会。

Method

第一，SE-ADG 提供安全执行的基底。它从 MAPF plan 编译出 action dependency graph，并强调每个 action vertex 对应空间互斥的移动段。这样做解决的是 ADG 中过细动作造成的依赖冗余问题，也为后续“单条反向依赖即可表达换序”提供结构条件。若 SE-ADG 无环，按依赖执行即可保证有限时间完成和机器人间无碰撞。

第二，switched dependency 定义了什么叫合法换序。对于一个 inter-agent dependency，反向边不是简单把边方向倒过来，而是连接到相邻 predecessor/successor event，以保证换序后两台机器人不会同时占用同一 roadmap resource。这个细节是安全性的核心，不是实现细节。

第三，SADG 把所有可切换依赖收集成 binary decision space。不可构造反向依赖的边保持固定；可构造的边进入 MILP。这样避免了在执行时任意改图，而是只在预先证明有 collision-avoidance 语义的 dependency pair 上选择。

第四，SHC/RHC MILP 同时优化事件时间和切换变量。约束包括单机器人事件顺序、激活 inter-agent dependency 的 precedence、以及新切换边的 head 必须仍是 staged。后者防止在机器人已经开始执行某事件后 retroactively 插入一个它已经违反的前置约束。

第五，RHC 的图切分是可实时性的关键。有限 horizon 不是简单截断，否则 horizon 外可能形成回边导致全局环。作者扩展有限子图直到外部不再有边指向内部，从而保证 horizon 内图与 horizon 外 acyclic SE-ADG 之间只有单向连接；根据图论引理，局部无环推出整体无环。

Key Insight / Why It Works

这篇论文有效的根本原因不是 MILP 本身，而是找到了 MAPF 执行问题中的一个合适 latent structure：原始计划诱导的 dependency graph。延迟下需要调整的不是连续轨迹，也不一定是路径，而是有限个冲突资源的先后顺序。SADG 正好把这个低维结构显式暴露出来。

最核心贡献是“可切换依赖 + 无环 feasibility certificate”。一旦换序被编码成 precedence constraints，deadlock-free 不需要额外复杂逻辑；任何环都会在时间不等式中产生矛盾。这使得 MILP 求解器同时承担优化和安全验证角色。相比重新跑 MAPF，它搜索空间小很多；相比局部 swapping，它有全局一致性。

RHC 的贡献更偏系统/工程，但不是纯 engineering。简单缩 horizon 会破坏全局无环保证；作者的 finite horizon SADG subset 通过单向边分割保存了递归可行性。这一点是把方法从概念推进到实时系统的关键。不过性能增益主要来自短 horizon 内及时释放被延迟 AGV 阻塞的依赖链，属于 test-time compute + structure-aware scheduling，而不是更强的全局规划能力。

dependency grouping、horizon 选择、big-M MILP 都更像 scaling machinery。它们对实时性很重要，但不改变方法本质。若没有 SADG 的可交换依赖空间和无环约束，这些优化没有独立价值。

需要注意，所谓“动态优化累计完成时间”并不是在完整真实未来上最优。MILP 使用的是当前状态和估计剩余事件时间，动态障碍未来行为没有被建模。因此它更像在线 reactive schedule repair，而不是 stochastic optimal control。论文没有声称完整预测，这一点合理，但也限定了上限。

Relation To Prior Work

这篇属于 MAPF execution policy / schedule repair 谱系，而不是 MAPF solver 谱系。最接近的是 ADG、RMTRACK、coordination-space homotopy 以及允许局部 order flipping 的方法。它继承了 ADG 的关键思想：把多机器人执行安全性转成依赖图执行；也继承了 segment graph / flipping order 的思想：冲突区域的通过顺序可以改变。

真正新增的是把 flipping 从局部 pairwise operation 提升为一个全局 combinatorial optimization problem，并且用 SADG 明确哪些 dependency 可以切换、切换后对应哪条安全边、如何保证图无环。换句话说，看似新的是 SADG 数据结构，实质创新是“将可换序空间编译成可由 MILP 联合选择的图族”。

和 robust MAPF 的差异更本质。robust MAPF 在规划阶段为所有可能 delay 留 buffer，因此对小 bounded delay 更有理论针对性，但会牺牲 nominal plan 并且扩展性差；SADG 则接受 nominal 或 suboptimal MAPF plan，然后在执行阶段根据真实发生的 delay 调整 ordering。它不是更强的 robust planner，而是更灵活的 execution-layer feedback controller。

和实时 re-planning 的关系文中没有充分展开。SADG 避免改变路径，因此比 rolling MAPF 便宜且更容易证明执行安全；但当最优响应需要改路径时，它只能在固定路线的 ordering 空间内修补。这是它的技术边界。

Dataset / Evaluation

评估覆盖了多种仓储风格 roadmap、不同 fleet size、不同人工延迟模式，并比较了固定 ADG 和 K-CBSH-RM。总体上实验确实验证了核心 claim：当延迟较大且局部时，在线 re-ordering 能显著减少不必要等待；当延迟较小且可由 bounded robust MAPF 覆盖时，robust MAPF 并不劣，甚至更适配。

Gazebo/ROS 仿真增加了一定部署可信度，因为延迟来自 move_base 与动态障碍交互，而不只是手工 stop model。但仍然不是真实机器人 fleet，底层导航、通信、定位误差和交通规则执行的不确定性没有充分暴露。

实验的明显 limitation 是对比对象仍偏有限。ADG baseline 很合理，因为它直接对应“固定顺序执行”；K-CBSH-RM 也合理，因为它代表 robust MAPF。但没有与在线 MAPF re-planning、bounded-suboptimal rolling repair、或更强的 decentralized/local priority reordering 做系统比较。因此实验足以支持“比固定 ADG 更好”和“对大延迟比小 k robust MAPF 更实用”，但不足以证明它是 execution-time replanning 的最优范式。

另外，评估中的 delay 模型有利于 SADG：大延迟但路径仍可继续，且换序机会丰富。对于稀疏图、瓶颈通道、或需要改路径绕行的场景，增益会自然下降；论文也显示稀疏 Islands map 改善较小。

Limitation

第一，固定路径是假设也是上限。SADG 只改变 ordering，不改变 route。如果动态障碍长期阻塞某段路径，或者 congestion 的根源是路径选择错误，方法只能重新排序等待队列，不能创造新的通行能力。

第二，安全证明依赖抽象准确性。碰撞被归约为 roadmap vertex/edge 上的空间互斥事件，且 Assumption 1 要求单机器人能处理静态/动态障碍。实际部署中，连续空间中的 footprint、非完整约束、定位误差、通信延迟、controller overshoot 都可能破坏这个抽象。论文在仿真中验证了，但没有充分讨论真实系统如何保证 SE-ADG 事件边界与底层控制一致。

第三，初始 SE-ADG 必须无环。作者认为在 |V| > N 或稍改 MAPF solver 时容易满足，但这仍然是一个前提：如果初始计划本身依赖精确同步或高密度占用，SADG 不能从不可执行结构中自动恢复。

第四，MILP scaling 仍是潜在瓶颈。RHC 和 dependency grouping 把问题压小，但 binary variable 数量仍由 horizon 内冲突密度决定。高密度十字路口、长 AGV 队列、复杂交织路径会使 branch-and-bound 变慢。文中展示 70 AGV 下短 horizon 可实时，但这不等价于大规模仓储所有拓扑都可实时。

第五，RHC 的目标是局部近似。短 horizon 下的换序可能降低近期完成时间，却制造后续拥堵；论文用实验说明小 horizon 效果不错，但没有给出性能界或 regret 分析。长期最优性未被证明。

第六，与在线重新规划相比，问题可能只是被转移：MAPF solver 的复杂性被替换成 execution MILP 的复杂性和 fixed-route suboptimality。这个 trade-off 在本文场景成立，但泛化到 lifelong MAPF 或高动态任务流仍需重新验证。

Takeaway

1. 最值得迁移的 insight 是：多机器人执行中的很多鲁棒性问题可以在 dependency graph 层解决，而不是立即回到路径规划层。
把 ordering 显式化为可优化变量，是比简单加 buffer 更有效的运行时适应机制。
2. SADG 的价值在于提供了一个“安全可交换空间”：不是所有 priority 都能随便改，只有能构造 switched dependency 且不违反 staged 状态的边才能改。
这种先编译可行动作空间、再在线优化的模式适合迁移到交叉口调度、自动仓储、列车/AGV 资源占用等问题。

一句话总结

这篇论文把 MAPF 执行期鲁棒性从“固定 ADG 同步”推进到“在可切换依赖图族中做 receding-horizon 调度优化”，其核心贡献是用 SADG 将安全换序空间显式化，并用无环可行性保证在线重排不会引入死锁。