自動駕駛汽車：綜述（七）---決策系統之運動規劃Motion Plan

僅供學習和參考，未授權。
本文僅作為學習和交流使用，如果作者或出版社有異議，請聯繫我進行刪除。一切都是為了更好地學術！註：鏈接文獻後面的數字代表該文章發表的年份。如[[XU17]]表示的是Xu 在2017年發表文章

導讀：這裡還是先對綜述性文章的內容進行介紹。後續也會進行更新一些相關的運動規劃相關的文章。

本文主要介紹了來自巴西聖埃斯皮里圖聯邦大學信息學系的研究者於2019年1月14日在 arXiv上發布了一篇自動駕駛汽車研究情況總結的第三部分決策系統中的路線規劃。

Self-Driving Cars: A Survey?

arxiv.org

運動規划子系統負責計算從自動駕駛車的當前狀態到由行為選擇子系統定義的下一個局部目標狀態的路徑或軌跡。運動計劃執行本地駕駛行為，並滿足汽車的運動以及動態約束，為乘客提供舒適性，同時也要避免與環境中的靜態和移動障礙物碰撞。

運動規劃可以是路徑或軌跡。該路徑是一系列汽車狀態，並且沒有定義汽車狀態如何隨時間演變。該任務也可以委託給其他子系統（如，行為選擇子系統），或者速度分布可以定義為曲率和與障礙物的接近度的函數。軌跡是對汽車指定狀態隨時間演變的路徑。

在文獻中已經提出了各種運動規劃方法。我們回顧那些專為道路運動規劃而設計並使用實際自動駕駛車進行實驗評估的方法。有關這些方法的更全面的評論，讀者可以參考González等人[GON16]和Paden等人[PAD16]的文章。

1）路徑規劃

路徑規劃涉及到汽車從當前狀態到下一個目標狀態階段生成的一系列狀態，但這個狀態不會定義汽車狀態隨時間的演變。路徑規劃通常分為全局路徑規劃和局部路徑規劃[KAM04]。在全局路徑規劃中，在汽車開始之前，全局路徑就已經通過離線地圖計算好了。在局部路徑規劃中，在汽車移動過程中，通過使用周圍環境的在線局部地圖得到局部路徑，這可以讓汽車處理移動的障礙物。路徑規劃的方法可以主要分為兩類：基於圖搜索以及基於插值曲線[GON16，PAD16]。

a）基於圖搜索的技術

基於圖搜索的方法是在以圖為特徵的狀態空間中搜索汽車的當前狀態和下一個目標狀態之間的最佳路徑（狀態序列）。它們將搜索空間表徵為圖形。他們將搜索空間離散化並在佔據柵格地圖上添加圖形，其中單元中心充當搜索圖中的鄰邊。用於自動駕駛汽車的路徑規劃的最常見的基於圖搜索的技術是Dijkstra，A*以及A*變體。

Dijkstra演算法[DIJ59]是通過找到圖的初始節點和目標節點之間的最短路徑。 Dijkstra演算法通過重複檢查最近尚未檢查的節點，將其鄰點添加到要檢查的節點集，並在達到目標節點時停止。Dijkstra演算法適用於全局路徑規劃。然而，由於檢查的節點數量很多，它在大面積地區的計算成本很高，並且有時候結果不連續[GON16]。 Arnay等[ARN16]使用Dijkstra生成一條全局路徑，該路徑被擴展用於構建自動駕駛車輛「Verdino」的軌跡。Bacha等人[BAC08]使用Dijkstra演算法為無人駕駛汽車Odin [BAC08]構建一條全局路徑，以便向停車位導航並倒車。 Kala等人[KAL13]使用Dijkstra演算法生成全局路徑和局部路徑，然而僅在計算機模擬中進行測試。

A*演算法[HAR68]是Dijkstra的擴展，其主要通過基於對目標節點的啟發式估計成本向節點分配權重來執行快速圖搜索。然而，這種演算法找到解決方案並不容易[GON16]。 Leedy等人[LEE07]採用A*演算法為無人駕駛汽車「Rocky」建立局部路徑，參與了2005年DARPA大挑戰賽。Ziegler等人[ZIE08]提出了一種局部路徑規劃方法，該方法將A*演算法與兩種不同的啟發式成本函數相結合，即（RTR）度量和Voronoi。其中第一個考慮了汽車的運動學約束，而第二個考慮了障礙物的形狀和位置的常識。該方法在機車「AnnieWAY」中進行了測試，該車參加了2007年DARPA城市挑戰賽。

其他作者提出了用於路徑規劃的A*演算法的變體。 Urmson等[URM08]為無人駕駛汽車「Boss」（卡內基梅隆大學的汽車在2007年DARPA城市挑戰賽中獲得第一名）提出任意時刻D*。Dolgov等人[DOL10]為無人駕駛車「Junior」[MON08]（斯坦福大學的汽車在2007年DARPA城市挑戰賽中獲得第二名）提出了混合動力A*。任何時候D*和混合狀態A*的演算法都會合併兩個啟發式演算法：一個是非完整的，因為它忽略了障礙物；另一個則是完整的，因為它考慮了障礙物，並用於非結構化環境（停車場）中的路徑規劃。Chu等人[CHU15]提出了A*的變體來建立考慮汽車運動學約束的局部路徑，通過忽略了網格單元的解析度並創建了平滑的路徑。 Yoon等人[YOO15]提出了一種A*的變體，該方法用於自動駕駛車「Kaist」的運動學限制。

b）基於曲線插值的方法

基於曲線插值的方法是通過使用插值處理。該方法通過插值處理在之前已知的點集的範圍內插入新的點集。方法採用之前已知的一組點（如，描述路線圖的航點）並生成描繪更平滑路徑的新點集。用於自動駕駛汽車的路徑規劃的最常用曲線插值的方法是是樣條曲線。

樣條曲線是以子間隔劃分為分段多項式參數曲線，這些曲線可以將其定義為多項式曲線。每個子段之間的連接稱為結（或控制點），其通常具有高度平滑約束。這種曲線具有較低的計算成本，因為其行為是由結來定義的。然而，這種方法的結果可能不是最優的，因為它更側重於實現部件之間的連續性而不是滿足道路的約束，並且它取決於全局航路點[GON16]。Chu等人[CHU12]和胡等人[HU18]使用三次樣條曲線進行路徑規劃。他們的方法都構成了從車道地圖獲得的一組航路點的中心線，並且生成一系列三次樣條的參數。這些三次樣條參數通過使用弧長和偏移到中心線來表示可能的路徑候選。其中，最佳路徑通過基於功能成本的加權和來選擇。這兩種方法之間的區別在於：第一種方法僅避免靜態障礙，而第二種既可以避免靜態也能避免移動障礙。另一個不同之處在於，第一個是在自動駕駛汽車「A1」(在2010年贏得了韓國的自動駕駛汽車競賽)上測試的，而第二個則通過計算機模擬評估，模擬了具有挑戰性的情景，包括單車道和多車道有靜止和移動障礙的道路。

2）軌跡規劃

軌跡規劃涉及自動駕駛車從當前狀態到下一個目標狀態（該狀態詳細說明了汽車狀態隨時間的變化過程）生成一系列狀態。軌跡規劃的方法可以主要分為四類：基於圖搜索、基於採樣、基於插值曲線以及基於數值優化[GON16，PAD16]。

a）基於圖搜索的技術

用於軌跡規劃的基於圖搜索的技術擴展了用於路徑規劃的技術（第4.2.1節），以用來詳細說明汽車狀態隨時間的變化過程。在自動駕駛汽車中，最常見的基於圖搜索的軌跡規劃方法是狀態點陣、彈性帶（EB）和A*。

狀態點陣是一種搜索圖，該搜索圖的頂點表示狀態，邊表示連接滿足設備運動約束的狀態的路徑。頂點以常規方式放置，並使得相同的路徑可用於連接所有頂點。通過這種方式，到目標的路徑可能通過圖中的一系列邊來展示。僅通過表徵解決方案中的可能狀態，該狀態網格必須適合於在線路徑規劃。此外，該方法必須通過添加時間和速度維度將這種「狀態晶格」擴展到動態環境。狀態格子能夠處理多個維度，例如位置，速度和加速度，並且適用於局部規劃和動態環境。但是，它們具有很高的計算成本，因為它會評估圖中的每個可能的解決方案[GON16]。McNaughton等人[MCN11]提出了一種用於道路軌跡規劃的共形時空狀態格。他們在方法中圍繞中心線路徑構建狀態網格，在距離中心線的橫向偏移處定義道路上的節點，並使用優化演算法計算節點之間的邊緣。該優化演算法找到定義連接任何節點對的邊的多項式函數的參數。他們為每個節點分配一個狀態向量，其中包含姿勢、加速度曲線以及時間和速度範圍。通過時間和速度間隔的更精細離散化相比，加速度曲線以更低的成本增加軌跡多樣性。此外，時間和速度的範圍通過允許將時間和速度分配給圖搜索階段而不是圖構建階段來降低計算成本。Xu等人[XU12]提出了一種迭代優化的方法，該迭代優化應用於從狀態點陣導出的合成軌跡，以用來減少規劃的時間並改善了軌跡質量。Gu等人[GU16]提出了一種將狀態晶格軌跡規劃與行為選擇融合的規劃方法。該方法對一組候選軌跡進行採樣，並從中提取不同的行為。通過選擇行為並選擇與所選行為相關聯的候選軌跡來獲得最終軌跡。Li等人[LI16]使用三次多項式曲線沿全局路徑生成候選路徑，此外通過計算速度分布對所生成的路徑的點進行分配，並通過成本函數評估所生成的軌跡，並選擇最佳軌跡。

在路徑規劃方法中，基於彈性帶方法的優化是通過具有彈性節點和邊緣的圖表來表徵狀態空間。通過用連接相鄰空間節點的內外邊緣對空間節點進行擴充來定義彈性節點。路徑是通過優化演算法獲取。其中優化演算法平衡兩種力:外部障礙產生的排斥力以及消除帶鬆弛的相鄰點所產生的收縮力。該方法展示了連續性和穩定性，具有非確定性的運行時間並且需要無衝突的初始路徑。

Gu等人[GU15]提出了一種解耦的時空軌跡規劃方法，該方法對路徑規劃和軌跡規划進行分別執行。軌跡規劃分為三個階段：在第一階段，考慮道路和障礙物約束來計算無碰撞路徑，並且使用純追蹤控制器和運動學汽車模型生成可行路徑；在第二階段，在幾個約束（速度限制、障礙物接近、橫向加速度和縱向加速度）下給出速度分布；最後，給定路徑和速度分布，通過參數路徑螺旋計算軌跡。通過模擬未來的運動，演算法可以對所有靜態和移動障礙物進行軌跡評估。 A*演算法通常用於路徑規劃（第4.2.1節）或非結構化軌跡規劃。道路軌跡規劃，Fassbender等[FAS16]對A*提出了兩種新的節點擴展方案。第一種方案通過數值優化來試圖找到汽車從當前節點直接連接到目標節點的軌跡。第二種方案使用純追蹤控制器去在沿著全局參考路徑上，生成引導汽車的短邊（即，短運動基元）。

b）基於抽樣的方法

基於採樣的方法是通過隨機地對狀態空間進行採樣來尋找汽車當前狀態和下一個目標狀態之間的連接。在自動駕駛汽車軌跡規劃中，最常用的基於採樣的方法是快速探索隨機樹（RRT）。

用於軌跡生成的RRT方法[LAV01]使用來自狀態空間的隨機樣本將汽車從當前狀態進行遞增，以用來構建搜索樹。在每個隨機狀態，控制命令應用在樹的最近頂點，以用來創建儘可能接近隨機狀態的新狀態。其中樹的每個頂點表示一個狀態，每個有向邊表示一個用於擴展狀態的命令。候選軌跡通過各種標準進行評估。RRT方法對於高維空間具有較低的計算成本，並且只要解存在，總是找到解決方案，但需要演算法給予足夠的時間。然而，它的結果並不是連續而且不穩定[GON16]。 Radaelli等[RAD14]提出了一種用於無人駕駛車「IARA」的軌跡規劃的RRT方法。它們為標準RRT方法提供了新的變體，該變體方法用來將隨機狀態的位置偏向車道區域，選擇最有希望的控制命令來擴展狀態，選擇最佳軌跡，丟棄非有希望狀態，並重新使用部分在在之前的規劃周期內構建的軌跡。Du等人[DU16]提出了一種RRT方法，該方法通過使用駕駛員在道路上的視覺搜索行為來指導RRT的狀態採樣。駕駛員在進行轉彎過長中會使用「近點」和「遠點」。他們利用彎道上顯示的駕駛員視覺搜索行為的這一特徵來指導RRT方法。此外，他們採用基於B樣條的後處理方法來生成平滑、連續和可行的軌跡。

c）基於曲線的插值方法

基於插值曲線的方法通過內插先前已知的一組點（如，道路地圖路點）並且構建更平滑的軌跡。該軌跡同時考慮汽車的運動和動態約束、舒適度、障礙物以及其他參數。在自動駕駛汽車的軌跡規劃中最常見的基於內插曲線的技術是迴旋曲線。

迴旋曲線允許定義具有線性可變曲率的軌跡，以便直線段到彎曲段之間的過渡是平滑的。然而，由於通過積分方法來定義，因此迴旋曲線具有高計算成本，並且它取決於全局航路點[GON16]。 Alia等[ALI15]使用迴旋觸角進行軌跡規劃。從汽車的重心開始，採用迴旋曲線的形式，根據不同的速度和不同的初始轉向角來計算出觸角。使用佔據柵格圖將觸角分類為可導航或不可導航。在可通航的觸角中，最好的觸手是根據幾個標準選擇的。 Mouhagir等[MOU16] [MOU17]也使用迴旋觸手進行軌跡規劃。然而，他們使用使用馬爾可夫決策過程啟發的方法來選擇最佳觸手。

d）基於數值優化的方法

基於數值優化的方法是將約束變數的函數最小化或最大化的過程。在自動駕駛汽車軌跡規劃中，最常見的基於數值優化的技術是函數優化和模型預測方法。

函數優化方法是在考慮軌跡約束(如位置，速度，加速度和加加速度）下最小化成本函數來找到軌跡。這些方法可以很容易地考量汽車的運動學和動力學約束以及環境的約束。然而，由於在每個運動狀態中都需要進行優化，並且取決於全局航路點，因此這種方法具有高計算成本[GON16]。Ziegler等人[ZIE14b]使用功能優化方法對自動駕駛汽車「Bertha」進行軌跡規劃。他們通過最小化成本函數並遵守軌跡約束。找到最佳軌跡。成本函數由一組項組成：使軌跡以指定的速度駕駛通道的中間行駛，對強加速度進行懲罰，抑制加速度的快速變化，並衰減高偏航率。

用於軌跡規劃的模型預測方法[HOW07]是通過對汽車從當前狀態和下一個目標狀態之間產生動態可行的控制命令。它們可用於解決生成滿足狀態約束的參數化控制命令的問題，其中動態可由微分方程表示。Ferguson等人[FER08]使用模型預測方法對自動駕駛汽車「Boss」[URM08]進行軌跡規劃。該方法可以生成到從中心線路徑導出的一組目標狀態的軌跡。為了計算每個軌跡，他們使用優化演算法逐漸修改軌跡控制參數的初始近似，直到軌跡終點誤差在可接受的界限內。軌跡控制參數包括軌跡長度以及定義曲率輪廓的樣條曲線的三個結點。基於若干因素（如，當前道路的速度極限，最大可行速度和目標狀態速度）為每個軌跡生成的速度分布。並根據它們與障礙物的距離、到中心線路徑的距離、平滑度、終點誤差和速度誤差來選擇最佳軌跡。Li等人[LI17]使用基於狀態採樣的軌跡規劃方案，該方案在全局參考路徑中對目標狀態進行採樣，並應用模型預測路徑規劃方法來產生將汽車從當前狀態連接到採樣目標狀態的路徑。速度曲線用於為生成路徑的每個狀態進行分配速度。考慮安全性和舒適性的成本函數用於選擇最佳軌跡。 Cardoso等[CAR17]使用模型預測方法進行自動駕駛車輛「IARA」的軌跡規劃。為了計算軌跡，他們使用優化演算法來找到軌跡控制參數，該軌跡控制參數在到目標狀態的距離，到中心線路徑的距離以及與障礙物的接近度進行最小化優化。其中軌跡控制參數包括軌跡時間和四個結點（指定轉向角輪廓的樣條曲線）。

對比圖片來自：自動駕駛汽車的運動規劃技術綜述