本研究は、自動倉庫のような実用的な環境での継続的な運用（lifelong basis）を想定した、反復的なマルチエージェント経路計画（MAPF）およびマルチエージェント・ピックアップ＆デリバリー（MAPD）を対象としている。従来の探索ベース（$A^*$やCBS）やコンパイルベース（SATやILP）の手法は、数百規模のエージェントを扱うオンライン・生涯運用シナリオでは計算コストが極めて高いという課題があった。これに対し、本研究はエージェントの動的な増減や新しい目的地への継続的な割り当てに対応可能な、スケーラブルかつ逐次決定型のアルゴリズムを求めている。
提案手法であるPriority Inheritance with Backtracking (PIBT) は、エージェント間の局所的な相互作用に焦点を当てた適応的な優先順位付けスキームを提供し、計算時間が予測可能でスケーラブルな特性を実現している。理論面では、グラフ $G$ が二重連結（biconnected）である場合、エージェント数に関わらず、すべてのエージェントが有限時間内に目的地へ到達する「到達可能性（reachability）」を証明した。実験的には、1,000体のエージェントが存在する大規模なグリッドマップ（$530 \times 481$）において、平均的な劣最適度を 1.5 未満に抑えつつ、5秒以内という極めて高速な実行時間を達成した。さらに、実ロボットを用いたデモンストレーションを通じて、実用的な環境における有効性を実証している。
PIBTは、各タイムステップにおいてエージェントの優先度 $p_i$ を動的に更新する中央集権的アルゴリズムである。目標に未到達のエージェントは優先度をインクリメントし、到達済みのエージェントは $\epsilon_i \in [0, 1)$ にリセットすることで、停滞を防ぐ。核心となる再帰関数 `PIBT(ai, aj)` は、エージェント $a_i$ が目標に近い隣接ノード $v$ を選択する際、そのノードを占有しているエージェント $a_k$ に対して優先度を継承させ、もし $a_k$ が移動不能（invalid）であれば $a_i$ は別のノードを再計画（replanning）する。このバックトラッキングプロトコルにより、優先度逆転によるデッドロックを回避し、安全な「push」操作の組み合わせとして衝突のない配置を決定する。1タイムステップあたりの計算量は $O(|A| \cdot (\Delta(G) + F + \log |A|))$ であり、ここで $|A|$ はエージェント数、$\Delta(G)$ はグラフの最大次数、$F$ は候補ノードのソートコストを表す。
評価はMAPFとMAPDの両方の文脈で行われた。MAPFの実験では、4連結グリッドを用いたベンチマークにおいて、HCA*、EECBS、CBS、BCPなどの既存手法と比較した。評価指標には、成功率、実行時間、および下界を用いた解の品質指標である $\text{sum-of-costs} / \sum_{i \in A} \text{dist}(s_i, g_i)$ と $\text{makespan} / \max_{i \in A} \text{dist}(s_i, g_i)$ が用いられた。MAPDの実験では、タスク頻度を0.2から10まで変化させた設定でToken Passing (TP) アルゴリズムと比較し、1ステップあたりの実行時間、サービス時間、makespanの観点から優位性を検証した。結果として、PIBTは既存手法では解決困難な大規模インスタンスを迅速に解決し、MAPDにおいても実行時間と解の質の両面で優位性を示した。
PIBTの主な限界として、失敗の原因が主にmakespan制限に起因することが挙げられる。これはグラフの到達可能性や閉路の欠如に依存する問題であり、補完ソルバーを用いた「PIBT+」を用いることで成功率を大幅に向上させることが可能である。また、本手法は全エージェントが同時に目的地に到達することを保証するものではなく、あくまで生涯運用シナリオに適した設計となっている。今後の課題として、現在の同期的な設定から、実環境におけるエージェント間の非同期性を考慮した「wild」な環境への拡張が挙げられている。
本研究では、自動倉庫などの実用的な環境における継続的な運用（lifelong basis）を想定した、反復的なマルチエージェント経路計画（MAPF）のための新しい劣最適アルゴリズムであるPriority Inheritance with Backtracking (PIBT) を提案している。PIBTは、複数のエージェントの隣接する移動に焦点を当てる適応的な優先順位付けスキームに依存しており、計算時間が予測可能でスケーラブルな特性を持つ。理論面では、グラフのすべての隣接ノードのペアが単純なサイクルに属する場合（例：二重連結グラフ）、エージェントの数に関わらず、すべてのエージェントが有限時間内に目的地に到達することを証明している。実験では、実ロボットを用いたデモンストレーションを含む様々なシナリオにおいて、数百規模のエージェントに対しても即座に許容可能な解を生成し、既存手法では解決困難な大規模インスタンスを解けることを示した。さらに、自動倉庫における荷物搬送の反復シナリオにおいて、PIBTは既存手法と比較して実行時間と解の質の双方で優位性を示すことが確認された。
本研究では、Lifelong MAPF（Multi-Agent Path Finding）やMAPD（Multi-Agent Pickup and Delivery）のような、エージェントが継続的に新しい目的地を受け取る反復的なシナリオに対応可能な、スケーラブルな逐次決定型アルゴリズムであるPriority Inheritance with Backtracking (PIBT) を提案している。PIBTは、低優先度エージェントがより高優先度なエージェントの移動を妨げる際に、一時的にその優先度を継承させる仕組みとバックトラッキングプロトコルを組み合わせることで、エージェントの停滞を防ぎつつ、グラフが二重連結（biconnected）であれば有限時間内に目的地への到達（reachability）を保証する。各タイムステップにおける計算量は $O(|A| \cdot (\Delta(G) + F + \log |A|))$ であり、ここで $|A|$ はエージェント数、$\Delta(G)$ はグラフ $G$ の直径、$F$ は目的地までの距離評価コストを表す。実験では、1,000体のエージェントが存在する大規模なグリッドマップ（$530 \times 481$）において、平均的な劣最適度を 1.5 未満に抑えつつ、5秒以内という極めて高速な実行時間を達成しており、既存の優先度ベースや探索ベースの手法を大幅に上回る性能を示している。PIBTは局所的な相互作用のみに依存するため分散実装の可能性が高く、実世界の自動倉庫のような動的な環境における実用的な解法として位置付けられている。
MAPFは、グラフ上の各エージェントに衝突のない経路を割り当てる問題であり、NP困難であることが知られている。既存手法は、探索ベース（$A^*$やCBSなど）、コンパイルベース（SATやILPなど）、優先順位付き計画、ルールベース、学習ベースの5種に分類され、前者の多くは完全かつ最適であるが、数百規模のエージェントを扱うオンライン・生涯運用シナリオでは計算コストが課題となる。提案手法であるPIBTは、優先順位付き計画とルールベースを組み合わせた手法であり、動的な優先順位とバックトラッキングを用いることで、単一エージェントまたはペアの移動に限定される従来のPush and Swap（PS）とは異なり、安全な「push」操作の組み合わせとして機能する。PIBTは、全エージェントが最終的に目的地に到達することを保証するものの、全エージェントが同時に目的地に到達することを保証しないため、従来の「one-shot」シナリオにおける完全性とは異なり、生涯運用（lifelong）シナリオに適した設計となっている。また、PIBTは1ステップごとの計画を繰り返す性質を持つため、エージェントが動的に増減するオンラインMAPFへの適応も容易である。
本セクションでは、従来のone-shot MAPF問題と、オンライン・生涯継続的なシナリオを扱うMAPD問題の定式化がなされている。MAPFは、有向グラフ $G = (V, E)$、エージェント集合 $A = \{a_1, \dots, a_n\}$、および単射な初期状態関数 $s$ と目標状態関数 $g$ によって定義され、各エージェント $a_i$ は時刻 $t$ において $\pi_i[t+1] \in \text{Neigh}(\pi_i[t]) \cup \{\pi_i[t]\}$ の範囲で移動する。解は、頂点衝突（$\exists i, j, i \neq j, \pi_i[t] = \pi_j[t]$）およびスワップ衝突（$\exists i, j, i \neq j, \pi_i[t] = \pi_j[t+1] \land \pi_i[t+1] = \pi_j[t]$）を回避する一連の経路の集合であり、評価指標には合計コスト $\sum_{a_i \in A} T_i$ とメイクスパン $T$ が用いられる。MAPDは、タスクのストリーム $\Gamma = \{\tau_1, \tau_2, \dots\}$ が与えられ、各タスク $\tau_j = (v_{\text{pickup}}, v_{\text{delivery}})$ をエージェントが順に訪問することで完了する問題であり、タスクが動的に追加される状況を含む。MAPDの目的関数は、サービス時間または（$\Gamma$ が有限の場合の）メイクスパンであり、解は衝突のない経路とタスク割り当ての組み合わせとして定義される。
PIBT（Priority Inheritance with Backtracking）は、反復的なマルチエージェント経路探索（MAPF）を解くための、優先度継承とバックトラッキングを組み合わせた中央集権的アルゴリズムである。各タイムステップにおいて、エージェントは目標に未到達であれば優先度 $p_i$ をインクリメントし、目標到達済みであれば $\epsilon_i \in [0, 1)$ にリセットすることで、動的な優先順位付けを行う。アルゴリズムの核心である再帰関数 `PIBT(ai, aj)` は、エージェント $a_i$ が目標に近い隣接ノード $v \in C$ を選択する際、そのノードを占有しているエージェント $a_k$ に対して優先度を継承させ、もし $a_k$ が移動不能（invalid）であれば $a_i$ は別のノードを再計画（replanning）する。この仕組みにより、優先度逆転によるデッドロックを回避しつつ、バックトラッキングを通じて衝突のない次ステップの配置を決定する。理論的には、グラフ $G$ が隣接するノード間に単純閉路を持つ条件（例：二連結グラフ）を満たす場合、すべてのエージェントが最終的に目標に到達する「到達可能性（reachability）」が保証される。1タイムステップあたりの計算量は $O(|A| \cdot (\Delta(G) + F + \log |A|))$ であり、ここで $|A|$ はエージェント数、$\Delta(G)$ はグラフの最大次数、$F$ は候補ノードのソートに要する時間である。
本セクションでは、提案手法であるPIBT（Priority Inheritance with Backtracking）の迅速性とスケーラビリティ、および解の品質をMAPF（Multi-Agent Path Finding）とMAPD（Multi-Agent Pickup and Delivery）の文脈で評価している。MAPFの実験では、4連結グリッドを用いたベンチマークにおいて、HCA*、EECBS、CBS、BCPなどの既存手法と比較し、PIBTが1000エージェント規模でも5秒以内で解を出力できる極めて高いスケーラビリティを持つことを示した。評価指標には、成功率、実行時間、および下界を用いた解の品質指標である $\text{sum-of-costs} / \sum_{i \in A} \text{dist}(s_i, g_i)$ と $\text{makespan} / \max_{i \in A} \text{dist}(s_i, g_i)$ が用いられている。PIBTの失敗原因は主にmakespan制限によるものであり、これはグラフの到達可能性や閉路の欠如に起因するが、補完ソルバーを用いたPIBT+により成功率を大幅に向上させることが可能である。MAPDの実験では、タスク頻度を0.2から10まで変化させた設定でToken Passing (TP) アルゴリズムと比較し、1ステップあたりの実行時間、サービス時間、makespanの観点からPIBTの優位性を検証している。
本研究では、MAPF（Multi-Agent Path Finding）を反復的に解くためのスケーラブルなアルゴリズムであるPIBTを提案しており、エージェント間の隣接移動に焦点を当てた単純な優先順位付けスキームを用いることで、オンラインやライフロングな状況への適用を可能にしている。実験結果により、PIBT(+)は他のソルバーが膨大な計算時間を要する大規模なMAPFインスタンスを迅速に解決できること、MAPD（Multi-Agent Pickup and Delivery）において既存手法を上回ること、そして数千規模のエージェントに対してもリアルタイムな計画立案が可能であることが示され、さらに実ロボットによる実行も実証された。本手法は実用的なスウォーム制御に寄与する知見を提供するが、今後の課題として、従来の同期的な設定から、実環境におけるエージェント間の非同期性を考慮した「wild」な環境への拡張が挙げられる。
PIBT+はPIBTとどう違う？どうやって成功率を向上した？
PIBT+とPIBTの違い、および成功率の向上方法については以下の通りです。
PIBTとPIBT+の違い
PIBT+は、PIBTに「補完的なソルバー（complement solver）」を追加したものです（Section 5.1.1）。PIBT単体では、グラフにサイクルが存在しない場合や、すべてのエージェントが同時にゴールに到達することを保証しない（reachabilityのみを保証する）性質があるため、失敗することがあります（Section 4.3.1, 5.1.2）。PIBT+は、このPIBTの欠点を補うために設計されています。
成功率の向上方法
PIBT+は、PIBTの解を補完するために別のソルバーを用いることで、成功率を劇的に向上させています（Section 5.1.2）。
補完ソルバーは具体的にどのような処理を行う？makespan制限とは何？
ご質問いただいた点について、論文の記述に基づき回答します。
補完ソルバーの具体的な処理について
論文内では、補完ソルバーが具体的にどのような計算アルゴリズムや内部処理を行うかについての詳細な記述はありません。
ただし、実験設定（Section 5.1.1）において、PIBT+は「PIBTの解を補完するために（to complement the solutions of PIBT）」別のソルバーを用いるとされており、実験では「PS+（Push and Swapの拡張版）」が使用されています。また、混雑した状況では、PIBTが解を見つけられず、補完ソルバーであるPS+が使用されることで解の質が低下する場合があることが述べられています（Section 5.1.2）。
makespan制限について
makespan制限とは、アルゴリズムが解を出す際に許容される「最大経過時間（タイムステップ数）」の閾値のことです。論文では、以下の文脈で使用されています。