Multi-Agent Path Finding (MAPF) において、既存の高速なルールベース手法である Priority Inheritance with Backtracking (PIBT) は、高優先度エージェントが一度に衝突できる対象を1体に限定するという根本的な限界がある。この制約により、一つの高優先度エージェントの経路が複数の低優先度エージェントと連鎖的に衝突するような、複雑なマルチステップの行動シーケンスを直接計画することができない。本研究は、空間・時間制約ではなく、エージェント間の「依存関係（agent dependencies）」を探索対象とする新しいアプローチを導入する。対象とする問題設定には、総コスト $\sum c$ を最小化するone-shot MAPFと、スループット $\theta$ を最大化するlifelong MAPFが含まれる。
提案手法である MD-PIBT は、エージェント間の依存関係を管理するエージェント依存グラフ (Agent Dependency Graph, AgDG) を用いた汎用的な計画フレームワークである。この手法は、特定のハイパーパラメータ設定を通じて PIBT や EPIBT を完全に再現できる柔軟性を持ち、既存手法の限界であった「単一の衝突対象」という制約を打破している。特に、エージェントのサイズが大きい PMLA (Pebble Motion with Large Agents) 設定において、MD-PIBT は EPIBT を大幅に上回る成功率を達成した。また、最悪計算量の理論的解析を行い、再計画回数 $K$ に基づく計算量境界 $O(nKp)$ を導出している。
MD-PIBT は、各エージェントが保持する $k$-step パスの集合と、優先度付きキュー $\mathcal{Q}$ を用いて依存関係を解消していく。依存関係は、未計画エージェントの安全なパスと衝突する「ハード依存関係」と、計画済みエージェントの暫定パスと衝突する「ソフト依存関係」に分類される。アルゴリズム内の `findBestPath` 関数は、予約テーブルを用いて衝突するエージェントの集合 $\mathcal{C}$ を特定し、そのサイズ $|\mathcal{C}|$ が最大衝突許容数 $k_{max}$ を超えない経路を選択する。有効なパスが見つからない場合、ハイパーパラメータ関数 $\text{fallToSafePath}$ に基づき、「安全なパスへの退避」または「親エージェントへの再計画要求」を選択することで、計算量の爆発を防ぐ設計となっている。
実験では、Pebble Motion (PM)、PMLA、Rotation Motion (RM)、および Differential Drive Robots (DDR) の各動的モデルを用いて検証が行われた。One-shot 実験において、PMLA モデルでは MD-PIBT が EPIBT を大幅に上回る成功率を示し、大きなエージェントが周囲の小さなエージェントを押し退けてデッドロックを回避できることが示された。Lifelong 実験では、スループットと実行時間を指標とし、PM では PIBT 的な設定、RM や DDR では EPIBT 的な設定が優れた性能を示すことを確認した。実験設定として、One-shot では Python を用い、PMLA では 3,600 秒のタイムリミット内で 25 インスタンスの平均と 95% 信頼区間を算出している。
MD-PIBT は、エージェントのサイズが大きい複雑な MAPF 設定において顕著な有効性を発揮する一方で、one-shot や lifelong MAPF の標準的な設定では、既存の PIBT や EPIBT の性能を再現するに留まる。最悪計算量については、再計画回数を $K$ とした場合に $O(nKp)$ となることが示されており、これは各エージェントが $K$ 回の失敗後に安全な経路を選択するという制約に基づいている。今後の展望として、学習ベースのマルチステップ MAPF ポリシーに対する衝突回避シールド (collision-shield) としての活用や、低レベル探索に依存しない特性を活かしたマルチロボットプロトコルへの発展が挙げられている。
本研究では、従来の Priority Inheritance with Backtracking (PIBT) や Enhanced PIBT (EPIBT) が、一度に衝突するエージェントを最大1体に制限するというルールベースの制約により汎用性に欠けるという課題に対し、エージェント間の依存関係（agent dependencies）に着目した新しい手法である Multi-Dependency PIBT (MD-PIBT) を提案している。MD-PIBT は、特定のパラメータ設定によって PIBT や EPIBT を再現できるだけでなく、複数のエージェントと衝突する経路を考慮できるマルチステップ計画への拡張を可能にする汎用的なフレームワークである。実験では、pebble motion、rotation motion、および速度・加速度制限を持つ differential drive robot といった様々な運動学的制約下において、最大 10,000 体の均質エージェントに対する効果的な計画能力が示されている。特に、エージェントのサイズが大きい MAPF 設定において MD-PIBT は顕著な有効性を発揮することが評価により明らかになった。
Multi-Agent Path Finding (MAPF) において、既存の高速な手法である Priority Inheritance with Backtracking (PIBT) は、高優先度エージェントと低優先度エージェント間の依存関係を一度に一つしか考慮できないという根本的な限界がある。このため、一つの高優先度エージェントの経路が複数の低優先度エージェントと衝突するようなマルチステップの行動シーケンスを直接計画することができない。本研究では、空間・時間制約ではなくエージェント間の依存関係を探索対象とする Multi-Dependency PIBT (MD-PIBT) を提案し、複数の依存関係を扱う汎用的なフレームワークを構築する。MD-PIBT は、特定のインスタンス化によって PIBT や EPIBT を再現可能な汎用アルゴリズムであり、複数のハイパーパラメータの最適化が可能である。実験の結果、MD-PIBT は大型エージェント（large agents）を扱う MAPF のバリエーションにおいて PIBT や EPIBT を大幅に上回る性能を示したが、one-shot や lifelong MAPF などの他の設定では、PIBT や EPIBT の性能を再現するに留まった。
MAPFは、エージェント集合 $\mathcal{A}$ が各々の開始地点から目標地点へ衝突を回避して移動する問題であり、頂点衝突およびエッジ衝突を回避する経路集合を求める。本稿では、Pebble Motion (PM)、PMLA、Rotation Motion (RM)、およびDifferential Drive Robots (DDR) の動的モデルを考慮し、総コスト $\sum c$ を最小化するone-shot MAPFと、スループット $\theta$ を最大化するlifelong MAPFを対象とする。既存手法として、CBSのような探索ベース、PPやPBSのような優先度ベース、および学習ベースがあるが、大規模なシナリオではルールベースの手法が求められる。最先端のルールベース手法であるPIBTは、高優先度エージェントが低優先度エージェント $a_j$ と衝突する場合に $a_j$ の優先度を一時的に継承する1ステップの計画アルゴリズムであり、数百のエージェントを200ms未満で処理できる極めて高い速度を持つ。しかし、PIBTやその拡張であるEPIBT、HetPIBTは、1つの経路が衝突を起こす対象を最大1つのエージェントに限定しており、複数のエージェントと衝突する多段階の経路を考慮できないという限界がある。本研究は、この制限を打破するために、複数の依存関係を扱うMulti-Dependency PIBTを導入することを目的としている。
本セクションでは、PIBT（Priority Inheritance Backtracking）をエージェント間の依存関係を推論する手法として再定義している。各エージェント $i$ は、計算中の暫定的な経路 $p_i$ と、全エージェント間で衝突のない安全な経路 $s_i$（初期状態では待機行動 $s_i = \text{wait}$）を持つ。エージェント $i$ の暫定経路がエージェント $j$ の安全経路と衝突する場合、エージェント $i$ は $j$ に対して依存関係を持つと定義され、その $j$ が計画済みか否かによって、ハード依存関係（$j \in \text{Planned}$）とソフト依存関係（$j \notin \text{Planned}$）に分類される。これに基づき、エージェントをノード、依存関係を有向エッジとするエージェント依存グラフ（Agent Dependency Graph, AgDG）が構成されるが、PIBTにおいて各エージェントの経路は1ステップであるため、AgDGは連結リストの構造をとる。PIBTのアルゴリズムは、優先度の高いエージェントから順に、依存関係にあるエージェントが衝突のない経路を見つけるまで計画を連鎖的に進めることで、全エージェントの経路決定を行う。
MD-PIBTは、衝突のない$k$-stepパスを生成するマルチエージェント経路計画（MAPF）アルゴリズムであり、エージェント間の依存関係を管理するエージェント依存グラフ（AgDG）を用いて計画を行う。各エージェントは、ゴールへの距離が近い順にソートされた$k$-stepパスの集合を保持し、優先度付きキュー $\mathcal{Q}$ を用いて依存関係の解消が必要なエージェントを順次処理する。依存関係には、未計画エージェントの安全なパス（safe path）と衝突する場合に発生するハード依存関係と、既に計画済みのエージェントの暫定パス（tentative path）と衝突する場合に発生するソフト依存関係の2種類が存在する。有効なパスが見つからない場合、エージェントは「安全なパスへの退避（falling to safe path）」または「親エージェントへの再計画要求（attempting to replan）」のいずれかを選択する。この選択はハイパーパラメータ関数 $\text{fallToSafePath}$ によって制御され、再計画の連鎖による指数関数的な計算量爆発を防ぐ役割を果たす。また、$\text{findBestPath}$ 関数における有効なパスの定義や、再計画を要求する親の選択 $\text{chooseParent}$ など、複数のハイパーパラメータを通じてPIBTやEPIBTといった既存手法を包含する柔軟な設計となっている。
本実験では、提案手法であるMD-PIBTの有効性を、One-shotおよびLifelong MAPFの文脈で、PM（Pebble Motion）、PMLA（Pebble Motion with Large Agents）、RM（Rectangle Motion）、DDR（Dynamic Disk Robots）の各エージェントモデルを用いて検証している。One-shot実験において、PMLAモデルではMD-PIBTがEPIBTを大幅に上回る成功率を示し、これはEPIBTが依存関係を $k=1$ に制限されているのに対し、MD-PIBTは $k > 1$ を許容することで、大きなエージェントが周囲の小さなエージェントを押し退けてデッドロックを回避できるためである。Lifelong実験では、スループットと実行時間を評価指標とし、優先順位付けとしてLET（Longer Elapsed Time）とSD（Shorter Distance）を比較している。PMエージェントを用いた実験では、特定の条件下でPIBTのSD優先順位が優れた性能を示す一方、RMおよびDDRエージェントを用いた実験では、EPIBTまたはそれを再現したMD-PIBTが最良の性能を維持することが確認された。実験設定として、One-shotではPythonを用い、PMは1,800秒、PMLAは3,600秒のタイムリミットを設けて25インスタンスの平均と95%信頼区間を算出している。
本研究では、エージェント間の依存関係を探索する汎用的なフレームワークとして MD-PIBT を提案しており、従来の PIBT や EPIBT が持っていた「最大で1つの他のエージェントとしか衝突しない経路しか考慮できない」という制約を解消している。実験の結果、MD-PIBT は one-shot および lifelong MAPF 設定において PIBT/EPIBT と同等の性能を示す一方で、エージェントのサイズが大きい MAPF 設定においてはこれらを大幅に上回る性能を達成した。今後の展望として、学習ベースのマルチステップ MAPF ポリシーに対する衝突回避シールド（collision-shield）としての活用や、CBS と同様に低レベル探索に依存しない特性を活かしたマルチロボットプロトコルへの発展が挙げられている。
Algorithm 5 に示される `findBestPath` 関数は、Algorithm 3 で使用され、指定された `find path mode` に基づいて、他のエージェントと衝突しない有効な経路をエージェント $a$ に対して探索する。まず、暫定的な経路を持つ全エージェントを特定し、各エージェント $a_i$ の最新の経路（暫定経路の場合は $\mathcal{P}_{tentative}$、それ以外は $\mathcal{P}_{safe}$）からなる予約テーブルを構築する。次に、現在の経路インデックスから候補経路を順次走査し、その候補経路と衝突するエージェントの集合 $\mathcal{C}$ を取得する。候補経路の妥当性は、$\mathcal{C}$ に含まれるエージェントの数 $|\mathcal{C}|$ が最大衝突許容数 $k_{max}$ を超えないこと、および `find path mode` に応じた制約を満たすことで判定される。具体的には、モードが $k_{max} > 0$ の場合は $\mathcal{C}$ のエージェントの最新経路と衝突しないことが条件となり、モードが $k_{max} = 0$ の場合は、(1) 現在の MDPIBT 関数呼び出し内で暫定経路を持つエージェント、(2) より高い優先度を持つエージェント、(3) 再計画の試行回数が残っていないエージェントのいずれとも衝突しないことが要求される。有効な経路が見つかればそれを返し、見つからない場合は失敗を返す。
MD-PIBTの最悪計算量について、各エージェント $i$ が持つ長さ $w$ の全経路集合 $\mathcal{P}_i$ のサイズを $p = a^w$（$a$ は離散アクション数）とし、エージェント数 $n$、最大再計画回数 $K$ と定義して解析している。Theorem 1および2によれば、$K$ が十分に大きい場合、MD-PIBTは各経路の組み合わせ $\mathcal{P} = \mathcal{P}_1 \times \dots \times \mathcal{P}_n$ を高々一度ずつ試行するため、最悪計算量は $O(p^n)$ となる。この境界は、デッドエンドの廊下にエージェントが並ぶようなインスタンスにおいて $O(p^n)$ の計算時間を要することから、探索空間を網羅するナイーブな境界であると同時に、探索の挙動を示す洞察に富むものである。さらに、有限の $K$ を考慮した場合、Theorem 3により、各エージェントが最大 $K$ 回の再計画を行うことから、最悪計算量は $O(nKp)$ となる。この結果は、各エージェントが $K$ 回の失敗後に安全な経路を選択し、それ以降再計画されないという制約に基づいている。
本セクションでは、提案手法であるMulti-Dependency PIBT (MD-PIBT) の有効性を検証するため、MAPF benchmark [20] に基づく多様なエージェントモデル（Pebble Motion: PM, Rotation Motion: RM, Pebble Motion w/ Large Agents: PMLA）とマップ（random, room, Paris, warehouse等）を用いた追加実験の結果が示されている。One-shot MAPFにおいて、MD-PIBTはEPIBTやPIBTと同等以上の成功率を達成し、特にPMLAエージェントを用いた実験では、EPIBTよりも高品質な解（Sum-of-costおよびMakespanの低減）を見出すことが確認された。評価指標として、解の品質は下限値（LB）に対する比率である $\text{Sum-of-cost} / \text{LB}$ および $\text{Makespan} / \text{LB}$ で測定されており、成功率が1未満の場合は成功した試行のみが計算対象となる。Lifelong MAPF（LMAPF）の実験では、PMエージェントにおいてPIBTを模した設定が強力である一方、RMエージェントではEPIBTを模した設定が最も高いスループットを示す傾向がある。また、エージェント密度が増加するにつれて、エージェントあたりの依存関係の数が増加する傾向が示されている。実験環境として、One-shotでは64コアのAMD Ryzen 3990X CPUを使用し、Lifelongでは高性能クラスターを含む複数のマシンを用いて計算リソースを確保している。