Deploying Ten Thousand Robots: Scalable Imitation Learning for Lifelong Multi-Agent Path Finding

📄 arXiv: 2410.21415v2 📥 PDF

作者: He Jiang, Yutong Wang, Rishi Veerapaneni, Tanishq Duhan, Guillaume Sartoretti, Jiaoyang Li

分类: cs.MA, cs.AI, cs.LG, cs.RO

发布日期: 2024-10-28 (更新: 2025-05-18)

备注: Accepted by ICRA 2025

💡 一句话要点

提出SILLM，用于大规模终身多智能体路径规划，性能超越现有方法。

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

关键词: 多智能体路径规划 模仿学习 大规模场景 碰撞避免 通信机制

📋 核心要点

  1. 现有LMAPF学习方法在大规模场景中性能不足，难以达到搜索算法的水平。
  2. SILLM通过模仿学习，结合通信模块、单步碰撞解决和全局引导，提升性能。
  3. 实验表明，SILLM在吞吐量上显著优于现有学习和搜索算法，并在真实机器人上验证。

📝 摘要（中文）

本文提出了一种基于模仿学习的终身多智能体路径规划（LMAPF）求解器，名为SILLM。LMAPF问题是指为多个智能体重复寻找无碰撞路径，当智能体到达当前目标时，会被持续分配新的目标。尽管近年来基于学习的方法在LMAPF领域取得了进展，但它们在大型环境中难以匹敌最佳的基于搜索的算法。SILLM引入了一种新颖的通信模块，以及系统的单步碰撞解决和全局引导技术。实验结果表明，在六个包含高达10,000个智能体和不同障碍物结构的大规模地图上，SILLM超越了最佳的学习和搜索基线，平均吞吐量分别提高了137.7%和16.0%。此外，SILLM还击败了2023年机器人赛跑联盟的冠军解决方案。最后，我们在一个模拟仓库环境中，使用10个真实机器人和100个虚拟机器人验证了SILLM。

🔬 方法详解

问题定义：论文旨在解决大规模终身多智能体路径规划（LMAPF）问题。现有方法，特别是基于学习的方法，虽然推理速度快，但在大规模场景下，其解的质量和效率难以与最佳的基于搜索的算法相媲美。痛点在于如何平衡快速推理和高质量路径规划，尤其是在智能体数量庞大且环境复杂的情况下。

核心思路：论文的核心思路是结合模仿学习的快速推理能力和搜索算法的高解质量。通过模仿学习，智能体可以学习到专家策略，从而快速生成行动。同时，引入通信机制和全局引导，以解决局部观测带来的次优解问题，并避免碰撞。

技术框架：SILLM的整体框架包含以下几个主要模块：1) 局部观测模块：每个智能体根据局部环境进行观测。2) 通信模块：智能体之间进行信息交流，共享邻域信息。3) 决策模块：基于局部观测和通信信息，利用模仿学习模型生成单步动作。4) 碰撞解决模块：系统性地解决智能体之间的碰撞。5) 全局引导模块：提供全局层面的引导，避免局部最优。

关键创新：论文的关键创新在于以下几个方面：1) 新颖的通信模块，允许智能体有效地共享邻域信息，从而做出更明智的决策。2) 系统性的单步碰撞解决机制，确保智能体在执行动作时避免碰撞。3) 全局引导技术，帮助智能体跳出局部最优，找到更优的路径。

关键设计：论文中模仿学习模型的具体网络结构未知，但可以推测使用了卷积神经网络或图神经网络来处理局部观测和通信信息。损失函数可能包括模仿学习损失（如交叉熵损失）和碰撞惩罚项。通信模块的设计可能涉及注意力机制或图神经网络，以实现高效的信息传递。具体的参数设置和超参数优化方法未知。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

SILLM在六个大规模地图上进行了实验，智能体数量高达10,000个。实验结果表明，SILLM的吞吐量平均比最佳学习基线提高了137.7%，比最佳搜索基线提高了16.0%。此外，SILLM还击败了2023年机器人赛跑联盟的冠军解决方案，并在真实机器人和虚拟机器人的混合环境中进行了验证。

🎯 应用场景

该研究成果可应用于大规模仓库自动化、交通管理、无人机集群控制等领域。通过高效的路径规划，可以显著提高物流效率、降低运营成本，并提升系统的整体性能。未来，该技术有望在更复杂的动态环境中得到应用，例如自动驾驶、智能城市等。

📄 摘要（原文）

Lifelong Multi-Agent Path Finding (LMAPF) repeatedly finds collision-free paths for multiple agents that are continually assigned new goals when they reach current ones. Recently, this field has embraced learning-based methods, which reactively generate single-step actions based on individual local observations. However, it is still challenging for them to match the performance of the best search-based algorithms, especially in large-scale settings. This work proposes an imitation-learning-based LMAPF solver that introduces a novel communication module as well as systematic single-step collision resolution and global guidance techniques. Our proposed solver, Scalable Imitation Learning for LMAPF (SILLM), inherits the fast reasoning speed of learning-based methods and the high solution quality of search-based methods with the help of modern GPUs. Across six large-scale maps with up to 10,000 agents and varying obstacle structures, SILLM surpasses the best learning- and search-based baselines, achieving average throughput improvements of 137.7% and 16.0%, respectively. Furthermore, SILLM also beats the winning solution of the 2023 League of Robot Runners, an international LMAPF competition. Finally, we validated SILLM with 10 real robots and 100 virtual robots in a mock warehouse environment.