共有環境内で複数のエージェントが衝突を回避しながら各々の目標へ到達する経路を求めるマルチエージェント経路探索（MAPF）を対象とする。この問題は最適解の算出がNP困難であり、従来の学習ベースの手法では、エージェント間の通信モジュールや単一エージェント用の計画ルーチンを併用する必要があるという困難さがあった。
通信や追加の意思決定支援ルーチンに頼らず、エキスパートデータからの模倣学習のみで高性能な分散型ポリシーを実現した点に新規性がある。また、10億件規模の観測と行動のペアを含む、MAPFにおける最大級の学習用データセットを構築した。これにより、学習時に含まれていない未知のマップに対しても、追加学習なしで対応できるゼロショット学習能力を持つ基盤モデルとしての可能性を示した。
エキスパートソルバーを用いて生成した成功事例を、エージェントの局所的な観測とそれに対応する行動のペアとして構成し、Transformerベースの非自己回帰型ニューラルネットワークで学習する。観測情報は、エージェントを中心とした11×11の範囲内の各セルにおける目標までのコスト、および周囲に存在する最大13名のエージェントに関する情報（現在位置、目標位置、過去の行動履歴、次の一手となる貪欲な行動）を、計256個のトークンに変換して入力する。学習にはクロスエントロピー損失を用い、推論時にはモデルが出力する確率分布に基づいたサンプリングによって行動を決定する。
ランダムなマップ、迷路状のマップ、倉庫、都市タイルといった多様な環境を用い、パラメータ数が異なる3つのモデル（2M, 6M, 85M）を評価した。既存の学習型ソルバーであるDCCおよびSCRIMPと比較した結果、ランダムおよび迷路状のマップにおいて、すべてのMAPF-GPTはDCCとSCRIMPを上回る成功率と、エキスパートの解に対する低いコスト比（Sum-of-Costs Ratio）を達成した。また、実行時間の検証では、128名を超える大規模な設定において、MAPF-GPT-85MはDCCやSCRIMPよりも高速であり、エージェント数の増加に対して計算時間が線形にスケールすることが示された。
倉庫環境においてエージェント数が128名を超える場合、SCRIMPの方が優れた性能を示すという限界がある。アブレーション研究により、目標位置やコスト情報、貪欲な行動の情報が欠落すると性能が低下することが確認された一方で、行動履歴の情報を除外した方が特定のマップ設定で性能が向上するというトレードオフも確認されている。今後の課題として、Lifelong MAPF（継続的なタスク）におけるファインチューニングによるさらなる性能向上などが挙げられる。
マルチエージェント経路探索（MAPF）は、共有環境内で複数のエージェントが衝突を回避する経路を見つける問題であり、その最適解の算出はNP困難です。本研究では、エキスパートによるMAPF解の膨大なデータセットとTransformerベースのニューラルネットワークを用いた模倣学習により、MAPFの基盤モデルであるMAPF-GPTを提案します。この手法は、単一エージェントの計画や通信、追加のヒューリスティックを用いることなく、エージェントの行動を生成できます。実験の結果、MAPF-GPTは学習データに含まれていない未知の問題に対してもゼロショット学習能力を示し、多様な問題設定において既存の最先端の学習型MAPFソルバーを上回る性能を達成しました。また、推論時における計算効率の高さも示されています。
マルチエージェント経路探索（MAPF）は、共有環境内の複数のエージェントが衝突を避けながら、各々の目標に可能な限り早く到達する経路を求めるNP困難な組合せ最適化問題である。本研究では、追加の計画ルーチンやエージェント間通信を用いず、エキスパートデータに対する大規模な教師あり学習のみで動作するMAPF-GPTを提案する。MAPF-GPTは、エージェントの観測情報と実行する行動を記述するための独自のトークン化手法を設計し、既存の最先端ソルバーを用いて生成した10億件の観測と行動のペアを含む大規模なデータセットを用いて学習を行う。モデルのアーキテクチャには、観測情報から正しい行動を予測する、Transformerベースの非自己回帰型ニューラルネットワークを採用している。実験の結果、MAPF-GPTは既存の分散型学習ベースのソルバーを上回る性能を示し、特に学習時とは異なる環境での評価において顕著な成果を上げた。また、未知のマップに対するゼロショット学習能力や、Lifelong MAPFへの適用、および実行時の効率性の高さも示されている。
マルチエージェント経路探索（MAPF）の手法には、高速だがコストの保証がないルールベース、問題を最小フローや充足可能性問題（SAT）へ変換して既存のソルバーを利用する帰着ベース、最適性や近似保証を持つグラフ探索ベース、および優先度付き計画のような簡略化された探索ベースが存在する。近年は、分散型学習を用いるPRIMALや、強化学習と通信モジュールを組み合わせたSCRIMP、DCC、Followerなどの学習ベースの手法も登場しているが、本研究はこれらとは異なり、エキスパートデータからの模倣学習のみに依存する。オフライン強化学習では、環境との相互作用なしに収集済みデータから方策を構築する手法があり、報酬を条件としてエキスパートの振る舞いをモデル化するDecision Transformer（DT）や、そのマルチエージェント版であるMADTが存在する。マルチエージェント模倣学習（MAIL）は、報酬関数の知識なしにエキスパートのデモンストレーションから学習する手法であり、交通制御などの分野で活用されている。しかし、複雑な方策や大規模なエキスパート軌跡データの不足により、単一の基盤モデルの提案には至っていない。本研究は、MAPFをTransformer基盤モデルを調査するためのテストベッドとして活用し、大規模な学習用データセットを提供するとともに、オンライン学習を必要としない模倣学習の可能性を探る。
マルチエージェント経路探索（MAPF）は、無向グラフ上のn個のエージェントに対し、各エージェントの開始地点から目標地点までの衝突のない経路集合を求める問題である。衝突とは、同一時刻に同じ頂点を占有すること、または逆方向に同じエッジを通過することを指し、目的関数には全エージェントの移動コストの総和であるSum-of-Costsや、全エージェントが目標に到達するまでの最大時刻であるMakespanが用いられる。本研究では、エージェントが目標到達後もその場に留まり続けるという設定を扱う。また、MAPFは逐次的意思決定問題としても定義でき、各エージェントが局所的な観測情報に基づき行動を選択する分散型のポリシーを構築することが可能である。この際、エージェントの過去の観測と行動の履歴から環境の状態を近似し、同質かつ協力的なエージェント群を制御するための単一の共通ポリシーを学習する。学習手法としては模倣学習が用いられ、既存のソルバーによって生成されたエキスパートの軌跡データを用いて、行動空間が離散的な場合にはクロスエントロピー損失関数を最小化するようにポリシーのパラメータを最適化する。
MAPF-GPTは、エキスパートによるマルチエージェント経路探索（MAPF）の解法を模倣学習する手法であり、シナリオ作成、正解データの生成、トークン化、学習ループの4段階で構成されます。学習用データセットの作成にはPOGEMAを用い、迷路状のマップ1万個とランダムなマップ2500個から、計375万件のインスタンスを生成しています。マップサイズは17×17から21×21の範囲で、エージェント数は16、24、または32個です。分散型ポリシーの学習を目的としているため、マップの大きさよりも、自由空間とエージェントが占有する空間の比率である密度を重視しており、協調が必要な困難な状況を作るために中程度からかなり高い密度を設定しています。正解データの生成には、時間予算内で解を高速に探索・改善するLaCAMの変種を使用し、1インスタンスあたり10秒の制限を設けて個々の計画を取得しています。得られた計画から各エージェントの局所的な観測と行動のペアを再構成し、後処理を経て学習に用います。
POGEMA Mapsの正解軌跡を用いて、10億件の観測と行動のペアを含む大規模なマルチエージェント経路探索（MAPF）のシナリオデータセットを構築しています。
実験に使用された問題インスタンスの構成について述べられています。評価では、10秒以内に解を生成する設定において、2500個のインスタンスが使用されました。データセットの構築にあたっては、エージェントの局所的な観測情報を生成し、そこから同一の観測内容を持つものや、目標地点に留まっている状態のフレームを除外するフィルタリング処理が行われています。
MAPF-GPTは、エキスパートソルバーであるLaCAMが生成した経路データを模倣学習することで、大規模なマルチエージェント経路探索を実現する手法である。学習データは、迷路状のマップから9億件、ランダムなマップから1億件の計10億件の観測・行動ペアで構成され、目標地点での待機行動の割合が高すぎる不均衡を解消するために、目標地点での待機行動の80%を削除している。観測情報は、エージェントを中心とした11×11の範囲内の正規化された目標までの最短経路コストと、周囲最大13名のエージェントの現在位置、目標位置、過去の行動履歴、および貪欲な行動をエンコードした計256トークンのシーケンスとして構成される。モデルのバックボーンにはデコーダーのみのTransformerを採用しており、最大85Mのパラメータを持つモデルを、クロスエントロピー損失を用いてAdamWにより学習する。推論時には、決定論的な最大確率の選択ではなく、分散型環境に適した多項分布サンプリングを用いて行動を選択する。
MAPF-GPTの性能評価では、パラメータ数が異なる3つのモデル（2M, 6M, 85M）を、既存の学習型ソルバーであるDCCおよびSCRIMP、そしてエキスパートとして用いたLaCAMと比較しています。RandomおよびMazesマップにおいて、すべてのMAPF-GPTはDCCとSCRIMPを上回る成功率を示し、コストの総和（SoC）についてもLaCAMに対する比率が低く、パラメータ数が多いほど性能が向上する傾向が確認されました。一方で、Warehouseマップではエージェント数が128人を超えると、価値に基づくタイブレーク機構を持つSCRIMPが最も優れた性能を示しました。アブレーション研究では、貪欲な行動やコスト・トゥ・ゴー情報の欠如が性能を低下させる一方、行動履歴の欠如がMazesやWarehouseにおいて性能を向上させるという結果が得られています。また、Lifelong MAPF設定においても、ゼロショットでの適用が可能であり、追加学習によってスループットが向上することが示されました。実行時間に関しては、MAPF-GPTはエージェント数に対して線形にスケールし、128人を超える大規模な設定では、最大モデルであるMAPF-GPT-85MであってもDCCやSCRIMPより高速に動作します。
本研究では、マルチエージェント経路探索（MAPF）問題を逐次的な意思決定タスクとして捉え、エキスパートのデータを用いた教師あり模倣学習に基づく手法であるMAPF-GPTを提案しています。この手法は、エキスパートによるMAPFの解を観測と行動のペアに変換してトークン化し、異なるパラメータ数を持つ複数のTransformerモデルを学習させることで、個別のエージェントの方策を導出します。実験の結果、2M程度の比較的控えめなパラメータ数であっても、MAPF-GPTは広範な設定において既存の学習可能なMAPF手法を大幅に上回る性能を示しました。これにより、模倣学習のみを用いて強力な学習型MAPFソルバーを構築できることが実証されました。