エージェント集合 $\mathcal{A}$ が共有グラフ上で衝突を回避しながら、連続的に発生するタスクのストリームを遂行する Lifelong Multi-Agent Pathfinding (L-MAPF) を対象とする。従来の Rolling-Horizon Collision Resolution (RHCR) は、各クエリを独立した問題としてゼロから解くため、連続するクエリ間で発生する開始・目標位置や衝突回避パターンの類似性を活用できていないという困難がある。
従来の RHCR が各クエリを独立して処理するのに対し、本研究は過去の MAPF クエリから得られた優先順位をシードとして次回の探索に転送する exRHCR を提案している。これにより、Priority-Based Search (PBS) の探索効率を向上させ、解を導くまでの時間を短縮できる点が新規性である。また、経験が不適切な場合に標準的な PBS へ切り替える幅制限付き深さ優先探索 (WL-DFS) を導入し、頑健性を確保している。
exRHCR は、各バッチの最初のクエリを PBS で解き、続くクエリに対しては経験に基づいた exPBS を用いる。exPBS は、前回の PBS で得られた優先順位集合 $\mathcal{P}_{\text{seed}}$ を優先度ツリー (PT) のルートノードの初期値として利用する。探索プロセスでは、PT の幅が指定された閾値 $W_{\text{limit}}$ を超えた場合や、ルートの優先順位が実行不能な場合には、通常の PBS へフォールバックする仕組みである。また、経験が過度に制約的になるのを防ぐため、experience lookahead $L$ 回ごとに新しい経験を生成する。
Warehouse および Sorting のベンチマーク環境において、エージェント数を変化させて RHCR と比較評価を行った。実験の結果、exRHCR は Warehouse で最大 $2.5\times$、Sorting で最大 $1.5\times$ の平均実行時間の短縮を実現した。パラメータ $L$ に関しては $L=1$ が最適に近い値であることが示され、探索の幅制限 $WL$ については、極端に小さい値ではフォールバックが頻発し、極端に大きい値では過剰な探索を招くという結果が得られた。なお、経験の再利用は解の品質やスループットには無視できる程度の影響しか与えず、効率性のみを向上させることが確認された。
エージェント数が少ない場合には、経験が不適切となり PBS へのフォールバック頻度が高まるというトレードオフが存在する。今後の課題として、パラメータの系統的な選択手法や、探索を終了・再開するための追加のヒューリスティックの検討が挙げられている。長期的には、類似クエリを検索するための経験データベースの構築や、学習ベースの手法を用いた経験の生成、および優先順位付きプランナーと exPBS を組み合わせた階層的な解決プロセスの拡張が期待される。
Lifelong Multi-Agent Path Finding (L-MAPF) において、エージェント群が共有グラフ上で衝突を回避しながら連続的なタスクを遂行する際、従来の Rolling-Horizon Collision Resolution (RHCR) のような手法では、各クエリを独立したものとしてゼロから解いており、連続するクエリ間の開始・目標位置や衝突回避パターンの類似性を活用できていない。本研究では、過去の MAPF クエリの経験を活用する exRHCR を提案し、その中核として Priority-Based Search (PBS) を拡張した exPBS を導入している。exPBS は、前回の MAPF インスタンスで使用されたエージェント間の優先順位を、次回の探索のウォームスタートとして利用することで、探索効率を向上させる手法である。実験の結果、exRHCR は RHCR と比較して L-MAPF インスタンスの解決速度を最大 39% 高速化し、一定の時間予算内で処理可能なエージェント数を増やすことで、タスクストリーム全体のシステムスループットを向上させる可能性を示した。
Lifelong Multi-Agent Pathfinding (L-MAPF) において、継続的に発生するタスクのストリームを効率的に解決するため、過去の解から得られた経験を活用する Experienced RHCR (exRHCR) アルゴリズムを提案している。従来の Rolling-Horizon Collision Resolution (RHCR) は、L-MAPF を一連の one-shot MAPF クエリに分割して解くが、本手法では各バッチの最初のクエリを Priority-Based Search (PBS) で解き、続くクエリには経験に基づいた Experienced PBS (exPBS) を用いることで、探索の効率化を図っている。exPBS は、前回の PBS で得られた優先順位集合を Priority Tree (PT) のルートノードの初期値として利用することで、探索木の深さを抑制し、解を導くまでの時間を短縮する。また、探索木の幅が制限を超えた場合やルートの優先順位が実行不能な場合には、通常の PBS をフォールバックとして使用する、幅制限付き深さ優先探索 (WL-DFS) を採用している。実験の結果、exRHCR は RHCR と比較して L-MAPF インスタンスの解決速度を最大 39% 向上させることが示されており、限られた時間予算内で処理可能なエージェント数を増加させることが可能である。
MAPFは、グラフ上のエージェント集合 $\mathcal{A}$ の各エージェントが、時刻 $t$ において頂点 $v_t$ に位置し、隣接する頂点への移動または待機を単位コストで行いながら、指定された始点 $s_i$ から終点 $g_i$ へ到達する経路集合 $\mathcal{P}$ を求める問題である。解の制約として、ある時刻 $t$ において複数のエージェントが同一の頂点を占有する頂点衝突、および時刻 $t$ と $t+1$ においてエージェントが同一の辺を逆方向に通過するエッジ衝突の回避が求められる。これに対し、Windowed-MAPFは、衝突回避の範囲を一定の窓幅 $w$ までの時刻 $t \le w$ に限定することで探索空間を削減する緩和手法である。Lifelong MAPF (L-MAPF) は、エージェントが連続するタスクのストリームを実行する設定であり、全タスクの完了時間の最小化、あるいは単位時間あたりのタスク完了数であるスループットの最大化を目的とする。L-MAPFの一般的な解決策として、タスクアサイナによって各エージェントの次なるタスクを決定し、一連のW-MAPF問題へと分割して逐次的に解くアプローチが用いられる。
本セクションでは、Lifelong Multi-Agent Pathfinding (L-MAPF) の基盤となる2つのアルゴリズム、Priority-Based Search (PBS) と Rolling-Horizon Collision Resolution (RHCR) について述べている。PBSは、エージェント間の優先順位を管理する優先度ツリー (PT) を探索する手法であり、各PTノードは優先順位集合 $\mathcal{P} = \{p_1, p_2, \dots, p_n\}$ を保持する。高レベル探索では、衝突が発生した際に優先順位を更新した2つの子ノードを生成し、深さ優先探索 (DFS) によって解を探索する。低レベル探索では、$\mathcal{P}$ に基づくトポロジカルソートを行い、高優先度のエージェントの計画を維持しつつ、低優先度のエージェントの計画を順次更新することで衝突を回避する。一方、RHCRはL-MAPFを、時間窓 $w$ と再計画レート $r$ を用いて一連の Windowed-MAPF (W-MAPF) クエリに分解して解くフレームワークである。RHCRは、あるクエリで得られた計画を $r$ ステップ分実行して次のクエリの開始位置を決定し、タスク割り当て器によって新たなゴールを設定する。実験的な知見として、RHCRの内部モジュールとしてPBSを用いる構成は、小さな時間窓 $w$ と再計画レート $r$ を設定することで、より多くのエージェントを含むクエリに対して高速な解を得られ、システムのスループットを向上させることが示されている。
Lifelong Multi-Agent Pathfinding (L-MAPF) において、連続する W-MAPF クエリ間の類似性を活用する Experienced RHCR (exRHCR) を提案している。exRHCR は、標準的な RHCR が各クエリをゼロから解くのに対し、PBS で得られた解から抽出した優先順位集合をシード優先順位集合 $\mathcal{P}_{\text{seed}}$ として、後続のクエリを解くための Experienced PBS (exPBS) を介して経験を転送する。exPBS は、探索の幅を制限する Width-Limited Depth-First Search (WL-DFS) を用いて優先順位木 (PT) の探索を行い、探索の幅が指定された閾値 $W_{\text{limit}}$ を超えた場合、あるいは解が見つからない場合には、経験が不適切であると判断して標準的な PBS へフォールバックする。経験の活用に関するパラメータとして、PBS の呼び出しごとに exPBS を実行する回数を示す experience lookahead $L$ と、PT の幅を制限する $W_{\text{limit}}$ が導入されており、経験が過度に制約的になるのを防ぐために $L$ 回ごとに新しい経験を生成する。また、代替手法として、すべてのエージェント間の優先順位を $\pi_i < \pi_j$ の形式で定義する total priority を用いる構成も提案されており、これは計算コストを抑えつつ、問題が容易な場合に高速な計画を可能にする。
提案手法であるexRHCRの性能を、倉庫（Warehouse）および仕分けセンター（Sorting）のベンチマーク環境を用いて、既存手法であるRHCRおよびexPBSと比較評価している。実験では、エージェント数をWarehouseで$N=180, 220$、Sortingで$N=150, 300$と変化させ、exRHCR（部分優先度を用いたexPBSベース）がRHCRと比較して、Warehouseで最大$2.5\times$、Sortingで最大$1.5\times$の平均実行時間の短縮を実現することを示した。特に、エージェント数が多い条件下では、exRHCRはRHCRや優先度計画を用いた手法よりも優れた性能を発揮するが、エージェント数が少ない場合は、フォールバック（PBSへの切り替え）の頻度が高まる傾向がある。また、経験の活用範囲を制御するlookaheadパラメータ $L$ について、提案手法はRHCRを全ての値で上回り、$L=1$ が最適に近い値であることが示された。さらに、探索の幅を制限するwidth limit $WL$ に関する評価では、極端に小さい $WL$ ではPBSへのフォールバックが頻発し、極端に大きい $WL$ では探索の過剰な拡大（overexploration）を招くため、適切な $WL$ の設定が実行時間と成功率のバランスにおいて重要であることが明らかになった。なお、経験の再利用は解の品質（solution cost）やスループットに無視できる程度の影響しか与えず、効率性のみを向上させることが確認された。
本論文では、Lifelong Multi-Agent Pathfinding (L-MAPF) において、過去のクエリから得られた優先順位集合を再利用することで計算コストを削減する手法である exRHCR を提案している。実験により、この手法が実行時間を大幅に短縮し、追加のエージェントを導入することでシステムのスループットを向上させる可能性が示された。今後の課題として、パラメータの系統的な選択手法や、exPBS の探索を終了・再開するための追加のヒューリスティックの検討が挙げられている。長期的には、類似したクエリを検索するための「経験データベース」の構築や、学習ベースの手法を用いて類似クエリの特定および経験の人工的な生成を行う戦略が期待される。また、提案手法を階層的なアプローチへと拡張する構想もあり、まず優先順位付きプランナーを用いて計算を行い、失敗した場合には exPBS によるウォームスタートを試み、それでも解決できない場合にのみ PBS へとフォールバックする階層的な解決プロセスが検討されている。