複数のエージェントが衝突を回避しながら始点から終点へ移動する経路を、総移動時間（SoC）を最適化するように見つけるマルチエージェント経路探索（MAPF）問題を対象とする。従来の学習ベースの手法は、各エージェントの局所的な視野情報に基づく分散型アプローチが主流であった。そのため、エージェント数やマップサイズの変動に合わせて特徴量を設計する必要があり、中央集権的な方策を構築することが困難であった。
個々のエージェントの特徴量に依存するのではなく、マップのグリッドセルに対して行動を生成する、初の中央集権的な学習ベースのMAPFソルバーを提案する。エージェントごとの特徴量設計の課題を克服し、エッジ重みの設計思想をニューラルネットワークに統合した点が新規性である。
MAPFの解を、各時刻において各グリッドセルが5つの移動方向（上下左右および待機）のうち1つを選択する有向グラフの連続として捉える。モデルのバックボーンにはU-Netを採用し、エンコーダで特徴マップの解像度を下げつつチャネル数を増やし、デコーダで転置畳み込みを用いて解像度を復元することで、異なるサイズのマップへの適応を可能にしている。入力には、通行不能なセル情報、エージェントの現在地と目的地、目的地までの最短経路コスト、および目的地へ近づく方向を示すコストの勾配の5種類を用いる。出力は各グリッドセルにおける5つのアクションの確率分布であり、推論時には現在の状態から次のアクションを繰り返し予測することで軌道を生成する。
POGEMAベンチマークを用い、LaCAM-v1によって生成された180種類の迷路マップと、エージェント数16から128までの計127通りのシナリオを用いて教師あり学習を行った。評価指標として、解の質（SoC/スループット）、成功率（CSR）、スケーラビリティ、協調性、最短経路探索能力、および未知環境への適応力（OOD）を用いた。実験の結果、実行時間がエージェント数ではなくマップサイズに依存する特性により、スケーラビリティにおいて他の学習ベースの手法を上回った。また、学習に含まれないLifelong MAPF（LMAPF）タスクに対しても、最短経路探索能力や協調性、スケーラビリティにおいて性能を示すゼロショット汎化性能を確認した。
解の質（SoCやスループット）に関しては、学習データであるLaCAM-v1の特性を模倣することを優先しているため、検索ベースの手法や一部の学習ベースの手法に劣る傾向がある。また、教師あり学習のみでは不十分な場合があり、強化学習の併用が示唆されている。今後の課題として、より高品質なデータを収集して基盤モデルとして訓練することや、タスク固有のコスト関数を用いた強化学習によるファインチューニングを行い、実世界のアプリケーションにおける解の質と成功率を向上させることが挙げられる。
RAILGUNは、エージェント数やマップサイズが変動するマルチエージェント経路探索（MAPF）問題に対し、従来の分散型アプローチではなく、マップ全体を対象とする初の集中型学習ベースのポリシーである。CNN（畳み込みニューラルネットワーク）を用いたマップベースのアーキテクチャを採用することで、異なるマップ形状や任意の数のエージェントに対しても汎用的に対応できる。学習手法としては、ルールベースの手法から収集した軌跡データを用いた教師あり学習を用いている。実験の結果、RAILGUNは多くのベースライン手法を上回る性能を示し、訓練データに含まれていない異なるタスク、マップ、エージェント数に対しても優れたゼロショット汎化性能を発揮することが確認された。
マルチエージェント経路探索（MAPF）は、複数のエージェントが衝突を回避しながら始点から終点へ移動する経路を、指定されたコスト関数を最適化しつつ見つけるNP困難な問題であり、倉庫自動化などの分野に応用されている。既存の学習ベースの手法は、各エージェントが自身の視野情報に基づいて行動を決定する分散型アプローチが主流であり、エージェント数やマップサイズの変動には対応できるものの、個々のエージェントの特徴に基づいた行動生成に焦点を当てている。これに対し、本論文が提案するRAILGUNは、個々のエージェントではなくマップのグリッドセルに対して行動を生成する、初の学習ベースの中央集権型MAPFアルゴリズムである。各タイムステップにおいて、各ノードがちょうど1つの出力を有する有向グラフを生成する設計を採用することで、マップ上のエージェント数に依存しない制御を実現している。また、モデルのバックボーンにU-Netを用いることで、入力特徴量と同じ次元の出力を得られるようにし、異なるサイズのマップにも適応可能としている。実験では、特定のマップタイプで学習したモデルが未知のマップやシナリオへ効果的に汎化することを示し、POGEMAベンチマークにおいて多くのベースライン手法を上回る性能を達成している。
マルチエージェント経路探索（MAPF）問題は、エージェントの集合、頂点と単位コストの辺で構成される無向グラフ、および各エージェントの開始地点と目標地点として定義される。本研究では、上下左右の4方向に接続された2Dグリッドマップを対象とし、その場に留まる「待機」アクションを自己ループ辺として扱う。各エージェントは、開始地点から目標地点まで、衝突を回避しながら各ステップで1単位の時間を用いて移動または待機を行う。衝突には、同じ時刻に複数のエージェントが同一の頂点を占有する頂点衝突と、同じ辺を互いに逆方向に同時に通過する辺衝突の2種類が存在する。本問題の目的は、すべてのエージェントが開始地点から出発して目標地点に到達し、かつ衝突が発生しない経路集合を、総移動時間（SoC: flowtime）を最小化するように見つけることである。
マルチエージェント経路探索（MAPF）には、各エージェントの経路を個別に計画する分離型、全エージェントの計画を同時に行う結合型、および衝突時のみ協調する動的結合型の戦略が存在する。Conflict-Based Search（CBS）に代表される探索ベースの手法は、最適性を保証できる一方で、問題規模の拡大に伴う探索空間の次元爆発により、制限時間内に解を生成することが困難になる課題がある。これに対し、学習ベースの手法は大量のデータから学習することで、経路コストの低減とスケーラビリティのトレードオフを解決できる可能性がある。既存の学習ベースの手法には、エッジの重みを予測してコストとして利用する段階的なアプローチや、エージェント自身に焦点を当てた分散型のアプローチが存在するが、前者は最適化の探索空間を肥大化させる恐れがあり、後者はエージェント数やマップサイズが変化する場合に中央集権的な方策を設計することが困難である。提案手法であるRAILGUNは、エージェントの特徴量設計の課題を克服し、エッジ重みの設計思想をニューラルネットワークベースのソルバーに統合した、初の中央集権的なMAPFソルバーである。
RAILGUNは、エージェントごとの特徴量を用いる従来の集中型手法では、マップサイズやエージェント数に応じて入力次元が膨大になり、異なるマップへの汎用性が失われる課題を解決する手法である。本手法は、有効なマルチエージェント経路探索の解を、各時刻において各グリッドセルに最大1つのエージェントが存在し、各エージェントが5つの移動方向のうち1つを選択する「特殊なグラフ」の連続として捉え、このグラフを生成する問題に置き換えている。モデルのアーキテクチャにはU-Netを採用しており、エンコーダで特徴マップの解像度を下げつつチャネル数を増やし、デコーダで転置畳み込みを用いて解像度を復元することで、推論時に異なるサイズのマップへの対応を可能にしている。入力特徴量には、通行不能なセルを示すマップ情報、エージェントのインデックスで表現された現在地と目的地、事前計算された目的地までの最短経路コスト、および目的地へ近づく方向を示すコストの勾配の5種類を用い、出力は各グリッドセルにおける5つのアクションの確率分布となる。このモデルは約3000万個のパラメータを持ち、推論時には現在の状態から次のアクションを繰り返し予測することで軌道を生成する。
POGEMAベンチマークを用い、LaCAM-v1によって生成された180種類の迷路マップと、エージェント数16から128までの計127通りのシナリオを学習データとして、クロスエントロピー誤差を用いた教師あり学習を行っています。評価指標には、解の質や成功率を測るPerformance、未知の環境への適応力を示すOOD、協力性能を示すCooperation、エージェント数増加に伴う実行時間の増大度を示すScalability、無効な行動の頻度を示すCoordination、および単一エージェントの最短経路探索能力を示すPathfindingの6つを用いています。実験の結果、RAILGUNはScalabilityにおいて、各タイムステップで特定の有向グラフを生成することで、理論上、実行時間がエージェント数ではなくマップサイズのみに依存するため、他の学習ベースの手法を上回る性能を示しました。また、学習時に含まれていないLMAPFタスクに対しても、Pathfinding、Coordination、Scalabilityにおいて高い性能を示すことで、強力なゼロショット汎化性能を示しています。一方で、解の質（SoCやスループット）に関しては、学習データであるLaCAM-v1の特性を模倣することを優先しているため、検索ベースの手法や一部の学習ベースの手法（SCRIMPなど）に劣る傾向があります。
本論文では、マルチエージェント経路探索（MAPF）問題に対する初の集中学習ベースの手法として、RAILGUNを提案している。個々のエージェントの行動を予測する代わりに、マップの各グリッドセルにおけるエッジの方向を予測する手法を採用することで、入力特徴量の次元の変化に伴う困難を克服した。これにより、任意のマップサイズやエージェント数に対応可能なCNNベースのアーキテクチャを実現している。POGEMAベンチマークを用いた実験では、6つの評価指標すべてにおいて高い性能を示し、未知のマップや異なるエージェント数、さらにはLMAPF問題といった異なるタスクに対しても優れた汎化性能を発揮した。今後の展望として、より高品質なデータを収集してRAILGUNを基盤モデルとして訓練することや、タスク固有のコスト関数を用いた強化学習によるファインチューニングを行い、実世界のアプリケーションにおける解の質と成功率を向上させることを計画している。