從零開啟自動駕駛工程師之路（六）| 規劃

作者：曉暢

內容來源：上汽零束SOA開發者論壇

原文連結：

https：//bbs。z-onesoft。com/omp/community/front/api/page/mainTz？articleId=8061

這一系列的第六篇文章我們來聊聊規劃。

這就好像你預測了股市未來的走勢，自然想去佈局規劃一番，在那個時間點買入賣出合適。雖然你也知道這預測非常不靠譜，但總想規劃一番。

扯遠了~自動駕駛也是如此，好不容易對周圍的環境完成了建模和預測，接下來就是規劃你的行駛路線了。

規劃可真是門大學問。這不，瞄了一眼Apollo的課程，好傢伙，直呼好傢伙，其他章節都是幾節十幾節課，規劃這一章直接搞了足足25節課！行吧，那就慢慢學唄。

規劃能有這麼多章節自然也是有原因的——在Apollo中它被分成兩個部分，即

路線規劃模組與軌跡規劃模組

。路線規劃屬於宏觀層面，用之前的地圖資料生成車輛的可行使路徑，這一步就是你手機上的地圖軟體每天在乾的事情。但是它不會細緻的告訴你每一步該怎麼走，而這個任務就屬於軌跡規劃。軌跡規劃做的是微觀層面的事情，定義好一系列的點，這些點自帶速度、角度、時間戳等屬性，可謂是奶媽級教程教車輛一步步如何行駛。這樣便能避開障礙物併為乘客創造平穩的乘車體驗。

1。路徑規劃

我們先來看看路徑規劃。

路徑規劃的目標是在地圖上找到從A到B的最佳路線。該模組一般需要三個輸入：地圖、自身位置以及目的地。前兩者都可透過之前的感知、定位模組獲得，目的地一般由乘客提供。有了這些資訊，路徑規劃便能開始工作，這一搜尋路線的過程被稱為

路由

。

顯然一開始就上高精地圖進行路線規劃實在是太複雜了——高精地圖的眾多資料會讓你眼花繚亂以致無法迅速找到那條最佳路線。這時候我們就需要一些抽象簡化手段，我們將起始地和目標地設成點，可行駛路線看成邊，那隻要想辦法用線將這兩個點連線起來，路線規劃不就成了！這種搜尋路徑的方式就是圖搜尋。

對於搜尋進行路徑規劃的演算法，計算機可是非常在行。原因無他，只要是重複做一樣事情，計算機就會非常得心應手。恰巧，路徑規劃就是這麼一種搜尋演算法，它會讓計算機不斷計算網格中一個節點周圍的所有節點的到達難度的數值，從而選取出裡面最小的那個作為下一個節點。以此類推，直到摸索到終點處，再倒退回去，就找到了兩點之間的最優路徑。

很顯然，這種暴力的演算法很浪費計算資源，尤其是在地圖增大之後，路徑搜尋任務將無法進行。那如何進行改進？

這時候就會用到經典的一種路徑規劃演算法叫A*（A star）演算法。這個演算法分兩步。第一步，我們需要計算從開始節點到候選節點的成本g，這很容易獲得，因為開始節點與“下一跳”的節點是相鄰的；第二步，也是關鍵的一步，我們需要估算從候選節點去往目的地的成本h，這就比較有難度了，因為兩者之間還有一段距離，不太好進行計算。一般採用的方式是啟發式的估算方法，我們可以透過自定義的方式來求得所需的成本。最後我們將求得的g和h加起來得到f，最佳候選節點便是f值最小的那個節點。不斷重複以上過程，我們終將獲得從起始點到目的地的穩定路徑。

我們來看一個具體的例子。

在這樣的一個有直線和環形的路線圖中，想要到達打星的目標點，我們有幾種選擇。首先我們把路線圖抽象為圖，透過節點和邊來表示，其次我們考慮每一步所耗費的值。在這個路口，車輛有三種選擇，直行、左轉或右轉。由於車輛是靠右行駛，很顯然直行和右轉都不會耗費什麼時間，而左轉所需要的cost就會較多。接下來我們再考慮從此處到終點的耗費值，由於直行的話相當於上了一個高架，要從高架上下來才能抵達終點，遠比繞弧線所需的時間要多，因此直行又成了一個不划算的選擇。