自動倉庫などの実世界応用で重要な、エージェントが目標到達のたびに新たな目標を受け取る Lifelong MAPF (LMAPF) を対象とする。従来、LMAPF は一連の MAPF 問題として解かれてきたが、グラフ上で位置の入れ替えが不可能な場合、全エージェントが同時に目標に到達する構成が存在せず、解が見つからないという不一致が生じる。既存の緩和策は計算コストの増大やデッドロック、非効率性を招く課題があった。
従来の MAPF が要求する「経路の終端が目標地点であること」という制約を緩和し、「経路の途中で目標地点を訪問すること」を許容する新しい問題設定 MAPF4L を提案する。これにより、LMAPF の要件と従来の MAPF の間の不一致を直接的に解消する。また、既存の主要な MAPF アルゴリズムを MAPF4L に適応させるための具体的な拡張手法を提示している。
MAPF4L の評価指標として、目標受領から初訪問までの経過時間の総和である $\text{SST}(\pi) := \sum (\min \{x \mid \pi_i[x] = t_i\} \mid \pi_i \in \pi)$ および、最大初到達時間である MKST を導入する。既存の PrP、LNS、CBS などのアルゴリズムを適用するため、$A^*$ 探索の状態定義を、位置 $v$、時刻 $x$ に加え、目標訪問済みフラグ $b \in \{\text{true, false}\}$ を含む $\langle v, x, b \rangle$ へと拡張する。このフラグは、現在の位置が目標地点であるか、あるいは親の状態のフラグが true であれば true となる。探索時は、位置と時刻が同一でも $b$ が異なる状態を区別して扱い、最終的なゴール状態を $\langle v, x, \text{true} \rangle$ と定義する。
手作りの LMAPF シナリオおよび標準的なベンチマークを用いた実験により、既存手法（PIBT, PrP, CBS）と提案手法（PrPL, CBSL）を比較した。エージェントがすれ違う必要があるシナリオでは、従来の CBS のスループットが 250 で実行時間が 29,198ms であったのに対し、CBSL はスループット 499 を記録し、実行時間も 33ms と劇的に高速化した。また、高密度な warehouse シナリオにおいて、PrPL は PrP よりも高いスループットを達成し、ターゲット数が限定的な環境での有効性が示された。
提案手法は、目標地点を通過するだけでよいという制約に基づいているため、エージェントがタスク完了のために目標地点で一定時間滞在しなければならないような、より一般的なアプリケーションへの拡張が今後の課題である。また、PIBT のような 1 ステップ先読みによる計画は、狭い通路が存在する複雑なシナリオでは効果が限定的になる可能性がある。
Lifelong Multi-Agent Path Finding (LMAPF) は、エージェントが現在の目標に到達するたびに新たな目標を受け取るオンライン形式の MAPF 問題であるが、従来の手法では LMAPF を一連の MAPF 問題の列として扱い、全エージェントが同時に目標地点に到達することを要求するため、不必要な制約が生じている。本論文では、既存の緩和手法が失敗するケースを指摘した上で、各エージェントが最終的に目標を訪問することのみを目的とし、全エージェントの同時到達を必須としない新しい問題設定である MAPF for Lifelong (MAPF4L) を提案する。この MAPF4L を解決するために、既存の複数の MAPF アルゴリズムを修正して適用する手法を提示している。限定的な実験評価の結果、MAPF4L アルゴリズムを用いることで、システムの総スループットを大幅に向上させられるケースが存在することが示されている。
Lifelong Multi-Agent Path Finding (LMAPF) は、エージェントが目標に到達するたびに新たな目標が割り当てられる問題であり、自動倉庫などの実世界応用において重要である。従来、LMAPFは各時点でのエージェントの現在地から目標までの経路を求める一連の MAPF 問題として解かれてきたが、この手法では、グラフ上でエージェントが位置を入れ替えられない場合に、全エージェントが同時に目標に到達する構成が存在しないため、解が見つからないという「MAPF-LMAPF の不一致」が生じる。この問題に対し、限定的なホライゾンでの計画、目標到達時の動的な再計画、目標到達後のダミーパスの定義、あるいは目標のシーケンス割り当てといった緩和策が提案されてきたが、これらは完全な解決策にはなっていない。本研究では、全エージェントが同時に目標に位置する必要はなく、各エージェントが経路のどこかの時点で目標を訪問することを目指す MAPF for Lifelong (MAPF4L) という修正された MAPF 問題を提案する。MAPF4L の特性を議論した上で、既存の主要な MAPF アルゴリズムをこの問題に適応させ、小規模な実験を通じて LMAPF システムにおける MAPF4L の有効性を示す。
マルチエージェント経路探索（MAPF）問題は、グラフ $G = (V, E)$、エージェントの集合 $\mathcal{A}$、および各エージェント $a_i \in \mathcal{A}$ に対する始点 $s_i$ と終点 $t_i$ によって定義される。解 $\pi$ は、各エージェントに $s_i$ から $t_i$ へ至る経路 $\pi_i$ を割り当てる写像であり、頂点衝突（ある時刻 $x$ において $\pi_i[x] = \pi_j[x]$ となる状態）およびスワッピング衝突（$\pi_i[x] = \pi_j[x+1]$ かつ $\pi_i[x+1] = \pi_j[x]$ となる状態）を回避する必要がある。評価指標として、全経路の長さの総和である Sum Of Costs (SOC) や、最長経路の長さである Makespan が用いられ、Conflict Based Search (CBS) はこれらに対して最適性を保証するが、Prioritized Planning (PrP) は保証しない。また、エージェントが目標に到達するたびに新たな目標が割り当てられる Lifelong MAPF (LMAPF) は、計画と実行を交互に繰り返すオンライン的な性質を持ち、一定時間内に目標に到達した回数を示すスループットによって性能が評価される。LMAPF の一般的な解法は、各計画期間において MAPF ソルバーを繰り返し呼び出し、エージェントの現在地から現在の目標までの経路を計算する手法である。
Lifelong Multi-Agent Path Finding (LMAPF) において、各計画期間ごとに MAPF 問題を逐次的に解く従来のアプローチは、エージェントの配置が特定の構成に依存するため、不完全なアルゴリズムとなる問題がある。この不完全性を緩和する手法として、ターゲット到達時に全エージェントが即座に再計画を行う動的再計画や、各エージェントにターゲットの順序を事前に割り当てる手法、ターゲット到達後に混雑を避けるためのダミーパスの導入などが提案されているが、計算コストの増大や新たな不完全性の発生、計画の困難化といった課題が残る。また、環境やタスクを修正してエージェントがターゲット上で滞在しやすくする well-formed instances や、将来 $w$ ステップ以降の衝突を無視する Rolling Horizon Collision Resolution (RHCR) のような限定的な計画ホライゾンを用いる手法も存在するが、これらはデッドロックや近視眼的な計画による非効率性を招く可能性がある。さらに、MAPF が解を見つけられなかった場合に備えた fail policies も提案されているが、これらはアドホックであり効率性に欠ける。本研究では、これらの間接的な緩和策とは異なり、各計画期間で解くべき MAPF 問題の形式そのものを直接的に変更することで、この不一致に対処する MAPF for Lifelong (MAPF4L) を提案する。
Lifelong Multi-Agent Path Finding (MAPF4L) は、各エージェント $a_i$ の経路 $\pi_i$ が目標地点 $t_i$ を通過することさえ満たせばよいという制約を持ち、従来の MAPF とは異なり、経路の終端が必ずしも $t_i$ である必要はありません。MAPF4L において、従来の Sum of Costs (SOC) や Makespan を用いると、スループットの指標と乖離が生じるため、本研究では Service Time（目標受領から初訪問までの経過時間）に基づく 2 つの新しいコスト関数を提案しています。一つは SST で、各エージェントが目標に初めて到達するまでのタイムステップの総和を $\text{SST}(\pi) := \sum (\min \{x \mid \pi_i[x] = t_i\} \mid \pi_i \in \pi)$ と定義し、もう一つは MKST で、全エージェントの中で目標への初到達時間が最大となるタイムステップを指します。具体例では、SOC や Makespan を最小化する解が、エージェントが目標に到達した後に不要な待機や移動を強いることで SST を増大させ、結果としてスループットを低下させる可能性があることが示されています。MAPF4L の最適解を求める問題は、一般的なコスト関数において MAPF と同様に NP-Hard であることが証明されています。
MAPF4L（Multi-Agent Path Finding with Lifetime constraints）を解く手法として、まずIterative MAPFを解くためのPriority Inheritance with Backtracking (PIBT) が挙げられるが、これはエージェントが目標に到達した後に新しい目標を割り当てず、最小の優先度を割り当てることでMAPF4Lへ適応可能である。しかし、PIBTの1ステップ先読みによる計画は、自動倉庫のような狭い通路が存在する複雑なシナリオでは効果が限定的となる。これに対し、PrP、LNS、CBSといったアルゴリズムをMAPF4Lに適用するため、A*探索における状態定義を、位置 $v$、時刻 $x$ に加え、目標を既に訪問したかを示すブール値 $b$ を含む $\langle v, x, b \rangle$ へと拡張する。このフラグ $b$ は、現在の状態が目標地点であるか、あるいは親の状態において $b$ が true であれば true となり、初期値は false である。探索においては、時刻と位置が同一であっても $b$ の値が異なる状態は、重複として破棄せずに異なる状態として区別して扱う必要がある。最終的なゴール状態の定義は、単に位置が目標と一致することではなく、$\langle v, x, \text{true} \rangle$ のように、目標を訪問した履歴を持つ状態に到達することへと変更される。
手作りのLMAPF（Lifelong Multi-Agent Path Finding）シナリオを用いた評価では、既存のMAPFアルゴリズム（PIBT, PrP, CBS）と、それらをLMAPF向けに拡張した提案手法（PrPL, CBSL）の比較が行われた。ケーススタディ1では、エージェントが特定の2点間を無限に往復する設定において、計画ホライゾンを10、実行時間を500ステップとした実験の結果、PrPLはPrPと比較して $A^*$ の展開回数を13,509回から11,965回へと削減し、実行時間も56msから50msへと短縮しつつ、PIBTを上回るスループット500を達成した。ケーススタディ2では、エージェントが互いにすれ違う必要があるシナリオにおいて、無限の計画ホライゾンを用いた実験を実施したところ、従来のMAPFソルバー（CBS, PrP）はスループットが250に留まったのに対し、MAPF4Lソルバー（CBSL, PrPL）はスループット499を記録し、実行時間においてもCBSの29,198msに対してCBSLは33msと劇的な高速化を実現した。ケーススタディ3では、標準的なMAPFベンチマークのグリッドを用い、計画ホライゾン $w=10$、計画間隔5ステップの設定で、ターゲット数を10から40の範囲で変化させて評価した。その結果、ターゲット数が限定的な高密度な環境において、例えば500エージェントと20ターゲットが存在する warehouse-20-40-10-2-1 シナリオでは、PrPLのスループット549はPrPのスループット491を上回り、LMAPF特有の課題に対して提案手法が有効であることが示された。
本研究では、Lifelong Multi-Agent Path Finding (LMAPF) 問題に対し、エージェントが目標地点に到達した後に留まる必要のない MAPF for Lifelong (MAPF4L) という一連の MAPF 変種を順次解く手法を提案した。これは、LMAPF の要件と従来の MAPF との間の不一致を解消するために必要であり、既存の MAPF アルゴリズムを MAPF4L へ適応させる手法を提示している。RHCR フレームワークを用いた評価の結果、病的なケースや目標地点の数が限られている状況において、MAPF4L は従来の MAPF 手法と比較してシステムスループットを向上させることが示された。今後の課題として、エージェントがタスク完了のために目標地点で一定時間滞在しなければならないような、より一般的なアプリケーションへの MAPF4L の拡張が挙げられる。