信号機のない交差点において、複数のCAVが衝突を回避しながら効率的に走行する問題。交差点は、一度に1台の車両しか占有できない16個の予約制サブゾーンに分割されており、車両は直進、左折、右折のいずれかの経路を通る。従来の、到着順に通過するFIFO戦略やモンテカルロ木探索（MCTS）を用いた手法では、車両の遅延を十分に抑えることが困難であった。
従来の優先度付き計画法（PP）やMCTSに対し、MAPFの知見を活用したOrder-based Search（OBS）を導入した点。OBSは全順序ではなく部分順序を扱うことで、既存手法よりも優れた解の質を実現する。また、簡略化された運動モデルに基づく順序決定と、複雑な運動学的自転車モデルに基づく軌道最適化を分離することで、モデル間の不一致に対する堅牢性を実現した。
車両の調整を、通過順序の最適化と軌道計算の2段階で行う。高レベルの探索では、交通構造に基づく枝刈りを行うPP、および部分的な順序関係を構築するOBSを用いる。低レベルの計画として、Kinematic Arrival Time Scheduling（KATS）を導入する。KATSは、各サブゾーンへの到着・出発時刻を、加速、定速走行、減速のプロセスを経て計算する。最後に、決定された順序に基づき、自転車モデルを用いた軌道最適化によって、先行車両やサブゾーンの時刻制約を満たす具体的な車両軌道を逐次的に算出する。
HighwayEnvを拡張したシミュレーション環境において、FIFO、MCTS、PPと比較検証を行った。評価指標は車両の平均遅延である。実験の結果、OBSは他の手法を上回る遅延低減を実現し、計算負荷が高い条件下でも、PPやMCTSよりも高いスループット（2160 veh/hr）を達成した。また、車線長、交差速度、再計画の間隔、および経路の種類（直進、右折、左折）を変化させた条件下でも、OBSの有効性が示された。
車線長が短いなど問題の複雑さが低い場合には、他の手法との性能差が縮まる傾向がある。再計画の頻度については、頻度が低すぎると遅延が増加するため、最適な再計画間隔が存在する。また、KATS（簡略モデル）と軌道最適化（複雑モデル）の間のモデルの不一致が、再計画時に制約のズレを引き起こす可能性がある。今後の課題として、人間の運転行動の不確実性が存在する混合交通環境への拡張や、より大規模な交通シナリオへの適用が挙げられる。
本研究は、信号機のない交差点におけるコネクテッド自動運転車（CAV）の協調的な走行を実現するため、マルチエージェント経路探索（MAPF）の知見と、車両の交差順序を最適化する構造およびヒューリスティックを融合させた手法を提案している。提案手法であるOrder-based Search with Kinematics Arrival Time Scheduling（OBS-KATS）は、車両の運動学的な制約を考慮した到着時刻のスケジューリングを伴う順序ベースの探索アルゴリズムであり、最適性と完全性を備えている。実験の結果、OBS-KATSは既存のアルゴリズムや固定的なヒューリスティック、およびKATSを用いた優先度付き計画と比較して高い性能を示した。この性能は、車両の到着率、車線の長さ、交差速度、および制御ホライゾンの異なる条件下においても維持される。本手法は、有向車線を持つ交通システムやマルチロボットのシナリオへ直接適用可能である。
本研究は、信号機のない交差点におけるコネクテッド自動運転車（CAV）の協調制御を目的とし、マルチエージェント経路探索（MAPF）の知見を導入した手法を提案している。車両の調整プロセスは、交差点の通過順序の最適化と、その順序に基づいた車両軌道の計算という2つの逐次的なフェーズに分割される。順序決定においては、交差点を予約制のサブゾーンに分割し、低レベルのKinematic Arrival Time Scheduling（KATS）を用いて各サブゾーンへの到着・出発時刻を計画する。既存の先入れ先出し（FIFO）やモンテカルロ木探索を用いた手法に対し、MAPFに着想を得た高レベルの優先度付き計画およびOrder-based Search（OBS）を用いることで、より優れた解の質を実現している。また、A*探索やSIPPのような単一エージェントの経路計画ではなく、軌道最適化を用いることで、自転車モデルに基づく車両の運動学的な制約を考慮した軌道生成を可能にしている。実験の結果、OBS-KATSは多様な交差点設定において、ベースライン手法と比較して車両の遅延を改善することを実証しており、さらにこの手法が車両の通過順序を見つける上で健全性、完全性、および最適性を備えていることを証明している。
信号機のない交差点における自動運転車の協調走行では、到着順に通過するFIFO戦略や、新しく到着した車両を既存の順序に挿入する動的再構成法、モンテカルロ木探索を用いて定期的に順序を再計画する手法などが提案されている。一方、古典的なマルチエージェント経路探索（MAPF）は、離散グラフ上で衝突を回避しつつ最短経路を求めるNP困難な問題であり、計算量を抑えるためにA*探索などの単一エージェント用プランナーを繰り返し呼び出す手法が一般的である。MAPFの代表的なアルゴリズムには、エージェントごとに優先順位を付けて順次計画を行う優先度付き計画法や、エージェント間の衝突をバックトラッキングによる木探索で解決する衝突ベース探索（CBS）、およびその拡張である優先度ベース探索（PBS）が存在する。また、連続的な時間や空間を扱う研究として、グラフ上のエッジを一定速度で進むような簡略化された運動学を用いる連続時間MAPFや、サンプリングベースの手法を用いたマルチロボット運動計画がある。本研究では、交通システムには明確に定義された車線が存在するため、連続的な2次元空間を扱うのではなく、MAPFの知見を活用したアプローチをとる。
本研究では、交差点における協調自動運転を、車両の経路に沿った1次元の縦方向位置に基づく問題として定式化しています。交差点は、車両の経路が交差する幾何学的形状に基づき、一度に1台の車両しか占有できない16個の予約サブゾーンに分割されており、左右折を行う4台の車両が同時に交差することを可能にしています。各車両は、経路上の位置、速度、加速度の状態を持ち、直進および旋回時の最大速度や加速度の制限を受けます。計画の目的は、他の車両が存在しない場合の最小走行時間と実際の走行時間の差である車両遅延の総和を最小化するように、車両の交差順序を決定することです。この順序付けは、同じ予約サブゾーンを通過する車両間でのみ先行関係を定義する部分順序として扱われます。また、経路上の1次元モデルで計画された制御入力は、車両の重心から前後輪までの距離、操舵角、車体方位角、スリップ角を考慮した運動学的自転車モデルへと変換され、実行されます。
本セクションでは、マルチエージェント経路探索（MAPF）の観点から、交差点における車両の最適な通過順序を決定する手法を提案している。低レベルの計画として、各車両のサブゾーンへの到着および出発時刻を決定するKinematic Arrival Time Scheduling（KATS）を導入しており、これは定速走行を前提としたモデルを代理として用い、加速、最大速度での巡航、減速のプロセスを経て遅延を最小化する。高レベルの順序探索には、交通構造に基づく枝刈りを行うPrioritized Planning（PP）と、部分的な順序関係を構築しながら探索を行うOrder-based Search（OBS）がある。OBSは、探索予算を制限することで計算時間を制御しつつ、漸近的に最適な通過順序を見つけ出すことが可能である。決定された順序に基づき、各車両の軌道は、先行車両の軌道やサブゾーンの到着時刻制約を考慮した最適化問題として、逐次的に計算される。この手法は、KATSのような簡略化された運動モデルと、実際の複雑な運動モデルを用いた軌道最適化との間のモデルの不一致に対し、順序を固定することで、後続車両の計画が破綻するリスクを抑え、堅牢性を高める効果がある。
HighwayEnvをベースに、時間ステップを離散化してシミュレーションを行う実験設定が記述されている。交差点は一辺の長さが一定の正方形であり、車両は直進、左折、右折をそれぞれ60%、20%、20%の確率で行い、左折と右折にはそれぞれ異なる旋回半径が設定されている。車両の衝突判定は、車両のバウンディングボックスが重なったときに行われ、アルゴリズムの正確性を検証するために車両周囲への時間的または空間的な余白は設けられていない。実験では、ブートストラップサンプリングを用いて平均値の95%信頼区間を算出している。実装にはPythonが用いられ、軌道最適化にはCVXPYが使用されている。
提案手法であるOBSの有効性を、FIFO、MCTS、およびPPの各手法と比較して検証した結果、OBSは計算コストに対する車両の平均遅延の低減において、他の手法を大幅に上回る性能を示しました。1回の交差順序計算に10秒を要する極めて高い計算負荷を与えた場合でも、OBSの処理能力は2160台/時であり、PPの2080台/時やMCTSの2050台/時よりも高いスループットを達成しています。この性能差は、交通ヒューリスティクスの使用によるものではなく、全順序の探索ではなく部分順序を柔軟に扱うというOBSのアルゴリズム的な優位性によるものです。交差点の構成に関する頑健性の実験では、車線長が短い設定では手法間の差は小さいものの、問題の複雑さが増すにつれて手法間の差が拡大することが確認されました。また、再計画の間隔については、再計画の頻度が低すぎると遅延が増加する一方で、最適な再計画間隔が存在することが示されています。交差の幾何学的形状に関する分析では、OBSは直進、右折、左折のすべての経路で遅延を削減しますが、特に最も高い交差速度が可能な直進経路において顕著な遅延削減効果を発揮しています。
本研究は、ロボティクス分野と制御および高度道路交通システム分野の間の隔たりを埋めることを目的としている。今後の展望として、交差順序の決定が有効に機能する他の交通状況やロボティクス環境の特定、および人間の運転行動に伴う不確実性に対処するための混合交通環境への提案アルゴリズムの拡張が挙げられる。また、大規模かつ一般的な交通シナリオにおけるコネクテッド自動運転車（CAV）の協調制御に向け、ロボティクス分野からの知見を取り入れることで、将来的なアルゴリズムの発展に寄与することを目指している。