自動駕駛汽車路徑規(guī)劃技術(shù)*

張栩源 李軍

（重慶交通大學(xué)機(jī)電與車輛工程學(xué)院；重慶市軌道交通車輛系統(tǒng)集成與控制重慶市重點(diǎn)實(shí)驗(yàn)室）

自動駕駛汽車為了完成自主導(dǎo)航的功能，通常要經(jīng)歷環(huán)境感知、路徑規(guī)劃和運(yùn)動控制3 個(gè)過程。其中，路徑規(guī)劃是無人車導(dǎo)航和定位技術(shù)中一個(gè)非常重要的環(huán)節(jié)，因此它也成為越來越多的研究者非常熱衷的課題[1]。隨著汽車市場的競爭加劇以及自動駕駛技術(shù)的優(yōu)點(diǎn)凸顯，自動駕駛成為智能交通系統(tǒng)的重要組成部分。它不僅排除了人為不確定因素的影響，而且在駕駛安全性、旅行時(shí)間、交通擁塞問題、能源利用率等方面也獲得了較大的提升和改進(jìn)。文章從理論和算法實(shí)時(shí)性等方面詳細(xì)介紹了各種算法的優(yōu)勢和缺點(diǎn)，并針對各類算法在最新研究的路徑規(guī)劃問題中存在的問題提出了一些改進(jìn)建議，為今后更進(jìn)一步地深入研究提供了參考。

1 路徑規(guī)劃分類

自動駕駛汽車的路徑規(guī)劃問題，基于研究對象對所行駛環(huán)境信息掌握程度的不同，可分為2 類。第1 類是已知行駛環(huán)境信息的全局路徑規(guī)劃，屬于靜態(tài)規(guī)劃[2-3]；第2 類是利用車載傳感器實(shí)時(shí)獲取環(huán)境信息的局部路徑規(guī)劃，屬于動態(tài)規(guī)劃[4-5]。

全局路徑規(guī)劃問題實(shí)質(zhì)上是在已掌握的所有環(huán)境信息的前提下，規(guī)劃出從起點(diǎn)到目標(biāo)點(diǎn)的路徑生成問題。通常是基于數(shù)字地圖，根據(jù)周圍環(huán)境的路網(wǎng)模型來選擇路徑。當(dāng)因環(huán)境或者其他因素導(dǎo)致規(guī)劃的路徑無法繼續(xù)通行時(shí)，則需要重新啟動全局規(guī)劃，以得到更新后的可行路徑。局部路徑規(guī)劃需要車載傳感器實(shí)時(shí)采集車輛周圍的環(huán)境信息，充分了解周圍環(huán)境地圖信息以準(zhǔn)確定位出車輛當(dāng)前位置及周圍障礙物分布，從而順利規(guī)劃出從當(dāng)前節(jié)點(diǎn)到下一子目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑。在無人駕駛系統(tǒng)中，局部路徑規(guī)劃在跟蹤全局路徑的同時(shí)能夠順利完成避障，大大提高規(guī)劃系統(tǒng)在動態(tài)未知環(huán)境下的路徑規(guī)劃能力。局部路徑規(guī)劃在路徑規(guī)劃的過程中非常重要，它通常以規(guī)劃的曲線作為未來車輛可能的行駛路線。對該曲線進(jìn)行安全分析，從而確定期望的曲率與速度。如果所規(guī)劃的曲線與期望的行駛軌跡不一致，則說明曲線的安全性分析失效，該無人車很有可能出現(xiàn)安全隱患，甚至?xí)萑肽骋华M小區(qū)域而無法通行[6]。

2 路徑規(guī)劃常用算法

2.1 傳統(tǒng)算法

傳統(tǒng)路徑規(guī)劃算法包括A*算法、人工勢場法、模糊邏輯算法、禁忌搜索算法等。文章僅對最常見的前兩種算法做詳細(xì)說明。

1）A*算法[7]是一種典型的啟發(fā)式搜索算法，它也是靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索算法。A*算法通過一個(gè)估價(jià)函數(shù)來引導(dǎo)和決定搜索方向，從起點(diǎn)開始向周圍進(jìn)行擴(kuò)展搜索，利用估價(jià)函數(shù)來獲取周圍每個(gè)節(jié)點(diǎn)的價(jià)值，并從獲取的周圍節(jié)點(diǎn)中選擇代價(jià)最小的節(jié)點(diǎn)作為下一個(gè)擴(kuò)展節(jié)點(diǎn)，不斷循環(huán)重復(fù)這一過程直到到達(dá)目標(biāo)點(diǎn)，結(jié)束搜索，從而生成最終路徑。由于每次選擇的擴(kuò)展節(jié)點(diǎn)的代價(jià)都是最低的，所以最終生成的路徑代價(jià)也是最低的。

該算法具有完備的特性，它的優(yōu)勢在于對解的捕獲能力是完全的。但由此會產(chǎn)生算法復(fù)雜度大、很難在動態(tài)移動障礙物的環(huán)境下較好運(yùn)用的弊端。針對這種情況，文獻(xiàn)[8]將該算法與跳點(diǎn)搜索算法相結(jié)合，在搜索過程中優(yōu)化搜索策略，通過跳點(diǎn)搜索算法挑選出一批具有代表性的跳點(diǎn)進(jìn)行擴(kuò)展，而不是評估所有相鄰節(jié)點(diǎn)進(jìn)行擴(kuò)展，避免了A*算法尋路過程中對大量中間節(jié)點(diǎn)的計(jì)算。此外，文獻(xiàn)[9]提出了一種凸優(yōu)化和A*算法相結(jié)合的避障路徑規(guī)劃算法，該算法允許A*算法利用大尺度網(wǎng)格規(guī)劃出一條最優(yōu)的大致趨勢路徑，并通過交替使用2 種凸優(yōu)化算法快速計(jì)算出地面環(huán)境中無障礙凸多邊形及其最大面積內(nèi)切橢圓，以便移動機(jī)器人在該區(qū)域內(nèi)進(jìn)行局部避障和任務(wù)動作規(guī)劃。

2）人工勢場法[10]（APF）是一種虛擬力法。將被控對象在環(huán)境中的運(yùn)動虛擬為在受力場中的運(yùn)動，行駛環(huán)境中的障礙物對被控對象生成斥力勢場并對其產(chǎn)生斥力，在目標(biāo)點(diǎn)位置以及希望被控對象進(jìn)入的區(qū)域生成引力勢場并對其產(chǎn)生引力，對被控對象產(chǎn)生的引力和斥力進(jìn)行矢量合成，二者產(chǎn)生的合力使得被控對象沿著無障礙物的路徑運(yùn)動。

該算法結(jié)構(gòu)簡單、實(shí)時(shí)性強(qiáng)、規(guī)劃路徑高效平滑，但遇到復(fù)雜環(huán)境易陷入局部最小點(diǎn)或者產(chǎn)生劇烈震蕩。因此，該算法不適合對動態(tài)目標(biāo)進(jìn)行定位、跟蹤和避障。文獻(xiàn)[11]提出了一種改進(jìn)的基于連通性分析的人工勢場方法，并將其應(yīng)用于LBS 系統(tǒng)的路徑規(guī)劃問題。在連通分析的基礎(chǔ)上，在傳統(tǒng)的人工勢場算法中引入速度因子，構(gòu)造新的重力場函數(shù)和排斥力場函數(shù)，利用速度因子這一矢量特性，使用戶可以跟蹤動態(tài)目標(biāo)，有效避開移動過程中的障礙物，從而獲得最佳路徑。文獻(xiàn)[12]針對傳統(tǒng)人工勢場法中的目標(biāo)不可達(dá)問題和局部極小值問題提出了一種改進(jìn)的斥力勢場函數(shù)，實(shí)現(xiàn)了勢場的調(diào)節(jié)。在改進(jìn)的斥力場函數(shù)中引入了智能車輛與目標(biāo)點(diǎn)的相對距離，增加了調(diào)節(jié)因子實(shí)現(xiàn)勢場調(diào)節(jié)，使得整個(gè)態(tài)勢場的最小勢點(diǎn)始終位于目標(biāo)點(diǎn)。同時(shí)針對障礙物與目標(biāo)點(diǎn)之間的引力和斥力平衡所引起的局部極小化問題，提出了模糊控制算法的策略，使其擺脫最小值點(diǎn)。

4 種常見的傳統(tǒng)路徑規(guī)劃算法在優(yōu)化路徑規(guī)劃時(shí)存在的優(yōu)缺點(diǎn)比較，如表1 所示。

表1 傳統(tǒng)算法在優(yōu)化路徑規(guī)劃時(shí)存在的優(yōu)缺點(diǎn)比較

2.2 智能仿生學(xué)算法

智能仿生算法主要有粒子群算法、蟻群算法、神經(jīng)網(wǎng)絡(luò)算法、遺傳算法、灰狼優(yōu)化算法、煙花算法、人工魚群算法等。

1）粒子群算法[13]（PSO）主要是通過模擬鳥群的覓食行為來搜索目標(biāo)函數(shù)的全局最優(yōu)值。由于傳統(tǒng)的粒子群優(yōu)化算法在尋找全局最優(yōu)解時(shí)存在早熟收斂及收斂精度低等缺點(diǎn)，因此針對粒子群算法的研究主要集中在改進(jìn)與優(yōu)化種群結(jié)構(gòu)以及相應(yīng)參數(shù)等方面。為了解決未知環(huán)境下的路徑規(guī)劃問題以及提高粒子群優(yōu)化算法的收斂速度，文獻(xiàn)[14]提出了一種基于仿生神經(jīng)網(wǎng)絡(luò)改進(jìn)的粒子群優(yōu)化方法，利用仿生神經(jīng)網(wǎng)絡(luò)優(yōu)化基于該方法的粒子群優(yōu)化算法的適應(yīng)度函數(shù)，并對粒子的速度更新算法進(jìn)行改進(jìn)，同時(shí)利用動態(tài)環(huán)境建模的方法來解決未知環(huán)境下的路徑規(guī)劃問題。此外，文獻(xiàn)[15]提出了一種基于電子海圖下的改進(jìn)粒子群優(yōu)化算法。利用電子海圖建立三維靜態(tài)環(huán)境模型，同時(shí)構(gòu)造期望的路徑航程、危險(xiǎn)度和平滑度函數(shù)。在改進(jìn)的POS 算法中綜合考慮粒子位置與速度的影響，引入了搜索因子和同性因子自適應(yīng)的調(diào)整粒子的慣性權(quán)重，并結(jié)合魚群算法的“跳躍”過程使算法具有較強(qiáng)的平衡“探索”與“利用”能力，以及逃離局部最優(yōu)“陷阱”的能力，有效地克服了粒子群算法在優(yōu)化目標(biāo)函數(shù)時(shí)存在過早收斂和求解能力差的問題。

2）蟻群算法[16]（ACA）是一種模擬自然界中螞蟻群覓食行為的群優(yōu)化算法。當(dāng)螞蟻處于覓食狀態(tài)時(shí)，它會在所遍歷的路徑上分泌信息素，而且該信息素可以被其他螞蟻?zhàn)R別，螞蟻會優(yōu)先選擇信息素濃度較高的路徑，并且其自身會釋放一定量的信息素，從而增強(qiáng)了該條路徑上信息素的濃度，因此形成了一個(gè)正反饋機(jī)制，同時(shí)信息素的濃度也會隨著時(shí)間的推移而減弱。最終，可以通過不斷的迭代獲得一段從出發(fā)點(diǎn)到目的地的最短的路徑。雖然這一正反饋機(jī)制能夠加快收斂速度，但是會有降低蟻群多樣性、減弱全局搜索能力且在復(fù)雜環(huán)境下容易陷入死鎖狀態(tài)的弊端。為此，文獻(xiàn)[17]提出了一種改進(jìn)的蟻群算法，調(diào)整傳統(tǒng)蟻群算法的轉(zhuǎn)移概率，自適應(yīng)地調(diào)整信息素強(qiáng)度Q 值并引入信息素約簡因子，加快算法的迭代速度，最后利用煙花算法中的爆炸算法來擴(kuò)展搜索區(qū)域，避免陷入死鎖狀態(tài)。此外，文獻(xiàn)[18]提出了一種自適應(yīng)路徑規(guī)劃方法，該方法利用自適應(yīng)調(diào)整啟發(fā)式函數(shù)提高了算法的搜索效率，對衰減系數(shù)進(jìn)行動態(tài)調(diào)整，加快了基于蟻群規(guī)則的算法的收斂速度。并更新信息素，限制信息素濃度的最大值和最小值，提高了該算法的搜索能力。

3）神經(jīng)網(wǎng)絡(luò)算法[19]是模擬人腦思維能力，通過大量模擬神經(jīng)元實(shí)現(xiàn)非線性算法功能的網(wǎng)絡(luò)。它與人腦處理信息的過程相似，具有學(xué)習(xí)和自適應(yīng)功能。區(qū)別在于其理論基礎(chǔ)是數(shù)學(xué)網(wǎng)絡(luò)拓?fù)?。人工神?jīng)網(wǎng)絡(luò)的主要特征是能夠并行處理信息的非線性網(wǎng)絡(luò)，具有學(xué)習(xí)功能、容錯(cuò)能力、信息的分布式存儲能力和魯棒性。盡管其具備優(yōu)秀的學(xué)習(xí)能力，但存在泛化能力差的問題。神經(jīng)網(wǎng)絡(luò)算法學(xué)習(xí)能力強(qiáng)，魯棒性較好，因此很多研究者將該算法與其他優(yōu)秀算法結(jié)合起來進(jìn)行路徑規(guī)劃的研究。針對移動機(jī)器人未知空間的路徑規(guī)劃問題，文獻(xiàn)[20]提出了一種基于門控遞歸單元-遞歸神經(jīng)網(wǎng)絡(luò)模型的動態(tài)路徑規(guī)劃方法。利用具有傳感器輸入的深度神經(jīng)網(wǎng)絡(luò)，生成新的控制策略輸出到物理模型中去，以控制機(jī)器人的運(yùn)動，從而避免機(jī)器人發(fā)生碰撞。并提出一種新的信息素更新和狀態(tài)轉(zhuǎn)移規(guī)則來提高算法的收斂速度，同時(shí)引入新的勢場來解決傳統(tǒng)APF 的不足。

4）遺傳算法[21]是一種基于生物進(jìn)化機(jī)制的優(yōu)化算法，具有易于實(shí)現(xiàn)、收斂速度快等優(yōu)點(diǎn)。遺傳算法在簡單地圖上有很好的表現(xiàn)力，但在復(fù)雜、有很多障礙的地圖上表現(xiàn)很差。由于遺傳算法只能在解空間中隨機(jī)搜索，不能充分利用給定的地圖信息。為了克服遺傳算法的早熟現(xiàn)象和上述不足，文獻(xiàn)[21]提出了一種自適應(yīng)遺傳算法，即在進(jìn)化過程中加入自適應(yīng)算子和監(jiān)督算子2個(gè)遺傳算子。自適應(yīng)算子可以根據(jù)障礙物的位置和地圖的復(fù)雜性，進(jìn)行自適應(yīng)的路徑調(diào)整。監(jiān)督算子用來配合自適應(yīng)算子檢測染色體中是否存在重復(fù)或冗余的基因，如果存在，相應(yīng)的基因?qū)⒈粍h除，將有助于加快進(jìn)化過程、縮短路徑長度以及平滑路徑。

4 種常見的智能仿生學(xué)算法在優(yōu)化路徑規(guī)劃時(shí)存在的優(yōu)缺點(diǎn)比較，如表2 所示。

表2 智能仿生學(xué)算法在優(yōu)化路徑規(guī)劃時(shí)存在的優(yōu)缺點(diǎn)比較

2.3 強(qiáng)化學(xué)習(xí)算法

強(qiáng)化學(xué)習(xí)算法[22]是一種完全不需要環(huán)境及自身先驗(yàn)知識的學(xué)習(xí)方法，利用人類思維模式中試錯(cuò)學(xué)習(xí)的方式，在規(guī)劃過程中感知當(dāng)前周圍環(huán)境的同時(shí)，根據(jù)當(dāng)前環(huán)境信息給予的反饋選擇行為來尋找最優(yōu)策略?；谠撗芯糠椒ǎ谥悄苘囈约耙苿訖C(jī)器人的路徑規(guī)劃方面取得了突破性的成果。文獻(xiàn)[23]針對智能車輛傳統(tǒng)路徑規(guī)劃算法中無法消除模型誤差、對跟蹤控制依賴程度高且無法求解控制動作的問題，提出了一種基于深度強(qiáng)化學(xué)習(xí)的模型遷移（DDPG）的智能車輛軌跡規(guī)劃方法。利用DDPG 算法降低了規(guī)劃方法對樣本數(shù)據(jù)的依賴，能夠處理連續(xù)輸入和連續(xù)輸出的模型訓(xùn)練，直接輸出控制動作和軌跡序列。該方法較最優(yōu)控制計(jì)算復(fù)雜度低，并使用模型遷移方法提高模型的泛化性能。但是，該方法并未解決智能車路徑規(guī)劃過程中常存在動態(tài)環(huán)境感知預(yù)估不足的問題。文獻(xiàn)[24]提出了一種使用基于蒙特卡羅預(yù)測及深度策略梯度學(xué)習(xí)（MCPDDPG）的智能車路徑規(guī)劃方法，將多個(gè)單一強(qiáng)化學(xué)習(xí)算法應(yīng)用到規(guī)劃系統(tǒng)的子任務(wù)中。利用提取的環(huán)境信息對周圍車輛的狀態(tài)變化進(jìn)行預(yù)測，設(shè)計(jì)Q 學(xué)習(xí)行為決策方法，便于智能車自行學(xué)習(xí)風(fēng)險(xiǎn)預(yù)估并及時(shí)做出決策規(guī)避，同時(shí)構(gòu)建深度強(qiáng)化學(xué)習(xí)最優(yōu)智能駕駛策略。文獻(xiàn) [25]提出了一種基于組合深度強(qiáng)化學(xué)習(xí)（DRL）的機(jī)器人巡邏路徑規(guī)劃方法，該方法結(jié)合強(qiáng)化學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)進(jìn)行路徑優(yōu)化。先通過異步優(yōu)勢動作評價(jià)（A3C）算法對DRL 進(jìn)行預(yù)訓(xùn)練，利用訓(xùn)練數(shù)據(jù)對隨機(jī)策略參數(shù)化的遞歸神經(jīng)網(wǎng)絡(luò)（RNN）進(jìn)行優(yōu)化，有效解決了單獨(dú)使用演員評論家（AC）方法的不收斂問題，且訓(xùn)練速度較快。再利用有效規(guī)劃（EP）搜索策略對當(dāng)前巡邏路徑進(jìn)行規(guī)劃，并將在A3C 中得到的訓(xùn)練參數(shù)作為EP 的輸入。在每個(gè)解碼步驟中，選擇概率最大的巡邏點(diǎn)。

3 結(jié)論

隨著科技的不斷發(fā)展，路徑規(guī)劃技術(shù)面對的環(huán)境會越來越復(fù)雜，路徑規(guī)劃所用到的算法必須具備迅速響應(yīng)復(fù)雜環(huán)境變化的能力。單獨(dú)使用某一種或某一類算法往往會因其自身的局限性不再能解決路徑規(guī)劃時(shí)遇到的復(fù)雜問題。因此提出3 點(diǎn)建議：

1）在對某類算法深入研究的基礎(chǔ)上，可以結(jié)合不同算法的優(yōu)點(diǎn)，使用2 種或多種混合算法進(jìn)行路徑優(yōu)化，大大提高路徑規(guī)劃的效率和可行性[26-27]，并把環(huán)境建模方法與路徑規(guī)劃算法巧妙結(jié)合起來，發(fā)揮最大的價(jià)值。同時(shí)，還要針對當(dāng)下研究熱點(diǎn)（如多智能體并聯(lián)路徑規(guī)劃、多車輛協(xié)作動態(tài)路徑規(guī)劃），設(shè)計(jì)出集合多種算法優(yōu)點(diǎn)的融合算法以解決更加復(fù)雜的問題。

2）當(dāng)下研究的自動駕駛車輛路徑規(guī)劃多針對單目標(biāo)、平面二維場景，隨著無人出租車及智能交通運(yùn)輸業(yè)等的快速興起，這些單一目標(biāo)簡單場景已經(jīng)不能滿足使用要求。在今后的研究中可針對多目標(biāo)、多維空間場景進(jìn)行避障路徑規(guī)劃以提高作業(yè)效率。利用強(qiáng)化學(xué)習(xí)算法的優(yōu)點(diǎn)，結(jié)合傳統(tǒng)路徑規(guī)劃算法或智能仿生學(xué)算法等來進(jìn)行路徑規(guī)劃以改善規(guī)劃結(jié)果，提高規(guī)劃效率[28]。

3）在今后的車輛路徑規(guī)劃研究中，應(yīng)該多結(jié)合考慮車輛幾何形狀、運(yùn)動學(xué)和約束條件，以此來提高路徑規(guī)劃的精確性?？梢岳脿顟B(tài)格策略進(jìn)行路徑在線搜索，縮短搜索時(shí)間[29]。