Open Source Robotics

精选高质量开源机器人项目、工具和软件，推动机器人社区发展。

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

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

许可协议

  • 开放获取
  • 论文: CC BY 4.0

以下内容均依据论文全文，按其 CC BY 4.0 许可协议使用；其中的图已注明作者。

一句话总结

SILLM 模仿一个强大的基于搜索的求解器，加入空间通信、交通引导和 PIBT 冲突修复，能以每步不到 1 s 的时间为 10,000 个智能体进行规划，并取得最高吞吐量。

为何重要

自动化仓库已经在运行数千台机器人（论文引用 2022 年 Amazon 履约中心有超过 4,000 台），因此一个能在这种规模下以每步亚秒级规划保持高吞吐量的规划器，与机队控制直接相关。结果表明，学习得到的策略结合搜索式冲突处理和交通感知引导，能够胜过最强的可扩展基于搜索的求解器，而不仅仅是胜过缓慢的最优求解器。

问题

终身多智能体路径规划（LMAPF）在每个智能体到达目标后立即给它分配一个新目标，因此必须持续重新规划无碰撞路径，同时最大化吞吐量（每个时间步到达的目标数）。基于学习的求解器能根据局部观测快速反应，但大多只在数十到数百个智能体上测试过，且无法击败 PIBT 等可扩展的次优搜索求解器。本文旨在 10,000 个智能体的规模下同时击败基于学习和基于搜索的求解器。

提出的方法

SILLM 是一个由所有智能体共享的卷积策略，视野为 11×11，带有一个 Spatially Sensitive Communication 模块，将每个邻居的特征向量插入其精确的相对网格位置。观测中编码了三种启发式引导图之一（Backward Dijkstra、交叉高速通道式的 Static Guidance，或基于 TrafficFlow 的 Dynamic Guidance），一个简化的 CS-PIBT 步骤在学习到的动作无冲突时予以保留，否则用 PIBT 修复。该策略通过迭代模仿 Windowed MAPF-LNS 进行训练，后者是 2023 League of Robot Runners 冠军方案 WPPL 的核心，训练在缩小的地图上以 600 个智能体进行。

关键见解

  • 把邻居的特征放在其精确的相对位置上（空间敏感通信），在消融实验中胜过基于注意力的通信和无通信，表明精确的空间推理对 LMAPF 很重要。
  • 模仿一个随时可用（anytime）的大规模求解器（Windowed MAPF-LNS），避免了限制 PRIMAL2、SCRIMP 和 MAGAT 等早期模仿学习器的小规模训练实例（8–10 个智能体）。
  • 最佳引导方式取决于地图：Static Guidance 适合交叉分拣地图和仓库地图，Backward Dijkstra 适合随机地图，Dynamic Guidance 在 Paris 和 Berlin 城市地图上表现最好。
  • 基于 PIBT 的冲突修复在学习到的动作无冲突时予以保留，避免了常见“冻结”策略带来的不必要等待和死锁。
  • 简单的 MAPPO 强化学习表现不如模仿学习，而在模仿之后再应用 MAPPO 也没有带来可测量的提升。

主要结果

  • 在六张有 10,000 个智能体的大地图上，平均吞吐量比最佳基于学习的基线提高 137.7%，比最佳基于搜索的基线提高 16.0%。
  • 大地图上的竞赛式得分：SILLM 0.99，SILLM（仅 Dynamic Guidance）0.94，WPPL 0.88，TrafficFlow 0.81，PIBT 0.61，Follower 0.52；RHCR 和 SCRIMP 每步需要数分钟，无法在此规模下评估。
  • 大地图上的平均单步规划时间：SILLM 为 0.349 s，WPPL 为 4.143 s，Follower 为 4.125 s。
  • 在大地图上，Learnable PIBT 在每种引导类型下都胜过普通 PIBT（平均得分：Backward Dijkstra 下 0.80 对 0.61，Static Guidance 下 0.85 对 0.75，Dynamic Guidance 下 0.94 对 0.81）。
  • 在模拟仓库中，10 台真实机器人无碰撞地到达了各自目标；在 100 台虚拟机器人下，Learnable PIBT 的吞吐量比 PIBT 高 50%。
  • 每次模仿迭代在 50 个回合中收集 1,500 万个动作-观测对，共重复 12 次；在配备 4 张 RTX 4090D GPU 的服务器上，每张地图的训练耗时不到 12 小时。

局限

  • 作者表示，受硬件和软件限制，实物验证仅限于迷你仓库中的 10 台真实机器人加 100 台虚拟机器人，且真实机器人实验以定性方式报告。
  • 规划器假设每个智能体的位置都是完全已知的；真实机器人需要 OptiTrack 动作捕捉系统进行定位，并需要 Action Dependency Graph 来吸收执行误差。
  • 引导启发式是人工设计的，最佳的一种取决于具体实例，必须凭经验选择，且其超参数会影响性能。
  • 由于内存需求，没有在 10,000 个智能体下进行训练；策略在缩小的地图上以 600 个智能体训练，再在大地图上评估。
  • 以所测试的形式，强化学习没有带来帮助；作者把更好的团队奖励分配留待未来工作。

对领域的影响

该论文获得 IEEE ICRA 2025 多机器人系统最佳论文奖和 IEEE ICRA 2025 最佳学生论文奖，被引用 35 次。论文表示代码将在被接收后发布，官方项目页面链接了代码仓库。

摘要

终身多智能体路径规划（Lifelong Multi-Agent Path Finding，LMAPF）是 MAPF 的一种变体，其中智能体会被持续分配新目标，因而需要频繁重新规划以适应这些动态变化。近来，该领域开始采用基于学习的方法，它们根据各自的局部观测以反应式方式生成单步动作。然而，这些方法仍难以达到最佳基于搜索的算法的性能，在大规模场景下尤其如此。本工作提出了一种基于模仿学习的 LMAPF 求解器，引入了新颖的通信模块，以及系统化的单步冲突消解和全局引导技术。我们提出的求解器 Scalable Imitation Learning for LMAPF（SILLM）借助现代 GPU，继承了基于学习方法的快速推理速度和基于搜索方法的高解质量。在六张具有多达 10,000 个智能体和不同障碍结构的大规模地图上，SILLM 超越了最佳的基于学习和基于搜索的基线，平均吞吐量分别提高了 137.7% 和 16.0%。此外，SILLM 还击败了 2023 League of Robot Runners 的获胜方案，这是一项由 Amazon Robotics 赞助的国际 LMAPF 竞赛。最后，我们在一个模拟仓库环境中用 10 台真实机器人和 100 台虚拟机器人验证了 SILLM。

链接

  • arXiv 2410.21415: https://arxiv.org/abs/2410.21415
  • DOI 10.1109/ICRA55743.2025.11127445: https://doi.org/10.1109/ICRA55743.2025.11127445
  • PDF: https://arxiv.org/pdf/2410.21415v1
  • 代码: https://github.com/DiligentPanda/Scalable-Imitation-Learning-for-LMAPF
  • 项目主页: https://diligentpanda.github.io/SILLM/

本网站需要 JavaScript 才能正常运行。请启用 JavaScript 以浏览我们的开源机器人项目。