対象は、複数のエージェントをグラフ上で移動させ、それぞれの開始地点から個別の目標地点へ、衝突なく到達させるマルチエージェント経路探索（MAPF）である。エージェントは離散時間で隣接地点へ移動するか待機し、他のエージェントとの相互作用を考慮して行動する必要がある。エージェント数や環境の複雑さが増すとMAPFは難しくなり、学習方策が複数エージェントを含むデッドロックに陥ることが問題になる。
本研究の中心的な新規性は、LLMを各エージェントの低レベル経路を毎時刻直接計画するものではなく、学習ベースMAPFモデルの実行を監視し介入する高レベル機構として使う点にある。LLMDRは、LLMによるデッドロック検出と解決戦略の生成を、学習モデルおよび優先度付き計画と組み合わせる。LLMが提案するエージェントの優先度や行動方針をPIBTに渡し、PIBTが衝突のない1ステップの行動へ変換することで、LLMに詳細な低レベル空間計画を委ねない設計を採用する。複数の学習ベースモデル、マップ、エージェント数を用いた評価により、この介入枠組みの適用可能性を検討した。
LLMDRは、基礎モデルが生成したエージェントの行動ログを一定長の検出窓でLLMに入力し、デッドロックの有無を分類する。提示された検出規則では、動かない状態や同じ付近を巡回する状態はデッドロック候補とされる一方、常に到達済みである状態、到達後に停止している状態、一貫して移動している状態はデッドロックとみなされない。検出されたエージェントは、互いにマンハッタン距離2以内であればグループ化され、近くにいる到達済みエージェントが同じグループへ含められる場合もある。独立したデッドロック、またはグループ内に目標までの距離が8より大きいエージェントがある場合にはリーダー方式を使い、グループ内の全エージェントが目標から8未満の距離にあり、デッドロックを繰り返しそうな場合には放射方式を使う。生成された優先度と行動の好みはPIBTに組み込まれ、PIBTは予約と再帰的な競合処理によって、指定された実行計画長の間、衝突を避ける行動を生成する。その区間が終わると、デッドロックが残っていても次の検出ループへ進む。
評価には、random32、random64、den312d、warehouseという4種類の標準MAPFベンチマークマップが使われた。エージェント数は4、8、16、32、64とし、最大時間ステップはrandom32、random64、den312dでは256、warehouseでは512に設定された。指標は、最大時間内に解決できたインスタンスの割合である成功率と、解決までに要した時間ステップの平均である平均エピソード長である。LLMDRはDCC、DHC、EPHの学習モデルと組み合わせて評価され、基礎言語モデルとしてgpt-3.5-turboとgpt-4oが試された。第1実験は300個のテストインスタンス、第2および第3実験はそれぞれ100個であり、ハイパーパラメータ分析を除く既定設定では検出窓長を4、実行計画長を16とした。
提示されたwarehouseの結果では、64エージェントの場合、DHCにLLMDRを加えると成功率が1%から83%へ、DCCでは14%から74%へ、EPHの元の推論戦略とアンサンブルを除いた基礎版では6%から68%へ上昇した。4エージェントの場合、DHCとEPHの基礎版はいずれもLLMDR併用時に成功率100%となったが、抜粋だけから全条件で全指標が改善したとはいえない。ハイパーパラメータの観察では、報告された条件で検出窓を4より長くしても大きな性能向上はなく、対象シナリオの多くのデッドロックは振動や巡回よりも停滞に起因する可能性が示された。実行計画長16は、解消に十分な介入ステップを与えつつ、介入が不必要に長くなることによる効率低下を抑えるバランスとして観察された。ただし、抜粋は全マップ、全モデル、全LLM設定の詳細結果、統計的有意性、LLM呼び出し回数、実時間の遅延を確立していない。
MAPFには、Conflict-Based Searchのような体系的探索法と、強化学習や模倣学習などを用いる学習ベース手法がある。Conflict-Based Searchは、困難な大規模インスタンスで指数的な最悪時計算量が問題になりうる。PRIMAL、DHC、DCCなどの学習ベース手法は、一般化、分散経路探索、エージェント間通信を学習によって改善してきた。先行研究には、学習モデルの行動確率分布をPIBTやLaCAMのような優先度付き手法と組み合わせるものや、過去の行動を規則で分析してデッドロックを検出するものもある。
学習ベースのMAPF方策は、個々の行動だけからは原因を特定しにくい形で失敗することがある。複数のエージェントが互いに進路を塞ぐ場合、局所的に妥当に見える行動やランダムな変更では、デッドロックが維持されたり別の競合が生じたりする。優先度付き計画は高優先度のエージェントを先に動かすことで協調を促せる一方、優先度の偏りによって他のエージェントが取り残される可能性もある。したがってLLMDRは、実行がデッドロックに入ったことを認識し、複数エージェントを対象とする訂正介入を選ぶ中間的な問題を扱う。
PIBTは優先度付き計画を拡張し、優先度継承、バックトラッキング、予約、再帰的な競合解決を用いて、1ステップ分の衝突のない行動を生成する。LLMDRはLLMにすべての低レベル経路を構築させず、どのエージェントや行動を優先すべきかを決めるためにLLMを使う。既定の検出窓長は4行動、既定の実行計画長は16ステップである。介入はその計画長だけ進み、その後、デッドロックの兆候がすべて消えていなくても検出へ戻る。
第1実験では、複数のマップとエージェント数において、基礎となる学習ソルバとLLMDRを追加したソルバを比較した。第2実験では言語モデルの影響を調べ、第3実験では検出窓長や実行計画長などのハイパーパラメータを調べた。warehouseの64エージェント条件では、検出窓長2および4、実行計画長8、16、32が比較された。抜粋は、実行計画長16が介入能力と不必要な介入による効率低下の間で観察上のバランスを示したと述べるが、これらの比較の全数値は示していない。
提示されたwarehouseのデータでは、LLMDRはDHC、DCC、EPHの基礎版の成功率を、特に64エージェントの条件で改善した。具体的な成功率の変化は、DHCが1%から83%、DCCが14%から74%、EPHの基礎版が6%から68%である。平均エピソード長も掲載された多くの併用条件で短くなっているが、すべてのソルバ、マップ、エージェント数、LLMについて改善したとは抜粋から断定できない。要旨と結論は、全体として、デッドロックが起こりやすい条件で性能と学習ベースMAPFのスケーラビリティが向上したとまとめている。
LLMDRは、LLMで実行履歴を調べて高レベルのデッドロック解消方策を提案し、学習ベースのMAPF方策とPIBTに低レベルの移動および衝突回避を担わせるハイブリッド構成である。報告された実験は、この構成がエージェント数の増加を含む条件で複数の学習ベースMAPFモデルを改善できることを支持している。その価値はMAPFソルバを置き換えることではなく、ソルバが停止した局面に対して対象を絞った回復機構を追加する点にある。
論文は、LLM推論の計算コストが資源制約のある環境やリアルタイム用途への適用を制限することを明示している。LLMにはマルチエージェント協調や空間推論の難しさもあり、低レベル計画を学習モデルとPIBTに任せる設計はそのリスクを軽減しようとするが、完全に消すものではない。提供された抜粋からは、推論遅延、金銭的コスト、プロンプトやLLM変更への頑健性、失敗事例の完全な一覧は確認できない。また、計算資源を揃えた条件で、すべての非LLM型デッドロック検出器とどのように比較されるかも判断できない。
本研究は、通常時には高速な学習方策を使い、挙動がデッドロックを示したときだけLLMベースの監督機構を呼び出す、学習ベースMAPF向けのハイブリッド設計パターンを示している。混雑したwarehouse条件で報告された改善は、すべての空間判断をLLMに任せず、選択的介入によって学習ベースソルバのスケーラビリティを補える可能性を示す。この点で、MAPFの回復処理、学習ベースのマルチロボット協調、計画におけるLLMの高レベル利用を研究するうえで重要である。
学習ベースMAPF、デッドロック検出と回復、優先度付き計画、PIBT、LLM支援ロボット計画を研究する読者に適している。特に、エージェント数が多い条件やデッドロックが起こりやすい条件で成功率が低下する既存の学習ソルバへ、介入層を追加したい研究者に参考になる。遅延、費用、統計的検定、網羅的なアブレーション結果を詳しく知りたい読者は、それらが提供された抜粋では未確立である点に注意すべきである。