対象は、共有グラフ上で複数エージェントが衝突せずに目的地へ移動するMulti-Agent Path Finding（MAPF）である。通常のMAPF解は、各エージェントが特定の時刻に特定の場所へ到達することを要求するが、実ロボットでは運動学的制約、車輪のスリップ、通信やハードウェアの問題による遅延が生じる。Temporal Plan Graph（TPG）は、時間に依存する経路解を、経路が空間的に交差する箇所を中心としたエージェント間の順序依存関係へ変換する。BTPGは一部の順序依存を双方向ペアに緩和し、遅延時に本来後のエージェントが先に通過できる選択肢を与える。
主な新規性は、既存のBTPG-oが見逃していた非デッドロック・サイクルも検出し、追加可能な双方向ペアがない局所最大のBTPGを構築するBTPG-maxである。理論面では、BTPGにおける可能な非デッドロック・サイクルを定式化し、どのサイクルが実行可能なデッドロックを引き起こすかを判定する基盤を与える。アルゴリズム面では、到達可能なデッドロック・サイクルだけを調べることで、型2エッジを双方向ペアへ変換できるかを評価する。実証面では、従来法より多くのペアを発見し、探索途中のanytime性能と遅延下の実行性能を改善できることを示す。
まずMAPFソルバが生成した衝突回避経路をTPGへ変換し、型2エッジを一つずつ検査する。検査中の型2エッジに反対向きのエッジを追加してもデッドロックが生じない場合、そのエッジを双方向ペアへ変換する点はBTPG-oと共通している。BTPG-maxの違いは、手作業で定めた限定的な規則ではなく、到達可能性を考慮した深さ優先探索でデッドロック・サイクルを検出することである。到達不能な頂点とは、デッドロック後に到達できない頂点だけでなく、型1・型2依存によってそのような頂点に依存する頂点も含む。さらに、エッジをまとめて扱うgroupingの有無を別構成として評価し、処理順序が結果に及ぼす影響も調べる。
評価では、最適MAPFソルバCBSH2-RTCを使って各インスタンスの解を生成し、それをTPGへ変換した後、BTPG-oとBTPG-maxを比較した。BTPG構築法には10分の時間上限を設け、6種類のベンチマークマップ、各マップ5〜8種類のエージェント数、各エージェント数10個のランダムインスタンスを用いた。遅延実行のシミュレーションは合計3,900回で、各インスタンスを10個の乱数シードで実行した。遅延条件は、各非遅延タイムステップでエージェントの10%が30%の確率で5タイムステップ遅れるという、先行研究と同じ設定である。評価指標は発見した双方向ペア数、平均および中央値の実行時間改善、探索途中のanytime性能、実際に使用された双方向ペアである。
BTPG-maxは、groupingなしの比較では全マップでBTPG-oより多くの双方向ペアを見つけ、平均改善も高かった。groupingを加えると、BTPG-oとBTPG-maxの双方で発見ペア数と全体的な改善が大きく向上した。もっとも、双方向ペアの総数と実行時間の改善は必ずしも一致せず、grouping付きBTPG-maxがより多くのペアを得ても、別の手法の方が平均改善で上回るマップがあった。これは、どのペアが実行中に実際に反転使用されるか、および型2エッジを調べる順序に依存する。したがって、ペア数の最大化は実行時間短縮の完全な代理指標ではなく、groupingや順序設計との組合せで評価する必要がある。
TPGは、MAPF解を実行前に処理して、エージェント内の移動順序とエージェント間の通過順序を依存関係として表す手法である。経路が交差しない場合は主に同一エージェント内の型1エッジが現れ、交差地点で一方を先に通す必要がある場合に型2エッジが現れる。BTPGは、型2の固定順序を双方向ペアへ緩和し、遅延時に待機を減らす選択肢を提供する。
固定された通過順序を実行時に厳密に守らせるTPGでは、一つの遅延が他エージェントの待機を連鎖させ、場合によっては衝突やデッドロックにつながる。BTPGは柔軟性を高めるが、反対向きの依存関係を無制限に追加すると、実行時にデッドロックを起こす可能性がある。したがって、デッドロックを避けながら追加できる双方向ペアをできるだけ多く発見することが問題となる。
BTPG-maxは型2エッジの反転候補ごとに、追加された双方向関係が到達可能なデッドロック・サイクルを作るかを検査する。深さ優先探索では、通常の型2エッジと既存の双方向ペアを、サイクルが成立し得る状態に合わせてたどる。デッドロック後に到達不能となる頂点を依存関係に沿って伝播させることで、見かけ上のサイクルと実際に危険なサイクルを区別する。
CBSH2-RTCで生成したMAPF解を対象に、BTPG-o、BTPG-maxのgroupingなし構成、groupingあり構成を比較した。各BTPG手法の構築には10分のカットオフを設け、実行シミュレーションでは指定された確率的な5タイムステップ遅延を使用した。論文抜粋には、6マップの個別名称や全ての数値結果、実行時間の絶対値は完全には示されていない。
BTPG-maxは6マップすべてで、grouping付きBTPG-oに対して3〜5倍の双方向ペアを一貫して発見した。ただし、中央値の改善で上回ったのは6マップ中4マップであり、ペア数が多いほど常に改善が大きいわけではなかった。groupingなしではBTPG-maxがBTPG-oより、ペア数、平均改善、anytime性能のすべてで優れていたと報告されている。
BTPG-maxは、非デッドロック・サイクルの分析に基づいて局所最大の双方向ペア集合を構築する。実験結果は、従来法より多くの実行上の選択肢を作り、遅延環境での実行性能を高められることを支持する。groupingは双方の手法を大きく改善する重要な要素である。
局所最大性は、追加できる双方向ペアがないことを意味するが、全体として実行時間を最小化する大域最適性を意味しない。実行性能は、ペアの発見順序、実際に反転使用されるペア、groupingに依存する。評価は抜粋で示された6マップと特定の遅延モデルに基づいており、他の環境、遅延分布、オンライン実行での一般性はこの資料だけでは確立されていない。
MAPFの経路計画だけでなく、遅延を含む現実のロボット実行を考慮するには、時間を固定しすぎない安全な依存関係が必要である。BTPG-maxは、既存のMAPF解を捨てずに実行前の後処理として柔軟性を増やせるため、遅延に頑健な運用の一手段となる。遅延モデルを事前に仮定する別のロバストMAPF手法とも直交し、その上に適用できると著者らは位置づけている。
MAPFの実行時遅延、TPG/BTPG、衝突回避の依存関係、またはロボット群のanytime実行性能に関心がある研究者に適している。特に、局所的な安全性判定と双方向の通過選択を研究したい人に有用である。抜粋には完全な証明、全アルゴリズム詳細、全データ表が含まれていないため、厳密な再現や細部の検証には原論文全体が必要である。