本研究は、エージェントがタスク完了後に即座に新しい目標を与えられる Lifelong Multi-Agent Pathfinding (LMAPF) 設定を対象としている。LMAPF の主要な評価指標は、一定期間内に完了できるタスク数を示すスループットである。既存の Prioritized Planning や LNS2 などの手法では、将来の混雑を予測して回避することが困難であった。本研究では、人工ポテンシャル場 (APF) を用いて、他エージェントの経路から距離を保つようなコストモデルを構築し、オンラインの調整効率を高めることを目的としている。
既存の経路探索アルゴリズムに APF を統合する汎用的なフレームワークを提案し、$\text{TA}^*\text{+APF}$、$\text{SIPPS+APF}$、および $\text{PIBT+APF}$ を導入した。APF を $h$-inspired（ヒューリスティックへの加算）ではなく、$g$-inspired（累積コストへの加算）として用いることで、回避性能を直接的に向上させる手法を確立した。実験により、高密度な環境においてタスク完了率を最大7倍向上させることが示された。また、APF が $\text{TA}^*$、$\text{SIPPS}$、$\text{PIBT}$、$\text{LaCAM}$ といった多様なアルゴリズムに統合可能であることを実証した。
$\text{TA}^*\text{+APF}$ では、他エージェントの経路 $\pi_i$ に対する斥力 $APF_i(v, t)$ を、距離 $d(v, \pi_i[t]) < d_{max}$ の場合に $w \cdot \gamma^{-d(v, \pi_i[t])}$、それ以外で $0$ と定義し、全エージェントの和 $APF(v, t) = \sum_{i=1}^{k'} APF_i(v, t)$ を用いる。経路選択には、APF を累積する $g$-inspired な手法 $aggAPF(n) = aggAPF(p) + APF(v, t)$ を採用している。$\text{SIPPS+APF}$ では、安全な時間間隔における最大 APF 値 $APF(n) = \max_{t \in [t_{nstart}, t_{nend}), i} APF_i(v, t)$ を用いて、ソフト制約違反数 $cAPF(n)$ と累積 APF コスト $gAPF(n)$ を更新し、Open List のソートに利用する。$\text{PIBT+APF}$ では、現在の時刻 $t_{curr}$ から $t_{max}$ ステップ先までの $\text{APF}_i(v) = \sum_{j=t_{curr}}^{t_{curr}+t_{max}} \text{APF}_i(v, j)$ を構築し、隣接頂点の評価値を $h(v) + \text{APF}(v)$ としてソートする。
LMAPF ベンチマークの4種類のマップを用い、エージェント数を50から450の範囲で評価した。実験では、APF のパラメータとして $d_{max}, \gamma, t_{max}, w$ を使用し、ウィンドウサイズおよびプランニングホライゾンは $5$ に設定している。$\text{PIBT+APF}$ は、既存の $\text{L-PIBT+GP}$ を上回り、元の $\text{PIBT}$ を大幅に改善する性能を示した。また、$\text{SIPPS+APF}$ の計算オーバーヘッドは $O(k \cdot d_{max}^2 \cdot l^2)$、$\text{PIBT+APF}$ の全エージェントに対するオーバーヘッドは $O(k \cdot (d_{max})^2 \cdot l)$ である。
提案手法は、APF を他のアルゴリズムへも統合可能であるという高い汎用性を示している。実験過程において、$\text{SIPPS}$ を用いた $\text{LNS2}$ よりも $\text{A}^*$ を用いた $\text{LNS2}$ の方が優れた性能を示すという、経路の短さの優先度に関する興味深い現象が観察された。これは、APF による混雑回避と経路の最適性のトレードオフを示唆している。高密度な環境において APF を導入することは、スループットの向上に極めて有効である。
本研究は、Lifelong Multi-Agent Pathfinding (LMAPF) において、人工ポテンシャル場 (APF) を用いてオンラインの調整効率を向上させる手法を提案している。LMAPFは、エージェントがタスク完了後に即座に新しい目標を与えられる設定であり、システムのスループット（一定期間内のタスク完了数）が評価指標となる。提案手法は、既存の協調アルゴリズム（Prioritized Planning, LNS2など）のコストモデルにAPFを組み込み、将来の混雑を回避するようにエージェントの経路選択を促すものである。具体的には、Temporal A* や SIPPS を拡張した $\text{TA}^*\text{+APF}$ および $\text{SIPPS+APF}$ を導入しており、これらは他のエージェントの経路 $\pi_1, \dots, \pi_{k'}$ と衝突を避けつつ、APFの斥力に基づいてそれらから距離を保つ経路を生成する。実験の結果、高密度な環境において、APFを統合することでタスク完了率が最大で7倍向上することが示された。
本セクションでは、Lifelong Multi-Agent Path-finding (LMAPF) において、人工ポテンシャル場 (APF) を用いて他エージェントとの距離を保つ手法 $TA^*+APF$ および $SIPPS+APF$ が提案されている。$TA^*+APF$ では、他エージェントの経路 $\pi_i$ に対する斥力関数 $APF_i(v, t)$ を、距離 $d(v, \pi_i[t])$ が $d_{max}$ 未満の場合に $w \cdot \gamma^{-d(v, \pi_i[t])}$、それ以外で $0$ と定義し、全エージェントの和 $APF(v, t) = \sum_{i=1}^{k'} APF_i(v, t)$ を用いてコストを計算する。この APF を $f$-値に加算する $h$-inspired な手法は探索速度に影響するのみで効果が低かったが、経路に沿って APF を累積する $g$-inspired な手法（$aggAPF(n) = aggAPF(p) + APF(v, t)$）は、他エージェントを回避する経路の選択に直接寄与する。また、ソフト制約を扱う $SIPPS+APF$ では、安全な時間間隔における最大 APF 値 $APF(n) = \max_{t \in [t_{nstart}, t_{nend}), i} APF_i(v, t)$ を用いて、ソフト制約違反数 $cAPF(n)$ と累積 APF コスト $gAPF(n)$ を更新し、これらに基づいて Open List をソートする。$SIPPS+APF$ の計算オーバーヘッドは $O(k \cdot d_{max}^2 \cdot l^2)$ であり、元の $TA^*$ や $SIPPS$ の時空間情報を維持しつつ、APF を優先度計算に組み込むことで回避性能を高めている。
本セクションでは、Lifelong Multi-Agent Path-finding (LMAPF) において、人工ポテンシャル場 (APF) を用いてエージェントを混雑回避へと誘導する手法が提案されている。PIBT+APF では、各エージェント $i$ が現在の時刻 $t_{curr}$ から $t_{max}$ ステップ先までの最適経路に基づき、式 $\text{APF}_i(v) = \sum_{j \in \{t_{curr}, \dots, t_{curr}+t_{max}\}} \text{APF}_i(v, j)$ を用いて APF を構築し、隣接頂点 $v$ の評価値を $h(v) + \text{APF}(v)$ （ここで $\text{APF}(v) = \sum_{i \in \{1, \dots, k'-1\}} \text{PIBT APF}_i(v)$）としてソートすることで、混雑を避ける行動を選択させる。APF の計算に伴う計算量は、1エージェントあたり $O((d_{\max})^2 \cdot l)$ （$d_{\max}$ は影響を受ける最大ノード数、$l$ は最長経路長）であり、全 $k$ エージェントに対して $O(k \cdot (d_{\max})^2 \cdot l)$ のオーバーヘッドが発生する。実験では LMAPF ベンチマークの4種類のマップを用い、エージェント数を50から450の範囲で評価した結果、PIBT+APF を含む APF 導入手法は、TA*、SIPPS、PIBT、LaCAM などの既存アルゴリズムにおいて、スループットを大幅に向上させることが示された。特に PIBT+APF は、既存の L-PIBT+GP を上回り、元の PIBT を大幅に改善する性能を示した。一方で、SIPPS を用いた LNS2 よりも A* を用いた LNS2 の方が優れた性能を示すという、経路の短さの優先度に関する興味深い現象も観察されている。
本研究では、RHCRフレームワークを用いてLifelong Multi-Agent Path Finding (LMAPF) 問題を解決しており、人工ポテンシャル場 (APF) を $TA^*$、$SIPPS$、および $PIBT$ といった既存のアルゴリズムに統合する手法を提案している。実験設定において、APFのパラメータとして $d_{\max}$、$\gamma$、$t_{\max}$、$w$ が用いられ、さらにウィンドウサイズおよびプランニングホライゾンは $5$ に設定されている。提案手法は、APFを他のアルゴリズムへも統合可能であるという汎用性を示唆している。