無人駕駛汽車路徑規劃研究綜述

袁師召 李軍

（重慶交通大學機電與車輛工程學院）

如今人工智能技術得到了不斷發展和應用，其中無人駕駛作為汽車逐漸智能化的一個方面備受關注。無人駕駛技術不僅可以減少由于駕駛員疲勞或操作不當等造成的交通事故以及擁堵現象的發生，而且可以提高能源的利用率，是未來汽車重要的技術發展趨勢之一。路徑規劃作為無人駕駛汽車運行的關鍵環節，具有重大的研究意義。文章從全局和局部路徑規劃2 個方面綜述當前無人駕駛汽車路徑規劃中的各種算法，分別從算法的搜索收斂能力、算法的實時性以及算法的復雜程度等方面進行闡述，并分析比較各算法的優缺點，為今后的深入研究提供參考。

1 無人駕駛汽車的路徑規劃

作為無人駕駛汽車順利運行的重要環節，路徑規劃是指無人駕駛汽車在具有障礙物的環境中，能夠規劃出一條從起始位置狀態到目標位置狀態無碰撞的最優路徑或次優路徑，并滿足所有約束條件，是實現汽車智能化的關鍵技術之一。根據路徑規劃的目標范圍，可以將其分為全局路徑規劃和局部路徑規劃2 種[1]。全局路徑規劃主要是對局部路徑規劃起到導向和約束作用，使車輛沿著導航系統提供的一系列期望局部目標點行駛。全局路徑規劃不算復雜，前提是有拓撲級地圖，而局部路徑規劃是在車輛沿期望路徑行駛時，通過車載傳感器感知周圍環境及交通信息，從而實現車道保持、動態避障等功能，又可以稱作避障規劃。局部規劃要求算法具有較高的實時性，以應對實時變化的環境信息，這對傳感器、算法的效率和處理器的運算能力都是極大的挑戰，避障規劃不僅考慮空間還考慮時間序列。目前，對于已知環境的路徑規劃，已存在很多成熟算法，可實現車輛無碰撞地到達目標地點，但在未知環境下，如何根據無人駕駛汽車的傳感器實時探測到的局部環境信息進行路徑規劃，仍處于試驗研究階段。

1.1 全局路徑規劃

全局路徑規劃是在已知的環境信息下，在事先已建好的環境模型中，去獲得一條從初始地到目標地中符合一定性能的可行或最優的路徑，其優點是保證了規劃路徑的最優性和可達性[2]。

全局路徑規劃在搜尋最優路徑的算法上，根據搜索算法可分為圖搜索類算法、隨機采樣類算法、智能算法等。圖搜索類算法[3]主要包括Dijkstra 算法[4]、A*算法[5-6]、D*算法等。與Dijkstra 算法相比，A*算法增加了啟發式估計，并減少了搜索量，提高了效率，同時保證了路徑的最優性，但在環境復雜、規模較大時，效率仍較低。文獻[7]采用仿真和試驗相結合的方法，對AGV 路徑規劃的A*算法和D*Lite 算法進行了比較研究，比較的重點是生成軌跡的計算時間和生成軌跡的距離。結果表明，D*Lite 能夠以比A*更快的計算速度規劃出更短的路徑。然而，在某些情況下，D*Lite 不如A*有效。這就表明選擇哪種算法合適應該根據系統的需求。針對A*算法的不足，文獻[8]將跳點搜索算法與原有的A*算法相結合，提出在生成最終路徑的過程中，通過篩選跳點進行擴展，并且在擴展過程中，將A*算法中可能被添加到OpenList 和ClosedList 中的大量不必要的節點用跳點來替代以改進A*算法，減少了計算量。文獻 [9]提出了一種優化路徑的方法，即拓展Moore 型元胞鄰居結構，使得路徑較原D*算法進一步優化。對于D*算法的改進，主要發生在路徑長度和運算時間上。就D*算法的路徑長度問題，提出了拓展Moore 型元胞結構，將原D*算法的路徑進一步縮短；與此同時，采用跳點搜索算法對原D*算法的運算速度進行一定幅度的提高。跳點搜索算法可以大量地節約內存，有效地提高運算效率，具有更快的速度、更高的空間復雜度。隨機采樣類算法主要包括概率路標算法、快速隨機樹算法，在復雜環境中得到了大量應用，如存在動態障礙物、高維狀態空間和存在運動學、動力學等約束條件下的環境中，但這類算法存在耗費代價較大、實時性較差、可能規劃得到非最優路徑的問題[10]。智能仿生算法是一種模擬生物進化和仿生自然界動物昆蟲覓食筑巢等行為的智能化算法，主要有遺傳算法[11-12]、蟻群算法[13]、粒子群算法[14-15]等。遺傳算法、蟻群算法適用于復雜問題的求解和優化，具有潛在的并行性的特點，但存在運算速度慢、解早熟的現象；與遺傳算法和蟻群算法相比較而言，粒子群算法的優點主要在于收斂速度快。文獻[16]提出了一種改進蟻群算法，應用在移動機器人路徑規劃中，對復雜環境下的機器人建立柵格模型，將指向上一節點的數組引入傳統轉移規則中，使算法逃逸能力得到了增強；在信息素更新中去掉最差螞蟻釋放的信息量，以利于種群的進化，使得在復雜環境中的路徑搜索能力優于傳統算法。文獻[17]提出的優化的蟻群算法改進了信息素的更新方式和狀態轉移概率、設置了信息素濃度的閥值，并引入了死鎖處理策略，避免求解過程中的早熟現象，增加解的多樣性，從而使螞蟻搜索最優路徑的范圍縮小，能夠降低搜索過程中的迭代次數以加快運算速度、提高搜索效率，從而使全局最優路徑可以高效、快速地獲得。文獻[18]提出的基于滾動窗口優化的智能汽車軌跡規劃方法，能夠同時滿足行駛安全和全局最優的要求，把路徑曲線描述為6 次多項式，并將路徑規劃問題轉化為求解a6k的過程。該方法引入滾動窗口優化策略，用以解決智能汽車在多約束條件下、未知環境中生成全局最優軌跡的問題。

1.2 局部路徑規劃

局部路徑規劃是指無人駕駛汽車根據自身傳感器獲取到的周圍環境信息，能夠在未知或部分未知的周圍環境中，自主規劃出一條無碰撞的最優路徑。用于局部路徑規劃的傳統算法有人工勢場法[19]、模擬退火法[20]、模糊邏輯法[21-22]、神經網絡法[23]、動態窗口法、強化學習法[24]及基于行為的路徑規劃方法。人工勢場法的優點是結構簡單、計算量較小，但存在容易產生局部最小值的問題。文獻[25]建立了改進的無人駕駛汽車人工勢場模型，該改進模型通過利用高斯組合隸屬函數在建立引力的目標點函數中，將障礙物約束和車輛約束考慮進去，并引入調節因子，解決了傳統人工勢場法容易陷入局部極小、目標不可達的問題。文獻[26]把傳統斥力勢場中的實際距離利用橢圓化距離代替，并在傳統人工勢場法中引入道路邊界斥力場模型，綜合考慮了車道引力勢能場、障礙物斥力勢能場和道路邊界勢能場三者對汽車的影響，從而能夠在較小車道空間內獲得合適的汽車避撞局部路徑。文獻[27]結合車輛的實際運行情況，通過一種用正弦避障換道的方式，以最小安全距離作為對稱距離的障礙點模型構建方法，使局部目標點處于對稱軸線上，解決目標不可達和局部最小值的局部路徑規劃問題。智能水滴算法模擬水流與泥沙相互作用而形成水道的機制，是一種新型的群落智能算法，在計算科學領域中，當求解的問題比較復雜時，可以應用該算法進行求解。但是對于路徑規劃問題，智能水滴算法在求解時，存在啟發性不足的缺陷，會導致所規劃的路徑不理想。文獻[28]針對原智能水滴算法的以上缺陷，通過變量更換、改進概率選擇策略和更新機制，使得該改進算法的求解能力較原算法明顯提高。模糊邏輯法是根據模糊的環境信息，依照對應表格規劃出的信息，實現局部路徑規劃，優點在于容易計算，能夠實時跟蹤規劃。文獻[29]提出一種基于模糊控制的移動機器人避障方法，但模糊規則根據經驗設定，存在經驗不完備等問題，因此該算法靈活性差、存在未知短板。可見，無論哪一種算法均存在各自的不足，因此，為了解決和彌補單一算法存在的問題和不足，可采用2 種算法相結合的方法。文獻[30]在研究移動機器人路徑規劃問題中，采用了雙層路徑規劃思想，將改進遺傳算法和改進人工勢場法相結合，首先采用改進的遺傳算法進行全局路徑規劃，解決最優個體丟失的問題；然后利用改進的人工勢場法，對已規劃好的全局路徑進行局部動態避障，解決了局部極小點問題。文獻[31]在蟻群算法搜索過程中加入人工勢場局部搜索尋優算法，用局部擴散信息素代替人工勢場法中的力因素，使蟻群在搜索過程中更傾向于朝著具有高適應值的子空間搜索，提高了蟻群的預避障能力。文獻[32]將修正APF 算法與模糊邏輯算法相結合，既解決了人工勢場法規劃中存在的局部極小值問題，又提高了算法在復雜環境中的有效性，并使用粒子群優化算法對模糊邏輯算法的隸屬度函數進行了優化，使得在靜態和動態的環境中能夠快速作出響應并規劃出合適的路徑。

2 結論

文章從無人駕駛汽車全局路徑規劃和局部路徑規劃兩方面對目前文獻中常見的規劃算法進行了概括和分析。對傳統經典算法，如人工勢場法及其改進算法和智能算法，做出了分析，初步得出不管是哪一種算法都有其自身局限性和缺點，如人工勢場法盡管具有算法簡單、實時性好、規劃的路徑軌跡圓滑的優點，但是存在容易進入局部最小點、目標不可達的問題和不足；遺傳算法、蟻群算法的不足在于存在容易陷入局部最優的問題；神經網絡算法的不足則是需要大量樣本。面對復雜多變的路徑規劃問題，采用單一的規劃方法往往已不能取得很好的效果，因此趨向于將多種研究方法相結合，如將局部路徑規劃與全局路徑規劃相結合，如將在局部環境已知條件下可實現的局部路徑規劃通過滾動窗口優化原理進行前后銜接，可實現全局路徑規劃；傳統規劃方法與新的智能方法相結合。如將蟻群算法與強化學習算法相結合，全局或局部路徑規劃與動態環境路徑規劃相結合等，可得到更加完美的、用于無人駕駛汽車的路徑規劃算法，這些是今后研究的重點與難點。