文章從策略實現的不同，將智能車運動規劃算法分為圖搜索、采樣法、插值法和數值優化法，綜合敘述了四種算法的演化以及優缺點。作者還以時間軸的形式，對世界范圍內智能交通系統研究單位所采用和實現的運動規劃算法進行的調研。對運動規劃算法的未來發展，文章認為主要有兩大趨勢：考慮感知和運動不確定性；融入駕駛員的大閉環。本篇文章綜合性強，詳盡地闡述了所有主流規劃算法以及應用這些算法的主流產品，巨細靡遺，值得推薦給大家

摘要：利用諸如基礎設施和其他車輛的信息（V2I和車聯網技術），車輛可以通過車載傳感器和通信網絡實時獲取環境信息。借助于這些環境信息，不同的運動規劃與控制技術能夠在復雜環境下促進自動駕駛的實現。當前運動規劃的研究重心集中在提升安全性、舒適性與經濟性。然而，動態環境下的避障、自動與半自動駕駛車輛的協同等在現實環境中的實現仍是挑戰，需進一步的研究。本文是對自動駕駛文獻中運動規劃技術的綜述，也介紹了各研究團隊所采取的運動規劃方法與所做的貢獻，文章還對未來的研究方向與應用進行展望。

【運動規劃】

90年代以前，由于投資的減少，智能車輛領域發展十分有限。得益于適用于車輛自動化信息技術的發展，形成了智能交通系統的概念。世界范圍內諸多研究中心（比如加利福尼亞的Path團隊，帕爾馬大學等等）的投入，為智能車輛系統的提升注入了源源不斷的力量。第一輛自動駕駛概念車的歷史可追溯到80年代末期90年代初。當時，為了提升公路系統的服務能力，Shladover等人提出了一種車輛的縱向控制系統（包括車輛的跟隨控制，車間通信，及與其他技術的比較）和橫向控制系統（考慮橫向動力學和磁力傳感器作為路徑引導物，并未涉及路徑規劃）。而Behringer等人則提出VaMoR-L車輛中集成的自動駕駛概念——通過視覺和路徑生成，車輛可以自動駕駛（來源自其普羅米修斯項目）。

隨后，自動駕駛衍生出許多控制架構。如圖1所示，感知，決策和控制是主要的三大塊。本文主要介紹決策當中的運動規劃技術。

圖1自動駕駛控制架構

在近幾十年，運動規劃開始作為移動機器人的一個研究分支。研究學者也將運動規劃劃分為全局規劃和局部規劃。大量的路徑規劃技術從移動機器人當中遷移到自動駕駛車輛領域，并根據所面臨的道路網絡與駕駛規則要求得以改進。這些規劃技術按照實現方法，大致可以分為四大類——圖搜索，采樣法，插值法和數值優化。

圖搜索

對自動駕駛而言，其基本思想是從A點到B點遍歷一個狀態空間。這個狀態空間多用占有柵格或晶格表示。自動駕駛當中實現的方法有：

Dijkstra算法

這是在圖表中找到單源最短路徑的圖搜索方法。搜索空間近似為一個離散的單元格，晶格[22,23]。具體描述和實現可見文獻[24,25]。在自動駕駛方面，文獻[26]實現了該算法在多車場景的仿真，Little Ben 自動駕駛車[27] 和Victor Tango團隊 [28] 上都有該算法實現。文獻[29]實現了該算法在城市工況下的應用。

A*算法

其核心是節點權重該如何確定。它適合具有先驗知識的車輛進行空間搜索，但又太消耗存儲和計算速度[30]。在移動機器人領域的一些應用被自動駕駛采用，并作為基礎進行改進。例如dynamicA* (D*) [31]，Field D* [32]，Theta* [33]，Anytimerepairing A* (ARA*) 以及 Anytime D*(AD*) [34]等等。Ziegler等人在Voronoi地圖表征的非結構化空間和泊車點實現了A*算法[35]。文獻[36]和文獻[37]分別是hybrid A*和A*在Junior和AnnieWay自動駕駛車輛上的應用。BOSS自動駕駛車使用的是AD*算法[16]。

狀態晶格算法

采用由狀態網格組成離散的規劃空間。這些網格被稱為狀態晶格，并在基于此進行搜索規劃[46]。路徑搜索是基于局部一系列的狀態晶格查詢或是包含所有可行特征的查詢，它允許車輛從一個初始狀態轉移到其他狀態。代價函數確定了狀態晶格地圖的最佳路徑。A*[47]和D*[48]在該方法中都有實現。Howard和Kelly將狀態晶格應用到了輪式移動機器人在崎嶇路面的運動規劃當中[49]，仿真表明該方法具有全局和局部比較好的結果。文獻[39]和文獻[50]采用了時間維度和速度維度的狀態晶格。

采樣法

這一類方法是為了解決時間的約束（在高維空間規劃）。這一過程包含在特征空間或狀態空間的隨機采樣，并尋找采樣點在這個空間里面的連接[21]。缺點在于結果的次優性。在無人車當中使用最為廣泛的是快速隨機擴展樹（RRT）[94]。

RRT適用于在線的路徑規劃，通過在導航區域執行隨機搜索，可以在半結構化空間實現快速搜索[94]。它還可以考慮非完整性約束。文獻[21]和文獻[95]對該方法進行了闡述。在自動駕駛方面，MIT團隊實現了該算法[61]，但是結果并不是最優，而且路徑曲率不連續。Karaman等人提出了一種RRT*[96]的改進方法，它可以得到最優路徑，但存在其他同樣的弊端。文獻[64]也對其有描述。

插值法

對于給定一系列路點，計算機輔助幾何技術（CAGD）在路徑平滑方面有很廣泛的應用[73]。它可以考慮諸如可執行、舒適性、車輛動力學以及其他參數的約束來規劃軌跡。

插值是在預先給定一系列點的情況下構造和插入一系列新的數據點的過程。這表明算法需要預先給定一系列節點，然后生成一系列有助于軌跡連續、滿足車輛約束和動態環境的導航軌跡[97]。在面對障礙物時，它能夠產生避障的新路徑（局部路徑），并重新回到先前規劃的路徑（全局路徑）。

直線段和圓弧法

已知路網可以進行分段，在已知路徑點插入直線或圓弧節點，使整段路徑用直線段和圓弧代替。在輪式車輛的路徑規劃方面，這是一種簡單的數學方法[41,98]。

回旋曲線法

這一類曲線是定義在Fresnel坐標下（菲涅耳積分）[73]。由于該方法的曲率對應于弧長變化，所以回旋曲線可以定義軌跡按曲率線性變化；可以實現直線段和曲線段在曲率上平滑過渡[42]。回旋曲線在高速、軌交和類車機器人的運動規劃中同樣使用，能夠實現[99]。VIAC項目對回旋曲線的實現進行了測試。文獻[69]中，當前曲率從轉向輪的位置上獲取，其他參數則考慮根據動力學約束（比如擺尾）或者物理約束（比如轉向輪轉角）獲得。

多項式曲線法

這一類曲線通常用來滿足插入點的所需求的約束，在位置擬合、轉角和曲率約束等方面比較適用。起點和終點的期望值以及約束決定了曲線的系數。為了計算多項式曲線的系數，可以參考文獻[76,77,79]。

研究車輛-基礎設施-駕駛員之間交互的實驗室（LIVIC）在換道場景中實現了這類算法[77]。四次多項式曲線用以滿足縱向的約束，五次多項式曲線用以滿足側向的約束。文獻[75]使用三次多項式曲線生成超車所需的安全軌跡。文獻[43]在狀態晶格中實現三次多項式曲線和四次多項式曲線的規劃。

貝塞爾曲線

這種參數化曲線的形狀由控制點決定。貝賽爾曲線的核心是伯恩斯坦多項式。由于曲線受控制點決定，這一方法的優點是計算量小。通過正確的放置控制點，起始點和終點的曲線約束可以得到滿足[81,100]。

文獻[100]展示了貝賽爾曲線的一個很好的模塊化和可擴展的例子，文獻[102]設計了一個滿足曲率連續的圓形和貝賽爾曲線相連接曲線軌跡。這些曲線常用以近似回旋曲線[103,104]，或者是快速規劃時替代嚴格的貝塞爾曲線[85,86]。文獻[81,83,44]在自動駕駛上實現了三階和四階貝賽爾曲線，并評估了不同場景（轉向、迂回、換道、避障等等）的最佳操作曲線。

樣條曲線

是分段多項式參數曲線，分段曲線可以是多項式曲線[28,76]，B樣條曲線[88,89]，貝賽爾曲線[105]或者是回旋曲線[99]。分段曲線的連接點叫節點，它一般具有高度平滑性的約束。一個B樣條帶變節點的例子如文獻[45]所示。

數值優化

這一方法的目的在對帶約束的目標函數進行最優求解，多用于計算平滑計算前的軌跡[54]或是計算滿足運動學約束的軌跡[5]。函數最優化是為了找到目標函數的實根（最小化輸出）。文獻[106]利用改進勢場法實現了在移動機器人狹窄空間避障的C1連續曲線規劃。文獻[5,38]也利用最小化考慮了位置、速度、加速度、加加速度的目標函數尋找C2連續曲線。

圖2展示以上所提運動規劃技術的效果，表格1和2對運動規劃技術以及優劣進行整理。

圖2 文獻中的運動規劃方法

表1 自動駕駛不同場景下應用的運動規劃技術分類

表2 運動規劃技術的優劣對比

【世界范圍內，智能交通系統研究團隊所推動的運動規劃技術】

智能汽車的概念雖然可追溯到1939年紐約世博會，但是，其實現卻花費了數十年。圖3以時間軸的形式展示了自動駕駛汽車的重要發展節點。

圖3 重要無人駕駛車輛及其運動規劃技術隨時間的發展

自1987年到1994年間，歐洲的尤里卡普羅米修斯項目是智能車研究的先鋒，這其中，來自戴姆勒和沃爾沃等工業合作伙伴的不同汽車都是自動駕駛。彎曲部分路徑用螺旋線實現以輔助控制系統實現循跡[14]。

在與通用汽車的合作下，PATH項目在加州圣地亞哥展示了其作為Demo’97部分內容的隊列駕駛。隊列由8輛行駛在專用車道上的汽車組成，車間間距6米?？▋然仿〈髮W也參與其中，并演示了Navlab車輛[113]。同年，一份來自荷蘭的報告介紹了首次應用于史基浦機場的CTS服務[114]，所解決的是最后一英里問題——提供上門服務以及按需服務[115]。在上述系統中，環境反應控制和車路協同要優于路徑規劃技術進行考慮。

首次嘗試路徑規劃技術的項目中，VisLab的ARGO算是其中一個[76]。基于視覺系統，規劃將五次多項式樣條曲線調整到前視相機檢測標定到的車道當中。之后，DARPA PerceptOR項目進行了越野車的自動導航仿真[116][117]，它是由DARPA挑戰賽(Grand and Urban challenge)所完成的，這促進了自動化導航系統的研究，推動了路徑規劃技術發展（如圖2所示）。

自2009年谷歌車輛進入市場，谷歌在諸多場合展示其自動駕駛能力，獲得超過了700000英里無事故的行駛里程。谷歌也在推動這項技術的立法，并于2012年5月獲得自動駕駛車輛的首個許可（兩個月后，內達華州頒布了首個自動駕駛汽車的法令）[118]。然而，并沒有谷歌自動駕駛中運動規劃和控制方面的技術公布。

2010年舉行的視覺實驗室國際自動駕駛挑戰賽（VISC）,車輛以自動模式從意大利（帕爾馬）到中國（上海）行駛13000公里，規劃當中主要考慮的是螺旋線生成的代價函數。同年及2012年，現代汽車在韓國本土舉辦了自動駕駛汽車挑戰賽。2010年的挑戰賽任務集中在循跡和避障。2012年的挑戰賽任務集中在城市駕駛場景的理解與信號燈的檢測[17]。涉及的運動規劃技術包括螺旋線[18]，[119]，RRT[120]及其他技術。

2011年，歐洲舉辦的協同駕駛挑戰賽（GCDC）以縱向控制開發為主[143]。然而，一些團隊也開發了路徑規劃策略（例如AnnieWAY的狀態格子[131]）。接下來的2016GCDC挑戰賽，隊列的橫向控制，擁擠道路條件下的并道和城市道路環境也將考慮進去。

最近，奧迪聯合斯坦福[42][144]開發了高性能的車輛控制，實現了螺旋曲線的規劃。參與的演示包括：2010年的派克峰攀登，2012年的雷山賽馬場的一圈跑圈，2014年F1賽車速達150邁，2015年從硅谷到拉斯維加斯真實場景下自動駕駛。也就是在2015年，德爾福自動駕駛首次實現了從美國東海岸到西海岸，長達9天，從舊金山到紐約。表3列舉了國際研究團隊的情況。

表3 國際智能交通系統研究團隊

【總結】

智能規劃算法的開發是機器人研究領域的一大關鍵技術[20][21]。延伸到自動駕駛汽車，相關的約束包括交通規則，車速，道路條件，以及時間限制（復雜條件下規劃到指定區域）等。本文從以下兩方面對自動駕駛車輛運動規劃技術進行了綜述：一，對比分析了四大類運動規劃技術（如表1所列），包括圖搜索、采樣法、插值法和數值優化的方法；二，調研了世界范圍內主要智能交通系統研究單位所實現的運動規劃算法（如表3所列）。

近年來為研究團隊實車實現的兩大主要算法分別是：

1、插值法。近年來，自動駕駛車輛所采用的規劃算法有螺旋線（奧迪、帕爾馬/VisLab，斯坦福），貝塞爾曲線（INRIA）和多項式曲線（戴姆勒，INRIA）。這是基于結構化道路環境下對地圖信息的豐富——可以提供所需的加州道路交通路點的數據。此外，出于舒適性、安全性、車輛幾何與動力學約束考慮，軌跡生成還需經過曲線優化這一步。

2、圖搜索。狀態格子是應用最廣泛的方法之一，例如CMU、KIT、GMC等研究單位都有實現。在考慮到舒適性、安全性、車輛幾何與動力學約束時，該算法可以快速搜索到最優路徑，盡管該算法只具備解析完備性。

【未來研究重點】

運動規劃現在所面臨的挑戰是動態環境下的實時規劃問題。城市道路場景下，存在眾多的交通參與者（比如，行人，騎自行車的人，其他車輛等），這要求對所規劃出來的軌跡進行不斷的評估。如何在有限的時間內實現多動態障礙無環境下的無碰撞軌跡生成是一個尚未解決的難題。難點主要在于耗時的環境感知[145]大大降低了運動規劃的決策時間窗。目前所實現的算法還不足以克服這個限制。

由于規劃是感知和控制之間的紐帶，當前的新規劃算法開發多考慮感知的不確定性以及控制的約束。在動態環境數據采集過程中，路徑規劃的最新發展目標是正確處理數據采集過程中的不確定性。這在實時的情況下會有更好的環境感知效果，并指導規劃過程。通過考慮感知階段的不確定性來提高防止危險情況的能力。從控制的角度來看，需考慮多目標，包括車輛的運動學約束和乘客的舒適性等。近年來，研究通過軌跡的平滑和可執行性來考慮這些控制約束。接下來的研究將可能是考慮控制約束的同時，融合感知的不確定性。KIT和CMU在這一方面已開始研究。

另一個趨勢是增加駕駛員的大控制環，類似于ADAS的功能，通過HMI實現軌跡與駕駛員的交互。在確保軌跡安全、平滑與可執行的條件下，感知不確定性，控制約束，駕駛員知識的多融合將是一個新的極具挑戰性的研究。