マルチエージェント経路探索（MAPF）は、複数のエージェントが衝突を避けながら各々の目的地へ到達する経路を計算する問題であり、エージェント間の強い相互依存性からNP困難な性質を持つ。従来のグラフニューラルネットワーク（GNN）やTransformerを用いた手法は、エージェント間の相互作用をペア単位でモデル化してきた。しかし、高密度な環境では、無関係なエージェントの存在によって重要なエージェントへの注意スコアが分散する「アテンションの希釈」が発生し、集団的なダイナミクスを捉えきれないという困難がある。
本研究の新規性は、エージェント間の高次のグループ相互作用を明示的に捉えるための、注意機構付きハイパーグラフニューラルネットワーク（HGNN）を用いた模倣学習フレームワークHMAGATを提案した点にある。従来のペアワイズな手法に対し、集団のダイナミクスをモデル化するための適切な帰納バイアスを導入した。これにより、モデルのパラメータ数や学習データの量に依存するのではなく、構造的なアプローチによって既存の学習ベースのソルバーを上回る性能を実現した。
HMAGATは、CNNによる観測情報のエンコード、HGNNによるメッセージ集約、およびMLPによるデコードで構成される。通信の仕組みとして、1つのヘッド（対象エージェント）と複数のテイル（周囲のエージェント）を持つ有向ハイパーグラフを採用し、テイルからハイパーエッジを経由してヘッドへと情報を伝達するメッセージパッシングを行う。ハイパーグラフの構築には、Lloydのアルゴリズムを用いたVoronoi分割に基づく手法や、k-means、最短経路距離に基づく生成戦略を用いる。学習にはエキスパートの軌跡を用いた模倣学習を用い、さらに解の品質を向上させるためのポストトレーニングや、エージェントの局所的な観測可能性に応じてソフトマックスの温度パラメータを動的に調整するモジュールを導入している。
実験では、成功率、探索ベースの手法に対する平均相対コスト（Rel. SoC）、およびマップあたりの平均実行時間を評価指標とした。k-meansやLloyd法を用いた戦略により、MAGATや小規模なMAPF-GPTを上回る解の品質を達成し、85M（8500万）個のパラメータを持つMAPF-GPTと比較しても、Mazeマップにおいて解の品質で上回り、実行速度においても優位性を示した。特にDense Warehouseのような高密度シナリオにおいて、他の手法の成功率が11%未満であるのに対し、HMAGATは75%以上を記録した。また、Shapley値を用いた分析により、HGNNがGNNと比較して、アテンションの希釈を防ぎ、複雑なグループ間の相互作用を効果的に区別してモデル化していることが示された。
本研究は、マルチエージェント問題において、モデルの巨大化よりも適切な帰納バイアスの導入が重要であることを示唆している。
マルチエージェント経路探索（MAPF）において、従来のグラフニューラルネットワークを用いた手法はエージェント間のペアワイズなメッセージ伝達に限定されており、高密度な環境で不可欠な集団的な調整を捉えきれず、アテンションの希釈という問題を引き起こしています。本研究では、この表現能力のボトルネックを解消するため、有向ハイパーグラフ上のアテンション機構を活用して集団のダイナミクスを明示的に捉える新アーキテクチャであるHMAGAT（Hypergraph Multi-Agent Attention Network）を提案します。実験の結果、HMAGATは100万個のパラメータを持ち、既存の最先端モデルと比較して100倍少ない学習データ量でありながら、8500万個のパラメータを持つ既存の最先端モデルを上回る性能を達成しました。アテンション値の詳細な分析により、ハイパーグラフ表現がペアワイズ手法では捉えられない複雑な相互作用を捉え、グラフニューラルネットワーク特有のアテンションの希釈を緩和することが示されました。この結果は、マルチエージェント問題においては、学習データの規模やパラメータ数よりも、適切な帰納バイアスを導入することの方が重要であることを示しています。
マルチエージェント経路計画（MAPF）は、複数のエージェントが衝突を避けながら目的地へ到達する経路を計算する問題であり、エージェント間の強い相互依存性からNP困難な問題として知られています。従来のグラフニューラルネットワークやTransformerを用いた手法は、エージェント間の相互作用をペア単位でモデル化してきましたが、MAPFは全エージェントの結合状態を考慮する必要があるグループ単位の相互作用を本質的に含んでいます。本研究では、高次のグループ相互作用を自然にモデル化できるハイパーグラフを活用した、新しい模倣学習フレームワークであるHMAGATを提案します。HMAGATは、動的に有向ハイパーグラフを構築する生成戦略を備えており、ペア単位の注意機構では捉えきれない複雑な動態を表現することが可能です。実験の結果、HMAGATは既存の学習ベースのソルバーと比較して、約1.2%のパラメータ数と約1%の訓練データ量でありながら、解の質とスケーラビリティの両面で最先端の性能を達成しました。
本セクションでは、高次相互作用を捉えるハイパーグラフの定義、マルチエージェント経路探索（MAPF）の定式化、および提案手法の基礎となる既存手法について述べる。ハイパーグラフは、複数のノードを一つのハイパーエッジで結ぶことができるグラフの拡張であり、各ハイパーエッジは始点となるノード集合と終点となるノード集合のペアとして定義される。MAPFは、グリッドグラフ上で複数のエージェントが衝突を避けながら各々の目的地へ到達する問題であり、解の質は各エージェントの移動時間の総和であるsum-of-costs（SoC）によって評価される。既存手法のMAGATは、通信半径内のエージェント間におけるペアワイズな相互作用をグラフニューラルネットワーク（GNN）で捉えるが、提案手法のHMAGATはGNNをハイパーグラフニューラルネットワーク（HGNN）に置き換えることで、より複雑な相互作用のモデル化を目指している。HMAGATは、CNNによる観測情報のエンコード、HGNNによるメッセージ集約、およびMLPによるデコードで構成され、さらに層の積み重ねや位置情報に基づくエッジ特徴の導入、模倣学習（IL）による学習プロセスが含まれる。エージェントの局所的な観測情報は、障害物、他エージェント、目標方向、および正規化された目的地までのコスト（cost-to-go）の4チャンネルからなる正方形の範囲として定義される。
HMAGATは、マルチエージェント経路探索（MAPF）における複雑な集団的相互作用を捉えるために提案された、注意機構付きハイパーグラフニューラルネットワーク（HGNN）に基づく模倣学習モデルである。従来のグラフニューラルネットワーク（GNN）はエージェント間のペアワイズな相互作用に限定されるため、高密度な環境では無関係なエージェントによって注意スコアが希釈される問題や、集団的な計画問題を捉えきれない限界がある。これに対しHMAGATは、1つのヘッド（対象エージェント）と複数のテイル（周囲のエージェント）を持つ有向ハイパーグラフを採用し、テイルからハイパーエッジ、そしてヘッドへと情報を伝達するメッセージパッシングを通じて、集団的なダイナミクスを明示的にモデル化する。ハイパーグラフの生成戦略には、Lloydのアルゴリズムを用いたVoronoi分割に基づくLloydハイパーグラフ、計算コストを抑えたk-meansハイパーグラフ、および最短経路距離に基づく手法が検討されている。学習は、高性能なMAPFソルバーであるlacam3が生成したエキスパートの軌跡を用い、クロスエントロピー損失関数とAdamW最適化アルゴリズムを使用して行われる。また、模倣学習特有の分布シフトに対処するためのオンデマンドなデータセット集約や、エージェントの局所的な観測可能性に基づいてソフトマックスの温度パラメータを動的に調整する強化学習モジュールも導入されている。
提案手法であるHMAGATは、既存の学習ベースのMAPFソルバーと比較評価されており、特に高密度な環境において高い性能を示します。評価指標には、全エージェントが目標に到達した割合を示す成功率、探索ベースの手法であるlacam3に対する平均相対コスト、およびマップあたりの平均実行時間が用いられています。実験の結果、HMAGATはk-meansやLloyd法を用いたハイパーグラフ生成戦略により、MAGATや小規模なMAPF-GPTモデルを上回る解の品質を達成し、最大規模のMAPF-GPT (85M) とも競争力のある性能を維持しつつ、大幅に高速な実行を実現しています。特に、Dense Warehouseのような困難なシナリオでは、他の手法の成功率が11%未満であるのに対し、HMAGATは75%以上の成功率を記録しました。アブレーション研究では、ハイパーグラフの導入や各最適化モジュールの追加が成功率と解の品質を向上させることが示されていますが、強化学習に基づく温度サンプリングは、成功率と解の品質の間にトレードオフの関係をもたらします。また、GNNを用いたモデルとの比較分析により、HGNNはエージェント密度が高まった際に生じるアテンションの希釈化を防ぎ、ペアワイズの相互作用では捉えきれない複雑なグループ間の相互作用を効果的にモデル化できることが、Shapley値を用いた検証によって示されています。
本研究では、複雑な相互作用を伴うマルチエージェント経路探索（MAPF）問題に対し、高次の相互作用をモデル化する手法として、ハイパーグラフニューラルネットワークに基づくHMAGATを提案した。実験の結果、ペアワイズな相互作用のみを考慮する既存の最先端手法を上回る性能を示し、さらに85倍大きなモデルサイズで100倍のデータ量を用いて学習されたMAPF-GPTと比較しても、優れた性能を達成した。詳細な分析により、ハイパーグラフを用いることで、従来のグラフニューラルネットワークよりも明示的なグループモデリングを通じて集団的な相互作用をより適切に捉えられることが示されている。本手法は、高次の表現学習モデルを用いることで、モデルのサイズやサンプル複雑性を抑えつつ性能を向上させられることを実証した。この結果は、高度に結合した相互作用を持つマルチエージェント問題において、モデルの巨大化とは別に、ハイパーグラフのような適切な帰納バイアスを導入することが有効な戦略であることを示している。
提案手法であるHMAGATモデルの構成および学習手順の詳細は、論文の第3節に記述されています。研究の再現性を確保するため、モデルのアーキテクチャやハイパーパラメータに関する詳細な情報は付録に記載されています。また、実験結果を再現するための手順書、学習済みモデルのチェックポイント、および学習と評価に使用するインスタンスを生成するためのスクリプトを含むコードベースが補足資料として提供されています。