原文鏈接：進(jìn)階課程?丨Apollo規(guī)劃技術(shù)詳解——Motion Planning with Autonomous Driving

自動駕駛車輛的規(guī)劃決策模塊負(fù)責(zé)生成車輛的行駛行為，是體現(xiàn)車輛智慧水平的關(guān)鍵。規(guī)劃決策模塊中的運動規(guī)劃環(huán)節(jié)負(fù)責(zé)生成車輛的局部運動軌跡，是決定車輛行駛質(zhì)量的直接因素。

在大多數(shù)情況下，運動規(guī)劃問題的精確解決方案在計算上是難以處理的。 因此，數(shù)值近似方法通常在實踐中使用。在最流行的數(shù)值方法中，變分方法將問題視為函數(shù)空間中的非線性優(yōu)化，圖形搜索方法構(gòu)建車輛狀態(tài)空間的圖形離散化并使用圖形搜索測量方法搜索最短路徑，此外基于樹的增量方法，從車輛的初始狀態(tài)逐步構(gòu)造可到達(dá)狀態(tài)的樹，然后選擇這種樹的最佳分支。

上周阿波君為大家詳細(xì)介紹了「進(jìn)階課程?Apollo規(guī)劃技術(shù)詳解——Basic Motion Planning and Overview」。

通過介紹了基本的運動規(guī)劃和概述，其中詳細(xì)的介紹了如何構(gòu)建汽車的運動規(guī)劃問題，其中包括路徑查找問題、路徑優(yōu)化，可以通過A-Star算法、D-Star算法對路徑搜索進(jìn)行優(yōu)化，通過曲線平滑的方式來優(yōu)化折線。除此之外，還簡單的介紹了無人駕駛的硬件系統(tǒng)和系統(tǒng)軟件。

本周阿波君將與大家分享Apollo規(guī)劃技術(shù)詳解——Motion Planning with Autonomous Driving。下面，我們一起進(jìn)入進(jìn)階課程第22期。

---

目錄

1 - 運動規(guī)劃基本方法

2 - 運動規(guī)劃框架

2-1 RRT（基于快速擴(kuò)展隨機(jī)樹算法）

2 - 2 Lattice網(wǎng)格方法

2 - 3 Polynomial方法

2 - 4 Functional Optimization方法

---

1 - 運動規(guī)劃基本方法

本節(jié)主要介紹運動規(guī)劃的一些基本方法，重點從robotics的角度闡釋。這些方法主要有RRT、Lattice、Spira、Polynomial、Functional Optimization等，如下圖所示。

???????????????????????????????????????????????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????????????????????????運動規(guī)劃方法

前面講到?jīng)Q策規(guī)劃問題，都是從質(zhì)點模型出發(fā)考慮。質(zhì)點模型將運動軌跡當(dāng)成一個點，這個點和無人車是不一樣的。假設(shè)把一個無人車看成一個點，這個點和另一個點不相撞，在數(shù)學(xué)定義上是點和點沒有交集，但是在實際生活中一個車和一個車可是會相撞。下面介紹解決這些問題的一些方法：Configuration Space （構(gòu)造空間），也就是說能夠控制什么變量。對于剛體而言，不僅是XY坐標(biāo)，還要有heading信息才能研究跟障礙物之間的關(guān)系。對于無人車來說有更多的變量。其復(fù)雜性主要體現(xiàn)在兩個方面，一個是Space Dimensionality（空間維度），另一個Geometric Complexity（幾何復(fù)雜性）。例如bounding box跟bounding box之間怎么相交，一個多面體跟一個多面體之間怎么檢測出路徑，以避免跟另一個障礙物相交。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????????????????????????????????構(gòu)造空間方法

規(guī)劃問題中涉及到一些約束條件，Constraints（約束）大概分為三類：一個是Local?Constraint，例如避免和障礙物碰撞。第二是Differential Constraint，比如邊界曲率。最后是Global Constraint。比如最短路徑。

---

2 - 運動規(guī)劃框架

運動規(guī)劃是在連續(xù)空間的一種優(yōu)化，對于連續(xù)空間過程的優(yōu)化往往比較難。因此，通常先將連續(xù)空間問題離散化表示，然后尋找對應(yīng)的解決方案。如下圖所示，可以使用圖搜索的方法對離散空間問題進(jìn)行求解。

那么，如何去離散化連續(xù)空間呢？有種方法叫做Roadmap，這個方法使用簡單的連通圖表示配置空間，類似于城市如何用地鐵圖表示。其中Visibility Graph是一種常用的Roadmap方法，如下圖所示。Visibility Graph將起始節(jié)點，所有障礙物的頂點和目標(biāo)節(jié)點相互連接來構(gòu)建路線圖。我們會發(fā)現(xiàn)，從紅點到綠點的最短路徑一定會通過靠近障礙物邊界的折線。

???????????????????????????????????????????????????? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????????????????????????圖搜索方法

除了Roadmap之外，還有Cell decomposition（網(wǎng)格分解方法）和Potential field（勢場法）等路徑規(guī)劃方法。Cell decomposition將整個空間分割成一個個cell，通過cell的連接圖表示自由空間的連接屬性。Potential field就是直接用微分方法處理。

?????????????????????????????????????????????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????????????????????????路徑規(guī)劃方法

一種常用的抽象連續(xù)空間的方法叫做PRM。它在整個配置空間隨機(jī)采樣一些點，如果點在障礙物上則去掉，然后將這些點連接起來，如下圖所示的紫色點。從點s到g的最短路徑就可以利用A-Star算法進(jìn)行求解。但是該方法要求是對全局感知，而無人車是一個部分感知的應(yīng)用場景，因此有RRT的改進(jìn)方法。

???????????????????????????????????????????????????? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????????????????????????PRM 方法

---

2-1 RRT（基于快速擴(kuò)展隨機(jī)樹算法）

如下圖所示，它構(gòu)造一個根結(jié)點為起始點的配置空間樹，通過隨機(jī)采樣增加葉子節(jié)點的方式，生成一個隨機(jī)擴(kuò)展樹，當(dāng)隨機(jī)樹中的葉子節(jié)點包含了目標(biāo)點或進(jìn)入了目標(biāo)區(qū)域，便可以在隨機(jī)樹中找到一條由從初始點到目標(biāo)點的路徑。如果葉子節(jié)點和目標(biāo)節(jié)點之間的連接被障礙物阻擋，則需要重新采樣。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????基于快速擴(kuò)展隨機(jī)樹算法

通過這種方式離散化的線是不適合無人車行駛的，因為這些線的curvature不連續(xù)，甚至curvature都沒有。針對這一問題MIT提出使用平滑曲線進(jìn)行連接的方法，如下圖所示。但是該方法得到的路徑可能還是不夠平滑，另外對動態(tài)障礙物的處理也存在問題。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????平滑曲線進(jìn)行連接的方法

---

2 - 2 Lattice網(wǎng)格方法

針對上述問題，就有人提出了Lattice網(wǎng)格方法。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????Lattice網(wǎng)絡(luò)方法

如上圖所示，最原始的Lattice網(wǎng)格方法非常簡單，它在XY世界坐標(biāo)系中，以1米為單位進(jìn)行網(wǎng)格劃分，然后用無人車可以行進(jìn)的、曲率連續(xù)的曲線將起始點和目標(biāo)點連接起來。但是這種方法還是不能滿足需求。對于道路來說，這種抽象方式并不合適。Lattice Sampling撒點不能在規(guī)則化坐標(biāo)系下去撒點，因為道路并不是一個完全XY的坐標(biāo)系。因此提出了在sl坐標(biāo)系下進(jìn)行離散的方法Lattice in Frenet Frame。

---

2 - 3 Polynomial方法

當(dāng)抽象出這些點之后，如何使用平化曲線連接呢？ 有一種使用螺旋曲線的方法，即Splines方法。此外，還可以使用路徑-速度迭代優(yōu)化的方法對Lattice方法進(jìn)行優(yōu)化，也就是Polynomial方法。它將問題降維，分成了path 和 speed兩個維度逐漸優(yōu)化，這是一種iterative的處理方式。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????Polynomial方法

---

2 - 4 Functional Optimization方法

還可以用Functional Optimization方法對運動規(guī)劃進(jìn)行處理，對整個問題建模，設(shè)計相應(yīng)的代價函數(shù)。二次規(guī)劃就是其中一種常用的方法。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????????????Functional Optimization方法???????

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。