マルチエージェント経路探索（MAPF）は、複数のエージェントが衝突を回避しながら各々の目的地へ到達する問題であり、エージェント間の強い相互依存性からNP困難な問題として定義される。従来の学習ベースの手法は、エージェント間の相互作用をペア単位（pairwise）でモデル化するGNNやTransformerに依存してきた。しかし、高密度な環境においては、複数のエージェントが同時に関与する高度に結合したダイナミクスを捉えることが困難であり、アテンションの希釈が発生するという問題がある。
本研究の新規性は、グループ単位の相互作用を自然にモデル化できるハイパーグラフの表現能力をMAPFに導入した点にある。従来のGNNがペアワイズなメッセージパッシングに限定されていたのに対し、提案手法は有向ハイパーグラフを用いることで、高次のグループダイナミクスを明示的に捉える帰納バイアスを導入している。これにより、モデルの巨大化に頼ることなく、パラメータ数および訓練データ量を大幅に削減しながら、既存の最先端モデルを凌駕する性能を実現した。
提案手法であるHMAGATは、単一のヘッドと複数のテイルノードを持つ有向ハイパーグラフ構造を採用したアテンション付きハイパーグラフニューラルネットワーク（HGNN）である。メッセージパッシングの更新は、ハイパーエッジの特徴量とテイルノードの集約された特徴量に対し、正規化されたアテンション重みを適用することで行われる。具体的には、第 $l$ 層のエージェント $i$ の特徴量 $\mathbf{h}_i^{(l+1)}$ は、$\sigma \left( \mathbf{W}^{(l)} \sum_{e \in \mathcal{E}_i} \alpha_{e,i}^{(l)} (\text{MLP}(\mathbf{e}) + \sum_{j \in \text{tail}(e)} \mathbf{h}_j^{(l)}) \right)$ として計算される。学習には、エキスパートによる軌跡を用いた模倣学習に加え、分布シフトを抑制するオンラインエキスパートによるデータ集約や、予測の信頼性を高める温度サンプリングが組み込まれている。
21,000個のインスタンスを用い、成功率、平均相対コスト（Rel. SoC）、および平均実行時間を指標として評価を行った。比較対象はMAGATおよびMAPF-GPT（2M, 6M, 85M）である。実験の結果、HMAGATはわずか $1 \times 10^6$ 個のパラメータで、85M個のパラメータを持つMAPF-GPTを上回る性能を示した。また、訓練データ量においても、既存の最先端モデルの約10%で同等以上の性能を達成している。特にエージェント密度が高いDense Warehouseマップにおいて、GNNモデルよりも高い成功率と低いRel. SoCを記録した。
本研究の結果は、マルチエージェント問題においてモデルの規模よりも適切な帰納バイアスの導入が重要であることを示唆している。アブレーション解析により、強化学習に基づく温度サンプリングの導入は、成功率と解の品質の間にトレードオフを生じさせることが判明した。また、ハイパーグラフによるグループモデリングは有効であるが、複雑な相互作用を正確に識別するためには、適切なハイパーグラフ生成戦略が重要となる。今後の課題として、これらの相互作用をより効率的に扱うためのさらなる検討が挙げられる。
本研究では、従来のグラフニューラルネットワーク（GNN）を用いたマルチエージェント経路探索（MAPF）において、エージェント間のペアワイズなメッセージパッシングのみでは、高密度な環境で不可欠なグループ単位の協調を捉えきれず、アテンションの希釈（attention dilution）が生じるという課題を指摘している。この表現能力のボトルネックを解消するため、有向ハイパーグラフ上のアテンション機構を活用してグループのダイナミクスを明示的に捉える新アーキテクチャであるHMAGAT（Hypergraph Multi-Agent Attention Network）を提案する。実験の結果、HMAGATはわずか $1 \times 10^6$ 個のパラメータを持ち、従来の最先端モデルよりも $100$ 倍少ない訓練データを用いながらも、$85 \times 10^6$ 個のパラメータを持つ既存の最先端モデルを上回る性能を達成した。アテンション値の詳細な分析により、ハイパーグラフ表現がGNN特有のアテンションの希釈を抑制し、ペアワイズな手法では失敗する複雑な相互作用を捕捉できることが示されている。この結果は、マルチエージェント問題においては、訓練データの規模やパラメータ数よりも、適切な帰納バイアスを導入することが極めて重要であることを示唆している。
マルチエージェント経路探索（MAPF）は、衝突を回避しながら各エージェントを目的地へ導く問題であり、エージェント間の強い相互依存性からNP困難な問題として知られている。従来の学習ベースのMAPF手法は、グラフニューラルネットワーク（GNN）やTransformerを用いてエージェント間の相互作用をペア単位（pairwise）でモデル化してきたが、これは複数のエージェントが同時に関与する高度に結合したダイナミクスを捉えるには不十分である。本研究では、グループ単位の相互作用を自然にモデル化できるハイパーグラフの表現能力に着目し、新しい模倣学習フレームワークであるHMAGATを提案する。HMAGATは、動的に有向ハイパーグラフを構築するハイパーグラフ生成戦略と、ハイパーグラフアテンションネットワークを活用することで、高次のグループ相互作用を効果的に学習する。実験の結果、HMAGATは既存の最先端の学習モデルを上回る性能を達成しており、従来のモデルと比較して約10倍少ないパラメータ数と約10%の訓練データのみで、高い解の品質とスケーラビリティを実現している。
本セクションでは、高次相互作用を捉えるためのハイパーグラフの定義と、マルチエージェント経路計画（MAPF）の定式化、および既存手法であるMAGATの構成について述べている。ハイパーグラフは、ノード集合 $\mathcal{V}$ と、始点 $s$ と終点 $t$ の順序対 $(s, t)$ からなるハイパーエッジ集合 $\mathcal{E}$ によって定義される構造 $\mathcal{H} = (\mathcal{V}, \mathcal{E})$ である。MAPFは、エージェント集合 $\mathcal{A}$、4連結グリッドグラフ $\mathcal{G}$、および各エージェントの開始地点と目標地点が与えられた問題であり、頂点やエッジでの衝突を避けつつ、各エージェント $a$ に衝突のない経路 $\tau_a$ を割り当てることを目的とする。解の質は、各エージェントが目標に到達するまでの移動時間の総和である sum-of-costs (SoC) によって評価される。既存の模倣学習（IL）手法であるMAGATは、半径 $r$ 以内の近接エージェントに基づく通信グラフを用いて、CNNエンコーダ、GNN層、MLPデコーダからなるポリシーを構成するが、本研究ではこれを拡張し、GNNをハイパーグラフニューラルネットワーク（HGNN）に置き換えたHMAGATを提案する。エージェントの観測情報は、障害物、エージェント、目標方向、および正規化されたコスト・トゥ・ゴー（$c(v) / c(v_{start})$）の4チャネルからなる、視野サイズ $F$ に基づく形状 $F \times F \times 4$ のテンソルとして定義される。
HMAGATは、マルチエージェント経路探索（MAPF）における既存のグラフニューラルネットワーク（GNN）が抱える、高密度な環境でのアテンションの希釈化およびグループ相互作用の表現不足という課題を解決するために提案された、アテンション付きハイパーグラフニューラルネットワーク（HGNN）に基づく模倣学習モデルである。本手法は、単一のヘッド（head）と複数のテイル（tail）ノードを持つ有向ハイパーグラフ構造を採用しており、メッセージパッシングの更新式は $\mathbf{h}_i^{(l+1)} = \sigma \left( \mathbf{W}^{(l)} \sum_{e \in \mathcal{E}_i} \alpha_{e,i}^{(l)} (\text{MLP}(\mathbf{e}) + \sum_{j \in \text{tail}(e)} \mathbf{h}_j^{(l)}) \right)$ と定義される。ここで、$\mathbf{h}_i^{(l)}$ はエージェント $i$ の第 $l$ 層のノード特徴量、$\mathbf{e}$ はハイパーエッジの特徴量、$\alpha_{e,i}^{(l)}$ は正規化されたアテンション重み、$\sigma$ は非線形活性化関数を表す。ハイパーグラフの生成には、Lloydのアルゴリズムを用いたVoronoi分割に基づくLloyd Hypergraphsや、計算コストを抑えた$k$-means Hypergraphs、および最短経路距離に基づく手法などが提案されている。実験では、21,000個のインスタンス（迷路状環境80%、障害物配置環境20%）を用い、expert solverであるlacam3から得られた軌跡で学習を行う。学習パイプラインには、分布シフトを抑制するためのオンラインエキスパートによるデータ集約や、解の品質を向上させるためのポストトレーニング、および予測の信頼性を高めるための温度サンプリングが含まれる。
提案手法であるHMAGATの評価では、MAGAT、MAPF-GPT（2M, 6M, 85M）、およびその微調整版であるMAPF-GPT-DDGを比較対象とし、成功率、検索ベースの解であるlacam3に対する平均相対コスト（Rel. SoC）、およびマップあたりの平均実行時間を指標として用いている。実験の結果、HMAGATはMAGATや各種MAPF-GPTモデルよりも一貫して高品質な解を生成し、特に大規模なost003dマップにおいて、スケーラビリティに課題のあるMAPF-GPT (85M) を上回る性能を示した。アブレーション解析では、各モジュールの追加が成功率と解の品質を向上させることが確認されたが、強化学習に基づく温度サンプリングのみ、成功率と解の品質のトレードオフが生じることが示された。GNNとHGNNの直接比較では、HGNNを用いたモデルがすべてのマップ、特にエージェント密度が高いDense Warehouseマップにおいて、GNNモデルよりも高い成功率と低いRel. SoCを達成した。アテンション解析によれば、GNNは高密度環境下でアテンションが希釈される傾向があるのに対し、HGNNは重要なエージェントに対して高いアテンションを維持できる。さらに、手作りのシナリオを用いた検証では、GNNがペアワイズな相互作用に依存するために重要でない領域のエージェント増加によってアテンションが希釈される問題や、グループ間の相互作用を捉えきれない限界が示された一方で、HGNNはShapley値を用いた分析においてグループ間の複雑な影響関係を正確に識別できることが証明された。
本研究では、複雑な相互作用を伴うマルチエージェント問題の代表例としてMAPF（Multi-Agent Pathfinding）に着目し、高次の相互作用をモデル化するためのハイパーグラフニューラルネットワーク（HGNN）に基づく解法であるHMAGATを提案した。実験の結果、ペアワイズな相互作用のみを考慮する既存の最先端手法を上回る性能を達成しており、より大規模なデータで学習されたMAPF-GPTよりも優れた性能を示すことが確認された。詳細な分析により、HGNNが明示的なグループモデリングを通じて、従来のGNNよりもグループ間の相互作用を効果的に捉えられることが示されている。HMAGATは、先行研究と比較してパラメータ数を大幅に削減しながら最先端の性能を実現しており、ハイパーグラフを用いた相互作用モデリングのような優れた帰納バイアスを導入することが、モデルの巨大化とは別の、困難なマルチエージェント問題に対する補完的な戦略となり得ることを実証した。
提案手法である HMAGAT モデルの詳細なアーキテクチャおよび学習手順については、付録 A にてハイパーパラメータとともに記述されている。研究の再現性を確保するため、学習済みモデルのチェックポイント、および結果を再現するための手順書を含むコードベースが補足資料として提供されている。また、モデルの学習および評価に使用されるインスタンスを生成するためのスクリプトもコードベースに含まれている。