本研究は、連続空間 $\chi = \chi_{\text{free}} \cup \chi_{\text{obs}} \subset \mathbb{R}^2$ におけるマルチエージェント経路計画（CS-MAPF）問題を対象としている。エージェント $a_i$ は半径 $r$ の円盤としてモデル化され、最大速度 1 で移動可能である。従来の $\text{ORCA}^*$ は速度空間で動作する分散型手法であるが、反応的な意思決定に依存するため、廊下のような制約環境でデッドロックを引き起こす課題がある。既存の $\text{ORCA}^* \text{-MAPF}$ も、デッドロック発生後に中央集権的なMAPFで再計画を行う事後的な介入（post hoc intervention）に留まっており、フロータイムの増大や離散的な解による不適合という問題があった。
提案手法 $\text{C-ORCA}^*$ は、エージェントの空間的な軌道全体とその空間的依存関係を考慮することで、デッドロックを能動的に回避するメカニズムを導入した。具体的には、事前にMAPFを用いて生成した経路をウェイポイント列に変換し、エージェント間の依存関係に基づいた制御モードの切り替えを行う。これにより、解決率（solve rate）、実行時間（runtime）、およびフロータイム（flowtime）のすべての指標において、従来の最先端手法を大幅に上回る性能を実現した。特に $\text{C-ORCA}^* \text{-MAPF}$ は、高コストな ECBS 等の MAPF フォールバックの呼び出し回数を、既存手法と比較して 3〜4 桁減少させることに成功している。
まず、環境を 4 連結グリッド $G = \langle V, E \rangle$ に離散化し、MAPF ソルバーで経路を生成した後、次数 $\text{deg}(v) \le 2$ のセルからなる廊下（corridor）を $O(N)$ の計算量で特定し、string-pulling 法を用いてウェイポイントへ変換する。実行時には、廊下における依存関係を「cross-corridor dependency（対向エージェント間の待機）」と「enter-corridor dependency（同一方向の連続進入時の待機）」に分類する。これに基づき、エージェントは「ORCAモード」または「driftモード」を選択する。driftモードでは、係数 $\alpha$ を用いて $v_{\text{pref}} = \alpha \cdot v_{\text{VORCA}}$ とすることで、ドリフト開始点へ緩やかに戻る挙動を取り、混雑を回避する。さらに、他者のウェイポイントを塞ぐエージェントに対しては、一時的な退避ウェイポイント（yielding position）を割り当てる。
Gap ($64 \times 64$), Random ($64 \times 64$), Room ($32 \times 32$), Warehouse ($321 \times 123$) の 4 種類のマップを用い、エージェント数を 10 から 200 まで変化させて評価を行った。実験の結果、$\text{C-ORCA}^* \text{-MAPF}$ は、特に狭い通路での対向衝突が発生しやすい Gap や Warehouse マップにおいて、$\text{ORCA}^*$ 系列を大幅に上回る成功率を達成した。アブレーション研究により、drift モードが Gap マップにおけるデッドロック解消に極めて重要であることが示された。また、$\text{C-ORCA}^*$ のステップあたりの平均計算時間は $\text{ORCA}^*$ とほぼ同等であり、依存関係メカニズムによる計算オーバーヘッドは無視できる程度に抑えられていることが確認された。
本研究は、MAPF による誘導、動的な依存関係の検出、および能動的なデッドロック解決メカニズムを組み合わせることで、ORCA* を実用的な CS-MAPF 手法へと拡張した。実験を通じて、提案手法がすべてのベンチマークにおいて従来手法よりも有意に高い成功率と解の質を達成することが示された。しかし、極端な混雑条件下では、アルゴリズムが局所最適解に収束する可能性があるという限界も存在する。今後の展望として、サンプリングベースの探索メカニズムを組み込み、本フレームワーク内で系統的な探索へと段階的に移行させることで、さらなる性能向上が期待される。
本論文では、連続空間におけるマルチエージェント経路計画（MAPF）において、将来的なデッドロックを未然に防ぐための新しいアルゴリズム群である $\text{C-ORCA}^*$ および $\text{C-ORCA}^* \text{-MAPF}$ を提案している。従来の $\text{ORCA}^*$ は各タイムステップで速度を割り当てるリアルタイム手法であるが、近視眼的な意思決定によりデッドロックを引き起こしやすく、その後の修正策として導入された $\text{ORCA}^* \text{-MAPF}$ も事後的な介入（post hoc intervention）による大きなフロータイムの増加という課題を抱えていた。これに対し、提案手法はエージェントの空間的な軌道全体とその空間的依存関係を考慮することで、デッドロックの発生を能動的に回避する。実験の結果、$\text{C-ORCA}^*$ ファミリーは、解決率（solve rate）、実行時間（runtime）、およびフロータイム（flowtime）のすべての指標において、従来の最先端手法を大幅に上回る性能を示した。
従来のMulti-Agent Path Finding (MAPF) は離散的なグラフやグリッド上で定義されることが多く、連続的な環境やロボットの運動学・動力学を十分に反映できないという課題がある。Configuration Space MAPF (CS-MAPF) は連続領域への拡張を試みているが、実行時の制御コストが理論的な解のコストを大幅に上回る問題がある。分散型のリアルタイム回避戦略であるORCA*は、速度空間で直接動作するため実行に近いものの、純粋に反応的な手法であるため、廊下のような環境で将来的なデッドロックを引き起こす可能性がある。既存のORCA*-MAPFはデッドロック発生後に中央集権的なMAPFで再計画を行うフォールバック機構を持つが、デッドロック発生後の対応であるため非効率であり、かつ離散的な解を用いることでORCA*の連続空間における利点を損なうという限界がある。本研究が提案するCooperative ORCA* (C-ORCA*) は、事前にMAPF（例：MAPF-LNS）から得た経路をストリング・プーリングによりウェイポイントへ変換し、エージェント間の空間的依存関係を考慮した修正版ORCA*を用いることで、デッドロックを未然に回避する。C-ORCA*はエージェントが将来のデッドロックを防ぐために能動的に待機することを可能にし、解決率、実行時間、およびフロータイムの観点において従来手法を大幅に上回る性能を示す。
本研究では、環境 $\chi = \chi_{\text{free}} \cup \chi_{\text{obs}}$ とエージェント集合 $A = \{a_1, \dots, a_n\}$ からなる連続空間におけるマルチエージェント経路計画（CS-MAPF）問題を定義している。環境は 2 次元矩形空間 $\chi \in \mathbb{R}^2$ であり、グリッド世界 $G$ 上の各点 $v_i \in V$ は $\langle x_i, y_i, b_i \rangle$（$b_i \in \{0, 1\}$）として表され、$\chi_{\text{obs}}$ は通行不能な領域を指す。各エージェント $a_i$ は半径 $r$ の円盤としてモデル化され、最大速度 1 で任意の方向に移動可能であり、時刻 $t$ における位置は $p_i(t) = (x_i(t), y_i(t))$ と記述される。衝突条件として、エージェントと障害物の間の最小ユークリッド距離が $r$ 未満の場合、およびエージェント間の中心間距離が $2r$ 未満の場合の 2 種類を考慮する。本問題の目的は、全エージェントが目標構成に安全に到達するまで、各エージェントの目標到達時刻の総和であるフロータイム $\sum_{i=1}^n \text{cost}(a_i)$ を最小化することである。
本研究では、連続空間におけるマルチエージェント経路計画（CS-MAPF）の既存手法として、State Lattice PlanningとORCA*ファミリーを比較検討している。State Lattice Planningは、ロボットの運動学的・動力学的制約を考慮したmotion primitivesを用いるが、db-CBSでは最大8エージェント、db-LaCAMでは約50エージェント程度にスケーラビリティが制限されるという計算上の課題がある。一方、速度空間で動作する分散型アルゴリズムであるORCA*は、計算効率が高く大規模な群衆シミュレーションに適しているものの、純粋な反応型手法であるため、狭い通路などの制約のある環境では局所的なデッドロックに陥りやすい。例えば、gap1-64-64マップにおいて、ORCA*はエージェント数が約40に達すると成功率が50%を下回る。デッドロック解消のためにMAPFをフォールバックとして利用するORCA*-MAPFも提案されているが、デッドロック発生後にのみ動作するため遅延が生じる点や、離散的な解が連続空間での実行において不適合であるといった限界がある。
C-ORCA*は、協調的な探索手法と局所的な衝突回避を組み合わせることで、連続空間におけるマルチエージェント経路計画（CS-MAPF）のデッドロックを未然に防ぐリアルタイム手法である。事前処理として、環境を4連結グリッド $G = \langle V, E \rangle$ に離散化してMAPFソルバーで経路を生成し、次数 $\text{deg}(v) \le 2$ のセルからなる廊下（corridor）を $O(N)$ の計算量で特定した後、string-pulling法を用いてウェイポイント列へと変換する。実行時には、廊下におけるエージェント間の依存関係を「cross-corridor dependency（対向するエージェント間の待機）」と「enter-corridor dependency（同一方向の連続進入時の待機）」の2種に分類し、これに基づきエージェントを「ORCAモード」または「driftモード」に切り替える。driftモードのエージェントは、固定の優先速度を持たず、近傍エージェントの最大速度に追従するか、あるいは係数 $\alpha$ を用いてドリフト開始点へ緩やかに戻る挙動（$v_{\text{pref}} = \alpha \cdot v_{\text{VORCA}}$）をとることで、廊下内での混雑やデッドロックを回避する。また、ウェイポイント更新プロセスにおいて、障害物による視界遮断やゴール地点での停止によるデッドロックを防ぐため、中間ウェイポイントの生成や、他者のウェイポイントを塞ぐエージェントへの一時的な退避ウェイポイント（yielding position）の割り当てを行う。
本実験では、提案手法である $\text{C-ORCA}^*$ および $\text{C-ORCA}^*\text{-MAPF}$ を、既存の $\text{ORCA}^*$ および $\text{ORCA}^*\text{-MAPF}$ と比較評価している。評価は、Gap ($64 \times 64$)、Random ($64 \times 64$)、Room ($32 \times 32$)、Warehouse ($321 \times 123$) の4種類のマップを用い、エージェント数を10から200まで変化させて、成功率 (success rate)、実行時間 (runtime)、フロータイム (flowtime) の3指標で測定した。$\text{C-ORCA}^*\text{-MAPF}$ は、特に狭い通路での対向衝突が発生しやすい Gap や Warehouse マップにおいて、$\text{ORCA}^*$ 系列を大幅に上回る成功率を達成しており、デッドロック回避のためのプロアクティブな待機メカニズムが、MAPF モードへの移行に必要なエージェント間の距離を維持する上で有効であることを示した。アブレーション研究により、ドリフトモード (drift mode) は Gap マップにおいて、廊下依存性 (corridor dependencies) だけでは解決できないデッドロックを解消するために極めて重要であることが確認された。また、$\text{C-ORCA}^*$ のステップあたりの平均計算時間は $\text{ORCA}^*$ とほぼ同等であり、依存関係メカニズムによる計算オーバーヘッドは無視できる程度に抑えられている。さらに、$\text{C-ORCA}^*\text{-MAPF}$ は、高コストな ECBS を用いた MAPF フォールバックの呼び出し回数を、既存手法と比較して 3〜4 桁減少させることに成功している。
本研究では、古典的なMAPF（Multi-Agent Path Finding）計画アルゴリズムによるエージェントの誘導、動的な依存関係の検出、および実行中の困難なデッドロック・シナリオを能動的に解決するメカニズムを導入することで、ORCA*をC-ORCA*へと拡張した。実験の結果、C-ORCA*（およびC-ORCA*-MAPF）は、ORCA*（およびORCA*-MAPF）を一貫して上回り、テストされたすべてのベンチマークにおいて、従来手法よりも有意に高い成功率と解の質を達成し、従来のORCA*では困難であったシナリオも処理可能であることを示した。しかし、極端な混雑条件下では、アルゴリズムが局所最適解に収束する可能性があるという限界が存在する。今後の展望として、サンプリングベースの探索メカニズムを組み込み、本フレームワーク内で系統的な探索へと段階的に移行させることで、さらなる性能向上を図ることが挙げられる。