従来のマルチエージェント経路探索（MAPF）は、単位コストのグラフや同期的な動きを前提としていた。一方、実数値コストと連続時間を扱う MAPF R は、幾何学的な衝突モデルにより状態空間が非有界となり、計算効率が著しく低下するという課題がある。本研究では、正の整数コスト $c(u, v)$ を持つグラフ $G = (V, E)$ 上で、全エージェントの経路コストの最大値であるメイクスパン $\max_{a_i \in \mathcal{A}} \text{cost}(p_i)$ を最小化する $\text{MAPF}_{\mathbb{Z}}$ を対象とする。
既存のグラフ設計手法は、時間離散化と衝突解決の相互作用を明示的に考慮して MAPF 問題と共同最適化されておらず、高密度な環境でのスケーラビリティに課題があった。本研究は、時間区間に基づく衝突検知と制約追加を行う CBS-NIC を導入し、さらに離散化パラメータを最適化する BOGD フレームワークを提案することで、計算効率と精度のバランスを最適化する。BOGD は、反復回数に対して劣線形なリグレット界を持つことが保証されている。
提案手法 CBS-NIC は、高レベルの Conflict-Based Search と低レベルの拡張 Safe Interval Path Planning (SIPP) で構成される。高レベルでは、エージェントの占有を半開区間 $[t_s, t_e)$ として定義し、頂点衝突およびエッジ衝突を検出して、滞在禁止制約やエッジ占有禁止制約を課す。探索には、正負の制約を組み合わせた Disjoint Splitting (DS) 技術を用いる。低レベルの SIPP は、離散時間ドメインで整数エッジ重みを直接扱い、制約を遵守しながら最短経路を計算する。また、BOGD フレームワークにより、計算時間 $T(\delta)$ と離散化誤差 $\mathcal{E}(\delta) = \sum_{i \in \mathcal{A}} \sum_{e \in \pi_i} |w_e - \lfloor w_e / \delta \rfloor \cdot \delta|$ の二目的最適化を通じて、最適な離散化パラメータ $\delta$ を決定する。
Moving AI のグリッドマップおよび制約付きドロネー三角形分割（CDT）を用いたロードマップ環境で、成功率、makespan、実行時間を指標に評価した。Berlin グリッドマップの 50 エージェント環境では、makespan が 5.83% 増加するものの、成功率が 68% 向上した。ロードマップ環境において、CCBS が 40 エージェントを超えると解を見つけられなくなるのに対し、CBS-NIC-B は 100 エージェントでも 100% の成功率を維持し、実行時間においても数桁の高速化を実現した。
倉庫マップのような狭い通路が多い環境では、障害物によって近傍ノードが遮断されやすく、BOGD による改善効果が限定的になるという限界がある。今後の課題として、より大規模な環境への拡張や、リアルタイムの実行制約をより正確に反映させるための時空間計画の導入が挙げられている。
本研究では、エッジコストが $1$ ではない整数値をとるグラフ上でのマルチエージェント経路探索問題である MAPF Z を提案している。従来の MAPF R は実数値コストと連続時間アクションを扱うが、幾何学的な衝突モデルにより状態空間が非有界となり計算効率が著しく低下するという課題があった。これに対し、提案手法である CBS-NIC は、高レベルで時間区間に基づく衝突検知と制約追加を行い、低レベルで改良された Safe Interval Path Planning (SIPP) を用いることで、有限な状態空間を維持しつつ効率的な探索を実現する。さらに、非単位エッジコストを扱うための離散化手法として Bayesian Optimization for Graph Design (BOGD) を提案しており、これは計算効率と精度のバランスを最適化し、時間の経過とともに性能が向上することを保証する劣線形レグレット（sub-linear regret bound）を持つ。実験の結果、提案手法は多様なベンチマークシナリオにおいて、実行時間と成功率の両面で既存の最先端手法を上回ることが示された。
本研究では、従来のMAPFが前提としていた単位コストのグラフや同期的なエージェントの動きという制約を緩和し、非単位整数コストのグラフを扱う新しい問題設定であるMAPF Zを提案している。MAPF Zは、幾何学的な衝突判定を必要とするMAPF Rのような連続時間モデルが抱える、状態空間の非有界性による計算効率の低下という課題を解決し、現実的なモデリングと計算効率のバランスを両立させることを目的としている。この問題に対し、時間間隔ベースの衝突検知、制約定義、および改良されたSIPPアルゴリズムを導入したCBS-NICという新しいConflict-Based Searchの変種を提案している。さらに、非単位コストのグラフを効率的な探索が可能な離散グラフへ変換するため、多目的ベイズ最適化を用いた二段階最適化フレームワークであるBOGDを導入しており、これはグラフ構造の探索（上位レベル）とCBS-NICによる評価（下位レベル）によって構成される。BOGDは、元のコスト構造への忠実度と経路探索の効率性のバランスを最適化するように設計されており、反復回数に対して劣線形なリグレット界を持つことが示されている。
マルチエージェント経路探索（MAPF）の研究は、コストの性質や時間表現、グラフ設計の観点から分類される。単位コストのMAPFにおいて、最適解を保証するCBSは、高レベルでの衝突に基づく二分木探索と低レベルでのA*を用いた探索を行うが、複雑な環境では計算コストが膨大になる。これに対し、解の質と速度のバランスを取る限定的な劣最適解ソルバーとして、高レベルと低レベルの両方でフォーカルサーチを用いるECBSや、高レベルで明示的な推定探索を行うEECBSがあり、解の質は $\epsilon$ の値に依存する。非単位コストや連続時間を扱う手法としては、コスト区間を用いたMDDを構築するICTSの拡張や、SIPPを統合して連続時間と幾何学的制約に対応するCCBS、階層的な移動抽象化を用いるCBS-CLなどが提案されている。グラフ設計においては、連続空間から衝突のない構成をサンプリングするPRMや、時空間情報を組み込んだCTRM、分散システム向けのMRPTなどのロードマップ構築手法が存在する。しかし、既存のグラフ設計手法の多くは、時間離散化と衝突解決の相互作用を明示的に考慮してMAPF問題と共同最適化されておらず、高密度かつ大規模なシナリオにおけるスケーラビリティに課題を残している。
本セクションでは、エッジコストが $1$ ではない正の整数値をとる新しい問題設定である $\text{MAPF}_{\mathbb{Z}}$ が定義されている。この問題は、正の重みを持つグラフ $G = (V, E)$ 上で定義され、各エッジ $(u, v) \in E$ には、エージェントがそのエッジを通過するのに要する時間を示す正の整数コスト $c(u, v)$ が割り当てられている。エージェントの集合を $\mathcal{A} = \{a_1, \dots, a_n\}$ とし、各エージェント $a_i$ に対して、単射写像 $s: \mathcal{A} \to V$ と $g: \mathcal{A} \to V$ によって開始地点と目標地点が与えられる。エージェント $a_i$ の計画は、時刻 $t$ における頂点のシーケンス $p_i = (v_{i,0}, v_{i,1}, \dots, v_{i,T_i})$ で表され、待機アクションは $v_{i,t} = v_{i,t+1}$ として表現される。解の目的は、全エージェントの経路コストの最大値であるメイクスパン $\max_{a_i \in \mathcal{A}} \text{cost}(p_i)$ を最小化する衝突のない計画を求めることである。また、既存手法として、低レベルで制約を満たす最短経路を探索し、高レベルで制約ツリー（CT）を探索する Conflict-based Search (CBS) が挙げられ、衝突の種類（cardinal, semi-cardinal, non-cardinal）に基づいて解決順序を決定する PC ヒューリスティックや、正負の制約を用いて探索の重複を減らす Disjoint Splitting (DS) 戦略についても述べられている。
CBS-NICは、エッジコストが整数であるMAPF Zの設定に対応した、高レベルのConflict-Based Search（CBS）と低レベルの拡張SIPP（Safe Interval Path Planning）を組み合わせた手法である。高レベルでは、エージェント $i$ が時刻 $t_s$ から $t_e$ までエッジ $e$ を通過する際の占有を半開区間 $[t_s, t_e)$ として定義し、頂点衝突（$pos_i(t) = pos_j(t)$）および、逆方向に同じエッジを通過する時間区間が重なるエッジ衝突（$[t_{s,i}, t_{e,i}) \cap [t_{s,j}, t_{e,j}) \neq \emptyset$）を検出する。衝突解決のために、頂点衝突には特定の時刻での滞在禁止制約を、エッジ衝突には特定の時間区間でのエッジ占有禁止制約を課す。さらに、探索効率を高めるため、負の制約（特定の時刻に特定の頂点にいないこと）と、複数の負の制約の集合として定義される正の制約（特定の時刻に特定の頂点にいること）を組み合わせたDisjoint Splitting（DS）技術を導入している。低レベルのSIPPは、離散時間ドメインで動作し、整数エッジ重みを直接扱うことで、与えられた制約（頂点の安全区間の分割やエッジの通過禁止区間の除去）を遵守しながら最短経路を計算する。また、グラフ離散化の最適化のためにBOGDフレームワークを提案しており、計算時間 $T(\delta)$ と離散化誤差 $\mathcal{E}(\delta) = \sum_{i \in \mathcal{A}} \sum_{e \in \pi_i} |w_e - \lfloor w_e / \delta \rfloor \cdot \delta|$ の二目的最適化を、ベイズ最適化とNSGA-IIを用いて解くことで、離散化パラメータ $\delta$ を決定する。
本実験では、提案手法であるCBS-NICおよびその改良版であるCBS-NIC-Bの有効性を、Moving AIリポジトリのグリッドマップおよび制約付きドロネー三角形分割（CDT）を用いて構築したロードマップ環境の両方で評価している。評価指標として成功率、makespan、実行時間の3点を用い、30秒の制限時間内で比較を行っている。実験の結果、CBS-NIC-BはBOGD戦略によって最適な離散化パラメータを選択できるため、既存のMA-CBSやEPEA、および連続空間を扱うCCBSと比較して、100エージェントを超える大規模なシナリオでも100%の成功率を維持しつつ、実行時間を大幅に短縮できることが示された。具体的には、Berlinグリッドマップにおいて50エージェントの場合、makespanが5.83%増加する代わりに成功率が68%向上するという、解の質と成功率のトレードオフにおける顕著な利点が確認された。一方で、倉庫マップのような狭い通路が多い環境では、障害物によって近傍ノードが遮断されやすく、BOGD戦略による改善効果が限定的になるという限界も示されている。ロードマップ環境においても、CBS-NIC-BはCCBSが40エージェントを超えると解を見つけられなくなるのに対し、100エージェントでも100%の成功率を維持し、実行時間においても数桁の高速化を実現している。
本論文では、エッジのコストが $1$ ではない整数値を取り得る、より現実的な異種エッジ重みを持つシナリオをモデル化した新しいマルチエージェント経路探索問題である $\text{MAPF}_{\mathbb{Z}}$ を提案している。この問題を効率的に解くために、時間区間ベースの衝突検知、洗練された制約定式化、拡張された SIPP アルゴリズム、および BOGD フレームワークを統合した手法である CBS-NIC-B を提案した。実験結果により、CBS-NIC-B は解の品質において競争力を維持しつつ、成功率を大幅に向上させることが示されている。今後の展望として、大規模な環境への拡張や、リアルタイムの実行制約をより正確に反映させるための時空間計画の導入が挙げられている。