複数のエージェントが衝突を避けながら各々の目標地点へ到達するマルチエージェント経路探索（MAPF）を対象とする。従来のヒューリスティック探索は、中央集権的な制御が必要なため、計算時間の制約下で大規模なエージェントを扱う際のスケーラビリティに課題がある。一方、機械学習を用いた分散型の方策はスケーラビリティに優れる可能性があるが、単一のタイムステップのみを予測する局所的な計画に留まるため、長期的な計画ができず、衝突やデッドロックが発生しやすい。
学習済みモデルの構造を変更せずに適用できる、モデルに依存しない改善フレームワークを提案する。具体的には、学習済み方策の出力確率分布を優先順位や行動順序として利用する衝突回避手法（CS-PIBT）や、学習済み方策を構成生成器として組み込む探索手法（LaCAM）との統合を実現した。これにより、機械学習ベースの手法として、エージェント密度が20%に達する高混雑シナリオにおいてもスケーラビリティを達成した。
提案手法は、学習済み方策が予測する行動確率分布を、エージェントの優先順位や行動の選択順序として利用する。まず、衝突が発生しそうな場合に、エージェントを停止させるのではなく、PIBT（優先度に基づく逐次的な行動決定）を用いて、確率の高い行動から順に試行することで衝突を回避する衝突シールド（CS-PIBT）を構成する。次に、このCS-PIBTをLaCAMのフレームワークに組み込み、バックトラッキングを伴う探索を行うことで、全期間の計画と理論的な完全性を確保する。さらに、ヒューリスティック値のタイブレークに方策の確率を用いる手法や、ヒューリスティック値に方策の確率に基づく補正項を加算して探索のバランスを制御する手法を導入する。
最先端モデルであるMAGATおよび、通信構造を持たない単純な学習済みポリシーを用いて評価を行った。CS-PIBTの適用により、既存の衝突回避手法（CS-Naive）と比較して成功率とスケーラビリティが向上し、特に確率的なサンプリングを用いることで性能が改善することを示した。LaCAMとの統合により、単純なポリシーでも最大400エージェント規模まで成功率を向上させた。また、経路コストの観点では、方策の好みをタイブレークに利用する手法（Otie）が、LaCAM単体と比較してコストを改善する結果を示した。
強力な2Dヒューリスティックが存在する環境では、古典的な探索手法が機械学習ベースの手法を上回る可能性がある。また、LaCAMはヒューリスティックに誤差が含まれる場合、成功率は維持できても解のコストが極端に増大するという脆さを持つ。今後の課題は、不完全なヒューリスティックを用いる状況下において、機械学習手法がどのように探索手法を補完、あるいは凌駕できるかを明らかにすることである。
マルチエージェント経路探索（MAPF）において、従来の古典的な手法はヒューリスティック探索を用いて数百規模のエージェントの衝突回避経路を解くが、中央集権的な制御を必要とするため、制限時間内でのスケーラビリティに課題がある。一方、各エージェントの方策を学習する機械学習アプローチは、分散型システムへの適用や高いスケーラビリティが期待されるが、既存の手法は単一のタイムステップのみを計画する「局所的」な方策に留まっており、成功率や拡張性が低い。本研究では、機械学習が生成する出力の確率分布に対してヒューリスティック探索を適用することで、デッドロックを解消し、目標到達までの全期間を考慮した計画を可能にする手法を提案する。この手法はモデルに依存しない複数の形式で提供され、エージェント密度が20%に達するような高混雑シナリオにおいても、機械学習ベースの手法として初めて高いスケーラビリティと成功率を達成した。
マルチエージェント経路探索（MAPF）において、従来のヒューリスティック探索手法は計算時間と解の質のトレードオフや中央集権的な計画が必要という課題があります。一方、機械学習を用いた手法は分散型でスケーラビリティに優れるものの、長期的な計画や衝突・デッドロックの回避において精度が不足しています。本研究では、学習済みの方策が衝突を引き起こす際に、エージェントを停止させるのではなく、PIBTというヒューリスティック探索手法を「スマートな衝突シールド」として利用することで、追加の学習なしに成功率とスケーラビリティを向上させる手法を提案します。さらに、学習済みの方策とLaCAMという別のヒューリスティック探索手法を密接に統合する、ニューラルネットワークに依存しないフレームワークを構築し、長期的な計画における理論的な完全性と性能向上を実現しました。実験の結果、既存の学習済みモデルであるMAGATに対し、提案するPIBTベースの衝突シールドを適用することで、エージェント数が増加しても高い成功率を維持できることが示されています。また、強力な2Dヒューリスティックが存在する環境では古典的な探索手法が優位であるものの、不完全なヒューリスティックを用いる状況下では、機械学習手法が特定の探索手法を上回る可能性があることも明らかにしています。
マルチエージェント経路計画（MAPF）には、最適化、ヒューリスティック探索、機械学習の各アプローチが存在する。本研究が対象とする単発の2D MAPFは、各エージェントが障害物や他のエージェントとの衝突を避けつつ目標地点に到達して待機することを目指し、全エージェントの総移動時間であるflowtimeを最小化する問題である。ヒューリスティック探索では、Conflict-Based Searchのように最適性を保証する手法がある一方、エージェント数の増加に伴い計算コストが指数関数的に増大する課題がある。これに対し、PIBTは優先度に基づき各エージェントの次の一手を逐次的に決定する貪欲な手法であり、逆方向ダイクストラ法を用いて目標地点からの最適コストを推定することで高いスケーラビリティを実現しているが、解の品質に課題がある。LaCAMは、PIBTを構成生成器として深さ優先探索に組み込み、制約を遅延的に追加することで、PIBTでは回避困難な局所解を脱出可能にし、理論的な完全性と高い成功率を両立させている。機械学習アプローチでは、局所的な観測情報から行動確率分布を学習する手法が提案されており、衝突を回避するために学習された行動を修正する衝突シールドなどの仕組みが用いられるが、エージェントが目標地点で待機する際にデッドロックが発生しやすいという共通の課題がある。
学習された1ステップのMAPF（マルチエージェント経路計画）方策は、将来の計画能力や理論的な完全性の保証を欠くため、エージェントの混雑時にデッドロックやライブロックに陥りやすい課題がある。従来の衝突回避手法は、衝突が予測されるエージェントを単に待機させることでデッドロックを招くが、提案するCS-PIBTは、エージェントの行動確率分布を優先順位に基づいた行動順序に変換してPIBTに適用することで、次善の策を考慮した衝突回避を実現し、待機を抑制する。このCS-PIBTを構成生成器としてLaCAMフレームワークに組み込むことで、バックトラッキングによる完全性を維持したまま、学習済み方策の利点を活かしたフルホライゾン（全期間）の計画が可能となる。さらに、学習済み方策とヒューリスティック関数を組み合わせる手法として、ヒューリスティック値のタイブレークに方策の確率を用いる方法や、両者の値を加算して評価する手法が提案されている。具体的には、ヒューリスティック値に、学習済み方策の確率の補数に重みRを乗じた値を加算したものを最小化する手法があり、Rの値によってヒューリスティック重視から学習済み方策重視まで挙動を制御できる。
本研究では、学習された局所的なマルチエージェント経路計画（MAPF）ポリシーの性能を、ヒューリスティック探索を用いて向上させる手法を評価しています。提案手法であるCS-PIBTは、従来の単純な衝突回避手法と比較して、エージェントが密集した状況や目標地点で停止しているエージェントを通り抜ける際の堅牢性が高く、最先端モデルであるMAGATおよび自作の単純なポリシーの両方において、エージェント数の増加に対するスケーラビリティを大幅に改善します。CS-PIBTにおいて、行動の優先順位付けに確率的なサンプリングを用いることは、決定論的な順序付けよりもライブロックを回避する上で極めて重要です。また、学習済みポリシーをLaCAMのフレームワークに統合することで、デッドロックを回避し、単純なポリシーであっても数百エージェント規模まで成功率を向上させることが可能です。さらに、ポリシーの行動確率とヒューリスティック情報を組み合わせる際、ポリシーの好みをタイブレークに利用する手法が、経路コストの削減において最も優れた結果を示しました。一方で、ヒューリスティックに誤差が含まれる場合、LaCAMは成功率は維持できるものの、解のコストが極端に増大する脆さを持つことも明らかにされています。
本研究では、学習された局所的なマルチエージェント経路計画（MAPF）のポリシーを、ヒューリスティック探索を用いて改善する、モデルに依存しない複数の手法を提案した。まず、PIBTを用いた衝突回避シールドであるCS-PIBTを導入し、学習済みモデルが出力する1ステップの確率分布を入力として、衝突のない有効なステップを出力することで、モデル自体を変更することなくスケーラビリティと成功率を向上させた。次に、学習済みモデルをLaCAMと組み合わせることで、理論的な完全性を備えた全ホライゾン計画を可能にし、実用面での成功率とスケーラビリティをさらに高める手法を示した。先行研究との比較において、探索を併用した学習済みMAPFポリシーが、古典的なヒューリスティック探索手法と同等の高いエージェント密度（20%以上）においてもスケールできることを初めて示した。