自動駕駛汽車軌跡規劃方法綜述

呂貴林 高洪偉 陳濤 田鶴 韓爽

（中國第一汽車股份有限公司研發總院，長春 130013）

0 引言

隨著多家公司相繼提出約在2025 年實現L5 級自動駕駛，真正意義上的自動駕駛車輛離我們越來越近。

自動駕駛汽車的最早貢獻之一可以追溯到20世紀20 年代的Houdina 無線電控制公司，該公司成功地演示了一輛由尾隨車輛發送的無線電信號控制的汽車。

當今，自動駕駛汽車的研究進入了蓬勃發展時期，許多自動駕駛汽車的相關技術已經被應用到高級駕駛輔助系統（Advanced Driving Assistance Systems,ADAS）中，如巡航控制（Cruise Control,CC）、智能速度適應（Intelligent Speed Adaptation,ISA）、車道保持輔助（Lane Keeping Assist,LKA）和車道偏離預警（Lane Departure Warning, LDW）、變道輔助（Lane Change Assist, LCA）、自適應巡航控制（Adaptive Cruise Control,ACC）和自動緊急制動（Automatic Emergency Braking,AEB）等[1]。

自動駕駛的分層體系由3 個模塊組成，包括感知（Perception）、規劃（Planning）、控制（Control），如圖1所示。根據實現方法不同，有些系統還具有地圖、定位、預測和V2X（Vehicle to X）通信模塊。通常情況下規劃模塊被分為3 個層次，包括全局路由規劃（Routing planning）、行為決策（Behavior decision）和軌跡規劃（Trajectory planning）。路由規劃根據環境信息（如交通語義地圖）規劃一條全局路線，行為決策模塊在給定的路由下根據交通規則、其他交通參與者的行為感知、道路狀況和基礎設施信號做出語義層動作決策（如車道保持、換道）。軌跡規劃層負責生成一條適合車輛運動、帶有速度信息的軌跡。這一層需要考慮安全性、效率、駕駛舒適性、不確定信息處理（如傳感器精度、遮擋區域）等因素。

圖1 自動駕駛控制體系

自動駕駛發展至今，軌跡規劃一直是自動駕駛研究的重點，安全問題一直是自動駕駛考慮的首要方面，一個優秀的軌跡會大幅提高駕駛安全。

本文通過綜述自動駕駛汽車軌跡規劃相關文獻，重點研究規劃模塊中軌跡規劃策略。第1章，分析對比了主要的軌跡規劃方法，并給出了這些方法的優缺點；在第2章，給出了已經在實際中應用的軌跡規劃算法，并進行相關分析。第3章，總結出軌跡規劃領域存在的問題與挑戰，并分析了未來發展方向。

1 軌跡規劃方法

現有的軌跡規劃算法主要起源于移動機器人領域，隨自動駕駛技術興起后被應用于解決自動駕駛的軌跡規劃問題。根據它們在自動駕駛領域的應用，這些軌跡規劃技術被分為圖搜索、采樣、數學優化、插值曲線以及機器學習。下面分別對以上技術進行闡述。

1.1 圖搜索

圖是數據結構中非常重要的一個概念，包含了節點和邊。在自動駕駛中，通常可以將地圖存儲為柵格地圖，每一格就代表了圖的節點，格與格之間的連線就代表了邊。

基于圖搜索的路徑規劃技術在表示為圖的狀態空間中搜索汽車當前狀態和目標狀態之間的最佳路徑。其基本思想是穿越一個狀態空間，從當前節點到達目標節點。這個狀態空間通常表示為一個網格或格子，用來描述物體在環境中的位置，從規劃的角度來看，路徑設置可以實現訪問網格中不同狀態的圖搜索算法，從而給出路徑規劃問題一個解決方案。基于圖搜索的軌跡規劃技術在基于圖搜索的路徑規劃技術上進行擴展，來說明車輛狀態隨時間的演化。但傳統圖搜索的算法所得到的路徑通常不能滿足車輛動力學要求，或無法適用于動態環境，因此實際應用于自動駕駛時需針對這類些問題進行改進。

1.1.1 Dijkstra

Dijkstra 算法[2]由荷蘭科學家Dijkstra 于1959年首先提出，是搜索最短路徑的經典算法。Dijkstra算法的主要特點是以起始點為中心向外層擴展（廣度優先搜索思想），直到擴展到終點為止。它的基本原則是：反復檢查最近的尚未檢查的節點，將其鄰居添加到要檢查的節點集中，并在達到目標節點時停止。Dijkstra算法步驟如Algorithm 1所示[2]。

其中，INITIALIZE 為初始化函數，其算法步驟如Algorithm 2所示[2]。

Algorithm 2:INITIALIZE for each v ∈G.V vd=∞∕∕初始時節點到起點的距離為無窮vπ=NULL ∕∕初始所有頂點的父節點為空sd=0 ∕∕起點的距離為0

RELAX為路徑替換函數，其算法如Algorithm 3所示[3]。

Algorithm 3:REALAX(u,v,w)if vd ＞ud+w(u,v) then ∕∕w( )u,v 為u 到v 的權值vd=ud+w(u,v) ∕∕更新v 到起點距離vπ=u ∕∕更新v 的父節點

Algorithm 1:Dijkstra INITIALIZE(G,s)S=? ∕∕S 開始為空集，用來存儲已訪問的頂點Q=G.V ∕∕初始化最小優先隊列Q，存放圖G 的所有節點while Q ≠? do u= dequeue-min(Q)∕∕Q 中最小元素出隊if u 為目標節點then break else S=S ∪{u}for each v ∈G.adj[u] and v is not in S RELAX(u,v,w)

最終所需的最短路徑通過從目標節點不斷搜尋父節點得到的頂點集合得到。

Victor Tango[3]團隊在2007 年的DARPA 挑戰賽上用Dijkstra 算法為Odin 生成路徑。2013 年，Kala 和Warwick 使用Dijkstra 生成路徑[4]，僅在計算機模擬中進行了測試。

Dijkstra算法的成功率是最高的，因為它每次必能搜索到最優路徑。但Dijkstra 算法的搜索速度是最慢的，隨著圖維度的增大，其計算效率會明顯變低。其時間復雜度為O(n2)，其中n代表算法的數據規模，在圖搜索算法中代表空間的節點個數，即執行時間和節點的個數相關。因此，在地圖數據較大時很難滿足路徑規劃中實時性的要求。

1.1.2 A?算法

A*算法[5]的主要特點是在Dijkstra 算法的基礎上為空間的每個節點定義了一個啟發函數（估價函數）h(v)，啟發函數為當前節點v到目標節點的估計值。在A*算法中遍歷節點的優先級通過以下公式計算：

式中，f(v)是節點v的綜合優先級；g(v)為節點v距離起點的代價；h(v)為節點v距離終點的預計代價。

當h(v)始終為0時，算法通過g(v)控制優先級，此時算法就變回Dijkstra 算法。A*算法[5]的步驟如Algorithm 4所示。

Algorithm 4:A*S=? Q=?Q ?s while Q ≠? do u= dequeue-min(Q)∕∕取出Q 中f 值最小的節點if u 為目標節點then break else S=S ∪{u}for each v ∈G.adj[u]計算f(v)if v is in Q then if v 當前估價值f(v)小于Q 中的f(v) then Update Q ∕∕替換Q 中f(v)else if v is in S then if v 當前估價值f(v)小于S 中的f(v) then Update S ∕∕替換S 中f(v)Q ?v else if v is not in S and is not in Q then Q ?v

啟發函數相當于為搜索提供了一個方向，可以減少搜索節點的數量從而提高效率。

A*算法為全局規劃算法，因此常用于路徑規劃。Leedy 等[6]在2005 年DARPA 大挑戰賽中采用A*算法為自動駕駛汽車構建路徑。Ziegler等[7]在2008年提出了一種將A*與2 種不同啟發式代價函數旋轉平移旋轉（Rotation Translation Rotation, RTR）和Voronoj 圖結合的路徑規劃方法。

在軌跡規劃中Fassbender 等[8]提出了2 種新穎的A*節點擴展方案，分別是一次性擴張（One-Shot Expansions）和純跟蹤擴張（Pure-Pursuit Expansions）。一次性擴張通過一步(或一次)找到可行的軌跡，將車輛從當前節點帶到目標，能夠有效改善常規的A*擴展緩慢的情況。

純跟蹤擴張使用純追蹤控制器生成短邊，引導汽車沿著全局參考路徑行駛。常規A*中對控制輸入離散化的需求可能導致路徑不平滑，從某種意義上說，它們包含非自然轉向，這使得它很難精確地遵循光滑的參考路徑。一種解決辦法是首先使用A*和有限數量的運動基元規劃一個粗路徑，然后使用數值優化對路徑進行平滑。這種方法的問題是，在需要高度精確機動的場景中，它可能會失敗，因為第一步的粗離散可能會阻止規劃算法找到任何解決方案。因此，Fassbender 等[8]將純跟蹤與A*結合開發了純追蹤擴張法，一種生成軌跡的替代方法，這種方法可以平滑地沿著道路行進。

A*算法在當前自動駕駛領域的應用也十分廣泛，2021年Pérez-Gill等[9]基于CARLA和ROS聯合仿真提出了一個適用于車輛的深度強化學習框架，利用A*算法獲得節點，來生成全局路徑。

A*算法在靜態道路網絡中非常有效，但不適于在動態道路網絡，即權重不斷變化的動態環境下，例如出現塌方、車禍、阻塞等狀況。

1.1.3 D*算法

通常，每次使用感知數據更新世界模型時，都要重復尋找從車輛當前位置到目標區域的最短路徑。由于每次更新通常只影響到圖的一小部分，所以每次完全從頭開始搜索是浪費時間。針對這個問題在A*的基礎上設計出實時重規劃搜索算法D*[10]。D*也被稱為動態A*（Dynamic A-Star,D-Star），該算法能夠在未知的、部分已知的、變化的環境中高效、最優、完整地規劃路徑。與A*不同的是D*以目標節點開始進行搜索，當路徑上遇到障礙物時所受到影響的點會增加成本，從而在循環時避免進行全面搜索，并且D*算法存儲了每個節點到目標結點的最短路徑信息，故在重新規劃時效率大大提升，如Algorithm 5所示[10]。

Algorithm 5:D*S=? Q=?Q ?target while Q ≠? do u= dequeue-min(Q)∕∕取出Q 中k 值最小的節點，k 為所有變化h 值中最小的值if u 為目標節點then break else S=S ∪{u}for each v ∈G.adi[u]h(v)=h(u)+w(u,v) ∕∕h(v)為目標節點到v 點的實際值if v is in Q then if v 當前估價值h(v)小于Q 中的h(v) then Update Q ∕∕用當前估價值h(v)替換Q 中原本h(v)，并將k 值取最小的h 值elseif v is in S then if v 當前估價值h(v)小于S 中的h(v) then Update S ∕∕替換s 中的h(v)，k 取最小的h值Q ?v elseif v is not in S and is not in Q then Q ?v

在D*基礎之上Focussed D*[11]和D*Lite[12]也被設計用來在每次環境底層發生變化時高效地重新計算最短路徑，同時保留以前搜索結果中的信息。

1.1.4 狀態柵格算法

狀態柵格（State Lattice）[13]是一個搜索圖，傳統的A*算法用于尋找最短路徑，但最終得到的圖對車輛來說未必可行，因此需要在圖的節點之間建立可行路徑，如圖2，其中頂點表示狀態，邊表示連接滿足機器人運動學約束狀態的路徑。頂點以一種常規的方式放置，這樣即使經過嚴格的平移和旋轉，也可以使用相同的路徑來構建從每個頂點到目標的可行路徑。這樣，到達目標的軌跡很可能被表示為圖2中的邊序列。狀態格能夠處理多個維度，例如位置、速度和加速度，并且適用于動態環境。然而，其計算成本很高，因為該算法評估了圖中的每一個可能的解決方案[1]。

圖2 狀態柵格示意[13]

McNaughton等[14]提出了一種用于軌跡規劃的時空聯合狀態柵格（Conformal spatiotemporal state lattice）。該算法圍繞著一條中心線路徑構造狀態格，定義了道路上從中心線橫向偏移的節點，并使用一種優化算法計算節點之間的邊緣。這個優化算法找到一個多項式函數參數，該函數定義了任意對連接的節點邊。為每個節點分配一個狀態向量，該狀態向量包含一個姿態、加速度剖面，以及時間和速度范圍。與追求時間和速度間隔更精細的離散化相比，加速度剖面以更少的成本增加了軌跡多樣性。此外，時間和速度的范圍通過將時間和速度分配到圖搜索階段，而不是圖構建階段，降低了計算成本。Xu等[15]提出了一種迭代優化方法，將其應用于時空聯合狀態柵格軌跡規劃，減少了規劃時間，提高了軌跡質量。Li等[16]通過使用三次多項式曲線生成候選路徑來構建狀態柵格。速度剖面也被用來計算分配所生成路徑的姿態，得到的軌跡由一個代價函數來評估，并選擇最優的一個。表1為圖搜索規劃算法對比。

表1 圖搜索規劃算法對比

1.2 采樣

在基于圖搜索的軌跡規劃中大部分需要通過網格化來達到離散化的目的，而基于采樣的技術對狀態空間進行抽樣以達到離散化的目的，從而尋找汽車當前狀態和下一個目標狀態之間的聯系[17]。

1.2.1 RRT

軌跡生成的快速遍歷隨機樹（Rapidly exploring Random Trees,RRT）方法[18]使用狀態空間中的隨機樣本，從汽車當前狀態逐步構建搜索樹，通過隨機采樣增加葉子節點，生成一個隨機拓展樹，當擴展的隨機葉子節點進入目標區域，就得出了一條從起始位置到目標位置的路徑，如Algorithm 6所示。

Algorithm 6:RRT Initialize RRT-tree ∕∕初始化RRT搜索樹RRT-tree ?xstart while()xrandom = Smple( M)∕∕在地圖M 中隨機采樣獲得xrandom 節點xnear =Near(xrandom,RRT-tree)∕∕在搜索樹中找到距離xrandom 最近的節點if distance( xrandom, xnear) ＞ th re sh old then ∕∕如果xrandom 與xnear 距離大于閾值xnew =Steer(xrandom, xnear, th re sh old)∕∕xnew 為xnear與xrandom 沿線上一點，與xnear 距離為th re sh old else xnew= xrandom if nocollision( M, edge( xnew, xnear)) then ∕∕如果xnew與xnear 連線沒有穿過地圖障礙物RRT-tree ?xnew RRT-tree ?edge(xnew, xnear)if distance(xnew, xtarget)＜th re sh old then break

與人類駕駛汽車一樣，自動駕駛汽車也受到一系列規則約束，然而在某些情況下（例如在道路上超車事故車輛）這些約束需要打破，此時就可能出現違反交通規則的問題。如果將交通規則以代價函數的形式與自動駕駛結合，則可以使用傳統的運動規劃方法來尋找代價最小的路徑。

基于RRT，RRT-Connect[19]能夠更快速地找到可行路徑，RRT-Connect同時擴展2棵樹，一棵樹從起始點擴展，另一棵樹從目標點擴展，當2棵樹之間建立聯系時，規劃器停止搜索。

然而由于樹的擴展方向是隨機的，使得最終得到的路徑不平滑、不符合車輛動力學且并不是最短路徑。并且，雖然通過隨機的方式能夠提升搜索樹擴展的速度，但可能擴展大量無用節點，占用大量內存。

為了解決RRT 所得軌跡不滿足車輛動力學的問題，Kuwata 等開發了閉環RRT（Closed Loop RRT,CLRRT）算法[20]。在CL-RRT 算法中，將閉環控制器與RRT 結合使用。樹中的每個節點都是通過使用帶有閉環動力學的低層控制器來擴展的，這樣樹中的每條邊都是動態可行的。在CL-RRT 中，參考命令r被輸入到控制器。該控制器向車輛動力學模型輸入車輛控制命令u，如圖3所示，該閉環系統生成動態可行軌跡x。因此，閉環控制器影響對動態可行軌跡的采樣，而不是直接從配置空間采樣。

圖3 CL-RRT車輛控制模塊

2.2.2 RRT*

傳統RRT算法不能保證所得路徑是最優的，為此Karaman等[21]開發了一個必然會收斂到最優解的算法RRT*。RRT*算法在每次迭代后都會在局部更新搜索樹，以優化路徑。相較于傳統RRT 算法多了2 個過程，分別為重新為加入搜索樹的有效節點選擇代價更小的父節點，即re-choose，以及重布線隨機樹，即rewire，如Algorithm 7所示。

Algorithm 7:RRT*Initialize RRT-tree RRT-tree ?xstart while()xrandom =Smple(M)xnear =Near(xrandom,RRT-tree)if distance(xrandom, xnear)＞th re sh old then xnew =Steer(xrandom, xnear, th re sh old)else xnew= xrandom if nocollision(M,edge(xnew, xnear))then RRT-tree ?xnew xmin =re-choose( xnew,RRT-tree)∕∕在樹中找到一個代價最小的節點作為xnew 新的父節點RRT-tree ?edge(xmin, xnew)Rewire()∕∕根據新的父節點重新配置搜索樹if distance(xnew, xtarget)＜th re sh old then break

RRT*算法是漸進優化的，也就是隨著迭代次數進行局部搜索樹的優化更新（通常會限制最大循環數），得到的路徑是越來越優化的，但在有限時間內無法得到最優解，也就是說要得到較優的路徑，需要耗費的時間更多。

RRT*-Connect將RRT*與RRT-Connect結合，形成了一種雙向方法，可以返回一個接近最優解的方案[22]。雖然RRT*和RRT*-Connect 能夠返回一個更優的路徑，但這不并是一個能夠有效降低計算成本的方案。Gammell 等證明了現有方法隨著空間維度的擴大，有效性顯著降低[23]，因此提出了Informed RRT*,在找到第一個可行方案后，根據橢圓上任意一點到其焦點的距離之和相等的特性，以起始點和目標點為橢圓焦點，用路徑長度作為橢圓上一點到兩焦點的距離之和畫一個橢圓，算法只需要在橢圓內抽樣即可，每找到一條更短的路徑，橢圓的范圍也會隨之變小。

然而Informed RRT*同樣存在其它單向樹規劃算法的問題，需要大量時間來找到相對優化的路徑，尤其是當遇到狹窄通道時，所需的時間更多。為了應對這個問題Mashayekhi 等[24]設計出Informed RRT*-Connect，通過RRT*-Connect 來尋找路徑，然后通過橢圓限制優化的范圍，從而降低搜索時間。

1.2.3 PMP

在一個時間段內搜索全局圖會降低效率。因此，可以使用局部運動規劃（Partial Motion Planning,PMP），而不是搜索整個狀態空間，以降低計算復雜度。Benenson 等[25]在使用PMP 時考慮了不可避免的碰撞狀態（Inevitable Collision States,ICS），通過在局部空間采樣節點進行擴展，并刪除ICS 節點避免碰撞。表2為采樣規劃算法的優缺點對比。

表2 采樣規劃算法對比

1.3 數學優化

數學優化方法的目標是最小化或最大化受不同約束變量的函數。在軌跡規劃中，通常用于平滑之前計算的軌跡，也用于從運動學約束計算軌跡[26]。基于數值優化的自動駕駛汽車軌跡規劃方法主要有函數優化和模型預測方法。

1.3.1 函數優化

函數優化方法通過最小化代價函數來尋找軌跡，該方法考慮了軌跡的位置、速度、加速度約束條件。這些方法能較好地考慮汽車運動學、動力學約束和環境約束。但是，函數優化方法計算成本很高，因為優化過程發生在每個運動狀態，并依賴于全局路徑點。Ziegler等利用函數優化方法對自動駕駛汽車Bertha進行軌跡規劃[27-28]。Ziegler等通過最小化一個函數來尋找C2連續軌跡，也就是在軌跡拼接處二階連續可導的軌跡，并且該函數考慮了車輛位置、速度、加速度作為規劃參數，遵循了軌跡的約束條件。1.3.2 模型預測

模型預測通過預測未來車輛的狀態，生成車輛當前狀態到下一目標狀態之間的控制指令[29]。使得車輛控制命令參數化，并滿足狀態約束，其動力學可以用微分方程表示。在2007 年的DARPA 挑戰賽中，卡梅隆大學使用模型預測進行自動駕駛汽車Boss 的軌跡規劃[30]。

Li 等[31]使用了一種基于狀態采樣的軌跡規劃方案，該方案對沿著路線的目標狀態進行采樣。采用一種模型預測路徑規劃方法來生成連接汽車當前狀態和采樣目標狀態的路徑。速度剖面用來分配沿著生成路徑的每個狀態的速度。采用考慮安全性和舒適性的成本函數來選擇最佳軌跡。

Cardoso 等[32]采用了一種模型預測方法進行自動駕駛汽車的軌跡規劃。為了計算軌跡，Cardoso等使用一種優化算法來獲得軌跡控制參數，以最小化到目標狀態的距離、到路徑的距離以及與障礙物的接近程度。表3為數學優化方法對比。

表3 數學優化規劃算法對比

1.4 插值曲線

基于插值曲線（Interpolating Curve）的技術可以對已知的一組姿態(例如，路徑的姿態)進行插值，并在考慮汽車運動學和動力學約束、舒適性、障礙物參數情況下，構建出更加平滑的軌跡。當遇到存在障礙的情況下，只需創造一條新的路徑去克服事件，然后重新回到之前計劃的路徑中[1]。

1.4.1 圓弧與直線

1990年，為了找到滿足車輛動力學的平滑最短路徑，Reeds等[33]設計了圓弧與直線（Lines and Circles）算法。Lines and Circles 是解決類車車輛規劃問題的一種簡單的數學方法，針對不同路段的路網可以用直線和圓形的路徑點插值來表示。

1.4.2 回旋曲線

回旋曲線（Clothoid Curves）允許定義具有線性可變曲率的軌跡，這樣在直線到曲線段之間的過渡是平滑的。回旋曲線與其它軌跡規劃方法相比的主要優勢在于它的曲率是線性變化的，它可以防止向心加速度的突然變化，從而提高車輛的駕駛舒適性，對于載人或重型的貨物運輸是非常重要的[34]。然而，由于定義該曲線的積分和它所依賴的全局路徑點，使得該曲線具有較高的計算成本。Alia 等[35]使用回旋約束（Clothoid Tentacles）進行軌跡規劃。根據不同的速度和不同的初始轉向角度，從汽車的重心開始，以線圈的形式計算觸須。使用路徑跟蹤控制器，從觸須的幾何參數中獲取轉向角度命令，并在占用網格地圖上運行碰撞檢查，將觸須劃分為可行駛或不可行駛。在可行駛觸須中，根據幾個標準選出最佳觸須。Mouhagir等也使用回旋觸須進行軌跡規劃[36-37]。然而，他們使用了一種受馬爾可夫決策過程（Markov Decision Process,MDP）啟發的方法來選擇最好約束。

2.4.3 多項式曲線

多項式曲線（Polynomial Curves）常被用于滿足插值點所需的約束條件，基于多項式的規劃允許獨立計算橫向和縱向車輛運動，同時保證軌跡具有連續的速度、加速度和曲率，可避免圓弧與直線中曲率不連續的問題。

Benloucif 等[38]提出一種計劃軌跡規劃方法，這是一種能夠根據駕駛員的行動和意圖不斷調整的自動化共享駕駛控制框架。Benloucif 等利用多項式，結合機動決策、沖突管理和駕駛員監控信息，制定協同軌跡規劃。

1.4.4 樣條曲線

樣條曲線（Spline Curves）是一種分段多項式參數曲線。它被劃分為子區間，可以理解為多段、多項式曲線的拼接，這種拼接必須滿足平滑銜接，可以被定義為多項式曲線。每個子段之間的連接稱為結點(或控制點)，這些結點通常具有高度平滑的約束。這種曲線計算成本低，因為它的行為是由節點定義的。然而，它的結果可能不是最優的，因為它更關注于實現子區間之間的連續性，而不是滿足道路約束。

Chu[39]和Hu[40]等使用3 次樣條曲線進行路徑規劃。2人的方法都是從道路網絡中提取的路線構造一條中心線。它們使用弧長和到中心線的偏移生成一系列參數化3次樣條曲線來代表可能的候選路徑，根據考慮安全性和舒適性的函數選擇最佳路徑。表4為插值曲線規劃算法對比。

表4 插值曲線規劃算法對比

1.5 機器學習

將機器學習應用于自動駕駛汽車領域，可以以模塊化的形式，將機器學習方法與自動駕駛其它模塊經典算法融合（例如基于深度學習的目標檢測器為經典的A*路徑規劃算法提供輸入），或將感官信息直接映射到車輛控制命令，使開發“端到端”解決方案成為可能，所謂“端到端”即使系統可以像人類駕駛員一樣駕駛車輛，即輸入是目的地、關于路網的知識和各種傳感器信息，輸出是直接的車輛控制命令，如轉向、制動[41-42]。

卷積神經網絡（Convolutional Neural Networks,CNN）是圖像識別領域最成功的深度學習模型，已經在自動駕駛車道和車輛檢測中得到了廣泛[43]。

在DARPA城市挑戰賽中，用于不同駕駛場景的行為決策方法有啟發式組合[30]、決策樹[44]和有限狀態機（Finite State Machine，FSM）[45]。然而，在現實世界中駕駛汽車，即使完全了解當前的交通狀態，但周圍交通參與者的意圖是未知的。因此需要對其它車輛、自行車和行人未來軌跡的意圖預測和估計。目前主流方案有基于機器學習的技術，如高斯混合模型[46]、高斯過程回歸[47]或基于支持向量機和人工神經網絡的預測[48]。而對于自動駕駛決策方法可分為基于規則的決策方法，基于馬爾可夫理論的決策方法以及基于人工智能（主要是循環神經網絡）的決策方法3類[49]。

而在軌跡規劃中有2種最具代表性的深度學習模式，分別為基于模仿學習（Imitation Learning,IL）的規劃和基于深度強化學習（Deep Reinforcement Learning,DRL）的規劃。

基于模仿學習的規劃通過記錄駕駛經驗來學習人類駕駛員的行為，該策略包含了一個從人的示范開始的車輛教學過程[50-51]。基于DRL的軌跡規劃主要是在模擬器中學習駕駛軌跡規劃[52-53]。

在軌跡規劃中IL 和DRL 各有優缺點。IL 的優勢在于它可以用從真實世界收集的數據進行訓練。盡管如此，這些數據在不常遇到的交通狀況下（例如，駕駛偏離車道，交通事故等）是稀缺的，因此當面對沒能覆蓋到的數據時，網絡的反應是不確定的。另一方面，盡管DRL系統能夠在模擬世界中探索不同的駕駛情況，但當這些模型移植到現實世界中時，往往會與模擬世界得到的結果有偏差。表5為機器學習規劃算法對比。

表5 機器學習規劃算法對比

2 軌跡規劃方法應用

本章列舉了至今為止關鍵性的自動駕駛項目，并對這些項目中實際采用的軌跡規劃方法進行分析。

為了推動自動駕駛技術的發展，美國國防高級研究計劃局（Defense Advanced Research Projects Agency，DARPA）在過去十幾年里組織了3場“DARPA挑戰賽”。

第一次挑戰賽（DARPA Grand Challenge）于2004年在美國莫哈韋沙漠舉行，要求自動駕駛汽車在10 h內穿越229 km 的沙漠路線。所有參加比賽的汽車都在前幾英里失敗了，卡內基梅隆大學的汽車Sandstorm走了最遠的距離，完成了11.78 km 的路程，可惜在一個急轉彎后被掛在了一塊巖石上。這一次比賽也讓參賽者發現了自身在環境信息采集、動態環境規劃以及局部避障上的不足。

2005 年DARPA 挑戰賽[54]中，共有23 名車隊進入決賽，4 輛車在規定時間內完成了比賽。其中斯坦福大學的汽車Stanley[45]獲得了第1 名。在比賽前DARPA 向所有參賽者提供了路由定義數據格式（Route Definition Data Format,RDDF）文件，RDDF文件在一定程度上消除了全局路徑規劃的需要，因此參賽者需要著重解決局部的避障問題。Stanley 的路徑規劃并不是在全局坐標系下進行，而是使用相對坐標系，通過相對RDDF 基礎路徑的橫向偏移實現避障。然而這一前提是保證基礎路徑平滑可行。RDDF提供的路徑只是粗略的描述，并不保證可行，于是Stanley 通過最小二乘法優化調整RDDF 的所有坐標點，再通過3 次樣條插值得到可微路徑。當無障礙時，Stanley的行駛軌跡與基本路徑平行，當遇到障礙時Stanley計劃一個平滑的橫向偏移。這種先計算相對中心線偏移，然后通過數學優化的方法可以使生成的軌跡更加平滑，但是對原始軌跡的要求較高。在原始軌跡不可行的情況下，可能出現無解情況。

2007年，DARPA 城市挑戰賽[55]舉行。6輛車在規定時間內完成了比賽，卡內基梅隆大學的汽車Boss[30]獲得了第1名，Boss采用模型預測方法進行軌跡規劃，它生成從中心線路徑導出的一系列目標狀態的軌跡。為了計算每個軌跡，他們使用一種數學優化算法，該算法逐漸修改軌跡控制參數的初始近似值，直到軌跡終點誤差在可接受的范圍內。軌跡控制參數是定義曲率輪廓樣條曲線的軌跡長度和3個結點。基于多個因素，包括當前道路速度極限、最大可行速度和目標狀態速度，生成每個軌跡的速度剖面。根據其與障礙物的距離、到中心線的距離、平滑度、終點誤差和速度誤差來選擇最佳軌跡。雖然這種基于模型預測的方法可以設計多種約束條件，使生成的軌跡更適合車輛運動，但是該方法的計算量較大，在實時性要求較高的場景下可能會出現控制滯后的情況。第2名是斯坦福大學的汽車Junior[56]，它使用了一種混合A*算法（Hybrid A*），混合A*在常規A*的每個特定單元上分配了一個連續坐標，以此解決了A*所得的離散路徑無法應用于現實世界的問題。弗吉尼亞理工大學的汽車Odin[3]獲得了第3 名，其軌跡規劃首先使用車道和障礙物數據創建成本網格圖，然后選擇一系列動作達到目標狀態，最后將這一系列動作處理成可行的運動輪廓。混合A*天然考慮了車輛運動學約束，通過合理的設計啟發函數，可以獲得一條滿足終點航向約束的最短路徑，但是該方法沒有考慮車輛的速度配比，需要單獨對速度進行規劃。

此次比賽證明了城市環境中的自動駕駛是可行的。盡管日常交通的復雜程度要高于比賽中的挑戰，但DARPA仍被譽為自動駕駛汽車發展的里程碑。從該次比賽中可以看出，在實際項目中，大部分軌跡規劃方法采用了基于搜索、數學優化和混合A*算法。雖然DARPA 距今已過了十多年，但基于搜索、采樣、插值經典算法的軌跡規劃在如今的自動駕駛開發項目中仍有著廣泛的應用。

百度Apollo自動駕駛框架于2018年首次開源，該項目不斷迭代更新日漸成熟，并逐漸成為國內外自動駕駛研究的樣板。該項目軌跡規劃算法在Frenet 坐標系中使用動態規劃和二次規劃方法進行路徑規劃和速度規劃，因此這是一種路徑和速度解耦的方法，該算法被稱為EMplanner。該框架在其3.5 版本中首次采用了基于場景的規劃方法，使得算法在不同場景中的適應性和規劃效果得到提升。然而其對場景的確定和分類采用基于規則的方法，在傳感器失真和部分可觀測的情況下可能導致對場景的錯誤判斷。未來可以通過應用機器學習方法對這一部分的內容進行改進，從而進一步提高規劃算法魯棒性。該框架的后續版本中使用了端到端機器學習方法進行規劃，在其給出的仿真對比效果中可以明顯看到機器學習方法的效果顯著高于傳統規劃方法。表6為軌跡規劃5種方法對比。

表6 軌跡規劃方法比較

3 挑戰與展望

本文分析了目前軌跡規劃的常見方法并給出了其具體應用。雖然這些方法可以在仿真或者部分固定場景中應用，但是距離5級駕駛自動化還有一定距離。

從安全性來看，雖然可以額外設計安全檢測和安全回退系統來規避危險場景，如Mobileye提出的RSS責任敏感安全模型（Responsibility Sensitive Safety，RSS），可以對場景和規劃路徑進行安全評判。但是從本質上來說，這種方法沒有從規劃算法本身考慮安全問題。

實時性對自動駕駛來說至關重要，在真實動態場景中，如何在單車有限算力情況下提高規劃算法運行效率是個值得研究的問題。在5G 網絡出現后，可寄希望于云端強大的算力來解決這一問題，目前基于車、路、云系統的自動駕駛系統也逐漸成為研究重點。

從舒適性角度來說，這些算法大部分僅僅對軌跡進行了簡單的運動學約束，沒有考慮不同駕駛員的駕駛風格，未來可在進一步考慮駕駛者及乘客的舒適性，設計符合不同駕駛風格的軌跡規劃算法。

在真實應用中，傳感器的精度和感知范圍有限，甚至大部分目標被城市中的高樓等遮擋，因此對于自動駕駛車輛來說環境是部分可觀測的。如何更好地解決這種未知性和環境高交互性也是一個巨大挑戰。

目前軌跡規劃算法設計大多處于仿真測試階段，對于室外真實交通環境下的軌跡選擇，以及結合交通規則和駕駛者意圖的協調處理仍存在很大空白。

機器學習方法應用到自動駕駛領域的時間尚短，但體現出了它獨有的優勢，計算機比人類更有能力持續關注和集中注意力，而隨著人工智能所達到的水平越來接近完全自動駕駛所需要的智能水平，機器學習的優勢也會更加明顯。

目前，汽車駕駛輔助系統的研究已被廣泛應用并趨于成熟，V2X的相關規范也日漸完善。自動駕駛的發展不應局限于研究自車本身，依靠自車的感知、規劃來做出相應的決策，而是應該與V2X通信模塊相結合，實現車路協同，通過路側單元的感知作為自車輸入，更快地實現端到端的解決方案。

除了技術問題，隨著自動駕駛的發展也衍生出了責任認定、事故理賠及倫理問題，這些問題的解決需要以政府為主導，制定自動駕駛汽車發展框架、標準和法規，規范和引導相關機構行為。