百度 Apollo EM 動作計画
1分まとめ
経路（SL）と速度（ST）を交互に最適化するEMフレームワークと、DP＋QPによる凸近似で、L4実運用向けの軽意思決定型プランナーを構成した。2018年5月時点で約6万8000kmの閉ループ実車走行で検証されている。
- Frenetフレーム上で経路（SL）と速度（ST）をEM的に反復最適化し、DPとスプラインQPを組み合わせる実時間動作計画を提案した。
- 計算複雑度をO(n(M+N))に削減し、Nuvo-6108GC上で平均100ms未満の実行時間を報告している。
- 2018年5月時点で約68,000kmの閉ループ実車走行と10万時間超のシミュレーションで検証されているが、客観的指標による他手法との性能比較は示されていない。
- 実車検証は実環境だが、ベンチマークデータセットでの定量比較がないため、優位性の評価は実運用報告とケーススタディに依存している。
課題
L4自動運転の動作計画では、安全性・快適性・拡張性を同時に満たす必要がある。従来の探索ベースの3次元SLT最適化は計算量が大きい。経路と速度を分離する手法は動的障害物に対して最適性を失う。また決定と計画を分離すると、ルールベースの意思決定はコーナーケースに弱く、モデルベースでも実行可能領域を保証しない。
提案手法
EMプランナーは、多車線戦略とレーン内最適化の階層構造を持つ。多車線層では候補レーンごとにレーン内最適化を並列実行し、コストと安全規則で軌跡を選択する。レーン内最適化では、過去サイクルの軌跡を使って動的障害物のSL投影を行い（E-step）、DPで粗い経路と障害物の意思決定（追い越し・回避）を得て、その凸領域内でスプラインQPにより滑らかな経路を生成する（M-step）。次に生成された経路に基づき障害物をSTグラフに投影し（E-step）、同様にDP＋QPで速度プロファイルを生成する（M-step）。この経路・速度の反復を1サイクル内で行う。QPはピースワイズ5次多項式（3〜5セグメント、約30パラメータ）を使用し、アクティブセット法で平均3msで解かれる。
評価と結果
定量的な性能比較は提示されていない。実行時間はNuvo-6108GC-GTX1080-E3-1275環境で平均100ms未満と報告されている。展開実績として、2017年9月のApollo v1.5以降、2018年5月16日時点で3,380時間・約68,000kmの閉ループ自動運転実車走行と、10万時間・100万km超のシミュレーション試験が報告されている。ケーススタディでは、対向車とのすれ違い時に経路と速度を4ステップで反復更新し、S=40mでの減速回避がS=30mでの追い越しに収束する例を示している。
新規性
EMアルゴリズムを動作計画に適用し、経路と速度の反復最適化によって、軽量な意思決定と凸最適化を組み合わせた実時間L4プランナーを構築した点が新規性である。
限界
著者は限界として、DPはサンプリンググリッドに依存して最適解を保証しないこと、QPはDPの決定なしには非凸問題を解けないことを挙げている。論文には以下の制約がある。(1) 客観的なベンチマークによる他手法との比較がなく、提案手法の優位性が定量評価されていない。(2) 評価指標（衝突率、乗り心地指標など）が定義されておらず、実車走行時間と走行距離のみが示されている。(3) 実行時間は環境依存で、当時の計算機性能での報告であり、現在の実装にそのまま適用できる値ではない。(4) 動的障害物の予測は過去サイクルの軌跡に依存しており、予測誤差に対する頑健性の議論がない。その後の研究では、ニューラルネットワークによる学習ベースのプランナーや、より直接的な軌跡最適化手法が発展し、この手法のDP+QPの2段階構成は現在の標準的なベースラインの一つとして位置づけられる。
産業へのインパクト
この論文は、L4自動運転の動作計画を産業レベルで実装するための基盤となった。経路と速度を分離してEM的に反復する枠組み、DPで非凸問題の大域的な意思決定を行いQPで凸領域内の滑らかな解を得る構成は、その後多くの自動運転プランナーに影響を与え、Apolloオープンソースプラットフォームを通じて標準的な実装例として広く参照された。現在では学習ベース手法と比較されることも多いが、安全保証と実時間性を両立する古典的なベースラインとして、日本の自動車メーカー・サプライヤーが自社プランナーを評価する際の参照点になる。