原文鏈接：進階課程?丨Apollo規劃技術詳解——Optimization Inside Motion Planning?

在自動駕駛軟件的開發中，運動規劃是最核心的模塊之一。它將綜合感知、定位和地圖等信息，規劃出無人車未來一段時間（約10秒）的一系列動作指令（方向盤轉角、油門、剎車等）。

運動規劃的問題——目標函數（objective function）和約束（constraint）。運動規劃的最終目的就是找出一條最優的運動軌跡，使其能夠最小化（或者最大化）目標函數，并且不違背任何約束。

在自動駕駛中，可以將環境抽象成SL坐標系，在此坐標下的曲線光滑度是有要求的，因此需要對軌跡線進行平滑處理。

上周阿波君為大家詳細介紹了「進階課程?Apollo規劃技術詳解——Motion Planning Environment」。其中詳細介紹了平滑的方法，包括對多項式進行優化，對?Bezier Spline?進行平滑處理，以及?Spline 2D?與?Spiral Path?等。

本周阿波君將繼續與大家分享Apollo規劃技術詳解——Optimization Inside Motion Planning的相關課程。下面，我們一起進入進階課程第25期。

目錄

1.運動規劃

2.二次規劃

---

約束問題的核心有三點：第一是目標函數的定義，目標函數比較清晰，對于后面的求解更有幫助。第二是約束，比如路網約束、交規、動態約束等。第三是約束問題的優化，比如動態規劃、二次規劃等。本節主要介紹動態規劃和二次規劃的基本概念，以及二次規劃問題的求解方法和形式化方法。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????運動規劃的概念

1.運動規劃

動態規劃通過類似于有限元的方式，把問題從連續空間抽象成離散空間，然后在離散空間中進行優化。雖然這種方法可以逼近連續空間中的最優解，但是計算復雜度很高。針對計算時間長的問題，可以使用牛頓方法進行優化，它的收斂次數是指數平方，也叫二次收斂。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????二次規劃算法

---

2.二次規劃

二次規劃算法的本質是牛頓法的 Taylor 展開，但是它的求解過程涉及更復雜的情況。因為二次規劃方法并不一定是處理一維問題，可能涉及更高階求導。在實踐中，二階導數基本可以滿足問題需求。

然而，牛頓法要求 locally convex 才能保證收斂，也就是導數是嚴格單調遞增的。但是一般函數并沒有這樣的特性，動態規劃或二次規劃都無法獲得全局最優解。為了解決這樣的問題，通常使用啟發式搜索方法。

首先通過動態規劃方式對整個問題有一個粗淺的認識，然后通過二次規劃進行細化。這種啟發式搜索方法也是目前百度 Apollo 的 EM 算法的核心思想。這種方法和人開車的過程是一樣的，通常駕駛員會先形成一個大概的指導思想，指明往什么方向開，然后再規劃一條最優路徑。

決策問題是一個離散空間中的優化問題，它的決定是什么？可以通過動態規劃對整個空間先形成一個粗淺的認識，然后以此為啟發，用二次規劃求最優解。

一般來說，二次規劃問題會寫成一個二次函數，如下圖所示。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????????????????二次規劃問題函數表達式

其中，X?是向量參數，Q?是一個對稱的正定矩陣，?是偏差項。對于這種沒有約束的二次規劃問題，只需要求導數等于0的那個點，使得 Qx=-C ，即可求解二次規劃問題。這是一個線性方程組，它的求解速度是 O（N3）。

對于帶約束的二次規劃問題，情況就相對復雜一點，如下圖所示。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????帶約束的二次規劃問題函數表達式

這種情況可以有很多種解法，其中一種把限制條件放到上面的式子中，通過換元，變成一個全新的 QP 問題求解，但是這種方法很慢。另一種方法是?Lagrangian method?，通過增加松弛變量的方式去掉約束條件，變成一個可以解決的問題。

對于不等式的約束條件，如何去求解呢？可以使用 active set method，其主要出發點是最后解，可能落到邊界上，如果真的是邊界最優，不等式約束就可以轉化為等式約束問題求解。有人總結出求解二次規劃問題的方法 KKT，其主要思想如下圖所示。

????????????????????????????????????????????????????????????????????????????????????????????????????????KKT條件

總的來說，對于求解非線性優化問題（自動駕駛中的規劃基本都是非線性的），通常就是用啟發式方法來求解。先用動態規劃給出一個粗略解，給出一個凸空間。然后用二次規劃方法在凸空間里去尋找最優解，如下圖所示。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????求解非線性優化問題

總結

以上是生活随笔為你收集整理的Apollo进阶课程㉕丨Apollo规划技术详解——Optimization Inside Motion Planning的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。