🤖 AI

A Theoretical Framework for Parallel Lifelong MAPF Using Group Decentralized Planning

本文从理论上证明了滚动时域冲突解决（RHCR）框架在终身多智能体路径规划中的近优性，并利用这一见解提出了分组去中心化 RHCR（GD-RHCR），这是一种通过对智能体进行分区来实现高吞吐量和高扩展性的并行规划方法，在保持近优保证的同时显著降低了计算成本。

原作者： Alex DeWeese, Jiaoyang Li, Guannan Qu

发布于 2026-08-19

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Alex DeWeese, Jiaoyang Li, Guannan Qu

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

在现代物流这个繁忙且自动化的世界里，一场无声的挑战每秒都在数字地图上上演。想象一下仓库的地面，数百个小型机器人必须将包裹从一点移动到另一点，不断地绕过货架、墙壁以及彼此。这就是多智能体路径规划（multi-agent pathfinding）的领域，该领域致力于研究如何让许多移动物体从起点到达终点而不发生碰撞。当这些机器人仅进行单次行程时，问题虽然困难但尚可应对。然而，在真实的仓库中，工作永不停歇；一旦机器人放下包裹，它会立即被分配新的任务。这种持续的循环被称为终身路径规划（lifelong pathfinding）。目标很简单：让机器人尽可能快地移动，以最大化交付包裹的数量。难点在于数学问题；随着地面上机器人的增加，它们可能发生碰撞的可能性呈指数级增长，以至于试图规划路径的计算机可能会不堪重负，导致整个作业陷入停滞。

研究人员长期以来一直在寻求速度与安全之间的平衡。一种流行的被称为“滚动视界冲突解决”（rolling-horizon collision resolution）的方法，通过观察短期的未来来为所有机器人同时规划安全的路径。这种方法在保持交通顺畅和避免拥堵方面表现出色，但代价高昂：计算机必须每隔几秒钟就进行大量的计算，为每一个机器人同时计算这些路径。另一种方法速度极快，但往往会做出贪婪且短视的决策，从而导致机器人因互相等待而陷入死锁。卡内基梅隆大学的研究人员面临的核心问题是，他们能否在保持这种细致、缓慢的方法的高性能的同时，使其足够快，以便处理数百个机器人而不至于让计算机崩溃。

由 Alex DeWeese、Jiaoyang Li 和 Guannan Qu 领导的团队通过重新思考机器人如何通信和规划来解决这个问题。他们首先证明了一个理论点：这种细致、缓慢的方法之所以有效，是因为它忽略了在时间上过于遥远的相互作用。如果一个机器人正在规划未来二十步的路径，它不需要担心可能发生在五十步之后的碰撞。基于这一洞察，他们提出了一个名为“分组去中心化滚动视界冲突解决”（Group Decentralized Rolling-Horizon Collision Resolution）的新框架。该系统不再将整个仓库视为一个需要同时解决的巨大问题，而是根据机器人之间的距离将其划分为更小的、独立的组。距离较远的机器人被归入不同的组，并允许它们并行规划各自的路径，在规划期间实际上忽略了彼此。

这种划分并非随意，而是基于特定的距离阈值。如果两个机器人处于一定范围内，它们被视为同一组，并且必须进行协调以避免碰撞。如果它们在该范围之外，系统则假设它们不可能在规划窗口内发生碰撞，因此可以分别进行规划。研究人员在数学上证明了这种分离并不会显著损害解决方案的质量。事实上，他们表明这种基于分组的新方法在表现上与原始的、较慢的方法一样，极其接近最优解。关键区别在于，通过将问题分解成更小的块，计算机可以更快地解决每个部分。此外，系统足够聪明，仅在必要时才为各组重新规划。如果一组机器人在预先计算好的路径上平稳移动，计算机就不会浪费时间重新计算它们的路线，直到发生变化（例如有新机器人进入其区域）。

为了测试他们的想法，研究人员在各种地图布局上进行了广泛的模拟，从简单的开阔地面到拥有许多障碍物的复杂仓库设计。他们将这种新方法与标准的细致方法以及快速的贪婪方法进行了对比。结果令人瞩目。在许多场景中，新方法实现了几乎与细致、缓慢的方法相当的高吞吐量（即每小时交付几乎同样多的包裹），但其消耗的计算能力仅为后者的极小部分。在某些测试中，计算单个计划所需的时间减少了近二十五倍。更重要的是，当机器人数量增加时，新方法并没有崩溃。虽然标准的细致方法随着机器人数量的增加最终会变得过于缓慢而无法使用，但这种基于分组的方法能够持续表现良好，能够处理旧方法会失效的数百个智能体。

研究还揭示了环境的物理布局如何影响该方法的成功。在障碍物多、通道窄的地图中，机器人由于无法跨越障碍物看到或触及彼此，自然会形成较小的、截然不同的组。这种拓扑结构使得新方法的效果更好，因为各组能更长时间地保持规模较小且相互独立。相比之下，在障碍物较少的开阔地图上，机器人倾向于形成较大的组，这需要更多的协调，但该系统仍然能够优于贪婪的替代方案。研究人员还发现，系统可以通过针对那些变得过于拥挤的特定组切换到更快、更简单的规划算法，从而使整个系统即使在最困难的条件下也能保持运转。

这项工作表明，通过理解机器人需要向前看多远的理论极限，工程师可以设计出既安全又具扩展性的系统。这个新框架提供了一种方法，可以在无需超级计算机管理交通的情况下，保持自动化仓库的高效运行。它暗示，大规模机器人的未来可能不依赖于一个计算每台机器每一个动作的单一、庞大的大脑，而是依赖于一个由多个小型、协同思维组成的并行网络。研究人员已经证明，实现两全其美是可能的：既拥有细致规划带来的安全与顺畅，又具备现实应用所需的速度与扩展性。随着自动化系统在我们的日常生活中变得越来越普遍——从送货无人机到工厂车间——这类方法对于确保机器之间无缝协作将至关重要，它们能将繁忙仓库中的复杂混沌转化为流畅、高效的流动。

技术摘要：基于组去中心化规划的并行终身 MAPF 理论框架

1. 问题陈述

本文研究了**终身多智能体路径规划（L-MAPF）**问题，即智能体必须在包含障碍物的地图上，在连续不断地从一个目的地导航至另一个目的地时，同时避免障碍物和智能体间的碰撞。主要目标是实现吞吐量最大化（例如，单位时间内完成的目标数量）。

虽然**滚动视界冲突解决（RHCR）框架被广泛认为是 L-MAPF 的高性能解决方案，但它面临着显著的计算瓶颈。RHCR 需要在极短的时间间隔内反复调用单次 MAPF 求解器（如基于优先级的搜索或基于冲突的搜索）。随着智能体数量的增加，这些求解器的计算成本呈指数级增长，限制了 RHCR 在中大规模智能体规模下的适用性。相反，像带有回溯的优先级继承（PIBT）**这样快速的贪婪方法虽然扩展性良好，但往往缺乏理论上的最优性保证，并且可能遭遇死锁。

核心挑战在于开发一种并行化的 RHCR 版本，在保持其高吞吐量和理论性能保证的同时，大幅降低计算成本，且不依赖于启发式方法。

2. 方法论

理论基础：LI-MDP

作者将其方法建立在**局部相互依赖多智能体马尔可夫决策过程（LI-MDP）**框架（DeWeese 和 Qu 2024, 2025）之上。他们将 L-MAPF 问题建模为一个折扣 MDP，其中智能体的局部交互由可见性半径定义。

RHCR 分析： 论文首先证明了原生 RHCR 在这种折扣设置下是近优的。具体而言，RHCR 与最优策略之间的次优性差距随规划视界（ $H$ ）的增加而呈指数级减小。至关重要的是，这一保证与重规划窗口（ $\alpha$ ）无关，这为使用更短的重规划窗口来提高效率提供了理论依据。
组去中心化： LI-MDP 文献表明，智能体可以根据基于传递通信方案（在距离 $V$ 内的连通性）进行分组，而不会牺牲近优性。不同组的智能体在一定步数（ $\lfloor V/2 \rfloor$ ）内不会发生碰撞，这使得它们可以并行规划。

提出的算法：组去中心化 RHCR (GD-RHCR)

基于 RHCR（基于时间的限制）与 GD-RHCR（基于空间的划分）之间的理论对偶性，作者提出了 GD-RHCR。该算法运行如下：

组划分： 在每个时间步，智能体根据可见性半径 $V$ 内的连通分量进行分组（使用最短路径距离）。
延迟评估： 系统并不在每一步都为所有组重新规划，而是采用“延迟”策略。只有当组内的智能体对当前计划产生分歧，或者计划执行完毕时，该组才会重新计算计划。这动态地调整了不同智能体子集的有效重规划窗口。
软约束： 在为特定组进行规划时，算法会结合来自前一时间步的其他组智能体的规划轨迹作为“软约束”。这使得规划器能够考虑到潜在的未来碰撞，而不会将其他组视为硬性障碍物，否则计算成本将难以承受。
异构求解器与回退机制： 该框架支持为不同的智能体组分配不同的求解器。
- 小型组使用高质量、可能较慢的求解器（如 PBS）。
- 大型、拥堵的组（超过阈值 $K_{threshold}$ ）会被立即移交给快速、可扩展的求解器（如 PIBT）。
- 与 RHCR 中回退被视为触发超时失败的情况不同，GD-RHCR 将针对大型组使用更快求解器的行为视为算法的组成部分，从而允许系统在拥堵增加时提高速度。

3. 核心贡献

RHCR 近优性的理论证明： 论文证明了在折扣 MDP 形式的 L-MAPF 中，RHCR 随规划视界的增加能以指数级速度收敛到最优解。
理论对偶性： 论文展示了 RHCR 的基于时间的限制与 GD-RHCR 的基于空间的划分之间的理论对偶性，并证明了 GD-RHCR 满足类似的近优性保证（在常数因子范围内）。
GD-RHCR 框架： 引入了一种全新的、具有理论原则的并行规划框架，该框架通过对智能体进行分组、利用延迟评估并集成软约束来实现。
可扩展性与效率： 该方法支持为不同的智能体组分配不同的求解器，从而平衡了求解质量与计算效率。它显著降低了相比于原生 RHCR 的单次规划计算成本。

4. 实验结果

作者在各种地图（仓库、分拣和随机导航环境）以及不同智能体数量下评估了 GD-RHCR，并将其与 RHCR（带 PIBT 回退）以及单独的 PIBT 进行对比。

性能对比 RHCR： 在 RHCR 可行的智能体数量范围内，GD-RHCR 实现了相当的吞吐量（在测试场景中差距约为 $\approx 2\%$ ），但将平均规划时间降低了 24.9 倍。
可扩展性： GD-RHCR 将 RHCR 的可行范围扩展到了更高的智能体数量。在拥有 800 个智能体的密集仓库场景中，GD-RHCR 相比于失效的 RHCR/PIBT 实现了 57.7% 的吞吐量提升，同时保持了较低的单次规划成本。
拓扑影响： 该方法在具有密集障碍物和复杂拓扑（如仓库）的地图中表现最佳，因为在这些地图中，最短路径与曼哈顿距离差异显著，从而自然地诱导出更小、独立的组。在更简单或更小的地图中，由于组变得更大，其优势会有所减弱，但该方法仍然保持了较高的计算效率。
鲁棒性与局限性： GD-RHCR 的性能受地图拓扑影响。在非双连通的地图（如 random-32-32-20 和 room-32-32-var1）中，PIBT 可能会遭遇死锁。由于 GD-RHCR 依赖 PIBT 处理大型组，如果它在 RHCR 失效之前就被迫依赖 PIBT，则可能会在这些特定环境中出现性能下降。然而，在组保持较小且分离的密集地图中，GD-RHCR 能维持高吞吐量并避免这些死锁问题。

5. 重要性与主张

本文声称 GD-RHCR 为 RHCR 的计算限制提供了一个具有理论依据的解决方案。通过利用 LI-MDP 框架，作者超越了启发式的并行化，提出了一种能够：

保留 RHCR 高吞吐量优势的方法。
扩展到以往仅能由 PIBT 等贪婪、次优方法处理的高智能体数量规模（在适用拓扑下）。
提供一个模块化框架，可根据组的大小和拥堵程度动态分配不同的规划算法。

作者强调，这项工作为将组去中心化集成到其他 MAPF 方法及学习型方法中开辟了新的研究方向，建立了一种在理论保证与计算可扩展性之间取得平衡的新范式。