本研究は、従来のMAPF手法が抱える、大規模環境における計算量・メモリ消費の増大、および時間拡張表現（time-expanded representation）に起因するグローバル同期の必要性という課題に対処する。従来のConflict-Based Search (CBS) 等の最適解ソルバーは、エージェント間の明示的な結合によりスケーラビリティに欠け、また多くの手法は通信遅延や非同期動作が避けられない実運用において、頻繁な同期を強いる。本研究では、幾何学的な経路計画と実行時の時間的調整を分離することで、非同期的な動作が可能な大規模ロボットチームへの適用を目指している。
第一の貢献は、時間拡張グラフを構築せずに、高優先度エージェントの幾何学的フットプリントに基づいて頂点進入コストを膨張させるGeometric Conflict Preemption (GCP) の提案である。これにより、明示的な時間推論なしに、将来の待機よりも安価な幾何学的迂回を促すことが可能となる。第二の貢献は、各頂点に保持されたFIFO形式の認可キュー $\mathcal{Q}_v$ を用いて、衝突が発生した際のみ待機アクションを挿入するDecentralized Local Controller (DLC) の導入である。これにより、グローバルな時空間予約テーブルを必要としない、分散的な衝突回避を実現している。最後に、最大1000エージェントの実験を通じて、ほぼ線形なスケーリング特性と、制約の強い環境下での高い成功率を実証した。
提案手法は二段階のプロセスで構成される。第1段階のGCPでは、優先順位の高いエージェントの幾何学的フットプリント $\mathcal{F}_i$ を考慮し、残差グラフ上でコストを膨張させた $A^*$ 計画を行う。具体的には、高優先度エージェントが頂点 $v$ を訪れるインデックス $idx(i, v)$ に比例したペナルティ $P(v)$ を導入し、膨張コスト $c'(u, v) = c(u, v) + P(v)$ を用いて経路を探索する。第2段階のDLCでは、各頂点 $v$ のFIFO認可キュー $\mathcal{Q}_v$ に基づき、エージェントがキューの先頭である場合のみ移動を許可し、それ以外は待機アクションを挿入することで、頂点衝突およびエッジスワップ衝突を回避する。このプロセスは、エージェントに優先順位が与えられ、到着後に目標地点で待機するという仮定（Assumption III.1）の下で、衝突のない完備な軌道を生成する。
実験では、ECBS、Cooperative A* (CA*)、PIBTの3手法と比較評価を行った。ベンチマークとして、広大な空間である`Paris_1_256`と、狭い通路がボトルネックとなる`room-64-64-8`の2種類を使用し、成功率 (SR)、実行時間 (Runtime)、Sum-of-Costs (SOC) を指標とした。結果として、提案手法はPIBTに次ぐほぼ線形なスケーリング特性を示し、ボトルネックの多いマップでも高い成功率を維持した。SOCに関しては、ECBSが最小となる傾向にあるものの、提案手法はCA*やPIBTを上回り、特にGCPによる待機時間の削減が寄与してECBSに匹敵する性能を示した。また、衝突の多いエージェントを先に処理するCL (Conflicting Last) ヘリスティックが、高密度シナリオで最も低いSOCを達成することも確認された。
アブレーション研究により、幾何学的コストのインフレ（Cost Update）を有効にすることで、空間コスト（経路の頂点数）はわずかに増加するものの、時間コスト（待機アクション数）が大幅に削減され、結果として総SOCが低減するというトレードオフが明らかになった。本手法は、待機コストが支配的となるボトルネック環境において最大の利得を得る。今後の課題として、膨張パラメータ $P(v)$ の適応的なチューニングや、観測された競合に基づいてオンラインで優先度を再順序付けする手法の検討が挙げられている。
本研究は、大規模または高密度な環境における Multi-Agent Path Finding (MAPF) のスケーラビリティ問題を解決するため、幾何学的計画と実行時の衝突回避を分離するハイブリッドな優先順位付きフレームワークを提案している。第一段階の Geometric Conflict Preemption (GCP) では、時間拡張モデルを用いず、高優先度のエージェントが使用する頂点への遷移コストを膨張させることで、明示的な時間推論なしに空間的な迂回を促す $A^*$ 計画を行う。第二段階の Decentralized Local Controller (DLC) では、頂点ごとの FIFO 認可キューを用いて幾何学的経路を実行し、頂点衝突やエッジの入れ替わり（edge-swap）を防ぐために待機アクションを挿入する。標準的なベンチマークマップを用いた最大 1000 エージェントの実験では、実行時間がほぼ線形 $O(n)$ の傾向でスケールし、幾何学的実行可能性の仮定を満たすインスタンスにおいて 100% の成功率を達成した。
Multi-Agent Path Finding (MAPF) は、共有グラフ上で複数のエージェントが頂点衝突やエッジスワップ衝突を回避しつつ、目標到着時間の総和である sum-of-costs (SOC) を最小化する問題であり、NP困難な性質を持つ。従来の Conflict-Based Search (CBS) 等の最適解を求める手法は、エージェント間の明示的な結合に依存するため、大規模環境では計算量とメモリ消費が膨大になる。また、多くの手法は時間を離散化して同期的な進化を仮定する time-expanded representation に依存しているが、これは通信遅延や非同期的な動作が避けられない大規模ロボットチームの実運用において、頻繁なグローバル同期を強いるという課題がある。本研究では、幾何学的な経路計画と実行時の時間的調整を分離する二段階の優先度付きフレームワークを提案しており、第一段階の Geometric Conflict Preemption (GCP) では、時間拡張グラフを構築せずに高優先度エージェントの幾何学的フットプリントに基づいて頂点進入コストを膨張させ、将来の待機よりも安価な幾何学的迂回を促す。第二段階の Decentralized Local Controller (DLC) は、頂点ごとのローカルな認可キューを用いて、競合が発生した際のみ待機アクションを挿入することで、衝突のない非同期な実行を保証する。実験の結果、提案手法はエージェント数に対してほぼ線形なスケーリング特性を示し、ボトルネックの多いマップにおいて待機時間を削減することで、競争力のある SOC を維持しつつスケーラビリティを向上させている。
MAPFアルゴリズムは、最適解を保証するCBSなどの最適解ソルバー、解の質を制限しつつ高速化を図るECBSなどの限定的劣最適ソルバー、そして数千規模の規模に対応可能なデカップリング手法に分類される。Prioritized MAPFに代表されるデカップリング手法は、エージェントを優先順位に従って逐次的に計画することで、エージェント数に対してほぼ線形な計算量 $O(n)$ を実現するが、高優先度エージェントの経路が制約となるため、SOC（Sum of Costs）の増大や待ち時間の連鎖を招く課題がある。本研究で提案するGeometric Conflict Preemption (GCP) は、時間拡張グラフを構築することなく、高優先度エージェントの幾何学的経路から導出されたコスト膨張を一度だけ適用することで、幾何学的な重複を抑制する。提案手法は、計画段階でのコスト修正と、実行段階におけるキューベースのローカルコントローラによる残存衝突の解決を組み合わせた、一回限りの（one-shot）デカップリング手法である。これにより、スケーラビリティを維持しつつ、混雑緩和による解の質の向上を図っており、特定の幾何学的実現可能性条件を満たすインスタンスに対して完全性が保証される。
本問題は、非負の辺コストを持つ連結無向グラフ $G=(V, E)$ において、各エージェント $i$ に開始頂点 $s_i$ と目標頂点 $g_i$ が与えられたマルチエージェント経路探索（MAPF）として定義される。エージェントの軌跡 $\tau_i$ は、時刻 $t$ における位置 $x_i(t)$ を示す関数であり、隣接する頂点間または同一頂点への待機を許容するが、本手法の計画段階では時間情報をエンコードしない幾何学的経路のみを扱う。衝突回避の条件は、任意の時刻 $t$ において $x_i(t) = x_j(t)$ となる頂点衝突、および $x_i(t) = x_j(t+1) \land x_i(t+1) = x_j(t)$ となるエッジスワップ衝突の不在であり、目的は総コスト（Sum-of-Costs, SOC） $\sum_i \text{cost}(\tau_i)$ を最小化することである。仮定 III.1 により、エージェントに優先順位が与えられ、到着後に目標地点で待機するとすると、優先順位に従って順次エージェントを移動させることで、残差グラフ $G_i$ 上の最短経路 $\pi_i$ を用いた衝突のない軌跡集合を構成できる。この構成により、得られる軌跡の総コストは、最適解のコスト $C^*$ に対して $\sum_i \text{cost}(\pi_i) \le C^*$ を満たすことが保証される。
本手法は、幾何学的計画と時間的調整を分離した、優先順位付きのMAPFフレームワークを提案している。第1段階のGeometric Conflict Preemption (GCP) では、優先順位の高いエージェントの幾何学的フットプリント $\mathcal{F}_i$ を考慮し、残差グラフ上でコストを膨張させた $A^*$ を実行することで、時間依存しない幾何学的経路を順次計算する。具体的には、高優先度エージェントが頂点 $v$ を訪れるインデックス $idx(i, v)$ に比例したペナルティ $P(v)$ を導入した膨張コスト $c'(u, v) = c(u, v) + P(v)$ を用いて、将来的な混雑を回避する経路を探索する。第2段階のDecentralized Local Controller (DLC) は、各頂点 $v$ に保持されたFIFO形式の認可キュー $\mathcal{Q}_v$ に基づき、エージェントがキューの先頭である場合のみ移動を許可し、それ以外は待機アクションを挿入することで、頂点衝突およびエッジスワップ衝突を回避する。このDLCは、グローバルな時空間予約テーブルを必要とせず、各エージェントの移動許可が局所的なキューの状態のみに依存するため、分散的な実装が可能である。理論的には、Assumption III.1 の条件下で、DLCは衝突のない（collision-free）かつ完備な（complete）軌道を生成することが証明されている。
本実験では、提案手法をECBS、Cooperative A* (CA*)、PIBTの3つの既存手法と比較し、大規模な開けた空間である`Paris_1_256`と、狭い通路がボトルネックとなる`room-64-64-8`の2種類のベンチマークマップを用いて評価を行っている。評価指標には、制限時間内に解を得られた割合を示す成功率 (SR)、計算時間を表すRuntime、および全エージェントの総行動数を表すSum-of-Costs (SOC) が用いられた。実験結果として、提案手法はボトルネックの多いマップでも高い成功率を維持し、Runtimeにおいては時間拡張グラフの構築を回避し局所的なキュー操作を行うことで、PIBTに次ぐほぼ線形なスケーリング特性を実現している。解の質に関しては、ECBSが最小のSOCを記録する傾向にあるものの、提案手法はCA*やPIBTを上回り、特に幾何学的な衝突回避（GCP）が待機時間を削減することで、制約の強い環境下でECBSに匹敵する性能を示す。アブレーション研究では、幾何学的コストのインフレ（Cost Update）を有効にすることで、空間コスト（経路の頂点数）がわずかに増加する一方で、時間コスト（待機アクション数）が大幅に削減され、結果として総SOCが低減されるトレードオフが確認された。また、優先順位付けのポリシーに関する調査では、衝突スコアに基づき衝突の多いエージェントを先に処理するCL (Conflicting Last) ヘリスティックが、高密度シナリオにおいて最も低いSOCを達成することが示された。
本研究では、幾何学的計画と実行時の調整を分離した優先度ベースのMAPFフレームワークを提案している。幾何学的衝突回避手法として、時間モデルを用いずに元のグラフ上で一回限りのコスト膨張を行う「Geometric Conflict Preemption」を導入し、高優先度エージェントの経路との重複を抑制する。実行フェーズでは「Decentralized Local Controller」が、局所的なFIFOキューを用いて衝突のない実行を強制し、競合が発生した場合にのみ待機を発生させる。評価の結果、この分離手法は、待機コストが支配的となるボトルネックの多い環境において最大の利得を得つつ、大規模なチームサイズにおいても競争力のあるSOC（Sum of Costs）を維持しながら安定したスケーラビリティを実現することが示された。今後の課題として、膨張パラメータの適応的なチューニングや、観測された競合に基づくオンラインでの優先度再順序付けが挙げられている。