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 による衝突修復を加えて、10,000 エージェントの計画を 1 ステップあたり 1 s 未満で行い、最も高いスループットを得る。

重要な理由

自動倉庫ではすでに数千台のロボットが稼働している（論文は 2022 年に Amazon のフルフィルメントセンターで 4,000 台超が稼働していたと引用している）。そのため、その規模で 1 ステップあたり 1 秒未満の計画によって高いスループットを保つ計画器は、フリート制御に直結する。結果は、学習されたポリシーに探索型の衝突処理と交通を考慮したガイダンスを組み合わせることで、遅い最適ソルバーだけでなく、最も強力なスケーラブルな探索ベースのソルバーをも上回りうることを示している。

課題

生涯型マルチエージェント経路探索（LMAPF）では、各エージェントがゴールに到達するとすぐに新しいゴールが与えられるため、スループット（タイムステップあたりに到達したゴール数）を最大化しながら、衝突のない経路を継続的に再計画しなければならない。学習ベースのソルバーは局所観測から素早く反応するが、そのほとんどは数十から数百のエージェントでしか試されておらず、PIBT のようなスケーラブルな準最適探索ソルバーに勝てていない。本論文は、10,000 エージェントの規模で学習ベースと探索ベースの両方のソルバーを上回ることを目指す。

提案手法

SILLM は全エージェントで共有される 11×11 の視野上の畳み込みポリシーであり、各近傍エージェントの特徴ベクトルを正確な相対グリッド位置に挿入する Spatially Sensitive Communication モジュールを備える。観測には 3 種類のヒューリスティックなガイダンスマップ（Backward Dijkstra、十字型ハイウェイの Static Guidance、または TrafficFlow ベースの Dynamic Guidance）のいずれかが符号化され、簡略化された CS-PIBT ステップは、学習された行動が衝突しなければそれを維持し、衝突する場合は PIBT で修復する。ポリシーは、2023 League of Robot Runners の優勝手法 WPPL の中核である Windowed MAPF-LNS を反復的に模倣することで、600 エージェントの縮小マップ上で学習される。

主な知見

  • 近傍エージェントの特徴を正確な相対位置に配置する方式（空間的に敏感な通信）は、アブレーションにおいてアテンションベースの通信や通信なしを上回り、LMAPF には正確な空間推論が重要であることを示している。
  • anytime 型の大規模ソルバー（Windowed MAPF-LNS）を模倣することで、PRIMAL2、SCRIMP、MAGAT など以前の模倣学習器を制約していた小規模な学習インスタンス（8–10 エージェント）を回避している。
  • 最適なガイダンスはマップに依存する。Static Guidance は十字型の仕分けマップと倉庫マップに、Backward Dijkstra はランダムマップに適し、Dynamic Guidance は Paris と Berlin の都市マップで最も良かった。
  • PIBT ベースの衝突修復は、学習された行動が衝突しない限りそれを維持し、一般的な「フリーズ」戦略による不要な待機やデッドロックを回避する。
  • 単純な MAPPO による強化学習は模倣学習に劣り、模倣の後に MAPPO を適用しても測定可能な改善は得られなかった。

主な結果

  • 10,000 エージェントの 6 つの大規模マップで、平均スループットは最良の学習ベースのベースラインより 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 は 1 ステップに数分を要し、この規模では評価できなかった。
  • 大規模マップでの単一ステップの平均計画時間：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 Best Paper Award on Multi-Robot Systems と IEEE ICRA 2025 Best Student Paper Award を受賞し、被引用数は 35 である。論文はコードを採択時に公開するとしており、公式プロジェクトページはコードリポジトリにリンクしている。

概要

生涯型マルチエージェント経路探索（Lifelong Multi-Agent Path Finding、LMAPF）は MAPF の一種であり、エージェントに新しいゴールが継続的に割り当てられるため、こうした動的な変化に対応する頻繁な再計画が必要となる。近年この分野では、個々の局所観測に基づいて単一ステップの行動を反応的に生成する、学習ベースの手法が取り入れられている。しかし、特に大規模な設定では、それらが最良の探索ベースのアルゴリズムの性能に匹敵することはいまだ難しい。本研究は、新しい通信モジュールと、体系的な単一ステップの衝突解消および大域的ガイダンスの手法を導入した、模倣学習ベースの LMAPF ソルバーを提案する。我々が提案するソルバー Scalable Imitation Learning for LMAPF（SILLM）は、最新の GPU の助けを借りて、学習ベースの手法の高速な推論速度と探索ベースの手法の高い解の品質を受け継いでいる。最大 10,000 エージェントとさまざまな障害物構造を持つ 6 つの大規模マップにおいて、SILLM は最良の学習ベースおよび探索ベースのベースラインを上回り、平均スループットをそれぞれ 137.7% および 16.0% 向上させた。さらに SILLM は、Amazon Robotics が後援する国際的な LMAPF コンペティションである 2023 League of Robot Runners の優勝ソリューションにも勝る。最後に、模擬倉庫環境において 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を有効にしてください。