多智能体路径规划（MAPF）旨在让大量智能体在地图上从起点前往终点，同时避开障碍物和彼此碰撞。其应用场景包括仓储物流、机场物流、无人机交通管理、停车导航和电子游戏。
当智能体持续移动时，例如仓库中的自动包裹配送，问题便进入一种称为终身多智能体路径规划（L-MAPF）的新范式。智能体抵达目的地后，会立即被分配新的目的地。它们必须在避开障碍物和其他智能体的同时，实现较高的吞吐量，例如完成更多包裹配送。
针对这一终身规划场景，研究人员提出了多种方法。其中一个重要基线是带回溯的优先级继承（Priority Inheritance with Backtracking，PIBT）。这是一种速度极快、可扩展性很强的方法，因而成为有力的基线，但也可能表现出贪心行为。与 PIBT 不同，另一种广受关注的方案是滚动时域碰撞消解（Rolling-Horizon Collision Resolution，RHCR）框架。在实现高吞吐量方面，RHCR 被认为是性能最出色的方案之一。
遗憾的是，RHCR 的计算成本很高，尤其是与 PIBT 相比。在仓库机器人导航等实际场景中，RHCR 必须在很短时间内反复调用一次性 MAPF 求解器。即便采用优先级搜索（Priority Based Search，PBS）这类次优求解器，我们仍然观察到 RHCR 的计算成本会呈指数级增长。在研究社区中，运行 RHCR 基线被视为仿真中计算开销较大的环节，通常需要在超时前报告部分规划结果，或改用规模更小的问题子集。实践中，也可以为 RHCR 配置回退机制：达到超时时间后，切换到 PIBT 等其他算法。
虽然通过跨智能体并行化来加速 RHCR 看似顺理成章，但如何在不牺牲 RHCR 性能的前提下，以理论严谨的方式实现这一目标，仍是一个悬而未决的问题。
贡献
本工作的目标是开发具有理论依据的 RHCR 并行化方法，在仅使用其一小部分计算成本的情况下，保持或超越 RHCR 的高吞吐量。为此，我们为 RHCR 构建了全新的理论基础，并由此提出一种理论上严谨的 RHCR 并行化方案：分组去中心化 RHCR（Group Decentralized RHCR，GD-RHCR）。
对于 RHCR 已经能够处理的小规模智能体数量，GD-RHCR 在许多情况下可以取得相近的吞吐量，同时显著提升规划速度。对于只有 PIBT 才能处理的大规模智能体数量，GD-RHCR 同样能够完成求解，并且始终实现更高的吞吐量。
实验验证
我们在多种地图上对 GD-RHCR 进行了实证评估。平均规划时间最多可缩短 [the reported speedup factor] 倍，并且在 RHCR 崩溃之前保持与其相当的性能。进入更大规模的智能体数量范围后，GD-RHCR 仍然表现良好；与 PIBT 以及已崩溃的 RHCR 相比，其吞吐量最高提升 [the reported throughput improvement]。
相关工作
基于学习的 MAPF 方法
基于学习的方法直接使用强化学习或模仿学习解决 MAPF 问题。这些方法可以通过去中心化实现一定程度的并行，但无法保证并行化或去中心化会带来多大的性能损失。
终身 MAPF
终身 MAPF 领域大体分为两类：RHCR 提供的速度较慢但质量较高的方案，以及 PIBT 等速度快但较为贪心的方案。
RHCR 能够将一次性 MAPF 求解器拓展到终身场景，但由于一次性 MAPF 属于 NP-hard 问题，可能带来很高的计算时间。
PIBT 既可用于一次性场景，也可用于终身场景。PIBT 及其变体仍是速度很快的替代方案，但它们具有贪心特性；当图不是双连通图时，还经常会陷入死锁。
类似地，研究人员也为这一场景开发了多智能体强化学习和模仿学习方法。
MAPF 中的分组
此前已有多项研究尝试通过对智能体分组来加快计算。静态分组方法可以将地图划分为多个子区域，并将每个子区域中的智能体视为一个群组。另一些研究则尝试动态识别相互独立的分组，方法更加复杂。
这类工作关注的是加速一个能够保持完备性保证的算法，而不是识别那些可能适合协同规划的协调群组。
局部相互依赖的多智能体 MDP
在 MAPF 研究之外，近期关于具有动态局部依赖的折扣多智能体马尔可夫决策过程环境的研究取得了突破。研究人员提出了局部相互依赖的多智能体 MDP（Locally Interdependent Multi-Agent MDP，LI-MDP）模型，用于从理论上刻画具有局部交互的多智能体系统。
同一系列研究提出了分组去中心化设定：根据智能体之间的可见性，将它们以传递方式连接起来。相互连通的智能体可以进行协调。这种介于集中式和去中心化之间的特殊可观测结构，能够提供去中心化设定无法实现的强理论保证，包括随着可见性增加，性能以指数速度逼近最优，同时仍允许不同智能体群组并行规划。
LI-MDP 框架有助于解释 RHCR 等现有方法为何有效，支持近似最优性的证明，并可用于提出 GD-RHCR 等融入这一可观测结构的新方法。
结论与未来工作
本工作借助 LI-MDP 领域的方法，为 RHCR 提供了理论基础。随后，我们利用这些分析技术提出 GD-RHCR 框架。该框架满足与 RHCR 类似的理论保证，并在许多地图上进行了实证验证：当智能体数量超过 RHCR 的可处理范围时，GD-RHCR 依然表现出良好性能。
分组去中心化是 MAPF 社区中相对较新的概念，可以通过多种方式加以整合。例如，它可以与传统的基于学习的方法结合，也可以用于并行化 PIBT 等其他方法。此外，这项工作还为在不同位置或场景中使用不同算法提供了一个简洁框架，从而开启了许多研究方向。
致谢
Guannan Qu 获得 NSF Grants 2339112 和 2512805、Jane Street 以及 Pennsylvania Infrastructure Technology Alliance 的支持。Jiaoyang Li 获得 NSF Grants 2328671 和 2441629 的支持。Alex DeWeese 获得 Leo Finzi Memorial Fellowship in Electrical & Computer Engineering、David H. Barakat and LaVerne Owen-Barakat CIT Dean’s Fellowship 以及 Fritsch Family Fellowship 的支持。
消融仿真
warehouse-10-20-10-2-1 上的消融仿真结果见论文中的消融实验结果。
常见问题
什么是终身多智能体路径规划？ 终身 MAPF 会在智能体抵达原先目的地后持续为其分配新目的地，同时要求避免碰撞并保持较高吞吐量。
为什么 RHCR 的计算成本很高？ RHCR 会反复调用一次性 MAPF 求解器；这类求解器的计算成本可能呈指数级增长，导致智能体数量较大时频繁超时。
什么是 GD-RHCR？ GD-RHCR 是 RHCR 的分组去中心化并行化方案，允许不同智能体群组进行协调并行规划。
GD-RHCR 与 PIBT 相比表现如何？ GD-RHCR 能够求解比 RHCR 更大规模的智能体问题，并且在报告的实验中始终取得高于 PIBT 的吞吐量。