本研究は、実世界の自動倉庫システムを模した、回転制約と堅牢な安全制約を含むLMAPF-R2モデルを対象としている。エージェントは4近傍の格子グラフ上で、前進、回転、待機の行動を選択するが、非ホロノミックな性質により隣接頂点への移動に最大3タイムステップを要する場合がある。また、頂点衝突に加え、エージェントが位置を入れ替える後続衝突も禁止される。従来の学習ベースのプランナーでは、これらの制約がデッドロックやライブロックを引き起こし、高度な協調が困難であった。
先行研究が小規模なシナリオや単純な運動モデルに限定されていたのに対し、本研究は数百規模のエージェントが存在する高密度なライフロング・シナリオへの適用を可能にした。探索アルゴリズムを学習と推論の両方にシームレスに統合し、Causal PIBTの変種をエージェントの方策に組み込むことで、衝突解決と意図の伝播を同時に実現している。さらに、環境のガイダンスグラフを強化学習の枠組みでエージェントの方策と共同で最適化する手法を導入した点が新規である。
SJRLは、エージェント方策と環境方策を統合的に最適化する。環境方策は、各エッジのコストをガウス分布からサンプリングし、エージェントは逆方向Dijkstra探索で計算されたヒューリスティック距離を報酬および入力として利用する。エージェントの報酬は、ステップごとのペナルティ $r_{step}$、サブゴール到達時の進捗報酬 $r_{progress} = d(s_{prev}, g) - d(s_{curr}, g)$、およびチーム報酬で構成される。衝突回避には、優先順位に基づきbusy状態のエージェントを障害物として扱う同期型Causal PIBTを導入し、エージェントの意図を伝播させる。環境方策の学習にはMAPPOを用い、エッジコストを $\sigma(x) = \frac{1}{1 + e^{-x}}$ と線形変換を用いて $[0, 1]$ の範囲に制御する。
6種類のマップを用い、エージェント数や初期状態の変化に対する汎化性能を評価した。比較対象として、エージェントのみを学習するSARL、環境のみを学習するSERL、および探索ベースのCausal-PIBTを用いた。評価指標にはスループットのほか、エージェント間の空間的分散を示す平均ペアワイズ距離 $MPD = \sum_{u,v} \mathbb{P}(u,v) d(u,v)$ を用いた。実験の結果、SJRLは高密度マップにおいてCausal-PIBTを大幅に上回り、エージェント数が増加した際にも高いスループットを維持した。また、8台の実機ロボットと248台の仮想ロボットを用いた混合現実環境でも有効性が検証された。
本手法は、環境レイアウトを固定したままガイダンスグラフのみを最適化することでスケーラビリティを確保しているが、学習の安定化のために、まず一様なエッジコストを用いてエージェントポリシーのウォームアップを行う必要がある。また、Causal PIBTによる衝突回避は、優先度継承と深さ優先探索による意図伝播に依存しており、これらが複雑な制約下での探索を支えている。今後の課題として、より多様な制約や環境レイアウトへの適応、および実世界へのさらなる展開が挙げられる。
本研究では、実世界の自動倉庫システムを模した、回転制約と堅牢な安全制約を含むLMAPF-R2モデルを提案している。このモデルは、エージェントがその場での回転制約を持つことで、従来の学習ベースのプランナーでは困難な高度な協調を必要とする。提案手法であるSearch-Aided Joint Reinforcement Learning (SJRL) は、まず単一ステップの探索ベースのプランナーであるCausal PIBTを用いてニューラルポリシーを拡張し、エージェント間の衝突回避と意図の伝播を実現する。さらに、エージェントのポリシーと環境のポリシーを統合的に最適化する強化学習の定式化を導入しており、環境ポリシーは逆方向のDijkstra探索を通じてグローバルな移動指針を与えるグラフエッジのコストを学習する。実験の結果、SJRLは高密度なマップにおいて強力な探索ベースのプランナーであるCausal-PIBTを大幅に上回る性能を示し、8台の実機ロボットと248台の仮想ロボットを用いた混合現実の倉庫環境においてもその有効性が検証された。
本研究では、高密度かつ制約の強い環境下でのLifelong Multi-Agent Path Finding (LMAPF) において、より現実的な運動モデルであるLMAPF-R2を導入し、その複雑な調整課題に対処するSearch-Aided Joint Reinforcement Learning (SJRL) を提案している。LMAPF-R2は、エージェント間の最小安全距離を確保する堅牢な安全制約と、差動駆動ロボット等の非ホロノミックな性質を反映したその場での回転制約を特徴としており、これらは環境の混雑を悪化させ、デッドロックやライブロックを引き起こす要因となる。提案手法であるSJRLは、局所的な反応的調整を行うエージェント方策と、グローバルな誘導を行う環境方策を同時に最適化する統一的な強化学習フレームワークであり、両者が互いに補完し合うことで交通流を改善する。具体的には、衝突を回避するためにCausal PIBTの変種を用いた衝突シールド技術を統合してエージェントの意図を伝播させるとともに、誘導グラフの最適化を通じてエージェント方策を補完する。実験の結果、この共同学習アプローチは、従来の学習ベースの手法と比較して、現実的な制約下でのスループット向上と効率的な交通制御を実現することが示されている。
本研究で扱う LMAPF-R2 は、4近傍の格子グラフ上で $N$ 台のエージェントが動作する Lifelong Multi-Agent Path Finding の変種であり、各エージェントは初期位置の頂点と向き $\theta$ を持ち、離散的なタイムステップごとに「前進」「時計回りに回転」「反時計回りに回転」「待機」のいずれかの行動を選択する。制約条件として、同一時刻に複数のエージェントが同じ頂点を占有する頂点衝突と、エージェントが前の時刻に他者がいた頂点へ移動する、あるいはエージェント同士が位置を入れ替えるといった後続衝突（following collision）の両方を禁止する。この「Robust」な制約により、先行エージェントが遅延した場合でも後続エージェントが安全な距離を保てるよう保証される。また、回転制約（Rotational constraints）により、隣接する頂点への移動に最大で3タイムステップを要する場合がある。本設定は、エージェントが目標に到達するたびに外部のタスク割り当て器から新たな目標が与えられる生涯（lifelong）設定であり、固定されたタイムホライゾンにおいて、全エージェントのタイムステップあたりの平均目標到達数であるスループットを最大化することを目的とする。
学習ベースのマルチエージェント経路探索（MAPF）における既存研究は、強化学習（RL）によるゼロからの学習、エキスパート探索アルゴリズムを用いた模倣学習（IL）、あるいは両者の組み合わせに分類されるが、回転制約や頑健な制約、複雑な運動学的制約を扱う研究は限定的である。先行研究では、推論時にアクション回数に基づくアドホックなデッドロック回避機構を用いる手法も存在するが、本研究は探索アルゴリズムを学習と推論の両方にシームレスに統合することで、回転制約下での効率的な協調を実現する。衝突解決に関しては、エージェントの動きを停止させる非効率な手法から、軽量な探索アルゴリズムであるPIBTを適用したCS-PIBTへと発展してきたが、本手法はCausal PIBTの変種をエージェントの方策学習に組み込むことで、衝突解決と意図の伝播、および回転制約への対応を同時に行う。環境側の方策については、地図上のエッジコストとしてガイダンスグラフを定式化し、CMA-ESを用いてコストまたはその生成ネットワークを最適化するGuidance Graph Optimization（GGO）を拡張し、RLの枠組みの中でエージェントの方策と共同で学習を行う。従来の環境とエージェントの共同設計に関する研究は、最大16エージェント程度の小規模なシナリオに限定されていたが、本手法は環境レイアウトを固定したままガイダンスグラフのみを最適化することで、数百規模のエージェントが存在する高密度なライフロング・シナリオへの適用を可能にしている。
本手法は、エージェントと環境の双方を強化学習で最適化するSJRL（Search-Aided Joint Agent-Environment Reinforcement Learning）を提案している。MDPの定式化において、環境ポリシーは各エッジのコストをガウス分布からサンプリングし、エージェントはそれに基づき逆方向Dijkstra探索で計算されたヒューリスティック距離を報酬および入力特徴量として利用する。エージェントの報酬は、各ステップの行動に対するペナルティ $r_{step}$、サブゴール到達時の進捗報酬 $r_{progress} = d(s_{prev}, g) - d(s_{curr}, g)$、およびローカルビュー内の全エージェントの平均報酬からなるチーム報酬で構成される。エージェントの学習には、CNN、通信モジュール、MLPを用いたアーキテクチャを採用し、候補となる次頂点へのヒューリスティック距離をスキップ接続により直接注入することで、環境ポリシーの誘導を強化している。衝突回避と意図伝播のため、同期型Causal PIBTを導入しており、これは自由なエージェントが優先順位に基づきサブゴールを選択し、busy状態のエージェントを障害物として扱うことで、廊下のような環境での効率的な探索を可能にする。環境ポリシーの学習にはMAPPOを用い、エッジコストを $[0, 1]$ の範囲に写像する $\sigma(x) = \frac{1}{1 + e^{-x}}$ と線形変換を組み合わせて制御している。学習の安定化のため、まず一様なエッジコストを用いてエージェントポリシーのウォームアップを行い、その後に両者を共同で学習させる。
Moving-AIおよびSILLMのベンチマークから選定された6種類のマップを用い、エージェント数や初期状態、ゴール位置の変化に対する汎化性能を評価している。提案手法であるSJRLは、エージェントの行動を学習するSARLや環境のガイダンスグラフを学習するSERLを統合した共同学習（Joint Learning）を行っており、スループットにおいてこれらを一貫して上回り、特にエージェント数が増加した際に強力な探索ベースの基準手法であるCausal-PIBTを大きく凌駕する。評価指標として平均ペアワイズ距離 $MPD = \sum_{u,v} \mathbb{P}(u,v) d(u,v)$ （ここで $\mathbb{P}(u,v)$ は頂点 $u, v$ がそれぞれエージェントによって占有される経験的確率、$d(u,v)$ は最短経路距離）を用いると、SJRLはエージェント間の空間的な分散を促進し、混雑を緩和していることが示される。また、最新手法であるSILLMやMAGAT+と比較した場合、SJRLは回転を考慮したLMAPF-R2モデルを採用しているため、標準的なLMAPFモデルに基づく既存手法よりも一貫して高い性能を示す。衝突回避メカニズムの比較では、単純な行動ベース（NACS）や頂点ベース（NVCS）の衝突シールドと比較して、優先度継承と深さ優先探索による意図伝播を備えたCausal-PIBTが、倉庫や狭い通路のあるマップにおける探索の困難さを克服し、極めて高い性能を達成している。
本研究では、現実世界のロボットシステムへの適用を見据え、堅牢性と回転制約を組み込んだ、より現実的かつスケーラブルな学習ベースのLifelong Multi-Agent Path Finding（LMAPF）モデルであるLMAPF-R2を提案している。このLMAPF-R2における協調の課題を解決するため、探索と学習の相補的な強みを活用し、エージェントと環境の両方の観点から協調を最適化するSJRLという手法を導入した。本研究の成果は、学習ベースのLMAPFにおいて、現実的な制約とスケーラビリティを両立させた問題定式化の研究を促進し、実世界への展開を容易にすることを目指している。