本研究は、エージェント間の相互作用が極めて強い高密度なMAPF問題に対し、探索の完全性とニューラルネットワークの強力なヒューリスティックを両立させる手法を対象としている。従来の学習ガイド付き探索はMAPFにおいて性能が低い傾向があったが、本研究では $\text{LaCAM}$ という完全性を備えた探索アルゴリズムに、グラフアテンション機構を持つ $\text{MAGAT}^+$ を組み込むことで、不正確なニューラルガイダンスによる停滞を防ぎつつ、効率的な探索を実現している。具体的には、$\text{PIBT}$ による衝突回避と、ニューラルポリシーの誤予測を補完するデッドロック検出スキームを導入している。
第一に、CNN、3層の積層型GNN、およびMLPデコーダで構成される、エッジ特徴量を取り込む $\text{MAGAT}^+$ アーキテクチャを提案している。第二に、$\text{lacam}_3$ の軌跡を用いた事前学習と、対象マップの特定密度（$N \in \{16, 24, 32, 64, 128\}$）に基づく微調整（fine-tuning）を組み合わせた学習戦略を導入した。第三に、エージェントが過去 $T$ ステップ以内に同一の状態を再訪した場合にデッドロックと判定し、$\text{PIBT}$ へフォールバックする検出メカニズムを構築した。これにより、高密度なシナリオにおいて $\text{lacam}_3$ や $\text{MAPF-GPT}$ を上回る解の質と成功率を達成している。
$\text{LaGAT}$ は、$\text{MAGAT}^+$ をヒューリスティックとして活用するマップ特化型の完全探索ソルバーである。$\text{MAGAT}^+$ のGNN更新式は、ノード特徴量 $\mathbf{h}_i^{(l)}$ とエッジ特徴量 $\mathbf{e}_{ij} = [ \Delta x_{ij}, \Delta y_{ij}, d_{ij} ]^\top$ を用い、$\mathbf{h}_i^{(l+1)} = \sigma \left( \mathbf{W}_1 \mathbf{h}_i^{(l)} + \sum_{j \in \mathcal{N}(i)} \alpha_{ij} \mathbf{W}_2 \text{MLP}(\mathbf{e}_{ij}) \right)$ として計算される。学習は、21Kの専門家データによる事前学習後、対象マップでの微調整を行う。探索フェーズでは、$\text{MAGAT}^+$ の予測確率に基づき $\text{PIBT}$ の優先順位を決定するが、目標未到達かつ位置・近傍が不変のまま $T$ ステップ経過した場合はデッドロックとみなし、デフォルトの $\text{PIBT}$ 挙動に切り替えることで完全性を維持する。
POGEMAベンチマークのWarehouseやMazeを含む6種類のマップを用い、エージェント密度 $0.1$ から $0.5$ の範囲で $\text{lacam}_3$、$\text{MAPF-GPT}$、$\text{SSIL}$、$\text{SCRIMP}$、$\text{DCC}$ と比較実験を行った。結果として、$\text{LaGAT}$ は高密度環境において $\text{MAPF-GPT}$ や $\text{lacam}_3$ よりも有意に高品質な初期解を生成し、制限時間内の最終的な解の質においても $\text{lacam}_3$ を凌駕した。大規模かつ疎なマップ（ost003d）では $\text{lacam}_3$ が優位な場面もあったが、LNS（Large Neighborhood Search）の活用により同等の性能に達している。アブレーション解析により、事前学習・微調整が成功率（solvability）に、ニューラルガイダンスとデッドロック検出が解のコスト（solution cost）に寄与することが示された。
$\text{LaGAT}$ の成功は、汎用的な事前学習とタスク特有の微調整の組み合わせ、およびニューラルポリシーの誤りを履歴から検出し標準的な探索へフォールバックする修正レイヤーの有効性に起因する。本手法は、教師モデルである $\text{LaCAM}_3$ が予算内で解を見つけられない高密度環境においても、より高品質な状態へ探索を導くことが可能である。一方で、局所的な方策の性質上、通信・観測範囲を超えるような大規模なマップでは劣解を導く可能性があるという限界も示唆されている。しかし、純粋な学習ベースの手法とは異なり、完全性を保証しつつニューラルヒューリスティックをプラグアンドプレイで交換可能な柔軟な基盤を提供している。
本研究では、高密度なマルチエージェント経路探索（MAPF）問題において、グラフアテンション機構を用いたニューラルMAPF方策であるMAGATから得られる学習済みヒューリスティックを、最先端の探索アルゴリズムであるLaCAMに統合したハイブリッドフレームワーク「LaGAT」を提案している。従来の学習ガイド付き探索手法はMAPFにおいて性能が低い傾向にあったが、提案手法は強化されたMAGATアーキテクチャ、対象マップに対する事前学習・微調整（pre-train–then–fine-tune）戦略、および不完全なニューラルガイダンスを補完するためのデッドロック検出スキームを導入することで、高密度なシナリオにおいて純粋な探索ベースおよび学習ベースの手法を上回る性能を実現している。実験の結果、適切に設計されたハイブリッド探索は、エージェント間の結合が強い困難な調整問題に対して強力な解決策となることが示されている。
本研究は、高密度なマルチエージェント経路探索（MAPF）において、探索と学習を組み合わせたハイブリッド手法である $\text{LaGAT}$ を提案している。$\text{LaGAT}$ は、軽量なニューラルヒューリスティックである $\text{MAGAT}^+$ を、既存の探索ベースのアルゴリズムである $\text{LaCAM}$ に組み込んだものであり、$\text{MAGAT}^+$ は $\text{lacam3}$ の軌跡を用いた模倣学習による事前学習と、対象マップ上での少量のデータによるファインチューニングを経て構築される。ニューラルポリシー特有の不正確さやデッドロックを回避するため、$\text{PIBT}$ による衝突シールドおよび新規のデッドロック検出メカニズムを導入している。実験の結果、$\text{LaGAT}$ は推論による計算オーバーヘッドを伴うものの、高密度な設定において $\text{lacam3}$ を上回るリアルタイム性能を示し、既存の探索ベースのアルゴリズムが形成していたパレート境界を、ニューラル手法として初めて突破して解の質を向上させることに成功した。
本セクションでは、提案手法LaGATの基礎となるMAPF（Multi-Agent Pathfinding）の定式化と既存手法が定義されている。MAPFは、4連結グリッドグラフ上のエージェント集合 $\mathcal{A}$ に対し、各エージェント $a$ に開始地点 $s_a$ と目標地点 $g_a$ を割り当て、頂点・エッジ衝突を回避しながら目標へ到達させる問題であり、解の質は各エージェントの移動時間の総和であるSum-of-Costs (SoC) で評価される。PIBTは、各エージェントの候補行動 $\mathcal{A}_a$ を $h(v, g_a)$（目標までの最短距離）の昇順でソートした優先順位に基づき、衝突を回避する構成を高速に生成する軽量なアルゴリズムであるが、デッドロックやライブロックが発生しやすい。LaCAMは、PIBTを探索のガイドとして利用し、制約 $\mathcal{C}$ を逐次的に追加することで、指数関数的な計算量を抑えつつ、解が存在すれば必ず見つける完全性を備えた探索手法である。一方、MAGATは、近傍半径 $r$ 内の通信グラフ $\mathcal{G}$ 上でメッセージパッシングを行うGNNベースの分散型方策であり、メッセージ依存のアテンション機構を用いることで、近傍からの情報の重要度を重み付けし、高密度な環境への汎化性能を高めている。
LaGATは、ニューラルポリシーをヒューリスティックとして活用する、マップ特化型の完全な探索ベースのMAPFソルバーである。提案手法の核となるMAGAT+は、CNNエンコーダ、3層の積層型GNN、およびMLPデコーダで構成され、エッジ特徴量 $\mathbf{e}_{ij} = [ \Delta x_{ij}, \Delta y_{ij}, d_{ij} ]^\top$ を取り込むことで、エージェント間の複雑な相互作用をモデル化する。具体的には、GNNの更新式において、ノード特徴量 $\mathbf{h}_i^{(l)}$ は、エッジ特徴量をMLPで処理した $\text{MLP}(\mathbf{e}_{ij})$ と注意重み $\alpha_{ij}$ を用いて $\mathbf{h}_i^{(l+1)} = \sigma \left( \mathbf{W}_1 \mathbf{h}_i^{(l)} + \sum_{j \in \mathcal{N}(i)} \alpha_{ij} \mathbf{W}_2 \text{MLP}(\mathbf{e}_{ij}) \right)$ のように更新される。学習パイプラインでは、まず$\text{lacam}_3$を用いて収集した21Kの専門家デモンストレーションデータで事前学習を行い、その後、対象マップのより高密度な設定（エージェント数 $N \in \{16, 24, 32, 64, 128\}$）を用いてファインチューニングを行う。探索フェーズでは、PIBTの優先順位をMAGAT+の予測確率に基づいて決定的に割り当てるが、エージェントが過去 $T$ ステップ以内に同じ状態を再訪した場合（条件：目標未到達、位置不変、かつ近傍 $\mathcal{V}(s) = \mathcal{V}(s')$ が同一）にデッドロックと判定し、そのエージェントの出力をデフォルトのPIBT挙動に上書きする機構を備えている。このデッドロック検出メカニズムを統合したLaCAMは、理論的な完全性を維持しつつ、ニューラルポリシーの誤予測による停滞を回避できる。
本評価実験では、提案手法であるLaGATを、検索ベースの高性能ソルバーであるlacam3や、GPTアーキテクチャを用いた模倣学習モデルMAPF-GPT、GNNベースのSSIL、強化学習ベースのSCRIMPおよびDCCと比較している。POGEMAベンチマークを用い、WarehouseやMazeなどの6種類のマップにおいて、エージェント密度を$0.1$から$0.5$の範囲で変化させて評価を行った。実験結果として、LaGATは高密度な環境において、MAPF-GPTやlacam3よりも有意に高品質な初期解を生成し、制限時間内における最終的な解の品質においてもlacam3を凌駕することを示した。一方で、ost003dのような大規模かつ疎なマップでは、lacam3が近最適解を生成するのに対し、LaGATは初期解がわずかに劣るものの、LNS（Large Neighborhood Search）の活用により最終的には同等の性能に達する。アブレーション解析により、事前学習とマップ特化型の微調整（fine-tuning）は解の成功率（solvability）の向上に、ニューラルガイダンスとデッドロック検出を含む探索メカニズムは解のコスト（solution cost）の削減にそれぞれ不可欠であることが確認された。
本研究は、高密度で混雑したMAPF（Multi-Agent Pathfinding）シナリオにおいて、探索手法とニューラル方策を組み合わせるLaGATが、従来の探索のみの手法や既存のハイブリッド手法よりも優れた性能を示すことを明らかにした。LaGATの成功要因として、まず汎用的な方策を事前学習した後にタスク特有の環境へファインチューニングを行う戦略が有効であり、次に、ニューラル方策が引き起こすデッドロックやライブロックを履歴から検出し、必要に応じて標準的な探索手法へフォールバックする修正レイヤーが不可欠であることが示された。また、低密度環境で生成された準最適軌跡を用いて学習したMAGAT+は、教師モデルであるLaCAM3が予算内で解を見つけられない高密度環境においても、より高品質な状態を探索に導くことで、速度と解の質のパレート境界を再定義している。LaGATの適用は、比較的小規模なマップ、障害物が豊富な環境、および高いエージェント密度を持つシナリオにおいて特に有効であるが、通信・観測範囲を超えるような大規模なマップでは、局所的な方策の性質上、劣解を導く可能性があるという限界も示唆されている。一方で、純粋な学習ベースの手法とは異なり、LaGATは完全性（completeness）を保証し、かつニューラルヒューリスティックをプラグアンドプレイ形式で交換可能であるという、柔軟かつ強力な基盤を提供している。