本研究は、従来のMAPFが想定していた「エージェント密度 $10\%$ 未満、エージェント数 $100$ 以下」という限定的な設定を超え、実世界の自動倉庫等で求められる極端な条件下でのLMAPFの課題を扱う。対象とするLMAPF-Rは、外部タスクアサイナから継続的に目標が割り当てられるLMAPFに、位置と方位（East, South, West, North）を含むエージェントの状態を組み合わせたものである。LRRコンペティションの設定では、最大 $10,000$ 体のエージェント、最大 $54,230$ 頂点のマップ、最大 $95\%$ のエージェント密度、およびステップあたり $1$ 秒という極めて厳しい計画時間が課される。本論文は、これらの条件下でスループットを最大化するための手法と、直面する技術的障壁を体系化している。
本論文の主な貢献は、大規模LMAPFにおけるスケーラビリティと実用性を阻害する要因を特定し、それらに対する具体的な解決策を提案した点にある。第一に、限られた計画時間内で高品質な解を得るための、並列化されたAnytimeアルゴリズムの枠組みを提示した。第二に、アルゴリズムの近視眼的な振る舞いが引き起こす交通渋滞を緩和するため、ガイダンスグラフの導入やエージェントの無効化（Disabling Agents）といった戦略を提案した。第三に、回転動作を含む現実的なアクションモデル（LMAPF-R）への適応手法を示し、既存モデルと実世界の乖離を埋めるための研究方向性を明らかにした。
提案手法である Windowed Parallel PIBT-LNS (WPPL) は、複数のアルゴリズムを組み合わせた階層的なアプローチをとる。まず、RHCRの概念に基づきウィンドウ幅 $w$ を用いた計画を行い、高速なルールベース手法であるPIBT (Priority Inheritance Backtracking) によって初期解を生成する。次に、Parallel MAPF-LNS を用いて、非同期に選択されたエージェントグループに対して逐次的な解の改善（Local Search）を行う。渋滞対策としては、エッジの重みを調整して移動コストをエンコードする「ガイダンスグラフ」や、デッドエンドでの滞留を防ぐために一部のエージェントの優先度を下げてゴールを現在地に設定する「エージェントの無効化」を用いる。また、回転動作を含むモデルに対しては、PIBTで次位置を計画した後に、その位置へ到達するための最初の動作のみを採用する手法を導入している。
実験は、32 vCPUsと84G Memoryを搭載したローカルマシンを用い、オフラインデータに対して評価が行われた。提案手法 WPPL は、10のインスタンス中9つでスコア1に近い 9.755 を記録し、Overall Best および Fast Mover トラックで優勝した。PIBT 単体では Sortation 10000 インスタンスにおいて 250 ms 以内に解を返しており、残りの時間を LNS に充てることでスループットを向上させている。エージェントの無効化の効果については、Game 4000 においてエージェント数を 4,000 から 2,500 に減らすことでスループットが最大化されることを確認した。また、無効化を行わない場合、Random 600, Random 800, Game 4000 においてスループットがそれぞれ $15.7\%$, $51.8\%$, $47.0\%$ 低下するという結果を得ている。回転モデルの導入により、WPPL は Game 4000, Warehouse 8000, Sortation 10000 においてそれぞれ 185.0%, 192.5%, 189.0% のスループット向上を達成した。
本研究では、スケーラビリティと解の品質のトレードオフが重要な課題として残っている。WPPL は高い性能を示す一方で、非構造的なマップや極端に混雑したシナリオでは PIBT の初期解の質に依存するという限界がある。また、近視眼的なコスト最小化が将来の渋滞を悪化させる悪循環についても指摘されており、今後は GGO (Guidance Graph Optimization) のスケールアップや、データ駆動型の渋滞予測、リアルタイム探索を用いたヒューリスティックの更新が必要である。さらに、実世界への適用に向けては、より複雑な運動学・動力学（kinodynamic）モデルの考慮、実行時の不確実性への対応、およびマップやエージェント数が変化する進化するシステム（Evolving Systems）への適応が不可欠な研究課題である。
本論文は、2023年のLeague of Robot Runners LMAPFコンペティションにおける優勝手法に基づき、Lifelong Multi-Agent Path Finding (LMAPF) における3つの主要な研究課題を提示している。第一の課題は、10,000体規模の大量のエージェントや97.7%という極めて高い密度において、限定された計画時間（例：1ステップあたり1秒）内で高品質な解を探索することであり、ルールベースやAnytimeアルゴリズムの高度化、および既存アルゴリズムの並列化が解決策として挙げられている。第二の課題は、混雑の緩和と近視眼的な振る舞いの抑制であり、移動ガイダンスや交通ルールの導入、将来予測とリアルタイム探索の統合、および最適なエージェント数の決定が重要となる。第三の課題は、既存のLMAPFモデルと実世界アプリケーションとの乖離を埋めることであり、より現実的な運動学的・動力学的（kinodynamic）モデルへの対応、実行時の不確実性、および進化するシステムへの適応が今後の研究方向として示されている。
本セクションでは、従来のMulti-Agent Path Finding (MAPF) から、エージェントに継続的に新しいタスクが割り当てられるLifelong MAPF (LMAPF) への拡張の重要性が述べられている。既存の研究の多くは、エージェント密度が $10\%$ 未満、エージェント数が $100$ 以下といった限定的な設定に留まっているが、実世界の自動倉庫等では、エージェント密度が $100\%$ に近いケースや数千台規模のロボット運用が求められる。これに対し、Amazon Roboticsが主催する「The League of Robot Runners (LRR)」コンペティションでは、最大 $10,000$ 体のエージェント、最大 $54,230$ 頂点の広大なマップ、最大 $95\%$ の極端なエージェント密度、ステップあたり $1$ 秒という厳しい計画時間、および向きや回転を考慮した現実的なアクションモデルという、極めて困難な設定が導入されている。本論文では、これらに関連する「限られた計画時間」「混雑や近視眼的挙動」「モデルと実世界の乖離」という3つの主要な研究課題を提示し、並列計算の活用や交通ルールの導入、実行の不確実性を考慮したモデル構築などの将来的な研究方向性を議論する。
本セクションでは、MAPF、LMAPF、およびMAPF-Rの定義が示されており、本研究の対象であるLMAPF-Rは、外部のタスクアサイナによって継続的に目標が割り当てられるLMAPFと、エージェントの状態に位置と方位（East, South, West, North）を含むMAPF-Rを組み合わせたものである。LMAPFの目的は、全エージェントの衝突を回避しつつ、ステップあたりの平均目標到達数であるスループットを最大化することである。実験設定では、32 vCPUsと84G Memoryを搭載したローカルマシンを用い、オフラインデータに対して評価を行っている。評価指標は、全提出者の最高スループットに対する解のスループットの比率として定義される正規化スコア（0から1の範囲）であり、Overall Best、Fast Mover、Line Honoursの3つのトラックで順位が決定される。提案手法であるWindowed Parallel PIBT-LNS (WPPL) は、PIBTで初期計画を生成した後、Parallel MAPF-LNSを用いて計画を洗練させる手法である。最終的に、提案手法は10インスタンス中9つでスコア1に近い9.755を記録し、Overall BestおよびFast Moverトラックで優勝した。
Lifelong Multi-Agent Path Finding (LMAPF) における限られた計画時間（LRRコンペティションでは各ステップ1秒以内）という課題に対し、本セクションでは既存手法の限界と提案手法 WPPL (Windowed Parallel PIBT-LNS) について論じている。既存の最適解アルゴリズム（CBS等）は計算量が指数関数的に増加し、境界劣解アルゴリズム（ECBS等）やルールベース手法（PIBT等）はスケーラビリティと解の品質の間にトレードオフがある。提案手法 WPPL は、RHCR の概念を用いたウィンドウ幅 $w$ による計画、高速な PIBT による初期解生成、および MAPF-LNS による逐次的な解の改善を組み合わせたものである。さらに、マルチコアを活用するために、非同期にエージェントグループを選択して並列に再計画を行う並列化戦略を採用している。実験では、PIBT が Sortation 10000 インスタンスで 250 ms 以内に解を返すことを示し、残りの時間を LNS による改善に充てることでスループットを向上させている。また、過去の計画ステップを再利用することで、Random 600 インスタンスにおいてスループットが 29.9% 向上するという結果を得ているが、非構造的なマップや混雑したシナリオでは PIBT の初期解の質に依存する限界も示唆されている。
LMAPF（Lifelong Multi-Agent Path Finding）における交通渋滞とアルゴリズムの近視眼的（myopic）な振る舞いの相関が議論されており、特にWPPLのような手法が、現在のウィンドウ内での近似的な合計コスト $\sum \text{costs}$ を最小化しようとする際、将来の衝突や渋滞を無視することで、結果的にPIBTよりもスループットを低下させ、渋滞を悪化させる悪循環が生じることが示されている。この問題に対し、エッジの重みを調整して移動コストをエンコードする「ガイダンスグラフ（Guidance Graph）」の導入が提案されており、手動での微調整や、計算コストは高いもののGGOアルゴリズムによる自動最適化が行われる。また、デッドエンドや狭い通路での渋滞を回避するため、一部のエージェントのゴールを現在地に設定し優先度を最低に下げる「エージェントの無効化（Disabling Agents）」という手法が用いられ、Game 4000のインスタンスでは、エージェント数を4,000から2,500に減らすことでスループットが最大化されることが確認された。実験結果として、エージェントの無効化を行わない場合、Random 600、Random 800、Game 4000においてそれぞれスループットが $15.7\%$、$51.8\%$、$47.0\%$ 低下することが示されている。今後の展望として、GGOのスケールアップ、オンラインでのガイダンス更新、データ駆動型の渋滞予測、およびリアルタイム探索を用いたヒューリスティックの更新による局所解の回避などが挙げられている。
本セクションでは、既存のLMAPFモデルと実世界アプリケーションの間の乖離（Gaps）を第3の課題として挙げ、特に回転動作を含むLMAPF-Rモデルへの適応について論じている。LMAPF-Rでは、従来の4方向移動モデルに対し、前進・回転・待機というより現実的なアクションモデルを採用しており、回転を計画アルゴリズムに直接組み込むことでスループットの向上が期待できる。著者らは、PIBTにおいて回転が次ステップの衝突判定を困難にする問題に対し、まず元のPIBTで次位置を計画し、その位置へ到達するための最初の動作のみを採用するという手法を提案している。実験では、回転モデルが混雑を引き起こしやすいことを示すため、WPPLとPIBTの比較を行い、Game 4000、Warehouse 8000、Sortation 10000においてWPPLがそれぞれ185.0%、192.5%、189.0%のスループット向上を達成した一方で、極端な高密度環境のRandom 800では依然として課題が残ることを示した。さらに、実世界への適用におけるその他の乖離として、複雑な運動学・動力学（Kinematics and Dynamics）の考慮、実行時の不確実性、非一様なタスク分布、およびマップレイアウトやエージェント数が変化する進化するシステム（Evolving Systems）への対応が必要であることを指摘している。
本論文は、2023年のLeague of Robot Runnersコンペティションでの経験に基づき、Lifelong Multi-Agent Path Finding (LMAPF) をより現実的な設定へスケールさせるための3つの主要な課題を提示している。第一に、限られた計画時間への対応として、WPPL（Windowed Prioritized Planning）を解決策として挙げ、ルールベース、Anytime、および並列アルゴリズムの重要性を指摘している。第二に、混雑問題の緩和策としてガイダンスグラフの適用やエージェントの無効化を挙げ、今後はより高度なガイダンスや交通ルールの設計、将来の交通予測、リアルタイム探索、および最適なエージェント数の決定が必要であるとしている。最後に、既存研究における簡略化されたLMAPFモデルと、運動学的制約（kinodynamic models）、実行時の不確実性、および動的に変化するシステムを含む複雑な実世界アプリケーションとの乖離を埋める必要性を論じている。