グリッドグラフ上で複数のエージェントが衝突を避けながら各々の目的地へ到達するマルチエージェント経路計画（MAPF）を対象とする。エージェント密度が高い環境では、スケーラビリティに優れた探索ベースの手法と、複雑な相互作用を学習できる学習ベースの手法の間に性能差があり、従来の学習を用いた探索支援手法は、探索手法の解の品質に及ばないという課題がある。
グラフアテンション機構を持つニューラル方策を拡張したMAGAT+と、探索アルゴリズムLaCAMを統合したフレームワークLaGATを提案する。事前学習とマップ特化型の微調整、およびニューラル方策の不完全さを補完するデッドロック検出スキームを導入することで、ニューラル手法として初めて、既存の探索ベースの手法が形成するパレート境界を上回る解の品質を達成した。
MAGAT+は、CNNによる局所観測のエンコード、3層のグラフニューラルネットワークによるメッセージパッシング、およびMLPデコーダで構成される。エージェント間の相対位置やマンハッタン距離をエッジ特徴量として取り入れ、アテンション機構によって隣接エージェントからの情報の重要度を動的に重み付けする。学習は、エキスパートの軌跡を用いた事前学習と、ターゲット環境の密度を高めたデータを用いた微調整の2段階で行われる。探索時には、LaCAMの枠組みにおいてMAGAT+の予測に基づきPIBTの優先順位を決定するが、エージェントがデッドロック状態にあると判定された場合は、当該エージェントの制御をデフォルトのPIBTメカニズムへと切り替える。
POGEMAベンチマークを用い、WarehouseやMazeを含む6種類のマップ、32から160のエージェント密度、計3,456のインスタンスで評価を行った。比較対象は、探索ベースのlacam3、模倣学習ベースのMAPF-GPTやSSIL、強化学習ベースのSCRIMPやDCC、および単体でのMAGAT+である。高密度な環境において、LaGATは30秒の制限時間内における最終的な解の質でlacam3を上回り、初期解の質もMAPF-GPTやlacam3より高い結果を示した。アブレーション解析により、事前学習と微調整が解決能力を、ニューラルガイダンスとデッドロック検出が解のコスト削減に寄与することが確認された。
本手法は、比較的小規模なマップ、障害物が多い環境、および高いエージェント密度という条件下で特に有効である。大規模かつ疎なマップでは、lacam3が準最適解を生成する傾向があり、LaGATの優位性は限定的となる。また、ニューラルネットワークの推論に伴う計算コストのオーバーヘッドが存在する。今後の課題として、エージェントの通信範囲や観測範囲よりも大幅に大きなマップにおける、局所的な方策の限界の克服が挙げられる。
高密度なマルチエージェント経路計画（MAPF）において、準最適解をリアルタイムで求めることは依然として困難な課題である。本研究では、グラフアテンション機構を用いたニューラルMAPF方策であるMAGATから得られる学習済みヒューリスティックを、既存の探索アルゴリズムであるLaCAMに統合したハイブリッドフレームワークLaGATを提案する。LaGATは、強化されたMAGATアーキテクチャ、対象となるマップに対する事前学習と微調整を組み合わせた戦略、および不完全なニューラルガイダンスを補完するためのデッドロック検出スキームを導入している。これにより、高密度なシナリオにおいて、純粋な探索手法および純粋な学習手法の両方を上回る性能を実現した。実験の結果、適切に設計されたハイブリッド探索は、エージェント間の結合が強い複雑な調整問題に対して強力な解決策となることが示された。
マルチエージェント経路探索（MAPF）の研究は、スケーラビリティと解の品質を重視する探索ベースの手法と、局所的な観測下での柔軟性を重視する学習ベースの手法の二つの流れがある。既存の学習ベースの手法は、スケーラビリティや解の品質において最先端の探索ベースの手法に大きく劣るという課題がある。本研究では、探索と学習を組み合わせたハイブリッド手法であるLaGATを提案し、高密度なMAPFインスタンスにおいて、既存の最先端な探索ベースのアルゴリズムが形成するパレート境界を、ニューラル手法として初めて超える解の品質を実現した。LaGATは、軽量なニューラルヒューリスティックであるMAGAT+を、探索アルゴリズムであるLaCAMに組み込んだ構成をとる。MAGAT+は、LaCAMの軌跡を模倣する事前学習を行った後、対象となるマップ上で少量のデータを用いて微調整を行うことで、静的なマップ環境への適応を図っている。学習ベースのポリシーが抱える不正確さやデッドロックの問題に対しては、PIBT衝突シールドと新たに提案するデッドロック検出メカニズムを併用することで補完している。この手法は、ニューラルネットワークの推論による計算オーバーヘッドを伴うものの、得られる解の品質の向上によってそのコストを十分に正当化できることを示している。
本セクションでは、提案手法の基礎となるマルチエージェント経路探索（MAPF）の定義と、関連する既存手法について述べる。MAPFは、グリッドグラフ上の複数のエージェントに対し、頂点やエッジでの衝突を避けながら各エージェントを目標地点へ到達させる経路を割り当てる問題であり、解の質は全エージェントの移動時間の総和であるsum-of-costsで評価される。PIBTは、各エージェントが目標までの最短距離を優先順位として行動を選択する軽量な衝突回避アルゴリズムだが、単体ではデッドロックやライブロックを招く可能性がある。LaCAMは、PIBTを探索のガイドとして利用し、制約を段階的に追加することで、計算量を抑えつつ解の存在を保証する完全性を備えた探索アルゴリズムである。一方、MAGATはグラフニューラルネットワークを用いた分散型ポリシーであり、近傍エージェントからのメッセージに対してアテンション機構を用いることで、情報の重要度を動的に重み付けし、高密度な環境への汎化性能を高めている。
LaGATは、ニューラルポリシーをヒューリスティックとして活用する、マップ特化型の完全な探索ベースのマルチエージェント経路探索（MAPF）ソルバーです。提案手法の核となるMAGAT+は、CNNによる局所観測のエンコード、3層のグラフニューラルネットワーク（GNN）によるメッセージパッシング、およびMLPデコーダで構成され、エージェント間の相対位置やマンハッタン距離を含むエッジ特徴量を取り入れることで、複雑な相互作用のモデリングを強化しています。学習プロセスは、エキスパートの軌跡を用いた事前学習と、ターゲット環境の密度を高めたデータを用いたマップごとの微調整の2段階で行われます。探索時には、LaCAMの枠組みの中でPIBTの優先順位をMAGAT+の予測値に基づいて決定的に決定しますが、エージェントが目標に到達せず、位置や周囲の状況が変化しないまま同じ状態を繰り返すデッドロックを検知した場合、そのエージェントの制御を学習に基づかないデフォルトのPIBTメカニズムへと切り替えます。このデッドロック検知は、エージェントが過去の一定期間内に同じ状態を再訪したかどうかを判定することで行われます。
本研究では、提案手法であるLaGATの性能を、探索ベースのlacam3、模倣学習ベースのMAPF-GPTやSSIL、強化学習ベースのSCRIMPやDCC、および改良版ニューラルポリシーであるMAGAT+と比較評価している。POGEMAベンチマークを用い、WarehouseやMazeなど6種類のマップ、32から160のエージェント密度、計3,456のインスタンスを用いて実験を行った。ニューラルポリシー単体の評価では、模倣学習ベースの手法が強化学習ベースの手法を上回り、特にMAGAT+はMAPF-GPTと同等の成功率を達成しつつ、C++実装による高い推論速度を実現している。LaGATとlacam3の比較において、高密度な環境では、LaGATは初期解の質がMAPF-GPTやlacam3よりも大幅に高く、30秒の制限時間内における最終的な解の質においてもlacam3を上回る結果を示した。一方で、大規模かつ疎なマップではlacam3が近最適解を生成する傾向があるが、LaGATも大規模近傍探索（LNS）の活用により同等の最終性能に達している。アブレーション解析の結果、事前学習とマップ特化型の微調整は解決能力の向上に、ニューラルガイダンスとデッドロック検出を含む探索メカニズムは解のコスト削減にそれぞれ寄与することが確認された。
本研究は、探索手法とニューラル方策を組み合わせることで、純粋な探索のみでは困難な高密度かつ混雑したマルチエージェント経路計画（MAPF）において効果を発揮することを示している。提案手法であるLaGATは、汎用的な方策を事前学習した後にタスク固有の環境へ微調整を行う戦略をとっており、地図の構造的特徴に適合した性能を実現している。また、ニューラル方策が引き起こすデッドロックやライブロックを直近の状態履歴から検出し、必要に応じて標準的な探索手法へ切り替える補正レイヤーを導入することで、ハイブリッドアプローチとしての性能を高めている。実験では、低密度環境で生成された準最適軌跡を教師データとして学習したMAGAT+が、教師自身が失敗するような高密度環境においても、探索をより高品質な状態へと導くことで、既存のLaCAM3よりも優れた解の質を実現できることが示された。LaGATは、比較的小規模な地図、障害物が多い環境、および高いエージェント密度という条件下で特に有効であり、計算速度と解の質のトレードオフにおけるパレート境界を更新している。さらに、純粋な学習ベースの手法とは異なり、探索を組み合わせることで完全性が保証され、ニューラルヒューリスティックをプラグアンドプレイ形式で入れ替えられる柔軟性も備えている。