本論文は、大規模な自動倉庫のような環境で発生する Lifelong MAPF 問題を対象としている。Lifelong MAPF では、エージェントが目的地に到達した後、タスクアサイナによって新たな目標が動的に割り当てられ続ける。従来の MAPF は全エージェントの到着時刻の総和である flowtime や最大到着時刻である makespan の最適化を目指すが、これは NP-hard である。既存の Lifelong MAPF 手法には、全ゴールを事前に知るオフライン手法や、ゴール到達後に「hold」動作や「dummy paths」を生成して完全性を保証しようとする手法があるが、これらはスループットの低下やスケーラビリティの欠如といった課題を抱えている。
本研究の主な貢献は、既存の多様な MAPF ソルバー（CA*, PBS, ECBS, CBS）を、限定された時間ホライゾン内で衝突を解決する Windowed MAPF 形式へと拡張し、Lifelong MAPF に適用可能にする RHCR フレームワークを提案した点である。RHCR は、タスク割り当てと経路計画を分離した階層的な構造を持ち、ドメインに依存せず適用可能である。実験を通じて、RHCR がシミュレーションされた倉庫環境において、マップ上の空きセルの 38.9% に相当する最大 1,000 エージェントという大規模な設定でも高品質な解を生成できることを示した。また、時間ホライゾン $H$ を適切に設定することで、スループットの低下を最小限に抑えつつ、実行時間を大幅に削減できることを実証した。
RHCR は、時間ホライゾン $H$ と再計画周期 $P$ の 2 つのパラメータを用いる。各エージェント $i$ に対し、現在の位置から目標地点シーケンス $\mathcal{G}_i$ をすべて訪問するまでの下限時間 $\sum_{j=1}^{|\mathcal{G}_i|} \text{dist}(g_{j-1}, g_j)$ を計算し、アイドル状態を防ぐ。低レベル探索には、ノードのラベルに訪問済み目標地点の数を保持する拡張 Multi-Label A* を用い、時空間制約下でシーケンス全体を最適化する。また、デッドロック回避のために、エージェントの進捗を評価するポテンシャル関数 $\Phi$ を導入し、進捗が不十分な場合に $H$ を段階的に増加させるメカニズムを備えている。これにより、ホライゾンが小さすぎることによるデッドロックのリスクと、大きすぎることによる計算コスト増大のトレードオフを管理する。
C++ で実装された RHCR を、CBS, ECBS, CA*, PBS をベースとした 4 種類の Windowed MAPF ソルバーを用いて評価した。Fulfillment Warehouse（16% の障害物）の実験では、RHCR は「holding endpoints (HE)」や「reserving dummy paths (RDP)」よりも高いスループットを達成した。Sorting Center（10% の障害物と方向性を持つマップ）の実験では、時間ホライゾン $H$ を小さく設定することで、スループットの低下を 1% 未満に抑えつつ、実行時間を最大 6 倍高速化できることを示した。また、$H=10$ の PBS が 700 エージェントで限界であったのに対し、$H=100$ では 1,000 エージェント以上までスケールすることを確認した。動的な $H$ の決定手法では、平均 $H=9.97$ でスループット 2.10 を記録したが、固定 $H=100$（スループット 2.02）と比較して、実行時間のオーバーヘッドが生じるという限界も示された。
RHCR は完全性や最適性を保証するものではないが、実用的なスループットとスケーラビリティを両立している。実験結果から、Lifelong MAPF において $H$ の選択は極めて重要であり、ホライゾンを大きくしすぎると不要な待機時間が増え、小さすぎるとデッドロックのリスクが高まることが示唆された。動的なホライゾン調整はスループットを向上させるものの、地平を繰り返し増大させるための計算コストが課題となる。今後の展望として、混雑状況や計算予算に基づくタイムホライゾンの自動調整、エージェントのグループ化による並列計画、および過去の探索結果を再利用する増分探索技術の導入が挙げられている。
本研究では、大規模な自動倉庫のようにエージェントが絶えず新しい目的地を与えられ続ける、Lifelong Multi-Agent Path Finding (MAPF) を対象としている。提案手法である Rolling-Horizon Collision Resolution (RHCR) は、問題を一連の Windowed MAPF インスタンスへと分解し、限定された時間ホライゾン内でのみエージェント間の衝突を解決することで、継続的に到着する新しい目的地に適応可能な柔軟な計画生成を実現する。実験では、様々な MAPF ソルバーを用いて RHCR を評価しており、シミュレーションされた倉庫環境において最大 1,000 エージェント（マップ上の空きセルの 38.9% に相当）という大規模な設定でも高品質な解を生成できることを示した。この結果は、既存手法を大幅に上回る性能を示している。
Multi-Agent Path Finding (MAPF) は、衝突を回避しながら複数のエージェントを始点から終点へ移動させる問題であり、解の質は全エージェントの到着時刻の総和である flowtime や、最大到着時刻である makespan によって評価されるが、最適解の算出は NP-hard である。本論文では、エージェントに次々と新しい目標が割り当てられる lifelong MAPF に対し、lifelong MAPF を一連の Windowed MAPF インスタンスに分解し、ユーザー指定の再計画周期ごとに経路を再計算する Rolling-Horizon Collision Resolution (RHCR) フレームワークを提案する。この Windowed MAPF では、単一のエピソード内でエージェントに目標のシーケンスを割り当てることが可能であり、衝突回避はユーザー指定のタイムホライゾン $T$ の範囲内のみで行う。RHCR は、CA*、PBS、ECBS、CBS といった多様な MAPF ソルバーを用いて評価されており、限定的なタイムホライゾンを用いることで、全期間のホライゾンを用いる場合と同等のスループットを維持しつつ、実行時間を大幅に削減できることが示されている。実験の結果、RHCR は既存手法を上回る性能を示し、シミュレーションされた倉庫環境において、マップ上の空きセルの 38.9% に相当する最大 1,000 エージェントまでのスケーラビリティを実現している。
本セクションでは、既存のMAPFソルバー、Lifelong MAPFに関する先行研究、および有界ホライゾン（bounded horizon）の概念について概説している。代表的なMAPFソルバーとして、完全性と最適性を備えた2レベル探索のConflict-Based Search (CBS)、焦点探索を用いてユーザー指定の範囲内で劣最適性を許容するEnhanced CBS (ECBS)、優先度順に経路を計算するCooperative A* (CA*)、およびCBSとCA*の概念を組み合わせたPriority-Based Search (PBS) が挙げられる。Lifelong MAPFの研究は、全ゴールを事前に知るオフライン手法、全エージェントを毎ステップ再計画する逐次分解手法、およびゴールに到達したエージェントのみを再計画する手法の3種に分類されるが、前者はスケーラビリティに欠け、後者は再計画の計算コストや、地図構造に依存する不完全性といった課題がある。特に、Completenessを保証するために導入される「well-formed infrastructures」や、ゴール到達後の「hold」動作、あるいは「dummy paths」の生成は、スループットを低下させる要因となる。最後に、WHCA*のようにホライゾンを制限する手法は、計算コストを下げつつ経路長を増大させる傾向があるが、本論文ではLifelong MAPFにおいて計算コストを抑えつつ解の質をわずかな低下に留める有界ホライゾン計画の有効性を示唆している。
本研究では、グラフ $G=(V, E)$ と初期位置を持つエージェントの集合 $\mathcal{A} = \{a_1, \dots, a_n\}$ を入力とし、目標地点 $g_i$ が事前にすべて判明していないオンライン設定における Lifelong Multi-Agent Path Finding (MAPF) を定義している。タスクアサイナによって動的に目標が割り当てられる仕組みを想定しており、タスクが終了した後は充電ステーションや現在地などのダミータスクが割り当てられる。各タイムステップにおいて、エージェントは隣接する頂点への移動または待機（共にコスト 1）を選択でき、同一時刻に同じ頂点を占有する vertex conflict や、エッジを逆方向に通過する swapping conflict を回避した衝突のないパス（MAPF plan）を計画する必要がある。本問題の目的は、すべてのエージェントを目標地点へ移動させつつ、タイムステップあたりの平均目標訪問数であるスループット $\theta$ を最大化することである。本手法はタスク割り当てと経路計画を分離した階層的なフレームワークを想定しており、タスクアサイナが制御不能な外部システムであっても、ドメインに依存せず適用可能であるという利点を持つ。
Rolling-Horizon Collision Resolution (RHCR)は、時間ホライゾン $H$ と再計画周期 $P$ の2つのパラメータを用いて、Lifelong MAPFにおける衝突を解決する手法である。RHCRは、各エージェント $i$ に対して、現在の位置を始点とし、残りの目標地点シーケンス $\mathcal{G}_i$ をすべて訪問するまでの下限時間 $\sum_{j=1}^{|\mathcal{G}_i|} \text{dist}(g_{j-1}, g_j)$ を計算し、エージェントがアイドル状態にならないよう目標地点を動的に割り当てる。低レベル探索には、目標地点シーケンスを考慮して拡張されたMulti-Label A*（Algorithm 1）を用い、ノードのラベルに訪問済み目標地点の数を保持することで、時空間制約を満たしつつシーケンス全体を最適化する。また、(E)CBS、CA*、PBSといった既存のMAPFソルバーを、最初の $H$ ステップ間のみ衝突を考慮するBounded-Horizon形式へと拡張することで、計算コストを削減している。実験的な知見として、Lifelong MAPFでは $H$ を大きくしすぎると不要な待機時間が増えスループットが低下する場合がある一方、$H$ が小さすぎるとデッドロックが発生するリスクがある。このデッドロックを回避するため、エージェントの進捗を評価するポテンシャル関数 $\Phi$ を導入し、進捗が不十分な場合に $H$ を段階的に増加させるメカニズムが提案されている。
本実験では、C++で実装されたRHCRを、CBS、ECBS、CA*、PBSをベースとした4種類のWindowed MAPFソルバーを用いて評価している。Fulfillment Warehouse（在庫保管倉庫）の実験では、16%の障害物を含む4近傍グリッドマップを用い、RHCRは既存のMethod (3) である「holding endpoints (HE)」や「reserving dummy paths (RDP)」と比較され、RHCRが最も高いスループットを達成した一方で、1回あたりの実行時間は競合手法より長いことが示された。Sorting Center（仕分けセンター）の実験では、10%の障害物と方向性を持つマップを用い、RHCRの性能をPBS、ECBS（劣最適化係数 $w=1.1$）、CA*、CBSを用いて検証した。その結果、時間地平 $H$ を小さく設定することで、スループットを1%未満の低下に抑えつつ、実行時間を最大6倍高速化できることが確認され、また $H=10$ のPBSは700エージェントが限界であったのに対し、$H=100$ では1,000エージェント以上までスケールした。さらに、デッドロック回避メカニズムを用いた動的な時間地平の決定手法を試行したところ、平均 $H=9.97$ を使用してスループット2.10、実行時間0.35sを記録したが、これは固定の $H=100$ を用いた場合（スループット2.02、実行時間0.17s）と比較して、高いスループットを実現する代わりに、地平を繰り返し増大させるための実行時間オーバーヘッドが生じるという限界が示された。
本論文では、Lifelong MAPFを一連のWindowed MAPFインスタンスへと分解する手法であるRolling-Horizon Collision Resolution (RHCR) を提案しており、既存の複数のMAPFソルバーをWindowed MAPFソルバーへと変換可能にしている。RHCRは完全性や最適性を保証するものではないが、倉庫や仕分けセンターのマップを用いた実験において、最大1,000エージェントまでのスケーラビリティと高いスループットを実証した。本手法は一般グラフに適用可能であり、ユーザー指定の頻度で再計画を行うことで、継続的に到着する新しいゴールに対応しつつ、遠い未来の予測による計算資源の浪費を回避する柔軟な計画生成を実現している。今後の展望として、混雑状況や計算予算に基づくタイムホライゾンの自動調整、エージェントのグループ化による並列計画、および過去の探索結果を再利用する増分探索技術の導入が挙げられている。