兩方面對自動(dòng)駕駛車輛運(yùn)動(dòng)規(guī)劃技術(shù)進(jìn)行了綜述

文章從策略實(shí)現(xiàn)的不同，將智能車運(yùn)動(dòng)規(guī)劃算法分為圖搜索、采樣法、插值法和數(shù)值優(yōu)化法，綜合敘述了四種算法的演化以及優(yōu)缺點(diǎn)。作者還以時(shí)間軸的形式，對世界范圍內(nèi)智能交通系統(tǒng)研究單位所采用和實(shí)現(xiàn)的運(yùn)動(dòng)規(guī)劃算法進(jìn)行的調(diào)研。對運(yùn)動(dòng)規(guī)劃算法的未來發(fā)展，文章認(rèn)為主要有兩大趨勢：考慮感知和運(yùn)動(dòng)不確定性；融入駕駛員的大閉環(huán)。本篇文章綜合性強(qiáng)，詳盡地闡述了所有主流規(guī)劃算法以及應(yīng)用這些算法的主流產(chǎn)品，巨細(xì)靡遺，值得推薦給大家

摘要：利用諸如基礎(chǔ)設(shè)施和其他車輛的信息（V2I和車聯(lián)網(wǎng)技術(shù)），車輛可以通過車載傳感器和通信網(wǎng)絡(luò)實(shí)時(shí)獲取環(huán)境信息。借助于這些環(huán)境信息，不同的運(yùn)動(dòng)規(guī)劃與控制技術(shù)能夠在復(fù)雜環(huán)境下促進(jìn)自動(dòng)駕駛的實(shí)現(xiàn)。當(dāng)前運(yùn)動(dòng)規(guī)劃的研究重心集中在提升安全性、舒適性與經(jīng)濟(jì)性。然而，動(dòng)態(tài)環(huán)境下的避障、自動(dòng)與半自動(dòng)駕駛車輛的協(xié)同等在現(xiàn)實(shí)環(huán)境中的實(shí)現(xiàn)仍是挑戰(zhàn)，需進(jìn)一步的研究。本文是對自動(dòng)駕駛文獻(xiàn)中運(yùn)動(dòng)規(guī)劃技術(shù)的綜述，也介紹了各研究團(tuán)隊(duì)所采取的運(yùn)動(dòng)規(guī)劃方法與所做的貢獻(xiàn)，文章還對未來的研究方向與應(yīng)用進(jìn)行展望。

【運(yùn)動(dòng)規(guī)劃】

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

隨后，自動(dòng)駕駛衍生出許多控制架構(gòu)。如圖1所示，感知，決策和控制是主要的三大塊。本文主要介紹決策當(dāng)中的運(yùn)動(dòng)規(guī)劃技術(shù)。

圖1自動(dòng)駕駛控制架構(gòu)

在近幾十年，運(yùn)動(dòng)規(guī)劃開始作為移動(dòng)機(jī)器人的一個(gè)研究分支。研究學(xué)者也將運(yùn)動(dòng)規(guī)劃劃分為全局規(guī)劃和局部規(guī)劃。大量的路徑規(guī)劃技術(shù)從移動(dòng)機(jī)器人當(dāng)中遷移到自動(dòng)駕駛車輛領(lǐng)域，并根據(jù)所面臨的道路網(wǎng)絡(luò)與駕駛規(guī)則要求得以改進(jìn)。這些規(guī)劃技術(shù)按照實(shí)現(xiàn)方法，大致可以分為四大類——圖搜索，采樣法，插值法和數(shù)值優(yōu)化。

圖搜索

對自動(dòng)駕駛而言，其基本思想是從A點(diǎn)到B點(diǎn)遍歷一個(gè)狀態(tài)空間。這個(gè)狀態(tài)空間多用占有柵格或晶格表示。自動(dòng)駕駛當(dāng)中實(shí)現(xiàn)的方法有：

Dijkstra算法

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

A*算法

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

狀態(tài)晶格算法

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

采樣法

這一類方法是為了解決時(shí)間的約束（在高維空間規(guī)劃）。這一過程包含在特征空間或狀態(tài)空間的隨機(jī)采樣，并尋找采樣點(diǎn)在這個(gè)空間里面的連接[21]。缺點(diǎn)在于結(jié)果的次優(yōu)性。在無人車當(dāng)中使用最為廣泛的是快速隨機(jī)擴(kuò)展樹（RRT）[94]。

RRT適用于在線的路徑規(guī)劃，通過在導(dǎo)航區(qū)域執(zhí)行隨機(jī)搜索，可以在半結(jié)構(gòu)化空間實(shí)現(xiàn)快速搜索[94]。它還可以考慮非完整性約束。文獻(xiàn)[21]和文獻(xiàn)[95]對該方法進(jìn)行了闡述。在自動(dòng)駕駛方面，MIT團(tuán)隊(duì)實(shí)現(xiàn)了該算法[61]，但是結(jié)果并不是最優(yōu)，而且路徑曲率不連續(xù)。Karaman等人提出了一種RRT*[96]的改進(jìn)方法，它可以得到最優(yōu)路徑，但存在其他同樣的弊端。文獻(xiàn)[64]也對其有描述。

插值法

對于給定一系列路點(diǎn)，計(jì)算機(jī)輔助幾何技術(shù)（CAGD）在路徑平滑方面有很廣泛的應(yīng)用[73]。它可以考慮諸如可執(zhí)行、舒適性、車輛動(dòng)力學(xué)以及其他參數(shù)的約束來規(guī)劃軌跡。

插值是在預(yù)先給定一系列點(diǎn)的情況下構(gòu)造和插入一系列新的數(shù)據(jù)點(diǎn)的過程。這表明算法需要預(yù)先給定一系列節(jié)點(diǎn)，然后生成一系列有助于軌跡連續(xù)、滿足車輛約束和動(dòng)態(tài)環(huán)境的導(dǎo)航軌跡[97]。在面對障礙物時(shí)，它能夠產(chǎn)生避障的新路徑（局部路徑），并重新回到先前規(guī)劃的路徑（全局路徑）。

直線段和圓弧法

已知路網(wǎng)可以進(jìn)行分段，在已知路徑點(diǎn)插入直線或圓弧節(jié)點(diǎn)，使整段路徑用直線段和圓弧代替。在輪式車輛的路徑規(guī)劃方面，這是一種簡單的數(shù)學(xué)方法[41,98]。

回旋曲線法

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

多項(xiàng)式曲線法

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

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

貝塞爾曲線

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

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

樣條曲線

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

數(shù)值優(yōu)化

這一方法的目的在對帶約束的目標(biāo)函數(shù)進(jìn)行最優(yōu)求解，多用于計(jì)算平滑計(jì)算前的軌跡[54]或是計(jì)算滿足運(yùn)動(dòng)學(xué)約束的軌跡[5]。函數(shù)最優(yōu)化是為了找到目標(biāo)函數(shù)的實(shí)根（最小化輸出）。文獻(xiàn)[106]利用改進(jìn)勢場法實(shí)現(xiàn)了在移動(dòng)機(jī)器人狹窄空間避障的C1連續(xù)曲線規(guī)劃。文獻(xiàn)[5,38]也利用最小化考慮了位置、速度、加速度、加加速度的目標(biāo)函數(shù)尋找C2連續(xù)曲線。

圖2展示以上所提運(yùn)動(dòng)規(guī)劃技術(shù)的效果，表格1和2對運(yùn)動(dòng)規(guī)劃技術(shù)以及優(yōu)劣進(jìn)行整理。

圖2 文獻(xiàn)中的運(yùn)動(dòng)規(guī)劃方法

表1 自動(dòng)駕駛不同場景下應(yīng)用的運(yùn)動(dòng)規(guī)劃技術(shù)分類

表2 運(yùn)動(dòng)規(guī)劃技術(shù)的優(yōu)劣對比

【世界范圍內(nèi)，智能交通系統(tǒng)研究團(tuán)隊(duì)所推動(dòng)的運(yùn)動(dòng)規(guī)劃技術(shù)】

智能汽車的概念雖然可追溯到1939年紐約世博會(huì)，但是，其實(shí)現(xiàn)卻花費(fèi)了數(shù)十年。圖3以時(shí)間軸的形式展示了自動(dòng)駕駛汽車的重要發(fā)展節(jié)點(diǎn)。

圖3 重要無人駕駛車輛及其運(yùn)動(dòng)規(guī)劃技術(shù)隨時(shí)間的發(fā)展

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

在與通用汽車的合作下，PATH項(xiàng)目在加州圣地亞哥展示了其作為Demo’97部分內(nèi)容的隊(duì)列駕駛。隊(duì)列由8輛行駛在專用車道上的汽車組成，車間間距6米。卡內(nèi)基梅隆大學(xué)也參與其中，并演示了Navlab車輛[113]。同年，一份來自荷蘭的報(bào)告介紹了首次應(yīng)用于史基浦機(jī)場的CTS服務(wù)[114]，所解決的是最后一英里問題——提供上門服務(wù)以及按需服務(wù)[115]。在上述系統(tǒng)中，環(huán)境反應(yīng)控制和車路協(xié)同要優(yōu)于路徑規(guī)劃技術(shù)進(jìn)行考慮。

首次嘗試路徑規(guī)劃技術(shù)的項(xiàng)目中，VisLab的ARGO算是其中一個(gè)[76]?；谝曈X系統(tǒng)，規(guī)劃將五次多項(xiàng)式樣條曲線調(diào)整到前視相機(jī)檢測標(biāo)定到的車道當(dāng)中。之后，DARPA PerceptOR項(xiàng)目進(jìn)行了越野車的自動(dòng)導(dǎo)航仿真[116][117]，它是由DARPA挑戰(zhàn)賽(Grand and Urban challenge)所完成的，這促進(jìn)了自動(dòng)化導(dǎo)航系統(tǒng)的研究，推動(dòng)了路徑規(guī)劃技術(shù)發(fā)展（如圖2所示）。

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

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

2011年，歐洲舉辦的協(xié)同駕駛挑戰(zhàn)賽（GCDC）以縱向控制開發(fā)為主[143]。然而，一些團(tuán)隊(duì)也開發(fā)了路徑規(guī)劃策略（例如AnnieWAY的狀態(tài)格子[131]）。接下來的2016GCDC挑戰(zhàn)賽，隊(duì)列的橫向控制，擁擠道路條件下的并道和城市道路環(huán)境也將考慮進(jìn)去。

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

表3 國際智能交通系統(tǒng)研究團(tuán)隊(duì)

【總結(jié)】

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

近年來為研究團(tuán)隊(duì)實(shí)車實(shí)現(xiàn)的兩大主要算法分別是：

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

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

【未來研究重點(diǎn)】

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

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

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