自動倉庫などの実用的なアプリケーションにおけるLMAPFでは、厳格な応答性の要求により、プランナーが制限時間内に衝突のない経路を生成できない「計画失敗」が発生する。本研究は、グラフ $G = (V, E)$ 上のエージェント集合 $A$ に対し、継続的に与えられる目的地へ衝突を回避しながら移動させる問題において、解不能な状態や時間切れによる失敗への対処を対象とする。従来のMAPF研究は完全な解の生成に焦点を当てており、オンライン環境での計画失敗への対応は十分に検討されていなかった。
計画失敗を回避・軽減・処理するための、エージェント選択ポリシー、プランナー、および失敗ポリシー（fail policy）からなる包括的なシステム設計を提案している。特に、産業界で利用されながらも学術的な分析が不足していた失敗時の振る舞いを形式化し、衝突回避とスループット維持を両立させる手法を明らかにした。これにより、最先端のベースラインと比較して、システムの処理能力を最大で2倍に向上させることに成功した。
提案システムは、計画期間の終了時に全エージェントが最初の $k$ ステップにおいて衝突を持たない $k$-safe な状態であることを保証する。エージェント選択では、全エージェントを対象とする AllAgents と、衝突のあるエージェントから範囲 $R$ 内を選択する Fail@LH($R$) を用いる。プランナーには、失敗時に空の解を返す Full、中断された経路を返す Restart、衝突を無視して可能な限り多くの経路を生成する Persist を導入する。失敗ポリシーとして、衝突エージェントを停止させる IStay や、衝突回避のために1ステップの移動とそれに続く待機を許容する IAvoid を定義し、計算可能な時間内での衝突回避を実現する。
8種類のグリッドマップ（Open, Random, Maze, Room, Warehouseなど）を用い、エージェント数を25から1000まで変化させて評価した。RHCRプランナーに Prioritised Planning を用い、タイムホライゾンを10、プランニング頻度を3タイムステップ、最大プランニング時間を1秒として実験を行った。結果として、Fail@LH(5) と Persist、および IAvoid を組み合わせた構成が最も高いスループットを示した。特に IAvoid は AllStay や IStay よりも優れた性能を示し、Fail@LH(5) と Persist の組み合わせはベースラインに対して劇的な向上を達成した。
エージェント選択において、範囲 $R$ を大きくしすぎると衝突から遠いエージェントの計画まで無効化され、探索効率が低下するというトレードオフが存在する。今後の課題として、失敗ポリシーを適用するエージェントの順序の最適化や、リアルタイム探索および手続き型MAPFアルゴリズムとの統合が挙げられる。また、衝突回避のために利用可能なアクションシーケンスをより長く設定するなどの拡張の可能性についても検討されている。
Lifelong Multi-Agent Path Finding (LMAPF) は、複数のエージェントが継続的に新しい目的地を受け取り、衝突を回避しながらスループットを最適化するように経路を更新し続ける問題である。自動倉庫のような実世界のアプリケーションでは、厳格な応答性の要求により計画に割り当てられる時間が制限されるため、MAPFアルゴリズムが制限時間内に解を生成できず、計画の失敗が発生する場合がある。本研究では、このような計画の失敗に対して堅牢なLMAPFのシステム設計を提案し、失敗を回避、深刻度を軽減、あるいは発生時に適切に処理するための異なるアプローチを探索する。特に、計画の失敗が発生した際に適用される Fail Policies を定義・分析することで、衝突の回避とスループットの不必要な低下の防止を両立させる手法を検討している。これら Fail Policies は産業界の実務では利用されているものの、学術的な研究はこれまで十分に行われていなかった。
Lifelong Multi-Agent Path Finding (LMAPF) は、エージェントが現在の目標に到達するたびに新しい目標を受け取り、一連の経路計画を継続的に解く問題であり、自動倉庫などの実用的なアプリケーションにおいて重要である。本研究では、現在の状態が解不能である場合や、アルゴリズムが制限時間内に解を見つけられない場合などの「計画失敗（planning failure）」に対処するための、エージェント選択ポリシー、プランナー、および失敗ポリシー（fail policy）からなる堅牢なシステム設計を提案している。プランナーには Rolling-Horizon Collision Resolution (RHCR) を拡張した手法を用い、計画失敗時に高品質な部分解を返せるようバイアスをかける。失敗ポリシーとして、衝突しないエージェントのみを移動させ衝突エージェントを停止させる IStay と、衝突エージェントに衝突回避のための単一のアクションを許可する IAvoid の2種類を導入しており、これらは衝突を回避しつつ計算可能な時間内で動作することが保証されている。標準的なベンチマークを用いた実験の結果、特定の構成を用いることで、最先端のベースラインと比較してシステムの処理能力（throughput）を最大で2倍に向上させることが示された。
Multi-Agent Path Finding (MAPF) は、グラフ $G = (V, E)$ 上のエージェント集合 $A$ の各要素 $a_i$ に対し、始点 $s_i$ から終点 $g_i$ への衝突のない経路 $\pi$ を割り当てる問題であり、本研究では頂点衝突とスワップ衝突のみを考慮する。Lifelong MAPF (LMAPF) は、エージェントが目標に到達するたびに新たな目標が与えられる設定であり、性能評価には一定時間 $X$ 内の目標到達回数を示すスループットが用いられる。本研究では、一定の再計画間隔と時間ホライゾンを持つ Rolling-Horizon Collision Resolution (RHCR) フレームワークを用い、その内部アルゴリズムとして、優先順位に基づき順次経路を計算する Prioritised Planning (PrP) またはその改良版である Random Restarts を用いた手法を想定している。問題設定として、計画時間が制限されたオンライン環境を想定しており、コントローラーが一定間隔 $k$ ごとにプランナーを呼び出し、各エージェントに少なくとも長さ $k$ の経路を指示する。プランニングの失敗は、解が存在しない状態、あるいはアルゴリズムの不完全性や時間制限により解が見つからない状態として定義され、実用的なシステムではこれらの失敗に対して適切な対処ポリシーが必要となる。
本セクションでは、Lifelong Multi-Agent Path Finding (LMAPF) における計画失敗（planning failure）に対処するための、堅牢なシステム設計が提案されている。まず、部分解 $\hat{\pi}$ において、エージェント $a_i$ が最初の $k$ ステップ以内に衝突を持つか、あるいは経路が割り当てられていない場合に $k$-invalid であると定義し、全エージェントが $k$-invalid でない状態を $k$-safe な解と定義する。提案システムは、エージェント選択ポリシー、プランナー、および fail policy の3つのコンポーネントで構成され、各計画期間の終了時に $\hat{\pi}$ が $k$-safe であることを保証する不変条件を持つ。エージェント選択には、全エージェントを対象とする AllAgents と、衝突のあるエージェントを基準に範囲 $R$ を広げて選択する Fail@LH($R$) があり、プランナーには、失敗時に空の解を返す Full、中断された反復の経路を返す Restart、および衝突を無視して可能な限り多くの経路を生成する Persist の手法が検討されている。Fail policy としては、全エージェントを停止させる AllStay、衝突のあるエージェントのみを停止させる IStay、および衝突回避のために1ステップの移動を許容する IAvoid が提案されており、IAvoid は $k$-invalid なエージェントに対し、隣接する各位置への移動とそれに続く $k-1$ ステップの待機を試行することで、より多くのエージェントの進行を可能にする。IAvoid の計算量は、グラフの最大次数に依存するが、実用上は無視できるほど小さい。
本実験では、提案された堅牢なLifelong Multi-Agent Path Finding (LMAPF) システムの性能を評価するため、8種類の異なるグリッドマップ（Open, Random, Maze, Room, Warehouseなど）を用い、エージェント数を25から1000まで変化させてスループットを測定した。実験設定では、RHCRプランナーにPrPを用い、タイムホライゾンを10、プランニング頻度を3タイムステップに設定し、各ステップの最大プランニング時間を1秒、最大200タイムステップとして評価を行った。エージェント選択ポリシーの比較では、Fail@LH($R$)において$R=3$または$R=5$が最も高いスループットを示し、特にFail@LH(5)が多くのマップで最大値を記録したが、$R$を大きくしすぎると衝突が遠いエージェントの計画まで無効化され、探索効率が低下することが確認された。部分解を求めるプランニングポリシーについては、PersistがRestartやFullよりも高い、あるいは同等のスループットを達成し、特にFullはエージェント数が増加すると性能が著しく低下する傾向が見られた。失敗ポリシー（Fail Policy）の比較では、IAvoidがAllStayやIStayよりも優れたスループットを示し、特にAllStayと比較して大幅な性能向上が認められた。アブレーション研究の結果、Fail@LH(5)とPersistを組み合わせた構成が最も高いスループットを実現しており、選択ポリシー、プランナー、失敗ポリシーの各要素を最適化して組み合わせることがLMAPFの解決において極めて有効であることが示された。
本セクションでは、Lifelong Multi-Agent Path Finding (LMAPF) に関する既存研究が概観されている。Ma et al. (2017) は、エージェントに常にペアとなるタスク（特定の場所でのピックアップとその後のデリバリー）を割り当てるオンラインの Pickup and Delivery タスクとしての MAPD を提案しており、タスク割り当てをアルゴリズムに組み込んでいるが、タイムステップごとの計画時間が厳密に制限されることによる計画の失敗については考慮していない。Li et al. (2021b) は、MAPD 問題の解決に Bounded-Horizon Planning を適用し、将来のタスクの予見可能性を考慮することで、参加可能なエージェント数を増加させる手法を示している。また、Xu et al. (2022) は、最新の MAPF ソルバーの技術を統合することで、実行時間の短縮とスループットの向上を図っている。エージェントが単一のタスクを受け取り、完了後に消滅して新しいエージェントが現れる Online MAPF も存在する。さらに、MAPF-LNS (Li et al. 2021a) やその拡張である MAPF-LNS2 (Li et al. 2022) は、エージェントのサブセットを選択して計画を行うことで解の品質向上や衝突の削減を目指しているが、これらは古典的な MAPF を対象としており、計画の失敗や LMAPF の文脈は考慮されていない。
本研究では、オンラインでの経路計画時間が厳密に制限され、計画が完全な解を見つけられない可能性があるLifelong Multi-Agent Path Finding (LMAPF) 環境におけるシステム設計を提案している。計画の失敗に対処するため、衝突を回避しながら目標への進行を維持する概念として、部分解（partial solution）と失敗時ポリシー（fail policy）を導入した。具体的には、計画対象となるエージェントの選択、計画手法、および計画失敗時の振る舞いを制御する設計要素を検討している。多様なベンチマークを用いた実験の結果、提案手法を用いることでシステムのスループットが劇的に向上することが示された。今後の展望として、失敗時ポリシーを適用するエージェントの順序の最適化や、リアルタイム探索および手続き型MAPFアルゴリズムとの統合、さらには衝突回避のために利用可能なアクションシーケンスの長文化などが挙げられている。