無人駕駛汽車路徑規(guī)劃研究綜述

袁師召 李軍

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

如今人工智能技術得到了不斷發(fā)展和應用，其中無人駕駛作為汽車逐漸智能化的一個方面?zhèn)涫荜P注。無人駕駛技術不僅可以減少由于駕駛員疲勞或操作不當?shù)仍斐傻慕煌ㄊ鹿室约皳矶卢F(xiàn)象的發(fā)生，而且可以提高能源的利用率，是未來汽車重要的技術發(fā)展趨勢之一。路徑規(guī)劃作為無人駕駛汽車運行的關鍵環(huán)節(jié)，具有重大的研究意義。文章從全局和局部路徑規(guī)劃2 個方面綜述當前無人駕駛汽車路徑規(guī)劃中的各種算法，分別從算法的搜索收斂能力、算法的實時性以及算法的復雜程度等方面進行闡述，并分析比較各算法的優(yōu)缺點，為今后的深入研究提供參考。

1 無人駕駛汽車的路徑規(guī)劃

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

1.1 全局路徑規(guī)劃

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

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

1.2 局部路徑規(guī)劃

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

2 結論

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