核心发现
方法论
本文首先将L-MAPF问题建模为折扣多智能体MDP，利用LI-MDP理论证明RHCR在此模型中具有指数级的近似最优保证。基于此，提出群去中心化的扩展框架GD-RHCR，通过将智能体划分为基于传递通信的连接组件，实现多组平行规划。该方法结合软约束机制和异构求解器，优化计算效率。理论上，证明GD-RHCR在空间划分和时间规划限制下仍能保持与RHCR相似的性能保证，且在实际仿真中表现出高吞吐率和显著的计算速度提升。
关键结果
- 在多种地图上，GD-RHCR的平均规划时间比传统RHCR快24.9倍，且在大规模智能体场景中，吞吐率提升高达57.7%，优于PIBT和原始RHCR。实验显示，GD-RHCR在保持高质量路径的同时，显著降低了每次规划的计算成本，验证了其在实际应用中的潜力。
- 理论分析证明，GD-RHCR在空间划分的最大距离V和规划时长H的关系下，仍能保持指数级的接近最优保证，具体表现为误差界由6γmin(⌊V/2⌋+1, H)/(1−γ)^2 + ϵ控制，确保了算法的鲁棒性。
- 通过引入异构求解器和软约束机制，GD-RHCR在复杂环境中表现出良好的适应性和扩展性，特别是在高密度、多目标、多障碍环境中，依然能实现高吞吐和低计算负担。
研究意义
本研究在多智能体路径规划领域具有重要理论突破，将RHCR的近似最优性理论基础扩展到分布式、并行规划中，为大规模、多目标、多约束的持续路径规划提供了坚实的理论支撑。其提出的群去中心化框架突破了传统集中式规划的计算瓶颈，为工业自动化、仓储物流、无人机交通管理等实际场景提供了高效、可靠的解决方案。通过结合LI-MDP理论，本文不仅丰富了多智能体强化学习和规划的理论体系，也为未来多智能体系统的自主协作提供了新的设计思路。
技术贡献
本文的核心技术贡献在于：1）首次将RHCR在折扣多智能体MDP中的性能分析引入LI-MDP理论，证明其指数级接近最优的性能保证；2）提出基于传递通信的群去中心化结构，有效降低规划复杂度，支持多组平行处理；3）设计了结合软约束和异构求解器的多层次规划机制，提升大规模环境下的适应性和效率；4）通过严格的理论分析和实证验证，建立了空间划分与时间规划限制之间的对偶关系，为多智能体路径规划提供了新的理论框架。
新颖性
本研究的创新点在于：首次将LI-MDP理论应用到L-MAPF的性能分析中，系统性证明RHCR在折扣MDP中的指数级接近最优；提出基于传递通信的群去中心化架构，有效结合了集中式和分布式优势，突破了传统单一规划模式的限制；引入软约束机制和异构求解器，增强了算法的灵活性和扩展性。这些创新共同推动了多智能体路径规划理论与实践的深度融合，填补了大规模、多目标、多约束环境下高效规划的研究空白。
局限性
- 本方法在理论分析中假设求解器输出的路径为ϵ-最优，实际中受求解器性能影响较大，可能导致性能保证的偏差；
- 群划分基于静态距离阈值V，实际环境中动态变化可能影响划分效果，需进一步研究自适应划分策略；
- 软约束参数csoft的设置对算法性能影响显著，如何自动调节以适应不同环境仍需探索；
未来方向
未来将致力于引入动态环境中的自适应群划分机制，优化软约束参数的自调节策略，结合深度强化学习提升求解器的鲁棒性。此外，将探索多智能体系统中的信息共享与通信机制，增强群体协作能力，拓展算法在无人机群、自动仓储等复杂场景中的应用潜力。还计划将理论分析扩展到非折扣模型，提升算法在长时间持续任务中的表现。
AI 总览摘要
多智能体路径规划（MAPF）作为机器人自主导航和调度的核心问题，近年来在工业自动化、仓储物流、无人机交通管理等领域引起了广泛关注。传统的MAPF算法在单次任务中已取得显著进展，但在持续、多目标、多障碍环境中的实时高效规划仍面临巨大挑战。尤其是在多智能体持续运行的场景下，如何兼顾路径的最优性、计算效率与系统的扩展性，成为研究的热点难题。
本文提出了一种基于LI-MDP理论的群去中心化框架GD-RHCR，旨在解决大规模、多目标、多障碍环境下的高效路径规划问题。该方法首先将L-MAPF问题建模为折扣多智能体MDP，并利用LI-MDP的理论工具，证明了RHCR在此模型中具有指数级的近似最优保证。基于此，作者设计了群划分策略，将智能体划分为基于传递通信的连接组件，实现多组平行规划，从而大幅降低计算复杂度。
技术上，GD-RHCR结合软约束机制和异构求解器，支持在不同环境和场景中灵活调度。理论分析表明，空间划分的最大距离V和规划时长H之间存在对偶关系，保证了算法在空间和时间限制下的性能接近最优。实证结果显示，在多个复杂地图中，GD-RHCR的平均规划时间比传统RHCR快24.9倍，吞吐率提升高达57.7%，验证了其在大规模、多目标环境中的优越性能。
这项研究不仅丰富了多智能体路径规划的理论体系，也为工业自动化、仓储管理、无人机调度等实际应用提供了高效、可靠的解决方案。未来工作将聚焦于动态环境下的自适应群划分、软约束参数的自动调节，以及多智能体系统中的信息共享机制，推动多智能体自主协作的智能化发展。
深度分析
研究背景
多智能体路径规划（MAPF）作为机器人自主导航的基础问题，经历了从集中式搜索到分布式优化的演变。早期方法如A*和其变体在小规模环境中表现优异，但在大规模、多目标、多障碍场景中计算复杂度迅速膨胀。Conflict-Based Search（CBS）和Enhanced CBS（ECBS）等算法通过冲突检测与解决机制实现了部分优化，但仍受NP-hard性质限制，难以满足实时性要求。近年来，优先级规划、PIBT等贪心策略提供了高扩展性，但牺牲了路径最优性。持续学习和强化学习方法也被引入，但缺乏理论性能保证。随着环境复杂度增加，如何在保证路径质量的同时实现高效、可扩展的持续路径规划，成为研究的核心难题。
核心问题
在持续、多目标、多障碍环境中，智能体需要不断地从当前位置移动到目标点，避免碰撞和障碍，同时保持高吞吐率。传统算法在大规模、多目标、多障碍场景中计算成本高昂，难以满足实时性和扩展性需求。尤其是在多智能体持续运行的背景下，路径冲突频繁发生，导致算法性能下降。如何在保证路径安全和效率的基础上，实现多智能体的高效协作，成为亟待解决的问题。现有方法多在单次任务中表现良好，但在持续、多目标、多障碍环境中缺乏系统性理论支撑，难以应对大规模、多目标、多约束的复杂场景。
核心创新
本研究的创新点主要包括：1）将RHCR在折扣MDP中的性能分析引入LI-MDP理论，系统性证明其指数级接近最优，为多智能体路径规划提供了坚实的理论基础；2）提出基于传递通信的群去中心化架构，将智能体划分为多个连接组件，实现多组平行规划，大幅降低计算复杂度；3）设计软约束机制，允许在多目标、多障碍环境中动态调整路径冲突的惩罚参数，提高算法的适应性；4）引入异构求解器策略，支持不同规模和复杂度的群体采用不同的规划算法，兼顾路径质量和计算效率。这些创新共同推动了大规模、多目标、多约束环境下多智能体路径规划的理论与实践发展。
方法详解
- �� 将L-MAPF问题建模为折扣多智能体MDP，定义状态空间、动作空间、转移函数和奖励函数，确保模型能反映路径冲突、目标达成和碰撞惩罚。
- �� 利用LI-MDP理论，分析RHCR在该模型中的性能，证明其在规划时长H趋向无穷时，性能指数级逼近最优。
- �� 设计群划分策略：基于传递通信的连接图，将智能体划分为若干连接组件，每个组内智能体共享信息，组间相互独立。
- �� 构建GD-RHCR算法：在每个时间步，动态识别连接组件，采用软约束机制调节跨组冲突惩罚，支持异构求解器并行处理不同组。
- �� 引入懒惰评估机制：只在必要时重新规划，减少重复计算，提高效率。
- �� 利用二级求解器（如PIBT）处理高密度或复杂区域，避免计算瓶颈。
- �� 理论分析证明，空间距离V和规划时长H的对偶关系保证了算法的近似最优性能。
实验设计
- �� 在多个复杂地图（如仓库布局、交通枢纽）上进行仿真，比较GD-RHCR、RHCR和PIBT的性能。
- �� 采用平均规划时间、吞吐率和成功率作为主要指标，设置不同智能体规模（从几十到几百个）和不同环境复杂度。
- �� 通过调节空间距离V和规划时长H，验证理论中的对偶关系。
- �� 进行消融实验，评估软约束参数、异构求解器和懒惰规划机制对性能的影响。
- �� 统计分析表明，GD-RHCR在大规模环境中显著优于传统方法，平均规划时间降低24.9倍，吞吐率提升57.7%。
结果分析
- �� 实验结果显示，GD-RHCR在多个测试场景中，平均规划时间比RHCR快24.9倍，且在大规模场景中保持高吞吐率，优于PIBT和原始RHCR。
- �� 理论分析验证了空间距离V和规划时长H的对偶关系，确保在空间划分的同时，性能误差界保持在可控范围内，误差界由6γmin(⌊V/2⌋+1, H)/(1−γ)^2 + ϵ定义。
- �� 结合软约束和异构求解器，算法在复杂环境中表现出良好的适应性和鲁棒性，尤其在高密度、多目标、多障碍环境中，仍能实现高效路径规划和低计算负担。
应用场景
- �� 该方法适用于仓储自动化中的多机器人调度，能在复杂仓库环境中实现高效路径规划，提升物流效率。
- �� 在无人机交通管理中，可实现多无人机的自主避障和目标追踪，确保空域安全与高吞吐。
- �� 在自动驾驶车辆的多车协调中，支持多车在复杂交通场景中的实时路径调整，减少交通拥堵和碰撞风险。
- �� 长远来看，该框架可扩展到智能制造、城市交通、应急救援等多智能体协作场景，推动自动化和智能化水平提升。
局限与展望
- �� 理论分析依赖于求解器输出的ϵ-最优路径，实际中求解器性能波动可能影响性能保证。
- �� 群划分基于静态距离阈值V，动态环境中可能需要自适应划分策略以保持效果。
- �� 软约束参数的调节缺乏自动化机制，需根据环境特性手动调整，影响算法的普适性。
- �� 当前算法在极端复杂或高密度场景下仍存在计算瓶颈，未来需引入更高效的求解器或学习机制以提升性能。
通俗解读 非专业人士也能看懂
想象一下你在一个大型工厂里工作，工厂里有许多机器人负责搬运货物。每个机器人都要从起点到终点，避开障碍物和其他机器人的路径。为了让整个工厂运转得更快、更顺畅，你希望每个机器人都能找到最短、最安全的路线，但同时又不能让它们撞到一起。传统的方法就像让每个机器人自己盯着地图，自己规划路线，虽然简单，但当机器人多了以后，冲突就会变得很多，计算也变得很慢。
这篇论文提出了一种聪明的办法，把机器人分成几个小组，每组内部的机器人可以互相通信，组与组之间也可以合作。这样一来，每个组可以同时规划自己的路线，减少了整体的计算量。更厉害的是，作者用了一些数学上的理论，证明这种方法几乎可以达到最优路径的效果，而且速度快得多。就像在工厂里，几个小组同时工作，互不干扰，效率大大提高。
通过模拟实验，作者发现这种新方法比传统的方案快了将近25倍，还能处理更多的机器人，保证它们都能顺利完成任务。这意味着未来的自动仓库、无人机调度甚至自动驾驶都能用上这种高效的路径规划技术，让机器人变得更聪明、更快、更安全。虽然还存在一些需要改进的地方，比如如何在动态环境中自动调整分组策略，但整体来看，这是一项非常有潜力的创新技术。
术语表
L-MAPF (Lifelong Multi-Agent Path Finding, 持续多智能体路径规划)
一种持续多目标、多任务、多障碍环境中的路径规划问题，智能体需要不断地从当前位置移动到目标点，避免碰撞，保持高吞吐。
论文中将L-MAPF建模为折扣多智能体MDP，分析其性能保证。
RHCR (Rolling-Horizon Collision Resolution, 滚动视界冲突解决)
一种基于短期规划、多次重规划的路径规划框架，旨在实现高吞吐率，但计算成本较高。
论文证明RHCR在LI-MDP模型中具有指数级的接近最优保证。
LI-MDP (Locally Interdependent Multi-Agent Markov Decision Process, 局部依赖多智能体MDP)
一种考虑智能体局部交互关系的MDP模型，支持多智能体系统的理论分析和分布式规划。
用以分析RHCR的性能和设计群去中心化结构。
GD-RHCR (Group Decentralized RHCR, 群去中心化RHCR)
本文提出的基于LI-MDP理论的扩展框架，将智能体划分为多个连接组件，实现多组平行规划。
核心创新，结合软约束和异构求解器，提升效率和扩展性。
软约束 (Soft Constraints)
在路径规划中允许一定程度的冲突惩罚，非硬性限制，有助于提高算法的灵活性和鲁棒性。
在GD-RHCR中用于调节跨组冲突的惩罚参数。
异构求解器 (Heterogeneous Solvers)
支持不同规模和复杂度的群体采用不同的路径规划算法，以优化整体性能。
如PBS用于小组，PIBT用于大组，结合使用以提升效率。
传递通信 (Transitive Communication)
在群划分中，允许连接组件内的智能体通过传递信息实现协调。
实现多组平行规划的基础机制。
传递图 (Connectivity Graph)
基于距离阈值构建的图，连接在一定距离内的智能体，划分为不同组。
实现群划分的关键工具。
懒惰评估 (Lazy Evaluation)
只在必要时重新规划路径，避免频繁重复计算，提高效率。
GD-RHCR中的动态调节机制。
二级求解器 (Secondary Solver)
在高密度或复杂区域，使用更快的算法（如PIBT）快速处理，避免计算瓶颈。
作为fallback机制，提高整体效率。
开放问题 这项研究留下的未解疑问
- 1 尽管本文在理论上证明了GD-RHCR的性能保证，但在实际动态环境中如何自适应调整空间划分参数V和规划时长H仍未充分解决。未来需要研究自适应机制，以应对环境变化带来的划分和调度挑战。
- 2 软约束参数csoft的自动调节策略尚未建立，如何根据环境复杂度和任务需求动态调整，确保路径质量与计算效率的平衡，是未来的重要研究方向。
- 3 目前算法主要在静态地图和已知环境中验证，面对动态障碍和未知变化时的鲁棒性和适应性仍需深入探索。
- 4 多智能体系统中的信息共享和通信机制尚未充分整合，未来可结合深度学习和强化学习技术，提升群体协作能力。
- 5 算法在极端高密度、多目标、多障碍场景下的性能瓶颈仍未突破，未来需引入更高效的求解器或学习机制，提升大规模系统的实用性。
应用场景
近期应用
仓储自动化机器人调度
在大型仓库中，GD-RHCR可实现多机器人高效路径规划，减少碰撞，提高货物运输效率，适用于自动化物流系统。
无人机交通管理
多无人机在空域中自主避障和路径规划，确保飞行安全与高吞吐，适合城市空中交通调度。
自动驾驶车辆协调
支持多车在复杂道路环境中的实时路径调整，减少交通拥堵和事故风险，提升城市交通效率。
远期愿景
智能制造中的多机器人协作
推动工业生产线中多机器人自主协作，实现高度自动化和柔性生产，降低人工成本。
城市级智能交通系统
整合多智能体路径规划技术，构建智能交通网络，缓解交通压力，提升城市运行效率。
原文摘要
In the Lifelong Multi-Agent Path Finding (L-MAPF) problem, agents must repeatedly move from one destination to another while avoiding obstacles and inter-agent collisions. Widely regarded as one of the highest-performing solutions to this problem is the Rolling-Horizon Collision Resolution (RHCR) framework. However, commensurate with its quality solutions, it incurs a computational cost that limits its applicability to even modest agent counts. In this paper, leveraging theoretical methods from the Locally Interdependent Multi-Agent MDP literature, we first theoretically prove the near-optimality of RHCR in a discounted MDP formulation of the L-MAPF problem. Then, we leverage these results to naturally motivate an extended framework called Group Decentralized RHCR (GD-RHCR) which incorporates a group decentralized structure that partitions agents based on a transitive communication scheme and plans for each partition of agents in parallel. We show that both RHCR and GD-RHCR achieve similar exponentially close to optimal guarantees, establishing a theoretical duality between the time based restrictions performed by vanilla RHCR and the additional space based partitioning performed by GD-RHCR. Lastly, we show that across varying maps, GD-RHCR is able to attain high throughput that scales into higher agent counts while maintaining a significantly lower per plan cost.
参考文献 (20)
On multiple moving objects
M. Erdmann, Tomas Lozano-Perez
Dynamic Agent Grouping ECBS: Scaling Windowed Multi-Agent Path Finding with Completeness Guarantees
Tiannan Zhang, Rishi Veerapaneni, Shao-Hung Chan 等
Searching with Consistent Prioritization for Multi-Agent Path Finding
Hang Ma, Daniel Damir Harabor, Peter James Stuckey 等
Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding
Keisuke Okumura
Lifelong Multi-Agent Path Finding in Large-Scale Warehouses
Jiaoyang Li, Andrew Tinka, Scott Kiesel 等
Locally Interdependent Multi-Agent MDP: Theoretical Framework for Decentralized Agents with Dynamic Dependencies
Alex DeWeese, Guannan Qu
Shard Systems: Scalable, Robust and Persistent Multi-Agent Path Finding with Performance Guarantees
C. Leet, Jiaoyang Li, Sven Koenig
winPIBT: Extended Prioritized Algorithm for Iterative Multi-agent Path Finding
Keisuke Okumura, Yasumasa Tamura, X. Défago
Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem
Max Barer, Guni Sharon, Roni Stern 等
Departure Scheduling and Taxiway Path Planning under Uncertainty
Jiaoyang Li, Mimi Gong, Zi Liang 等
Structure and Intractability of Optimal Multi-Robot Path Planning on Graphs
Jingjin Yu, S. LaValle
Conflict-based search for optimal multi-agent pathfinding
Guni Sharon, Roni Stern, Ariel Felner 等
PRIMAL$_2$: Pathfinding Via Reinforcement and Imitation Multi-Agent Learning - Lifelong
Mehul Damani, Zhiyao Luo, Emerson Wenzel 等
Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks
Hang Ma, Jiaoyang Li, T. K. S. Kumar 等
Multi-Agent Path Finding with Priority for Cooperative Automated Valet Parking
Ayano Okoso, Keisuke Otaki, Tomoki Nishi
PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning
Guillaume Sartoretti, J. Kerr, Yunfei Shi 等
Moving Agents in Formation in Congested Environments
Jiaoyang Li, Kexuan Sun, Hang Ma 等
EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding
Jiaoyang Li, Wheeler Ruml, Sven Koenig
Thinking Beyond Visibility: A Near-Optimal Policy Framework for Locally Interdependent Multi-Agent MDPs
Alex DeWeese, Guannan Qu