1. 引言
在一套完整的自動駕駛系統(tǒng)中，如果將感知模塊比作人的眼睛和耳朵，那么決策規(guī)劃就是自動駕駛的大腦。大腦在接收到傳感器的各種感知信息之后，對當(dāng)前環(huán)境作出分析，然后對底層控制模塊下達(dá)指令，這一過程就是決策規(guī)劃模塊的主要任務(wù)。同時，決策規(guī)劃模塊可以處理多么復(fù)雜的場景，也是衡量和評價自動駕駛能力最核心的指標(biāo)之一[1]。
圖1. 自動駕駛系統(tǒng)中的決策規(guī)劃模塊分層結(jié)構(gòu)，引用自[2]
如圖1所示，典型的決策規(guī)劃模塊可以分為三個層次。
其中，全局路徑規(guī)劃（Route Planning）在接收到一個給定的行駛目的地之后，結(jié)合地圖信息，生成一條全局的路徑，作為為后續(xù)具體路徑規(guī)劃的參考；
行為決策層（Behavioral Layer）在接收到全局路徑后，結(jié)合從感知模塊得到的環(huán)境信息（包括其他車輛與行人，障礙物，以及道路上的交通規(guī)則信息），作出具體的行為決策（例如選擇變道超車還是跟隨）；
最后，運(yùn)動規(guī)劃（Motion Planning）層根據(jù)具體的行為決策，規(guī)劃生成一條滿足特定約束條件（例如車輛本身的動力學(xué)約束、避免碰撞、乘客舒適性等）的軌跡，該軌跡作為控制模塊的輸入決定車輛最終行駛路徑。
本文將分別介紹各層的主要作用與常見算法，并且比較各種算法的優(yōu)劣性及適用情景。
2. 全局路徑規(guī)劃（Route Planning）
全局路徑規(guī)劃是指在給定車輛當(dāng)前位置與終點(diǎn)目標(biāo)后，通過搜索選擇一條最優(yōu)的路徑，這里的“最優(yōu)”包括路徑最短，或者到達(dá)時間最快等條件。這一過程類似于我們生活中經(jīng)常用到的“導(dǎo)航”功能，區(qū)別在于自動駕駛中使用的高精地圖與我們常見的地圖不太一樣，在高精地圖中包含了每條車道在內(nèi)的更多信息。常見的全局路徑規(guī)劃算法包括Dijkstra和A算法，以及在這兩種算法基礎(chǔ)上的多種改進(jìn)。Dijkstra算法[3]和A*算法[4]也是在許多規(guī)劃問題中應(yīng)用最為廣泛的兩種搜索算法。
圖2. 全局路徑規(guī)劃示意
1. Dijkstra算法
Dijkstra算法是由計算機(jī)科學(xué)家Edsger W. Dijkstra在1956年提出，用來尋找圖形中節(jié)點(diǎn)之間的最短路徑。在Dijkstra算法中，需要計算每一個節(jié)點(diǎn)距離起點(diǎn)的總移動代價。同時，還需要一個優(yōu)先隊列結(jié)構(gòu)。對于所有待遍歷的節(jié)點(diǎn)，放入優(yōu)先隊列中會按照代價進(jìn)行排序。在算法運(yùn)行的過程中，每次都從優(yōu)先隊列中選出代價最小的作為下一個遍歷的節(jié)點(diǎn)。直到到達(dá)終點(diǎn)為止。
Dijkstra算法的優(yōu)點(diǎn)是：給出的路徑是最優(yōu)的；缺點(diǎn)是計算時間復(fù)雜度比較高（O(N2)）,因為是向周圍進(jìn)行探索，沒有明確的方向。
2. A*算法
為了解決Dijkstra算法的搜索效率問題，1968年，A算法由Stanford研究院的Peter Hart, Nils Nilsson以及Bertram Raphael發(fā)表，其主要改進(jìn)是借助一個啟發(fā)函數(shù)來引導(dǎo)搜索的過程。具體來說，A算法通過下面這個函數(shù)來計算每個節(jié)點(diǎn)的優(yōu)先級:
其中：
f(n) 是節(jié)點(diǎn)n的綜合優(yōu)先級。當(dāng)我們選擇下一個要遍歷的節(jié)點(diǎn)時，我們總會選取綜合優(yōu)先級最高（值最小）的節(jié)點(diǎn)。
g(n)是節(jié)點(diǎn)n距離起點(diǎn)的代價。
h(n) 是節(jié)點(diǎn)n距離終點(diǎn)的預(yù)計代價，這也就是A*算法的啟發(fā)函數(shù)。
3. 行為決策（Behavioral Layer）
在確定全局路徑之后，自動駕駛車輛需要根據(jù)具體的道路狀況、交通規(guī)則、其他車輛與行人等情況作出合適的行為決策。
這一過程面臨三個主要問題：
首先，真實(shí)的駕駛場景千變?nèi)f化，如何覆蓋？
其次，真實(shí)的駕駛場景是一個多智能體決策環(huán)境，包括主車在內(nèi)的每一個參與者所做出的行為，都會對環(huán)境中的其他參與者帶來影響，因此我們需要對環(huán)境中其他參與者的行為進(jìn)行預(yù)測；
最后，自動駕駛車輛對于環(huán)境信息不可能做到100%的感知，例如存在許多被障礙物遮擋的可能危險情形。
綜合以上幾點(diǎn)，在自動駕駛行為決策層，我們需要解決的是在多智能體決策的復(fù)雜環(huán)境中，存在感知不確定性情況的規(guī)劃問題。可以說這一難題是真正實(shí)現(xiàn)L4、L5級別自動駕駛技術(shù)的核心瓶頸之一，近年來隨著深度強(qiáng)化學(xué)習(xí)等領(lǐng)域的快速發(fā)展，為解決這一問題帶來了新的思路和曙光。
以下將行為決策層的模型分為四類分別介紹[5]：
1. 有限狀態(tài)機(jī)模型
自動駕駛車輛最開始的決策模型為有限狀態(tài)機(jī)模型[6]，車輛根據(jù)當(dāng)前環(huán)境選擇合適的駕駛行為，如停車、換道、超車、避讓、緩慢行駛等模式，狀態(tài)機(jī)模型通過構(gòu)建有限的有向連通圖來描述不同的駕駛狀態(tài)以及狀態(tài)之間的轉(zhuǎn)移關(guān)系，從而根據(jù)駕駛狀態(tài)的遷移反應(yīng)式地生成駕駛動作。
有限狀態(tài)機(jī)模型因為簡單、易行，是無人駕駛領(lǐng)域目前最廣泛的行為決策模型，但該類模型忽略了環(huán)境的動態(tài)性和不確定性，此外，當(dāng)駕駛場景特征較多時，狀態(tài)的劃分和管理比較繁瑣，多適用于簡單場景下，很難勝任具有豐富結(jié)構(gòu)化特征的城區(qū)道路環(huán)境下的行為決策任務(wù)。
2. 決策樹模型
決策/行為樹模型[7]和狀態(tài)機(jī)模型類似，也是通過當(dāng)前駕駛狀態(tài)的屬性值反應(yīng)式地選擇不同的駕駛動作，但不同的是該類模型將駕駛狀態(tài)和控制邏輯固化到了樹形結(jié)構(gòu)中，通過自頂向下的“輪詢”機(jī)制進(jìn)行駕駛策略搜索。這類決策模型具備可視化的控制邏輯，并且控制節(jié)點(diǎn)可復(fù)用，但需要針對每個駕駛場景離線定義決策網(wǎng)路，當(dāng)狀態(tài)空間、行為空間較大時，控制邏輯將比較復(fù)雜。另外，該類模型同樣無法考慮交通環(huán)境中存在的不確定性因素。
3. 基于知識的推理決策模型
基于知識的推理決策模型由“場景特征－駕駛動作”的映射關(guān)系來模仿人類駕駛員的行為決策過程，該類模型將駕駛知識存儲在知識庫或者神經(jīng)網(wǎng)絡(luò)中，這里的駕駛知識主要表現(xiàn)為規(guī)則、案例或場景特征到駕駛動作的映射關(guān)系。進(jìn)而，通過“查詢”機(jī)制從知識庫或者訓(xùn)練過的網(wǎng)絡(luò)結(jié)構(gòu)中推理出駕駛動作。
該類模型主要包括：基于規(guī)則的推理系統(tǒng)[8]、基于案例的推理系統(tǒng)[9]和基于神經(jīng)網(wǎng)絡(luò)的映射模型[10]。
該類模型對先驗駕駛知識、訓(xùn)練數(shù)據(jù)的依賴性較大，需要對駕駛知識進(jìn)行精心整理、管理和更新，雖然基于神經(jīng)網(wǎng)絡(luò)的映射模型可以省去數(shù)據(jù)標(biāo)注和知識整合的過程，但是仍然存在以下缺點(diǎn)：
其“數(shù)據(jù)”驅(qū)動機(jī)制使得其對訓(xùn)練數(shù)據(jù)的依賴性較大，訓(xùn)練數(shù)據(jù)需要足夠充分[11]；
將映射關(guān)系固化到網(wǎng)絡(luò)結(jié)構(gòu)中，其解釋性較差；
存在“黑箱”問題，透明性差，對于實(shí)際系統(tǒng)中出現(xiàn)的問題可追溯性較差，很難發(fā)現(xiàn)問題的根本原因。
4. 基于價值的決策模型
根據(jù)最大效用理論，基于效用／價值的決策模型的基本思想是依據(jù)選擇準(zhǔn)則在多個備選方案中選擇出最優(yōu)的駕駛策略／動作[12]。
為了評估每個駕駛動作的好壞程度，該類模型定義了效用（utility）或價值（value）函數(shù)，根據(jù)某些準(zhǔn)則屬性定量地評估駕駛策略符合駕駛?cè)蝿?wù)目標(biāo)的程度，對于無人駕駛?cè)蝿?wù)而言，這些準(zhǔn)則屬性可以是安全性、舒適度、行車效率等，效用和價值可以是由其中單個屬性決定也可以是由多個屬性決定。
澳大利亞格里菲斯大學(xué)的Furda和Vlacic提出了多準(zhǔn)則決策方法從候選動作集中選擇最優(yōu)的駕駛動作[13]；新加坡國立大學(xué)的Bandyopadhyay等人提出了基于POMDP的行為決策模型[14]，用以解決存在感知不確定性的情況；卡內(nèi)基梅隆大學(xué)的Wei J等人提出基于PCB（Prediction and-Cost-function based）的行為決策模型[15]，其側(cè)重點(diǎn)在于如何構(gòu)建恰當(dāng)?shù)拇鷥r函數(shù)來指導(dǎo)對環(huán)境的預(yù)測；為了解決在多智能體參與的復(fù)雜環(huán)境中的決策問題，許多基于博弈論的模型也被研究者用來推理車輛之間的交互行為[16]，[17]；此外，因為在特征提取方面的優(yōu)勢，深度強(qiáng)化學(xué)習(xí)技術(shù)也開始被廣泛應(yīng)用，以完成最優(yōu)駕駛動作的生成[18]。
4. 運(yùn)動規(guī)劃（Motion Planning）
在確定具體的駕駛行為之后，我們需要做的是將“行為”轉(zhuǎn)化成一條更加具體的行駛“軌跡”，從而能夠最終生成對車輛的一系列具體控制信號，實(shí)現(xiàn)車輛按照規(guī)劃目標(biāo)的行駛。這一過程稱為運(yùn)動規(guī)劃（Motion Planning），運(yùn)動規(guī)劃的概念在機(jī)器人領(lǐng)域已經(jīng)有較長時間的研究歷史，我們可以從數(shù)學(xué)的角度將它看做如下的一個優(yōu)化問題：
路徑規(guī)劃（Path Planning）
圖3. 路徑規(guī)劃的定義
在以機(jī)器人為代表的許多場景中，我們可以認(rèn)為周圍的環(huán)境是確定的。在這種情況下，所謂的路徑規(guī)劃，是指在給定的一個狀態(tài)空間Χ，尋找一個滿足一定約束條件的映射σ:[0,1]Χ，這些約束包括：
確定的起始狀態(tài)以及目標(biāo)點(diǎn)所在的區(qū)域
避免碰撞
對路徑的微分約束（例如在實(shí)際問題中路徑曲率不能太小，對應(yīng)于其二階導(dǎo)數(shù)的約束）
該優(yōu)化問題的目標(biāo)泛函定義為J(σ)，其具體意義可以表示為路徑長度、控制復(fù)雜度等衡量標(biāo)準(zhǔn)。
然而在自動駕駛問題中，車輛周圍的環(huán)境是持續(xù)動態(tài)變化的，因此單純的路徑規(guī)劃不能給出在行駛過程中一直有效的解，因此我們需要增加一個維度——時間T，相應(yīng)的規(guī)劃問題通常被稱為軌跡規(guī)劃。
軌跡規(guī)劃（Trajectory Planning）
圖4. 軌跡規(guī)劃的定義
時間維度的增加為規(guī)劃問題帶來了巨大的挑戰(zhàn)。例如，對于一個在2D環(huán)境中移動一個抽象為單點(diǎn)的機(jī)器人，環(huán)境中的障礙物近似為多邊形的問題。路徑規(guī)劃問題可以在多項式時間內(nèi)求解，而加入時間維度的軌跡規(guī)劃問題已經(jīng)被證明是NP-hard問題。
在自動駕駛的實(shí)際場景中，無論是對車輛本身還是對周圍環(huán)境，建立更為精確的模型意味著對優(yōu)化問題更為復(fù)雜的約束，同時也意味著求解的更加困難。因此實(shí)際采用的算法都是建立在對實(shí)際場景的近似前提下，在模型精確性和求解效率二者之間尋求一個最佳的平衡點(diǎn)。
下文對自動駕駛領(lǐng)域目前常見的幾類運(yùn)動規(guī)劃算法分別進(jìn)行介紹，在實(shí)際中，往往是其中幾類思想的結(jié)合才能最終達(dá)到比較好的規(guī)劃結(jié)果，并滿足更多的不同場景。
1. 基于搜索的規(guī)劃算法
通過搜索來解決運(yùn)動規(guī)劃問題是最樸素的思路之一,其基本思想是將狀態(tài)空間通過確定的方式離散成一個圖,然后利用各種啟發(fā)式搜索算法搜索可行解甚至是最優(yōu)解。
在將狀態(tài)空間離散化的過程中，需要注意的是確保最終形成的柵格具有最大的覆蓋面積，同時不會重復(fù)。如圖5所示，左邊的柵格是由直行、左轉(zhuǎn)90°、右轉(zhuǎn)90°這三種行為生成；而如果選擇直行、左轉(zhuǎn)89°、右轉(zhuǎn)89°三種行為，最后就無法生成一個覆蓋全部區(qū)域的柵格結(jié)構(gòu)。
圖5. 構(gòu)建柵格圖，引用自[2]
在將狀態(tài)空間柵格化之后，我們就可以使用前文已經(jīng)介紹的Dijkstra、A*搜索算法，完成最終的規(guī)劃。然而在實(shí)際復(fù)雜環(huán)境中，柵格數(shù)目眾多，并且環(huán)境隨時間動態(tài)變化，會導(dǎo)致搜索結(jié)點(diǎn)過多，因此發(fā)展出了多種改進(jìn)算法，用以處理不同的具體場景：
1） Hybrid A* 算法，在A*算法的基礎(chǔ)上考慮了車的最大轉(zhuǎn)向問題，例如限定計算的路徑上車最大轉(zhuǎn)向不超過5°。該算法目前的應(yīng)用場景有車掉頭（Stanford 參加DARPA 挑戰(zhàn)賽使用的Junior車采用了該算法進(jìn)行uturn），泊車等等對方向盤控制要求較高的場景。
2）D*、D*Lite算法，事先由終點(diǎn)向起點(diǎn)進(jìn)行搜索，使用Dijkstra算法，存儲路網(wǎng)中目標(biāo)點(diǎn)到每個點(diǎn)的最短路徑長度k, 和該節(jié)點(diǎn)到目標(biāo)點(diǎn)的實(shí)際長度值h，開始情況下 k==h， 并且存儲每個節(jié)點(diǎn)的上一個節(jié)點(diǎn)，保證能夠沿著鏈接走下去。
計算結(jié)束后，獲取了一條當(dāng)時最優(yōu)路徑。當(dāng)車行駛到某個節(jié)點(diǎn)時，通過傳感器發(fā)現(xiàn)該節(jié)點(diǎn)已經(jīng)無法通行（有障礙物），則對已存儲的路網(wǎng)信息一些相關(guān)點(diǎn)的h值進(jìn)行修改（變大），選擇一個鄰居點(diǎn)滿足仍然h==k的，即仍然是最優(yōu)路徑上的點(diǎn)，作為下一個點(diǎn)。
然后走到終點(diǎn)。該類算法適用于在未知環(huán)境中的導(dǎo)航以及路徑規(guī)劃，廣泛用于目前各種移動機(jī)器人和自主車輛載具，例如“機(jī)遇號”和“勇氣號”火星車。
2. 基于采樣的規(guī)劃算法
通過對連續(xù)的狀態(tài)空間進(jìn)行采樣，從而將原問題近似成一個離散序列的優(yōu)化問題，這一思路也是在計算機(jī)科學(xué)中應(yīng)用最為廣泛的算法。在運(yùn)動規(guī)劃問題中，基于采樣的基本算法包括概率路線圖(PRM)和快速搜索隨機(jī)樹(RRT)算法。
圖6. 利用RRT算法實(shí)現(xiàn)u形彎的軌跡規(guī)劃，引用自[19]
1）基本算法：概率路線圖(PRM)
預(yù)處理階段：對狀態(tài)空間內(nèi)的安全區(qū)域均勻隨機(jī)采樣n個點(diǎn)，每個采樣點(diǎn)分別與一定距離內(nèi)的鄰近采樣點(diǎn)連接，并丟棄掉與障礙物發(fā)生碰撞的軌跡,最終得到一個連通圖。
査詢階段：對于給定的一對初始和目標(biāo)狀態(tài),分別將其連接到已經(jīng)構(gòu)建的圖中,再使用搜索算法尋找滿足要求的軌跡。
容易看出,一旦構(gòu)建一個PRM之后,可以用于解決不同初始、目標(biāo)狀態(tài)的運(yùn)動規(guī)劃問題,但是這個特性對于自動駕駛運(yùn)動規(guī)劃而言是不必要的。另外PRM要求對狀態(tài)之間作精確連接，這對于存在復(fù)雜微分約束的運(yùn)動規(guī)劃問題是十分困難的。
2） 基本算法：快速搜索隨機(jī)樹(RRT)
樹的初始化：初始化樹的結(jié)點(diǎn)集和邊集,結(jié)點(diǎn)集只包含初始狀態(tài),邊集為空。
樹的生長：對狀態(tài)空間隨機(jī)采樣，當(dāng)采樣點(diǎn)落在狀態(tài)空間安全區(qū)域時，選擇當(dāng)前樹中離采樣點(diǎn)最近的結(jié)點(diǎn)，將其向采樣點(diǎn)擴(kuò)展(或連接)。若生成的軌跡不與障礙物發(fā)生碰撞，則將該軌跡加入樹的邊集，該軌跡的終點(diǎn)加人到樹的結(jié)點(diǎn)集。
RRT是一種增量式采樣的搜索方法，無須設(shè)置任何分辨率參數(shù)。在極限情況，該搜索樹將稠密的布滿整個空間，此時搜索樹由很多較短曲線或路經(jīng)構(gòu)成，以實(shí)現(xiàn)充滿整個空間的目的。
3）多種改進(jìn)算法
從以上基礎(chǔ)算法的描述我們可以了解到，對狀態(tài)空間進(jìn)行采樣，可以保證得到連接起始點(diǎn)與終點(diǎn)的可行解，但由于采樣過程是對整個空間進(jìn)行均勻采樣，因此效率很低；在復(fù)雜場景下無法實(shí)現(xiàn)實(shí)時求解；此外，最終規(guī)劃結(jié)果無法保證得到的可行解是最優(yōu)解。針對這些劣勢，多種改進(jìn)算法被提出并應(yīng)用于自動駕駛問題：
效率改進(jìn)--不均勻采樣
- RRT-Connect：同時構(gòu)建兩棵分別起始于初始狀態(tài)和目標(biāo)狀態(tài)的樹,當(dāng)兩棵樹生長到一起時則找到可行解。
- 啟發(fā)式（hRRT）：使用啟發(fā)式函數(shù)增加擴(kuò)展代價低的結(jié)點(diǎn)被采樣的概率。
- 結(jié)合駕駛員模型：結(jié)合駕駛員視覺注意力模型進(jìn)行偏向性采樣，利用視覺特征信息引導(dǎo)運(yùn)動規(guī)劃，使規(guī)劃出的軌跡更符合人類駕駛行為。
- 構(gòu)造新度量RG-RRT(reachability guided RT)：常規(guī)類歐式距離的度量并不能真實(shí)反映構(gòu)形或狀態(tài)之間的遠(yuǎn)近，RG-RRT計算樹中結(jié)點(diǎn)的能達(dá)集，當(dāng)采樣點(diǎn)到結(jié)點(diǎn)的距離大于采樣點(diǎn)到該結(jié)點(diǎn)能達(dá)集的距離時, 該節(jié)點(diǎn)才有可能被選中進(jìn)行擴(kuò)展。
- 加入障礙物懲罰（RC-RRT、EG-RRT、ADD-RRT等）：降低靠近障礙物的結(jié)點(diǎn)獲得擴(kuò)展的概率。
實(shí)時性改進(jìn)
- anytime RRT先快速構(gòu)建一個RRT,獲得一個可行解并記錄其代價.之后算法會繼續(xù)采樣,但僅將有利于降低可行解代價的結(jié)點(diǎn)插入樹中,從而逐漸獲得較優(yōu)的可行解.。
- Replanning將整個規(guī)劃任務(wù)分解為若干等時間的子任務(wù)序列，在執(zhí)行當(dāng)前任務(wù)的同時規(guī)劃下一個任務(wù)。
最優(yōu)性改進(jìn)
- PRM*、RRG、RRT*：根據(jù)隨機(jī)幾何圖理論（在狀態(tài)空間中隨機(jī)采樣m個點(diǎn),并將距離小于r(n)的點(diǎn)連起來,就構(gòu)成了隨機(jī)幾何圖）對標(biāo)準(zhǔn)PRM 和RRT做出改進(jìn),得到了具有漸近最優(yōu)性質(zhì)的PRM*、RRG和RRT*算法
3. 直接優(yōu)化方法
在絕大多數(shù)情況下，不考慮高度的變化，自動駕駛的軌跡規(guī)劃問題是一個三維約束優(yōu)化問題（2D空間+時間T），因此，我們可以采用解耦的策略，將原始問題分解為幾個低維問題，從而大大降低求解難度。
1）Frenet坐標(biāo)系
圖7. Frenet坐標(biāo)系
由于真實(shí)世界中的道路都是彎曲的，為了簡化求解優(yōu)化問題的參數(shù)表達(dá)，在自動駕駛中通常采用Frenet坐標(biāo)系。
在Frenet坐標(biāo)系中，我們使用道路的中心線作為參考線，使用參考線的切線向量t和法線向量n建立一個坐標(biāo)系，如右圖所示，它以車輛自身為原點(diǎn)，坐標(biāo)軸相互垂直，分為s方向（即沿著參考線的方向，通常被稱為縱向，Longitudinal）和d方向（或L方向，即參考線當(dāng)前的法向，被稱為橫向，Lateral），相比于笛卡爾坐標(biāo)系（左圖），F(xiàn)renet坐標(biāo)系明顯地簡化了問題。
因為在公路行駛中，我們總是能夠簡單的找到道路的參考線（即道路的中心線），那么基于參考線的位置的表示就可以簡單的使用縱向距離S（即沿著道路方向的距離）和橫向距離L（即偏離參考線的距離）來描述。
3）路徑-速度解耦法：
在Frenet坐標(biāo)系中，路徑-速度解耦法分別優(yōu)化路徑和速度，路徑優(yōu)化主要考慮靜態(tài)障礙物，通過動態(tài)規(guī)劃生成一條靜態(tài)的參考路徑（SL維度），接著基于生成的路徑，考慮對速度的規(guī)劃（ST維度）。這一過程可以不斷迭代，從而實(shí)現(xiàn)對軌跡的實(shí)時更新。在百度的開源自動駕駛平臺Apollo中采用的EM planner就是基于類似的解決思路。這一方案具有較強(qiáng)的靈活性，可以普適性的適用于許多場景。
除此之外，也可以選擇不同的解耦方式，例如分別對縱向軌跡（ST維度）和橫向軌跡（LT維度）進(jìn)行規(guī)劃。但需要指出的是，通過解耦的方法得到的解可能不是最優(yōu)的，并且這種算法不具備完備性，在一些復(fù)雜環(huán)境可能找不到可行解。
4. 參數(shù)化曲線構(gòu)造法
圖8. 常見的參數(shù)化曲線構(gòu)造法，引用自[19]
參數(shù)化曲線構(gòu)造法的出發(fā)點(diǎn)是車輛本身的約束，包括運(yùn)動學(xué)與動力學(xué)的約束，因此一般規(guī)劃的路徑需要是曲率連續(xù)的。這類方法根據(jù)起始點(diǎn)和目標(biāo)點(diǎn)，考慮障礙物，通過構(gòu)造一族符合車輛約束的曲線給出一條平滑路徑。
如圖8所示，常見的曲線有Dubins曲線（由直線和圓弧構(gòu)成，是一種簡單車輛模型Dubin模型在二維空間中的最短曲線族），回旋曲線，多項式曲線，貝塞爾曲線，樣條曲線等。單純應(yīng)用參數(shù)化曲線構(gòu)造法很難滿足實(shí)際復(fù)雜場景，因此現(xiàn)在越來越多的自動駕駛系統(tǒng)將其與其他方法結(jié)合，用來對已經(jīng)規(guī)劃生成的軌跡做平滑處理，以滿足車輛運(yùn)動學(xué)與動力學(xué)約束。
5. 人工勢場法
人工勢場法是受物理學(xué)中電磁場的啟發(fā)，假設(shè)障礙物和目標(biāo)位置分別產(chǎn)生斥力和引力，從而可以沿著勢場的最速梯度下降去規(guī)劃路徑。這類方法的一個關(guān)鍵問題是如何選擇合適的勢場函數(shù)，例如：Stephen Waydo使用流函數(shù)進(jìn)行平滑路徑的規(guī)劃[20]，Robert Daily在高速車輛上提出諧波勢場路徑規(guī)劃方法[21]。在簡單場景下，人工勢場法具有較高的求解效率，但其存在的最大問題是可能陷入局部最小值，在這種情況下，所獲得的路徑不是最優(yōu)，甚至可能找不到路徑。
5. 算法復(fù)雜度（Complexity）
在規(guī)劃問題中，對于一個算法的評價除了要考慮其時間和空間復(fù)雜度之外，還要考慮其是否具有完備性和最優(yōu)性，退一步的情況下考慮其是否具有概率完備性和漸進(jìn)最優(yōu)性。只要在了解這些性質(zhì)的基礎(chǔ)上，我們才能針對不同的實(shí)際場景設(shè)計和應(yīng)用不同的算法，從而達(dá)到模型復(fù)雜和效率最優(yōu)的最佳衡點(diǎn)。
1）完備性（Completeness）：如果在起始點(diǎn)和目標(biāo)點(diǎn)間有路徑解存在，那么一定可以得到解，如果得不到解那么一定說明沒有解存在；
2）概率完備性（Probabilistically Completeness）：如果在起始點(diǎn)和目標(biāo)點(diǎn)間有路徑解存在，只要規(guī)劃或搜索的時間足夠長，就一定能確保找到一條路徑解；
3）最優(yōu)性（Optimality）：規(guī)劃得到的路徑在某個評價指標(biāo)上是最優(yōu)的（評價指標(biāo)一般為路徑的長度）
4）漸進(jìn)最優(yōu)性（Asymptotically optimality）：經(jīng)過有限次規(guī)劃迭代后得到的路徑是接近最優(yōu)的次優(yōu)路徑，且每次迭代后都與最優(yōu)路徑更加接近，是一個逐漸收斂的過程
表1 常見算法比較6. 未來發(fā)展趨勢圖9. 自動駕駛發(fā)展時間線及過程中重要的運(yùn)動規(guī)劃算法，引用自[19]
人類對自動駕駛的興趣最早可以追溯到1925年，近年來對自動駕駛的研究熱潮始于美國國防先進(jìn)研究項目局（Defense Advanced Research Projects Agency, DARPA ）在2004-2007年舉辦的3屆自動駕駛挑戰(zhàn)賽[22]，如圖9所示。在此之后，上文提到的各類決策規(guī)劃方法的有效性都被實(shí)際驗證。同時，將運(yùn)動規(guī)劃方法與控制理論、狀態(tài)參數(shù)估計、機(jī)器學(xué)習(xí)等多領(lǐng)域方法相結(jié)合的解決方案也不斷出現(xiàn)，成為未來的發(fā)展趨勢：
1）與車輛動力學(xué)結(jié)合：將動力學(xué)參數(shù)評價指標(biāo)和最優(yōu)規(guī)劃等結(jié)合，從最優(yōu)控制角度進(jìn)行規(guī)劃是近年采用較多的方法，在這個過程中可以充分考慮車輛動力學(xué)因素，規(guī)劃出的軌跡更加合理。例如采用模型預(yù)測控制理論（Model Predictive Control）。其不足在于：對車輛的約束越多，優(yōu)化其軌跡的難度越大，較難實(shí)現(xiàn)在線的實(shí)時計算。
2）與狀態(tài)參數(shù)估計結(jié)合：狀態(tài)參數(shù)估計可以更加準(zhǔn)確獲得車輛參數(shù)，因此可以將狀態(tài)估計器加入規(guī)劃模塊中，通過在線估計車輛狀態(tài)并將其反饋給規(guī)劃器，提高軌跡質(zhì)量。例如：不同地面類型會引起車輛滑移特性的變化，進(jìn)而影響車輛狀態(tài)，通過結(jié)合估計參數(shù)實(shí)時重新規(guī)劃軌跡，閉環(huán)規(guī)劃從而提高軌跡安全性。
3）與機(jī)器學(xué)習(xí)結(jié)合：隨著以神經(jīng)網(wǎng)絡(luò)為代表的人工智能的快速發(fā)展，許多傳統(tǒng)的規(guī)劃問題也帶來了新的解決思路。在自動駕駛領(lǐng)域，其發(fā)展趨勢包括：
端到端模型：使用一個深度神經(jīng)網(wǎng)絡(luò)，直接根據(jù)車輛狀態(tài)和外部環(huán)境信息得出車輛的控制信號。盡管目前的端到端模型存在類似“黑箱”的不可解釋性，但相信隨著人類對深度神經(jīng)網(wǎng)絡(luò)理解的不斷加深，這一方法因其突出的簡潔高效優(yōu)勢而具有很強(qiáng)的發(fā)展?jié)摿Α?/div>
決策與運(yùn)動規(guī)劃模塊融合
自動駕駛車輛在復(fù)雜環(huán)境中作出最優(yōu)決策，這一問題與強(qiáng)化學(xué)習(xí)的定義非常吻合，因此如前文所述，隨著深度強(qiáng)化學(xué)習(xí)技術(shù)的快速發(fā)展，越來越多的研究團(tuán)隊開始將其應(yīng)用于自動駕駛決策規(guī)劃中，將行為決策與運(yùn)動規(guī)劃模塊相融合，直接學(xué)習(xí)得到行駛軌跡。為了解決環(huán)境獎勵函數(shù)不易獲得的問題，人們還提出了首先利用逆強(qiáng)化學(xué)習(xí)（IRL）根據(jù)人類專家演示學(xué)習(xí)，然后使用強(qiáng)化學(xué)習(xí)來學(xué)習(xí)最優(yōu)策略。
參考文獻(xiàn)
[1] Schwarting W, Alonso-Mora J, Rus D. Planning and Decision-Making for Autonomous Vehicles[J]. Annual Review of Control, Robotics, and Autonomous Systems, 2018, 1(1): 187–210.
[2] Paden B, Cap M, Yong S Z, et al. A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles[J]. IEEE Transactions on Intelligent Vehicles, 2016, 1(1): 33–55.
[3] E. W. Dijkstra, “A note on two problems in connexion with graphs,”Numerische mathematik, vol. 1, pp. 269–271, 1959.
[4] N. J. Nilsson, “A mobile automaton: An application of artificial intelligence techniques,” tech. rep., DTIC document, 1969.
[5] 耿新力. 城區(qū)不確定環(huán)境下無人駕駛車輛行為決策方法研究[D]. 中國科學(xué)技術(shù)大學(xué), 2017.
[6] Montemerlo M, Becker J, Bhat S, et al. Junior: The Stanford entry in the Urban Challenge[J]. Journal of Field Robotics, 2008, 25(9): 569–597.
[7] Olsson M. Behavior Trees for decision-making in Autonomous Driving[M]. 2016.
[8] Zhao L, Ichise R, Sasaki Y, et al. Fast decision making using ontology-based knowledge base[C]//Intelligent Vehicles Symposium (IV), 2016 IEEE. IEEE, 2016: 173–178.
[9] Vacek S, Gindele T, Zollner J M, et al. Using case-based reasoning for autonomous vehicle guidance[C]//Intelligent Robots and Systems, 2007. IROS 2007. IEEE/RSJ International Conference on. IEEE, 2007: 4271–4276.
[10] Chen C, Seff a, Kornhauser A, et al. Deepdriving: Learning affordance for direct perception in autonomous driving[C]//Proceedings of the IEEE International Conference on Computer Vision. 2015: 2722–2730.
[11] Bouton M, Cosgun a, Kochenderfer M J. Belief state planning for autonomously navigating urban intersections[C]//Intelligent Vehicles Symposium (IV), 2017 IEEE. IEEE, 2017: 825–830.
[12] Russal S, Norvig P. Artificial intelligence: a modem approach[M]. Pearson Education, 2002.
[13] Furda a, Vlacic L. Enabling Safe Autonomous Driving in Real-World City Traffic Using Multiple Criteria Decision Making[J]. IEEE Intelligent Transportation Systems Magazine, 2011, 3(1): 4–17.
[14] Bai H, Cai S, Ye N, et al. Intention-aware online POMDP planning for autonomous driving in a crowd[C]//2015 IEEE International Conference on Robotics and Automation (ICRA). 2015: 454–460.
[15] Wei J, Snider J M, Gu T, et al. A behavioral planning framework for autonomous driving[C]//2014 IEEE Intelligent Vehicles Symposium Proceedings. 2014: 458–464.
[16] Aoude G S, Luders B D, How J P, et al. Sampling-based Threat Assessment Algorithms for Intersection Collisions Involving Errant Drivers[J]. 2010.
[17] Martin A, Schenato L, Altho D. Interactive Motion Prediction using Game Theory[J]. : 100.
[18] Vitelli M, Nayebi a. Carma: A Deep Reinforcement Learning Approach to Autonomous Driving[J]. 2016.
[19] Gonzalez D, Perez J, Milanes V, et al. A Review of Motion Planning Techniques for Automated Vehicles[J]. IEEE Transactions on Intelligent Transportation Systems, 2016, 17(4): 1135–1145.
[20] WAYDO S, MURRAY R M. Vehicle motion planning using stream functions[C]//2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422). 2003, 2: 2484–2491 vol 2.
[21] DAILY R, BEVLY D M. Harmonic potential field path planning for high speed vehicles[C]//2008 American Control Conference. 2008: 4609–4614.
[22] The DARPA Urban Challenge: autonomous vehicles in city traffic[M]. BUEHLER M, IAGNEMMA K, SINGH S. Berlin: Springer, 2009.
(文/小編)
13861291831