対象は、複数のロボットがそれぞれのゴールへ移動し、障害物や他のロボットとの衝突を避けるマルチエージェント経路探索（MAPF）である。従来の高性能なMAPFプランナの多くは中央集権的に計画するため、エージェント数が数百を超えると計算量が急増し、ノイズや不確実性に応じて数秒から数分ごとに経路を再計算する用途には適しにくい。PRIMALでは、各エージェントが限られた視野から観測し、実行時に共同探索を行わず、オンラインで反応的に行動を選択する。
本研究の中心的な貢献は、著者らの従来の分散型マルチエージェント強化学習を、専門家MAPFプランナのデモンストレーションを用いる模倣学習と統合した点にある。さらに、他エージェントの移動を妨げる行動へのペナルティ、報酬設計、協調が必要な状況を経験させる環境サンプリングを組み合わせ、学習の安定化を図る。学習後の方策は複数のエージェントへコピーでき、チームサイズや世界の大きさが変わっても利用できるとされる。したがって、これは新しい厳密探索アルゴリズムというより、実行時の中央集権的な共同計画を学習済みの分散方策で置き換える提案である。
各エージェントは、障害物、近傍エージェント、近傍エージェントのゴール、自身のゴールに関する情報を視野内のチャネルとして観測する。自身のゴールへの正規化された方向ベクトルと距離も入力し、7個の畳み込み層と最大プーリング層、その後のLSTMからなるネットワークで、上下左右への1セル移動または停止を選ぶ。学習中は壁や他エージェントへの移動などの無効行動をサンプリング対象から除外し、テスト中に無効行動が選ばれた場合は停止として扱う。エージェントは各時刻にランダムな順序で逐次実行され、価値関数によるブートストラップ、方策勾配、探索を促すエントロピー項、専門家デモンストレーションを用いて学習する。全エージェントが同時にゴールへ到達した場合に正の報酬を与え、衝突や他エージェントの妨害には負の報酬を与える。
評価は、正方形グリッド世界の大きさ、障害物密度、エージェントとゴールの配置をランダム化したシミュレーションで行われ、最大1024エージェントのチームを含む。PRIMALの成功率を、既存の代表的なMAPFプランナおよび速度ベースの衝突回避手法と比較し、本文抜粋では経路長と計画時間も調べたと説明されている。さらに、工場を模したモックアップで、実世界のロボットとシミュレーションロボットを組み合わせたハイブリッド検証を行っている。ただし、提示された抜粋には完全なデータセット定義、すべてのベースライン名、全条件の数値表、試行回数、ハイブリッド実験の詳細なハードウェア仕様は含まれていない。
障害物のない160×160の世界では、中央集権的プランナは共同状態空間の急増により100エージェントを超えると苦戦する一方、PRIMALは1024エージェントまでほぼ完全な成功率で扱った。PRIMALの成功率は他のプランナより早く低下し始めるが、512エージェントの条件でも60％を超え、他手法は低い性能にとどまった。障害物が非常に密な小規模世界では、すべての手法が扱えるのは最大64エージェントであり、PRIMALは8エージェントを超えると苦戦したのに対し、ODrM*は64エージェントまで扱えた。この結果は、局所観測に基づく分散的な反応と大規模実行性が、開けた環境では有利でも、激しい混雑では頑健性とトレードオフになることを示す。抜粋だけから、すべての障害物密度、地図構造、ロボット力学、ノイズモデルでPRIMALが優れるとは結論できない。
MAPFは、航空ロボット群、倉庫自動化、工場など、多数のロボットを運用するシステムの基盤要素である。中央集権型の探索は高品質な解を求められる一方、エージェント数に伴って共同状態空間が増大するため、大規模化が難しい。分離型、速度ベース、優先度ベースの手法は探索を簡略化できるが、衝突、デッドロック、ライブロック、通信や全体情報への依存などの問題を持ちうる。
想定されるのは、エージェントが静的障害物と他エージェントを避けながら割り当てられたゴールへ進む、部分観測のグリッド世界である。ノイズや不確実性がある実環境ではオンライン再計画が必要だが、1回の中央集権的計画に数秒から数分を要すると頻繁な再計画は困難になる。個別の最短経路だけでは、エージェント同士の相互ブロックや循環的な待機を解決できない。提示された抜粋は、成功率、経路長、メイクスパン、最適性を統合した厳密な目的関数や、その保証を確立していない。
行動空間は、上下左右のいずれかへ1セル移動するか、その場に留まるかで構成される。実際のブロッキングには、他エージェントのゴール到達を妨げる場合だけでなく、到達を大きく遅らせる場合も含まれ、ペナルティは実験上−2とされた。全エージェントが同時にゴールへ到達した場合の報酬は＋20で、衝突にも−2の報酬が与えられる。学習環境の大きさは10、40、70から選ばれ、10の世界が2倍選ばれやすく、障害物密度は0〜50％の三角分布から選ばれてピークは33％に置かれる。割引率は0.95、エピソード長は256、バッチサイズは128であり、テスト時の大規模世界ではゴール距離を75で上限化すると成功率が大幅に改善した。
アブレーションでは、環境サンプリング、ブロッキングペナルティ、模倣学習をそれぞれ除いた条件を調べている。抜粋によれば、これらのいずれかを除くと学習が不安定になって学習できないか、元の方法より悪い方策へ収束した。ランダム化された評価には80×80および160×160の大規模世界が含まれ、工場モックアップでは実ロボットとシミュレーションロボットを組み合わせた。提示資料は、完全なエピソード数、乱数種、信頼区間、ハードウェア構成、実機ロボットの詳細な設定を示していない。
障害物のない大規模世界ではPRIMALが他のプランナを大きく上回り、低障害密度の世界でも僅かに上回った。高障害密度の世界では強く下回り、8エージェントを超えると苦戦したため、大規模性の利点は環境によらず一様ではない。本文抜粋は、1ステップ・1エージェントあたりの将来計画時間が標準GPUで0.1秒未満、CPUで0.2秒未満だったと報告しているが、測定手順の全詳細は示していない。512エージェントでの成功率は60％超、障害物のない世界での1024エージェントの結果はほぼ完全と記述されているものの、全条件の基礎数値は提示されていない。
PRIMALは、強化学習と模倣学習を、報酬 shaping、ブロッキングペナルティ、環境サンプリングと組み合わせ、部分観測下で暗黙の協調を行う分散MAPF方策を学習できることを示した。学習済み方策はオンラインに反応し、チームサイズに応じて複製できるため、大規模で開けた環境では中央集権的な共同計画に代わる実行時の選択肢となる可能性がある。提示された証拠は、障害物のない、または障害物の少ない環境でのスケーラビリティと成功率を最も強く支持しており、普遍的な性能や厳密な解の保証を示すものではない。
限られた視野では、長い通路の行き止まりのような遠方のボトルネックや、ペナルティの原因を観測できない場合があり、協調判断を難しくする。障害物が密集し、エージェント同士の相互作用が頻繁になると局所方策の失敗が現れ、未知の動的障害物、センサノイズ、分布の変化に対する定量的な頑健性は抜粋で確立されていない。最適性、完全性、広範なシミュレーションから実機への移行保証も示されていない。著者らは今後、PRIMALを完全なプランナと組み合わせ、高速な分散計画と困難な状況への対応を両立させることを検討している。
多数のロボットで頻繁な再計画が必要な運用では、同じ方策を複数エージェントへ適用することで、中央集権的な共同探索を繰り返すコストを避けられる可能性がある。専門家のデモンストレーションと強化学習を組み合わせ、部分観測下で暗黙の協調を学習させる点は、MAPFにおける学習型分散実行の一つの道筋を示す。開けた環境と密集環境の対照的な結果は、スケーラビリティや局所反応だけでは混雑の難しさを解消できないことも明確にする。したがってPRIMALは、すべてのMAPFプランナを置き換える完成手法というより、他の計画器と併用しうる学習型コンポーネントとして理解するのが適切である。
大規模な分散ロボット実行、部分観測下のオンライン計画、マルチエージェント強化学習、専門家プランナからの模倣学習に関心を持つMAPFおよびMAPD研究者に適している。特に、チームサイズをまたいだ方策の再利用、報酬設計、環境サンプリング、協調機構のアブレーションを研究したい読者に有用である。厳密な最適性、完全性、密集環境での強い性能保証を必要とする読者は、提示された限定的な結果だけで判断せず、原論文全体を確認すべきである。