従来のマルチエージェント経路計画（MAPF）は、離散的な時間、単一の目標、円形の移動体、および全エージェントが目標到達後に停止することを前提としていた。そのため、エージェントごとの異なる運動モデル、非幾何学的な衝突、タスクのシーケンス、およびタスク完了後に移動を続けるエージェントを扱うことが困難であった。本研究では、各エージェントが独自のグラフと状態空間を持ち、連続的な時間軸上で順序付けられたタスクを実行する、より汎用的な問題設定を扱う。入力としてエージェントのグラフ構造、タスクのシーケンス、および衝突定義を受け取り、制約を満たす経路を出力する。
既存の厳密な連続時間ソルバーであるOC-CBSに対し、最適解が見つかるまで解を返さないという制約を解消し、探索のあらゆる段階で最適性ギャップの上限が既知である暫定解を提供できるAnytime性を導入した。また、複数の探索ポリシーや修復関数を組み合わせたモジュール式のポートフォリオ構成を採用することで、複数のプロセッサによる並列実行を可能にした。これにより、厳密な最適解の発見能力を維持したまま、扱えるエージェント数を数十規模から数百規模へと拡張した。
高レベル探索では、制約ツリー（CT）を管理し、未展開のノードから一つを選択する選択ポリシーと、既存の計画を修正する修復メソッドの集合からなるポートフォリオを用いる。修復メソッドの一つであるTP-SIPPは、エージェントのデッドラインに基づき優先度を3つの階層に分けて計画を行い、タスク完了後の退避を可能にする。探索が進むにつれて、CTノードから得られる下界が上昇し、修復や分岐によって得られる暫定解の上界が低下することで、最終的に両者が一致して最適解に到達する。
MovingAIベンチマークのグリッドマップおよびロードマップを用い、円形エージェント、連続的なエッジ軌道、および多角形形状のエージェントを含むモデルで検証した。評価指標として、解の発見能力、エージェント数に対するスケーラビリティ、および最適性ギャップを用いた性能比較を行った。実験の結果、修復関数を使用する構成は、緩い最適性ギャップにおいては解の発見能力を向上させるが、最適解の証明を目指す段階では下界の更新を遅らせるトレードオフがあることが示された。また、複数のポリシーを並列運用する構成は、難易度の高いインスタンスにおいて高速化を実現し、最適性ギャップに応じてポリシーを切り替える構成は、迅速な解の発見と下界の引き上げの両立に成功した。
本手法は、最適性の証明と解の発見が異なる負荷であることを示している。修復関数は、許容される最適性ギャップが大きい場合にはスケーラビリティを向上させるが、最適解の証明を優先する場合には計算コストとなる。また、並列化は問題の難易度が高まった際のスループット向上に寄与するが、単一コアで解ける容易な問題に対しては管理オーバーヘッドが生じる。今後の課題として、3次元空間への拡張、非分離的な衝突の導入、および計算資源と最適性の間のトレードオフをより動的に制御する仕組みの検討が挙げられる。
本研究では、離散的な時間、単一の目標、円形の移動体といった従来のマルチエージェント経路計画（MAPF）の制約を解消し、連続時間、非幾何学的な衝突、タスクの順序、および目標到達後の移動を許容する一般化されたMAPFの定式化を提案している。提案手法であるAOC-CBSは、最終的に最適解を返すことを保証しつつ、実行中には既知の最適性ギャップの上限を持つ暫定解を逐次報告する、厳密かつ解の完全性を備えたソルバーである。この手法は、複数のプロセッサコアを活用できるほか、新たに導入されたTier-Prioritized Safe Interval Path Planningを含む複数の修復関数のポートフォリオを選択可能である。非凸な形状を持つ多様なエージェントが滑らかで動力学的に実行可能な軌道を描く混合フリートを用いた実験において、AOC-CBSは既存の厳密ソルバーであるOC-CBSと同等の最適解発見能力を持ちつつ、最適性のギャップを許容することで、扱えるエージェント数を数十規模から数百規模へと拡張できることを示した。
本研究では、各エージェントが独自のグラフと状態空間を持ち、連続的な時間軸上で動作する汎用的なマルチエージェント経路計画（MAPF）問題を扱う。提案手法であるAOC-CBSは、最適解が見つかるまで解を返さないという既存手法の課題を解決するAnytimeアルゴリズムであり、実行中いつでも、最適解との差（最適性のギャップ）の上限が既知である暫定解を提供できる。この手法は、エージェントごとに異なる運動モデルを持つ異種混合フリートや、幾何学的な衝突だけでなく、ドローンのダウンウォッシュのような抽象的なペアワイズの衝突を許容する。さらに、頂点での滞在時間やエッジの通過をタスクとする設定に加え、タスク完了後にエージェントが移動を継続できることや、待機不可能な頂点の存在も考慮されている。具体的な構成要素として、優先度に基づいた経路計画手法であるTP-SIPPを導入している。実験では、MovingAIベンチマークにおいて、既存手法と同等の最適解性能を維持しつつ、対応可能なエージェント数を数十から数百へと大幅に向上させている。
本セクションでは、マルチエージェント経路計画（MAPF）における既存の定式化と、Conflict-Based Search（CBS）の基礎について述べている。古典的なMAPFは離散的な時間とグラフ構造を前提とするが、エージェントの物理的な体積や非一様な移動時間を考慮できない制約がある。これに対し、連続時間MAPF（MAPF R）は実数値の時間と軌道を扱えるものの、全エージェントが同一のグラフを共有するため、移動モデルが最も制限的なエージェントに制約される。一方、マルチエージェント・モーション・プランニング（MAMP）はエージェントごとに個別のグラフを定義できるが、空間をセルに離散化して衝突判定を行うため、精度と計算コストのトレードオフが生じる。本研究では、空間の離散化を避け、グラフ要素間の不適合性を直接保持する手法を採用している。また、従来のMAPFは全エージェントが同時に目標地点に到達し停止することを要求するが、本研究は目標到達後に移動を継続できる到達可能性（reachability）の概念を取り入れている。CBSアルゴリズムは、制約ツリー（CT）を探索する高レベルと、個別の経路を計画する低レベルの二層構造で構成される。高レベルの探索では、衝突が発生するたびに制約を追加して子ノードを生成し、低レベルの経路計画によって制約を満たす新たな経路を再計算することで、最適解を導出する。
本セクションでは、異種エージェントによる連続時間での経路計画問題を、グラフ構造とタスクの実行として定式化しています。各エージェントは、状態を表す頂点と、それらを結ぶ軌跡を表すエッジからなる有向マルチグラフ上で移動し、エッジの通過または頂点での待機というアクションを通じて、順序付けられたタスクを一つずつ完了させます。タスクには、エッジを通過するエッジタスクと、特定の時間以上頂点に留まる頂点タスクがあり、これらは指定された順序で実行される必要があります。各アクションにはドメイン固有のコストが割り当てられ、多くの場合、コストはアクションの継続時間と一致しますが、エネルギー消費のように時間とは異なる定義も可能です。衝突は、2つのエージェントが特定の時刻に占有する状態の組み合わせに対して定義される関数として抽象化されており、幾何学的な衝突だけでなく、ドローンのダウンウォッシュによる干渉のような非幾何学的な事象も扱えます。この定式化は、エージェントの運動学的制約をグラフの構築段階に集約することで、エージェントの物理的性質に依存しない汎用的な協調計画を可能にしています。
AOC-CBSは、従来のOC-CBSが持つ「最適解のみを対象とする」「逐次的な探索により並列化が困難」という2つの制限を解消した、Anytime-Optimalな連続時間衝突ベース探索手法である。高レベル探索において、複数のポリシーからなるモジュール式のポートフォリオを採用しており、各ポリシーは独立してノードの選択と修復を行うため、複数のプロセッサによる並列実行が可能である。各ポリシーは、未展開のノードから一つを選択する選択ポリシーと、既存の計画を修正して解を試みる修復メソッドの集合で構成される。選択ポリシーには、最適性を保証するために少なくとも一つは最小コスト下界に基づくものが含まれる必要があるが、解が見つかった後はランダム選択などの多様な手法へ切り替えが可能である。
低レベルの経路計画には、複数の連続するタスクとエージェントの待機を扱えるMG-CSIPPが用いられ、A*探索と安全区間の概念を組み合わせることで、制約条件下での最小所要時間を保証する。また、修復メソッドの一つであるTP-SIPPは、エージェントのデッドラインに基づき優先順位を3つの階層に分けて計画を行うことで、タスク完了後にエージェントが退避して他のエージェントの経路を確保することを可能にしている。本手法は、探索が進むにつれて下界が上昇し、修復や分岐によって得られる上界が低下することで、最終的に両者が一致して最適解に到達する仕組みを持つ。
AOC-CBSは、最適解のみを返す厳密性と、解が存在する場合に有限時間内に解を返す解の完全性を備えたアルゴリズムである。計算機における有限精度の浮動小数点演算を用いるため、極めて微小な時間スケールでの衝突判定には限界があるものの、実世界のセンサー誤差等を考慮すれば十分な精度を持つ。本手法の核心となる不変性は、各反復の開始時点で、未展開のノードを通じて最適解への到達可能性が維持されているか、あるいは既に最適解が見つかっているかのいずれかが成立することである。この性質により、ノードキューが空になった時点で得られる解は必ず最適解となり、探索中に維持される下界と上界は常に正しく、任意の停止時点において有効な最適性ギャップを算出できる。また、既に解が見つかっている場合、または下界を最小化するノードを常に選択する方策がポートフォリオ内に存在する場合のいずれかにおいて、有限回数の反復で最適解に到達することが理論的に保証されている。
AOC-CBSの実験評価では、円形エージェントかつ一定速度の直線移動を仮定したモデル、任意の連続的なエッジ軌道を含むモデル、および多角形形状のエージェントを含むモデルの3段階で検証が行われています。評価にはMovingAIのグリッドマップおよびそれらをサンプリングしたロードマップが使用され、エージェントの半径は0.5、エージェント数が増加するまで解を探索するシナリオ設定でベンチマークが行われました。アブレーション研究では、単一または複数のポリシー（CPUコアごとに異なる探索戦略を実行）の構成、修復関数（TP-SIPP）の有無、およびノード選択ルール（最小コスト、最小衝突回数、最小合計衝突時間など）による性能差を調査しています。実験結果によれば、修復関数を使用する構成は解の発見には寄与するものの、衝突木（CT）の展開による下界の更新を遅らせるトレードオフが存在しますが、解の最適性ギャップに応じてポリシーを切り替える構成C6は、迅速な解の発見と下界の引き上げの両立に成功しています。また、マルチポリシー構成（C3）は、集計的な成功率では単一ポリシー（C1）に対し劇的な向上は見られないものの、難易度の高いインスタンスにおいて顕著な高速化を実現することが示されました。事前処理については、全対最短経路の計算や幾何学的な衝突情報の抽出が行われ、これらは円形エージェント・直線移動モデルにおいて実用的な時間内で完了することが確認されています。
AOC-CBSは、最適解のみを返すOC-CBSに対し、限定的な最適性のギャップを許容することで、同一の計算予算内で解決可能な問題数を増加させる手法である。実験の結果、グリッドマップやロードマップにおいて、AOC-CBSはOC-CBSとほぼ同等の最適性を維持しつつ、マップの規模が大きくなるほど、劣最適性を許容することによる解決可能問題数の増加幅が拡大することが示された。アブレーション解析により、解の発見と最適性の証明は異なる負荷であることが明らかになり、修復関数TP-SIPPは到達可能なエージェント数を増やす一方で、修復に時間を費やすことでノード展開や下界の更新が遅れるというトレードオフが確認された。また、並列化は問題の難易度が高まった際にスループットを向上させ、実行時に動的にポリシーを切り替えることで、静的な設定よりも広い範囲の問題に対応できる。本手法の汎用性は、幾何学的な形状や衝突の定義を事前処理として切り離すことで実現されており、円形エージェントや非凸多角形エージェントなど、異なる特性を持つエージェントを同一のソルバーで扱える。現在の実装はPythonによるもので、C++実装のOC-CBSと比較して実行速度は劣るものの、データ構造や事前処理の選択が言語の差を上回る重要性を持つことが示唆されている。
本研究では、異種エージェント、個別のグラフ、連続時間、抽象的なペアワイズ衝突、エッジおよび頂点タスクのシーケンス、およびタスク完了後の自由移動を許容する、より一般的なマルチエージェント経路計画（MAPF）問題を定義し、その解決手法としてAOC-CBSを提案した。AOC-CBSは、下界を確定させる探索と、構成可能な複数の修復関数を用いて暫定解を探索するプロセスを分離することで、探索のあらゆる段階で暫定解と、その解が最適解からどの程度離れているかを示す保証付きの最適性ギャップを提示できるAnytime特性を持つ。修復関数の一つであるTP-SIPPは、タスク完了後にエージェントがその場を離れる必要がある状況に対応しており、これらを並列に実行することで、従来のOC-CBSと同等の最適解の発見・検証能力を維持しつつ、許容可能な最適性ギャップ内での解の発見においては、エージェント数を数十から数百へと拡張することに成功した。アブレーション解析の結果、修復関数は緩い最適性ギャップにおいてエージェント数のスケーラビリティを向上させる一方で、最適解の証明を目指す段階では下界の更新を遅らせるコストとなることが示された。また、複数のポリシーを並列運用する構成は、単一コアで解ける容易な問題よりも困難な問題において、解の到達可能性を高める効果がある。AOC-CBSは、最適解を証明するまで解を返さない厳密解法と、品質保証のない高速な近似解法の間のトレードオフを解消し、用途に応じて高速なヒューリスティック解法としても厳密解法としても利用可能な柔軟性を実現している。