🤖 AI

Scalable Long-Horizon Planning with Staggered Updates for Lifelong MAPF

本文介绍了 PUSH，一种可扩展的终身多智能体路径规划器，它通过结合交错子集规划、窗口化路径更新以及受 EPIBT 启发的冲突解决机制，在通用地图上实现了针对数千个智能体的高吞吐量、长时程协调。

原作者： Vaibhav Sanjay, Jiaoyang Li

发布于 2026-08-10

📖 1 分钟阅读☕ 轻松阅读

原作者： Vaibhav Sanjay, Jiaoyang Li

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一个繁忙的城市，数百万辆微小、隐形的汽车正在四处穿梭，试图从 A 点到达 B 点，同时又绝不发生碰撞。这不仅仅是一场交通拥堵；这是一场被称为“多智能体路径规划”（Multi-Agent Path Finding, MAPF）的高风险舞蹈。在现实世界中，这就是那些充满机器人的仓库、分拣中心和物流车队的背后那颗隐形的“大脑”。但棘手的地方在于：在这些地方，机器人并不仅仅是开到一个位置然后离开。它们通常必须停下来，装载包裹，或者等待人类完成某些操作。这创造了一个“终身”（liflifelong）问题，即机器人在完成旧任务的同时，会不断地接到新任务。

科学家面临的巨大挑战是如何同时协调成千上万个这样的机器人。如果你试图为每个机器人规划从起点到终点的完整旅程，计算机就会不堪重负并崩溃。如果你只是告诉它们“向前走”而不看前面，它们就会因为看不见即将到来的问题而陷入交通拥堵或死胡同。这是一种在“预见长远以避免麻烦”与“快速反应以保持移动”之间的平衡艺术。

现在，一位新的英雄登场了：一种名为 PUSH 的算法。把它想象成一个超级聪明的交通指挥官，它终于找到了管理 1 万个机器人而不至于崩溃的方法。

旧方法的缺陷

为了理解为什么 PUSH 特别，让我们看看以往管理机器人的两种主要方式，以及它们各自的缺陷。

“全盘考量”法 (RHCR)：
想象一个交警试图为城市里每一辆车规划接下来一小时的路线，而且是同时进行的。这被称为“滚动时界冲突解决”（Rolling Horizon Collision Resolution, RHCR）。它擅长观察大局并避免长期交通拥堵。但它极其缓慢。如果你有 1 万个机器人，计算机在计算路径上花费的时间太多，以至于根本无法告诉机器人何时移动。这就像是在时钟滴答作响时试图解开一个拥有百万块拼图的谜题；在你完成之前，时间就用完了。

“仅看一步”法 (PIBT/EPIBT)：
现在，想象另一种交通警，他只看一步。 “好吧，向前走。如果撞墙了，就停下。”这就是“反应式”（Reactive）方法（如 PIBT 和 EPIBT）。它速度极快，可以轻松处理数千个机器人。但它存在“时间近视”（temporal myopia）的问题——这是一个高级说法，意思就是它非常短视。如果一个机器人知道自己需要等待 20 秒来装载包裹，这种短视的规划器并不会意识到这种等待会阻塞它身后的整个走廊。它只看到“移动”和“停止”，从而导致大规模且不必要的交通拥堵。

新的解决方案：PUSH

本文作者 Vaibhav Sanjay 和 Jiaoyang Li 开发了 PUSH（基于交错时界的路径更新，Path Updates over Staggered Horizons），旨在兼顾两者的优点。他们想要一个既能像慢速规划器一样看得长远，又能像反应式规划器一样移动迅速的系统。

以下是 PUSH 的工作原理，我们用一个简单的类比来说明：

1. 交错偏移（子集规划）
想象一个有 1 万人需要离开的大型体育场。与其试图在同一秒钟告诉所有人该去哪里（这会导致混乱），不如让 PUSH 先让一小组人移动。几秒钟后，再告诉下一组人。它实现了更新的“交错”。
在论文中，这意味着计算机在任何给定时刻只规划机器人的一小部分子集。这让数学计算变得简单且快速，就像反应式规划器一样。

2. 长远视角（窗口化规划）
但转折点在于：即使它一次只规划少数机器人，它也会为这些机器人规划很远的未来。它不仅仅是说“移动一步”，而是说，“这是你接下来的 10 步路径”。这就是“窗口化”的部分。这让机器人能够看到拐角处的情况，并知道前面的机器人正因为要装载包裹而停顿，从而能在到达那里之前提前减速。

3. 递归推动（优先级继承）
如果两个机器人仍然想去同一个位置怎么办？在旧的反应式系统中，它们可能会互相碰撞或尴尬地等待。PUSH 使用了一种巧妙的技巧，称为“递归优先级继承”。
想象一队人试图挤过一扇门。如果一个高优先级的人（比如等待了很久的人）需要移动，他可以“推动”一个低优先级的人让路。但神奇之处在于：那个低优先级的人并不会仅仅停在那里，他会立即寻找一个新位置，并可能推动另一个人让路。这是一种在人群中蔓als（蔓延）的礼貌推搡链式反应，直到每个人都找到合适的位置。这使得系统能够瞬间解决复杂的交通拥堵，而不会卡住。

研究发现

研究人员在两个完全不同的世界中测试了 PUSH：

“装卸平台”世界： 机器人必须停下来等待 20 秒来执行任务的地图。这是短视规划器通常失败的地方，因为它们无法预见造成的阻塞。
“狭窄走廊”世界： 拥有长而细的走廊和死胡同的地图，机器人必须非常小心，以免把自己困住。

结果：

速度： PUSH 处理高达 10,000 个智能体（机器人）的时间不到一秒。这与最快的反应式规划器处于同一规模。
吞吐量： 在“装卸平台”测试中，PUSH 移动到目标的机器人数量显著高于其他任何方法。在其中一个测试（"random-32-32-20" 地图）中，它比之前的最佳方法（EPIBT-LNS）将吞吐量提高了 300%。在另一个测试（"warehouse-large"）中，提高了 25%。
鲁棒性： 当研究人员让机器人等待时间变长（增加任务时间）时，旧的短视规划器崩溃了，而 PUSH 依然运行顺畅。
“轻量版”： 作者还测试了一个没有使用“递归推动”技巧的版本，称为 "PUSH-lite"。它在小规模群体中表现尚可，但当机器人数量过多时就会崩溃。这证明了“推动”机制对于处理人群是至关重要的。

为什么这很重要

这篇论文表明，你不需要在“快”和“聪明”之间做选择。通过将“仅为少数机器人进行规划”（子集规划）与“能够看得很远”（窗口化规划）以及“智能解决冲突”（递归推动）相结合，PUSH 解决了一个困扰多年的瓶颈问题。

这不仅仅是一个理论上的胜利。作者在用于竞赛和工业界的真实地图布局上进行了模拟。他们发现，虽然其他方法在处理几百个机器人时可能有效，但在扩展到现实中繁忙仓库所需的数千个机器人时，它们会表现得非常糟糕。PUSH 是第一个能够成功协调如此多机器人，同时又能看得足够远以避免因机器人停下工作而产生的交通拥堵的方法。

简而言之，PUSH 就像是给交通指挥官配备了一个水晶球和一个扩音器，让他们即使在道路狭窄且司机需要停下来喝咖啡的情况下，也能平稳地指挥一座拥有 1 万个机器人的城市。

技术摘要：基于交错更新的规模化长时界终身多智能体路径规划（Lifelong MAPF）

问题定义

本文研究的是终身多智能体路径规划（Lifelong Multi-Agent Path Finding, LMAPF），这是标准 MAPF 问题的一个变体，其中智能体在到达当前目标后会不断接收新目标。核心挑战是在严格的实时约束下，为大规模集群（数千个智能体）生成无碰撞路径，同时避免**时间性近视（Temporal Myopia）**问题。

现有方法在可扩展性与长时界推理之间面临权衡：

反应式规划器（如 PIBT, EPIBT）： 利用基于规则的、逐步协调的方法，可以轻松扩展到数千个智能体，但存在严重的“时间性近视”，在需要预见未来拥堵（如狭窄走廊或任务执行延迟）的场景中表现不佳。
窗口式规划器（如 RHCR）： 通过多步时界进行规划以提高预见性，但在同时对整个集群进行重规划时会产生巨大的计算开销，从而阻碍了可扩展性。
子集规划器（如 Token Passing - TP）： 通过仅对智能体的一个子集进行重规划来实现扩展，但它们受限于高度结构化的“良好形态”地图，无法处理通用拓扑结构。

本文识别出一个空白：目前还没有一种算法能够在通用地图上实现大规模的长时界规划，同时还能处理拥堵环境和任务执行延迟（Task Completion Time, TCT）。

方法论：基于交错时界的路径更新（PUSH）

作者提出了 PUSH，这是一种综合了 TP、RHCR 和 EPIBT 优点的规划器。它通过在每个时间步仅规划智能体的子集，并结合交错窗口来维持长时界推理，从而实现可扩展性。

核心机制

交错子集规划：
- 不同于 RHCR 同时重规划整个集群，PUSH 在每个时间步仅重规划智能体的子集 ( $Q$ )。
- 每个智能体被分配一个 time2Replan 计数器。当智能体的计数器归零或其当前路径被迫等待时，它会进入重规划队列。
- 这种交错方法防止了与全集群同步重规划相关的计算爆炸。
带有回退机制的窗口化路径规划：
- PUSH 为所有智能体维护一组全局性的安全、无碰撞回退路径 ( $\Pi$ )。
- 智能体不是规划通往目标的完整路径（如 TP 中那样），而是规划 $W$ -步窗口路径。
- 如果无法找到新计划，智能体会默认执行其现有的回退路径，从而保证在任何时刻都能实现无碰撞执行。
递归优先级继承与推送（Pushing）：
- 为了处理拥堵并提高路径质量，PUSH 集成了受 EPIBT 启发的优先级继承机制。
- 智能体被分配全局优先级。当高优先级智能体规划的路径与低优先级智能体发生冲突时，低优先级智能体会被“推送”。
- 被取代的智能体会递归地重新规划其路径，并暂时继承更高的优先级。这一过程持续进行，直到找到无碰撞解或达到递归限制 ( $M$ )。
- 与仅限于 1 步或短时界推送的 EPIBT 不同，PUSH 使用改进的窗口时空 A* 来寻找最优的 $W$ -步路径，且该路径最多只与一个低优先级智能体发生冲突。
随时优化（LNS）：
- 在主要规划周期之后，PUSH 利用剩余时间运行大规模领域搜索（Large Neighborhood Search, LNS）。
- 它随机选择智能体，移除它们的路径，并尝试以更高的优先级重新规划它们，以改善全局目标（最小化到目标的距离）。
- 只有当方案能改善到目标的总距离时，该解才会被接受。

理论保证

完备性： PUSH 保证在有限时间内为所有智能体返回无碰撞路径。
无死锁： 在特定条件下（双连通图、零 TCT 以及“更长经过时间”优先级排序），PUSH 保证每个智能体都能在有限个时间步内到达其目标，这与 EPIBT 的保证一致。

主要贡献

首个通用地图子集规划器： PUSH 是第一个将子集规划（用于可扩展性）与长时界窗口规划相结合的算法，适用于无需 Token Passing 那种拓扑限制的通用地图结构。
可扩展的长时界推理： 它成功协调了高达 10,000 个智能体的多步规划时界（ $W=10$ ），这是此前在通用地图上无法实现的。
对拥堵和延迟的鲁棒性： 通过集成递归优先级推送和交错更新，PUSH 有效处理了狭窄走廊、深处死胡同以及随机任务完成时间（TCT）等反应式规划器失效的场景。

实验结果

作者在两种类型的场景下将 PUSH 与基准算法（RHCR-PBS, EPIBT-LNS, PIBT 以及消融版本 PUSH-lite）进行了对比评估：

TCT 地图（任务延迟）：
- 设置： 智能体在目标点等待 $T=20$ 个时间步。
- 结果： PUSH 和 PUSH-LNS 在所有地图规模（高达 10,000 个智能体）下均实现了最高的吞吐量。
- 对比： 虽然 EPIBT-LNS 在开放地图中保持了平滑的扩展性，但在狭窄走廊和密集障碍物中性能显著下降。RHCR 随着拥堵增加而耗尽了其规划预算。PUSH-LNS 在 warehouse-large 场景下比 EPIBT-LNS 实现了 25% 的吞吐量提升，在 random-32-32-20 场景下提升了 300%。
复杂地图（结构约束）：
- 设置： 带有长走廊和死胡同的地图（Symbotic, Delivery 地图），此时 $T=0$ 。
- 结果： PUSH-LNS 取得了最高的吞吐量（例如 Symbotic 为 3.8）。
- 失效模式： EPIBT-LNS 在高密度深处走廊中表现挣扎；RHCR 经常超时。PUSH-lite 消融版本（不含递归推送）在大规模集群中出现了灾难性的性能崩溃，凸显了递归优先级置换的必要性。
消融研究：
- TCT 敏感度： PUSH-LNS 在非零 TCT 下仍保持高吞吐量，而近视规划器（EPIBT-LNS）则显著退化。
- 窗口大小 ( $W$ )： 增加 $W$ 提升了 PUSH-LNS 的性能，使其能够利用长时界规划而不发生计算崩溃。相比之下，EPIBT-LNS 在 $W=7$ 时由于可能操作的指数级爆炸而导致性能崩溃，而 RHCR 在更大的窗口下则退化为近视规划。

重要性与主张

论文声称 PUSH 弥合了反应式规划器的极端可扩展性与长时界规划器的预见性之间的关键差距。它被呈现为第一个能够实现以下目标的 LMAPF 算法：

协调 10,000 个智能体进行长时界规划。
在无需限制性拓扑假设的情况下在通用地图结构上运行。
有效管理导致反应式规划器失效的拥堵场景和任务执行延迟。

作者将 PUSH 定位为解决现实工业挑战（如机器人分拣中心）的基础性步骤，这些挑战需要同时具备大规模集群协调能力和长期预见能力，而这种组合此前被认为在通用地图上是难以实现的。建议的未来方向包括将其框架扩展到运动学约束和动态窗口调整。