エージェントが現在の目標に到達するたびに新しい目標が継続的に割り当てられるLifelong Multi-Agent Path Finding (LMAPF)を対象とする。この問題の目的は、エージェント間の衝突を回避しながら、単位時間あたりの目標到達数であるスループットを最大化することである。従来の学習ベースの手法は、数十から数百規模のエージェントを用いた小規模な設定に限定されることが多く、数千から数万規模の大規模な設定では探索ベースの手法に性能が及ばないという困難があった。
スケーラブルな探索アルゴリズムの出力を教師データとして用いることで、大規模環境への適用を可能にした。従来の注意機構を用いた通信とは異なり、エージェント間の精密な空間関係を保持したまま情報を集約するSpatially Sensitive Communication (SSC)を導入した。さらに、単一ステップの衝突回避メカニズムと、交通流を制御する3種類のグローバルな誘導技術を統合することで、既存の学習ベースおよび探索ベースの最先端手法を凌駕する性能を実現した。
提案手法SILLMは、ニューラルネットワークによる方策と衝突回避アルゴリズムを統合したLearnable PIBT (L-PIBT)で構成される。通信部には、畳み込みニューラルネットワークを用いて静止・動的障害物や目標位置の空間的関係性を特徴量として処理するSSCを用いる。学習には、Windowed MAPF-LNSによる経路を模倣する手法を採用し、wステップ先までの経路情報を利用して自己ブートストラップ形式で学習を行う。推論時には、ネットワークが出力する行動確率を優先順位として、Collision Shield PIBT (CS-PIBT)を用いて、優先度の高いエージェントの行動を優先しつつ衝突を回避する。また、最短距離を示すBackward Dijkstra、特定の通行方向を促すStatic Guidance、混雑を回避するDynamic Guidanceの3種類のヒューリスティックを観測情報として組み込んでいる。
最大10,000体のエージェントを含む6つの大規模マップ、および実機ロボット10台と仮想ロボット100台を用いた模擬倉庫環境で検証を行った。既存の学習ベース手法と比較してスループットを平均137.7%向上させ、最新の探索ベース手法と比較しても16.0%の向上を達成した。また、2023年の国際コンペティションの勝者であるWPPLを上回る性能を示し、10,000体のエージェントに対しても1ステップあたり1秒未満という高速な計画実行を実現した。
地図の構造によって最適な誘導手法が異なり、Static Guidanceは倉庫のような規則的なマップに適し、Dynamic Guidanceは都市型マップに適するという特性がある。また、L-PIBTは従来のPIBTと比較してスループットは向上するものの、計算時間は増加するというトレードオフが存在する。現在の学習手法は強化学習（RL）を用いるよりも模倣学習（IL）の方がチームの協調動作を学習しやすいが、今後はより高度な強化学習手法をSILLMに適用することが課題である。
Lifelong Multi-Agent Path Finding (LMAPF)は、エージェントが現在の目標に到達するたびに新たな目標を割り当て続ける問題であり、単位時間あたりの目標到達数であるスループットの最大化が求められます。本研究では、最大10,000体のエージェントを管理可能な、模倣学習に基づく解決手法であるSILLMを提案します。SILLMは、空間的な疎性を重視した新しい通信モジュールであるSpatially Sensitive Communication (SSC)を導入しているほか、単一ステップの衝突回避とグローバルな誘導のためのヒューリスティックな探索改善技術を統合しています。実験の結果、SILLMは最大10,000体のエージェントを含む6つの大規模なマップにおいて、既存の学習ベースおよび探索ベースの最先端手法を上回り、スループットをそれぞれ平均で137.7%および16.0%向上させました。また、2023年の国際コンペティションの勝者であるWPPLを上回る性能を示し、GPUの活用により10,000体のエージェントに対しても1ステップあたり1秒未満での計画実行を実現しています。さらに、10台の実機ロボットと100台の仮想ロボットを用いた模擬倉庫環境での検証により、実世界への適用可能性も示しています。
Lifelong Multi-Agent Path Finding (LMAPF)は、エージェントが次々と新しい目標を与えられる環境において、衝突を回避しながらスループット、すなわち単位時間あたりの平均目標到達数を最大化する経路計画問題である。本研究で提案するSILLMは、エージェント間の空間的な位置関係を明示的に保持しながら情報を集約する、Spatially Sensitive Communication (SSC) モジュールを導入している。このモジュールは2つの畳み込みニューラルネットワーク（CNN）で構成され、エージェントの視野内にある静止障害物、動的障害物、および目標位置などの情報を、空間的な関係性を維持したまま特徴量として処理する。さらに、SILLMはBackward Dijkstra (BD)、Static Guidance (SG)、Dynamic Guidance (DG) と呼ばれる3種類のグローバルなガイダンスをヒューリスティックとして活用する。衝突解決にはCS-PIBTという手法を用いており、実験では10,000台のエージェントという大規模なスケールでの動作を実現している。
本研究では、ニューラルネットワークによる方策と衝突回避アルゴリズムを統合したLearnable PIBT（L-PIBT）を提案している。L-PIBTは、最短経路や動的な交通情報を考慮したガイドパスに基づくヒューリスティック値を、正規化された絶対値と中心点からの相対的な差を示す2チャンネルの2D特徴マップとしてエージェントの観測情報に組み込む。学習には、大規模な問題でもスケーラブルに動作する探索ベースのアルゴリズムであるWindowed MAPF-LNSの出力を模倣する手法を採用しており、これによりエージェント間の協調動作を学習させる。推論時の衝突回避にはCollision Shield PIBT（CS-PIBT）を用い、エージェントの優先度に基づいた行動選択と、衝突が発生した際に優先度の高いエージェントに再選択を促すバックトラッキング処理によって、単一ステップ実行の安全性を確保している。既存の模倣学習を用いた手法は、学習データの収集コストに起因して小規模な設定に限定される傾向があったが、本手法はスケーラブルな探索アルゴリズムを教師データとすることで、大規模なエージェント数への適用を可能にしている。
提案手法であるLearnable PIBT (L-PIBT)は、ニューラルネットワークが出力する行動確率を優先順位として、衝突回避アルゴリズムであるPIBTに組み込む手法である。具体的には、学習された行動が衝突を回避できる場合はそのまま採用し、そうでない場合はPIBTのルールに従って他の行動を順位付けするCS-PIBTの簡略版を採用している。学習プロセスでは、現在の観測から得られるwステップ先までの経路を収集して教師あり学習を行う自己ブートストラップ形式をとり、w=15、各イテレーションで1,500万の行動観測ペアを収集する設定で実験が行われた。実験の結果、L-PIBTは従来のPIBTと比較して、計算時間は増加するものの、スループットにおいて一貫して高いスコアを記録した。また、地図の特性に応じて、静的なガイド（Static Guidance）はソートや倉庫マップに、動的なガイド（Dynamic Guidance）は都市型のマップに適しており、これらを組み合わせたSILLMは、大規模な10,000エージェントの環境においても既存の探索ベースおよび学習ベースの手法を上回る性能を示した。
提案手法であるSILLMは、大規模なLifelong Multi-Agent Path Findingにおいて、従来の学習ベースの手法であるFollowerの約2倍のスコアを記録し、最新の探索ベースの手法であるTrafficFlowも大幅に上回る性能を示しています。また、SILLMはWPPLと比較して、すべてのマップにおいて同等以上の性能を維持しつつ、実行速度において大幅な優位性を持ちます。アブレーション研究では、提案する空間的に敏感な通信モジュールであるSSCが、アテンションベースの通信であるABCや通信なしの構成よりも一貫して高い性能を発揮しており、LMAPFにおける精密な空間推論の重要性が示されています。学習手法の比較では、単純なMAPPOを用いた強化学習よりも、提案する模倣学習の方が優れた性能を示しました。既存のRHCRやSCRIMPは計算コストの高さから大規模環境へのスケーリングが困難ですが、SILLMは10,000体のエージェントに対して1秒未満で計画を立てることが可能です。