自動駕駛汽車路徑規劃技術*

張栩源 李軍

（重慶交通大學機電與車輛工程學院；重慶市軌道交通車輛系統集成與控制重慶市重點實驗室）

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

1 路徑規劃分類

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

全局路徑規劃問題實質上是在已掌握的所有環境信息的前提下，規劃出從起點到目標點的路徑生成問題。通常是基于數字地圖，根據周圍環境的路網模型來選擇路徑。當因環境或者其他因素導致規劃的路徑無法繼續通行時，則需要重新啟動全局規劃，以得到更新后的可行路徑。局部路徑規劃需要車載傳感器實時采集車輛周圍的環境信息，充分了解周圍環境地圖信息以準確定位出車輛當前位置及周圍障礙物分布，從而順利規劃出從當前節點到下一子目標節點的最優路徑。在無人駕駛系統中，局部路徑規劃在跟蹤全局路徑的同時能夠順利完成避障，大大提高規劃系統在動態未知環境下的路徑規劃能力。局部路徑規劃在路徑規劃的過程中非常重要，它通常以規劃的曲線作為未來車輛可能的行駛路線。對該曲線進行安全分析，從而確定期望的曲率與速度。如果所規劃的曲線與期望的行駛軌跡不一致，則說明曲線的安全性分析失效，該無人車很有可能出現安全隱患，甚至會陷入某一狹小區域而無法通行[6]。

2 路徑規劃常用算法

2.1 傳統算法

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

1）A*算法[7]是一種典型的啟發式搜索算法，它也是靜態路網中求解最短路徑最有效的直接搜索算法。A*算法通過一個估價函數來引導和決定搜索方向，從起點開始向周圍進行擴展搜索，利用估價函數來獲取周圍每個節點的價值，并從獲取的周圍節點中選擇代價最小的節點作為下一個擴展節點，不斷循環重復這一過程直到到達目標點，結束搜索，從而生成最終路徑。由于每次選擇的擴展節點的代價都是最低的，所以最終生成的路徑代價也是最低的。

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

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

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

4 種常見的傳統路徑規劃算法在優化路徑規劃時存在的優缺點比較，如表1 所示。

表1 傳統算法在優化路徑規劃時存在的優缺點比較

2.2 智能仿生學算法

智能仿生算法主要有粒子群算法、蟻群算法、神經網絡算法、遺傳算法、灰狼優化算法、煙花算法、人工魚群算法等。

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

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

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

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

4 種常見的智能仿生學算法在優化路徑規劃時存在的優缺點比較，如表2 所示。

表2 智能仿生學算法在優化路徑規劃時存在的優缺點比較

2.3 強化學習算法

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

3 結論

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

1）在對某類算法深入研究的基礎上，可以結合不同算法的優點，使用2 種或多種混合算法進行路徑優化，大大提高路徑規劃的效率和可行性[26-27]，并把環境建模方法與路徑規劃算法巧妙結合起來，發揮最大的價值。同時，還要針對當下研究熱點（如多智能體并聯路徑規劃、多車輛協作動態路徑規劃），設計出集合多種算法優點的融合算法以解決更加復雜的問題。

2）當下研究的自動駕駛車輛路徑規劃多針對單目標、平面二維場景，隨著無人出租車及智能交通運輸業等的快速興起，這些單一目標簡單場景已經不能滿足使用要求。在今后的研究中可針對多目標、多維空間場景進行避障路徑規劃以提高作業效率。利用強化學習算法的優點，結合傳統路徑規劃算法或智能仿生學算法等來進行路徑規劃以改善規劃結果，提高規劃效率[28]。

3）在今后的車輛路徑規劃研究中，應該多結合考慮車輛幾何形狀、運動學和約束條件，以此來提高路徑規劃的精確性。可以利用狀態格策略進行路徑在線搜索，縮短搜索時間[29]。