LNS2+RL: Combining Multi-Agent Reinforcement Learning with Large Neighborhood Search in Multi-Agent Path Finding

📄 arXiv: 2405.17794v3 📥 PDF

作者: Yutong Wang, Tanishq Duhan, Jiaoyang Li, Guillaume Sartoretti

分类: cs.RO

发布日期: 2024-05-28 (更新: 2025-01-31)

备注: Accepted for presentation at AAAI 2025

💡 一句话要点

提出LNS2+RL算法，结合多智能体强化学习与大邻域搜索解决多智能体路径规划问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 多智能体路径规划 强化学习 大邻域搜索 碰撞避免 课程学习

📋 核心要点

  1. 现有MAPF方法如LNS2依赖快速但低质量的优先级规划，而MARL方法虽然协作性好但速度慢，难以兼顾效率与质量。
  2. LNS2+RL算法结合LNS2的快速性和MARL的协作性，早期使用MARL进行低级重规划以减少碰撞，后期切换到PP算法以提高效率。
  3. 实验表明，LNS2+RL在高智能体密度和复杂地图结构下，显著优于LNS2、LaCAM、EECBS和SCRIMP等算法，成功率大幅提升。

📝 摘要（中文）

多智能体路径规划（MAPF）是物流和仓库管理的关键组成部分，其重点在于为已知环境中一组机器人规划无碰撞路径。最近的研究引入了一种新的MAPF方法LNS2，该方法通过迭代重规划来修复快速获得的一组不可行路径，并依赖于快速但质量较低的优先级规划（PP）算法。与此同时，基于多智能体强化学习（MARL）的MAPF算法也取得了进展，与PP算法相比，这些算法表现出更好的协作性，但速度较慢。本文提出了一种新的MAPF算法LNS2+RL，它结合了LNS2和MARL的不同但互补的特性，有效地平衡了它们的个体局限性，并充分利用了两者的优点。在早期迭代中，LNS2+RL依赖于MARL进行低级重规划，这比PP算法更能消除碰撞。我们的基于MARL的规划器允许智能体推理过去和未来的信息，通过精心设计的课程学习逐步学习协作决策。在规划的后期阶段，LNS2+RL自适应地切换到PP算法，以快速解决剩余的碰撞，从而自然地权衡解决方案质量（解决方案中的碰撞次数）和计算效率。在各种团队规模、世界规模和地图结构的高智能体密度任务上的综合实验一致表明，与包括LNS2、LaCAM、EECBS和SCRIMP在内的许多MAPF算法相比，LNS2+RL具有卓越的性能。在具有复杂结构的地图中，LNS2+RL的优势尤为明显，在近一半的测试任务中，LNS2+RL的成功率超过50%，而LaCAM、EECBS和SCRIMP的成功率降至0%。

🔬 方法详解

问题定义：多智能体路径规划（MAPF）旨在为多个智能体在共享环境中寻找无碰撞的路径。现有方法，如LNS2，虽然速度快，但依赖于优先级规划，导致协作性差，容易陷入局部最优。而基于MARL的方法虽然协作性好，但计算复杂度高，难以应用于大规模场景。

核心思路：LNS2+RL的核心思路是结合LNS2的快速性和MARL的协作性，通过自适应地切换两种规划策略，在规划的不同阶段利用各自的优势。在早期阶段，利用MARL进行低级重规划，以更有效地消除碰撞；在后期阶段，切换到PP算法，以快速解决剩余的碰撞，从而在解决方案质量和计算效率之间取得平衡。

技术框架：LNS2+RL算法的整体流程如下：1) 初始路径规划：使用某种快速算法（例如优先级规划）生成初始路径；2) 迭代重规划：重复以下步骤，直到满足停止条件：a) 碰撞检测：检测当前路径中的碰撞；b) 策略选择：根据当前迭代次数和碰撞情况，选择MARL或PP算法进行重规划；c) 重规划：使用选定的算法对发生碰撞的智能体进行局部重规划；3) 路径优化：对最终路径进行优化，例如通过平滑处理减少路径长度。

关键创新：LNS2+RL的关键创新在于自适应的策略切换机制。它不是简单地使用一种算法，而是根据规划的进展情况，动态地选择最合适的算法。这种策略切换机制能够充分利用MARL的协作性和LNS2的快速性，从而在解决方案质量和计算效率之间取得更好的平衡。此外，该算法还设计了精细的课程学习，以提高MARL的训练效率和泛化能力。

关键设计：MARL部分使用了集中的训练和分布式的执行框架。智能体通过观察局部环境信息来做出决策，并使用共享的奖励函数来鼓励协作行为。课程学习的设计包括逐渐增加任务的难度，例如增加智能体的数量和环境的复杂度。策略切换的触发条件可以基于迭代次数、碰撞数量或某种性能指标。具体参数设置（如学习率、折扣因子、探索率等）需要根据具体任务进行调整。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，LNS2+RL在各种地图结构和智能体密度下均优于其他MAPF算法。在高智能体密度任务中，LNS2+RL的成功率显著高于LNS2、LaCAM、EECBS和SCRIMP等算法。在复杂地图中，LNS2+RL的优势尤为明显，在近一半的测试任务中，LNS2+RL的成功率超过50%，而LaCAM、EECBS和SCRIMP的成功率降至0%。这表明LNS2+RL能够有效地解决复杂环境下的多智能体路径规划问题。

🎯 应用场景

LNS2+RL算法可广泛应用于物流、仓储、交通运输等领域，例如无人仓的货物搬运、自动驾驶车辆的路径规划、以及机器人集群的协同作业。该算法能够提高多智能体系统的效率和可靠性，降低运营成本，并提升服务质量。未来，该算法有望应用于更复杂的动态环境和更大规模的智能体系统。

📄 摘要（原文）

Multi-Agent Path Finding (MAPF) is a critical component of logistics and warehouse management, which focuses on planning collision-free paths for a team of robots in a known environment. Recent work introduced a novel MAPF approach, LNS2, which proposed to repair a quickly obtained set of infeasible paths via iterative replanning, by relying on a fast, yet lower-quality, prioritized planning (PP) algorithm. At the same time, there has been a recent push for Multi-Agent Reinforcement Learning (MARL) based MAPF algorithms, which exhibit improved cooperation over such PP algorithms, although inevitably remaining slower. In this paper, we introduce a new MAPF algorithm, LNS2+RL, which combines the distinct yet complementary characteristics of LNS2 and MARL to effectively balance their individual limitations and get the best from both worlds. During early iterations, LNS2+RL relies on MARL for low-level replanning, which we show eliminates collisions much more than a PP algorithm. There, our MARL-based planner allows agents to reason about past and future information to gradually learn cooperative decision-making through a finely designed curriculum learning. At later stages of planning, LNS2+RL adaptively switches to PP algorithm to quickly resolve the remaining collisions, naturally trading off solution quality (number of collisions in the solution) and computational efficiency. Our comprehensive experiments on high-agent-density tasks across various team sizes, world sizes, and map structures consistently demonstrate the superior performance of LNS2+RL compared to many MAPF algorithms, including LNS2, LaCAM, EECBS, and SCRIMP. In maps with complex structures, the advantages of LNS2+RL are particularly pronounced, with LNS2+RL achieving a success rate of over 50% in nearly half of the tested tasks, while that of LaCAM, EECBS and SCRIMP falls to 0%.