グラフ上でN個のエージェントが衝突を回避しながら各々の目標地点へ到達する、非同期アクションを伴うマルチエージェント経路計画（MAPF-AA）を対象とする。各エージェントは異なる移動速度を持ち、アクションの実行時間は連続的な実数値をとる。従来の同期的なMAPF向け手法をそのまま適用すると、非同期動作による待機時間の変動やエージェント間の速度差、衝突の時間的な重なり具合の違いにより、生成されるノードが許容される劣最適性の範囲外に外れやすくなり、探索が停滞するという困難がある。
非同期性による探索効率の低下を防ぐため、エージェント間の衝突特性を考慮して劣最適性の許容範囲（境界値）を各エージェントに分配する新たな手法を提案している。具体的には、制約による遅延時間やエージェントの速度を反映した境界分配と、衝突の回数ではなく時間的な重なりの長さに着目したノード優先順位付けを導入することで、先行研究よりも高い成功率と探索効率を実現している。
高レベルおよび低レベルの双方にフォーカル探索を導入したBCBS-AAを提案する。境界値の分配には、制約による禁止時間間隔から遅延を推定する非同期境界分配（ABD）、高速なエージェントへより多くの境界値を割り当てる速度境界分配（SBD）、およびこれらを組み合わせつつ生成されるノードがグローバルな劣最適境界内に収まるよう調整する混合境界分配（MBD）を用いる。ノードの優先順位付けには、衝突の回数ではなく、衝突が発生する時間的な重なりの長さを指標とする衝突強度優先順位付け（CIP）を用いる。高レベルでは、各衝突ペアにおける禁止時間間隔の合計に基づいた衝突強度が小さいノードを優先し、低レベルでは、経路上の各頂点における他エージェントとの時間的な重なり時間の累積であるソフト衝突強度を最小化するように状態を選択する。
4つのベンチマークマップを用い、エージェントの速度が1から20の間でランダムに設定される環境で評価を行った。提案手法であるMBDは、既存手法を非同期環境に単純適応させたECBS-AAと比較して成功率を大幅に向上させ、特定のマップでは最大64%の改善を示した。また、衝突強度に基づく優先順位付けを低レベルと高レベルの両方に適用した手法は、既存手法と比較して高レベルノードの展開数を最大で1桁削減し、最も高い成功率を達成した。
本手法は、非同期アクションによって生じる異なる種類の衝突を区別して扱っていない。非同期アクションに起因する衝突は、その解決によって生じるコストの増加幅が衝突の種類によって異なるため、今後は衝突の種類に応じた境界分配を行うことが課題である。
マルチエージェント経路計画（MAPF）では、全エージェントが同期して一定時間の動作を行うという仮定が一般的であるが、実用性を高めるためには非同期かつ非一律な動作時間を扱うMAPF-AAへの対応が求められる。既存の有界劣最適アルゴリズムをそのままMAPF-AAに適用すると、非同期動作の影響により性能が低下するという課題がある。本研究では、エージェント間の衝突に基づいて劣最適性の許容範囲を各エージェントに分配する手法と、探索時のノード選択手法の両方に非同期性を考慮した新たな技術を導入している。実験の結果、提案手法は既存手法と比較して成功率を最大60%向上させ、探索におけるノード展開数を最大で1桁削減することに成功している。
本研究は、エージェントごとに移動速度が異なり、各アクションの実行時間が連続的な実数値をとる非同期アクションMAPF（MAPF-AA）において、解の品質保証を伴う有界劣最適解を求める手法BCBS-AAを提案している。従来のMAPFにおける有界劣最適化手法をそのまま適用すると、非同期性による待機時間の変動やエージェント間の速度差、および衝突の時間的な重なり具合の違いにより、生成されたノードが許容誤差の範囲外に外れてしまい、探索効率が低下するという課題がある。これに対し、提案手法は、制約条件に基づく時間間隔の長さから遅延を推定する非同期バウンド分布（ABD）、高速なエージェントにより多くの許容誤差を割り当てる速度バウンド分布（SBD）、およびこれらを組み合わせた混合バウンド分布（MBD）を用いることで、探索ノードを効率的にFOCALリスト内に保持する。さらに、衝突の数ではなく、衝突が発生する時間的な重なりの長さに基づく衝突強度優先順位付け（CIP）を導入することで、ノードの優先順位決定を最適化している。MAPFのベンチマークを用いた評価の結果、BCBS-AAは既存手法を単純に適応させた場合と比較して、成功率を最大60%向上させ、探索時のノード展開数を最大で1桁削減している。
非同期アクションを伴うマルチエージェント経路計画（MAPF-AA）は、N個のエージェントが、頂点とエッジからなる無向グラフ G = (V, E) 上で、各エージェントの開始地点から目標地点まで、衝突を回避する経路集合を求める問題である。各エッジの移動時間はエージェントごとに異なり、エージェントは任意の時間、頂点で待機することが可能である。エージェントがアクションを実行する際、開始頂点と終了頂点の両方がアクションの継続時間中も占有される「期間占有（Duration Occupancy）」という概念を用いる。複数のエージェントが同じ頂点を非空の時間間隔にわたって同時に占有する場合を「期間衝突（Duration Conflict）」と定義する。経路のコストは、各エージェントが目標地点に到達し、その後衝突なく滞在可能となる時刻として定義され、目的関数は全エージェントのコストの総和（SoC）の最小化となる。移動時間の設定には、エージェントの速度とエッジの長さの比から算出する速度駆動型と、任意の正の値を直接入力する一般型の2種類が想定されている。
CBS-AAは、非同期アクションを伴うマルチエージェント経路探索において最適解を求めるための2レベル探索アルゴリズムです。この手法は制約木を構築して衝突を検出し、時間区間制約を付与することで分岐を行います。低レベルのプランナーであるSIPPS-WCは、エージェントが安全な時間区間内で待機する際に発生し得るソフト衝突を考慮し、状態に待機によるソフト衝突回数を保持することで、連続的な時間軸での再計画を可能にします。衝突解決にはCMAが導入されており、これは衝突に関与するエージェントの進入および退出にかかる最小移動時間に基づき、特定の時間区間において衝突頂点への進入アクションを禁止する制約を複数のアクションに伝播させます。本研究の基盤となる手法では、最適解のw倍以内のコストを保証する有界劣最適化の枠組みを用い、高レベルの探索において、全体の最小下界のw倍以下のコストを持つ制約木ノードを優先的に探索します。さらに、Flex Distributionを用いることで、再計画するエージェントに他のエージェントの余剰なコスト分を境界として割り当て、再計画の柔軟性を高めます。具体的には、衝突数に比例して分配するCFDや、制約による遅延を推定して分配するDFD、およびこれらを組み合わせつつ、生成されるノードが常にグローバルな劣最適境界内に収まるよう制御するMFDといった戦略により、探索の効率化を図っています。
本手法は、非同期アクションを伴うマルチエージェント経路探索（MAPF-AA）において、限定的な劣最適性を保証しつつ探索効率を高めるECBS-AAを提案している。高レベルおよび低レベルの双方にフォーカル探索を導入し、衝突の強度に基づいた柔軟な境界値（Bound）の分配とノード選択を行う。
境界値の分配には、CMA制約の禁止時間間隔から遅延を推定する非同期境界分配（ABD）、エージェントの速度に基づき速いエージェントへより多くの境界値を割り当てる速度境界分配（SBD）、およびこれらを組み合わせつつ、子がグローバルな劣最適性の範囲内に収まるよう調整する混合境界分配（MBD）を用いる。MBDでは、ABDによる遅延推定とSBDによる速度比を用いた値のうち、大きい方を候補として選択し、それがグローバルな劣最適性の境界を超えないよう必要に応じて境界値を縮小する。
高レベルの探索では、各衝突ペアにおける禁止時間間隔の最小値の合計である衝突強度スコアを用い、このスコアが小さいノードを優先的に展開する。低レベルのプランニングにおいても、単なる衝突回数ではなく、経路上の各頂点における他エージェントとの時間的な重なり時間の累積であるソフト衝突強度を最小化するように状態を選択する。これにより、衝突解決に伴うコスト増加を抑え、探索が効率的に解に到達することを可能にしている。
4つのベンチマークマップを用い、エージェントの速度が1から20の間でランダムに設定される非同期アクション環境下での評価が行われました。提案手法であるMBDは、衝突の時間の重なりを考慮するABDと、高速なエージェントに余裕を持たせるSBDを組み合わせることで、従来のECBS-AAと比較して成功率を大幅に向上させ、特にmaze-128-128-10マップでは成功率が最大64%改善されました。MBDは、制約の蓄積状況に応じてABDとSBDを動的に切り替えることで、生成されたノードがグローバルな劣最適境界内に留まる割合であるGB ratioを高め、高レベルノードの展開数を抑制します。さらに、衝突強度に基づく優先順位付けを行うCIPを低レベルおよび高レベルの両方に適用したMBD-LHは、既存手法と比較して高レベルノードの展開数を約1桁削減し、最も高い成功率を達成しました。これらの結果は、非同期性を考慮した境界の分配と、衝突の性質に応じた優先順位付けが、探索効率と解の発見能力の両面で有効であることを示しています。
本研究では、非同期アクションを伴うマルチエージェント経路探索において、有界劣最適解を求めるための新しい柔軟な境界分布およびノード優先順位付け手法を提案した。提案手法であるBCBS-AAは、実験の結果、厳しい境界条件下においても既存手法と比較して成功率が高く、高レベルのノード展開数を抑えられることを示した。今後の課題として、非同期アクションによって生じる異なる種類の衝突を考慮した研究が挙げられる。非同期アクションに起因する衝突は、その解決によって生じるコストの増加幅が異なるため、衝突の種類に応じた柔軟な境界分布を適用することが求められる。