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

徐瑞 李軍

摘 ?要：文章針對近年來的無人駕駛汽車路徑規劃算法進行總結和歸納。首先對目前主流的環境建模方法進行闡述;其次對路徑規劃算法進行介紹，通過分析其優缺點，指出融合軌跡規劃算法具有最好的適用性;最后總結當前研究挑戰并提出了相關建議。

關鍵詞：無人駕駛汽車;環境建模;路徑規劃;搜索算法

中圖分類號：U462 ? ? 文獻標識碼：A ? ? 文章編號：1005-2550（2020）05-0084-06

Abstract： Autonomous vehicle path planning latest algorithms have been investigated in this paper. Firstly， the current mainstream environmental modeling methods are described; Afterwards， corresponding path planning algorithms are introduced， by analyzing their advantages and disadvantages to pointed out that the fusion trajectory planning algorithm has the best applicability. Finally， by summarizing the current research challenges and proposes relevant suggestions.

Key Words： Autonomous Vehicle; Environment Modeling; Path Planning; Search Algorithm

引言

無人駕駛汽車將先進的環境感知、路徑決策規劃、車輛控制技術融合到傳統車輛載體中，旨在提高汽車及道路交通的安全性能。路徑規劃技術作為無人駕駛汽車最為核心的技術之一，其技術核心在于：根據特定的道路環境模型，定義車輛的起始點和目標點，提供方位引導。然后，通過定量化的性能指標及規則，設計出一條相對安全而又快捷的有效路徑。

路徑規劃主要包含全局路徑規劃和局部路徑規劃。全局路徑規劃需依賴于全局道路高精度地圖信息，并基于路徑規劃算法求解出車輛從當前位置到目標位置的最優可行路徑;而局部路徑規劃屬于全局路徑規劃的實時補償規劃，其基于多傳感器獲得的外界環境信息及駕駛人的狀態，對當前道路中出現的障礙物和特殊情況進行局部重新規劃，從而提高軌跡的合理性及安全性。

無人駕駛路徑規劃的選擇引導車輛的行駛方向，對車輛行駛安全起到至關重要作用，其技術原理如圖1所示。通過建立包含障礙區域與自由區域的環境地圖;然后，根據當前環境信息及相關成本函數，判斷出最優的路徑搜索算法，從而達到實時精準的對多條可行性路徑進行搜索。

1 ? ?環境建模

當感知系統傳遞周圍環境信息后，局部路徑規劃處理器將信息融合為相應的環境地圖，環境建模的方法有：柵格法、可視圖法、維諾圖法、拓撲法等，文中將詳述環境建模所常用的柵格法、可視圖法的應用現狀。

1.1 ? 柵格法

柵格法作為目前最成熟的軌跡規劃算法，由W.E.Howden于1968年率先提出[1]，其原理是將外界環境圖像信息進行單元分割，并利用等尺寸二值信息的矩形柵格來表征。而柵格的尺寸是影響規劃算法魯棒性的重要指標，柵格越小環境分辨率越高。相對而言，存儲空間占用率會增大，路徑規劃決策效率將會收到干擾;若柵格越大，便會降低在高密度多目標等復雜場景中的路徑識別能力。

文獻[2]針對傳感器測量的不確定性問題，將概率推理思想用于柵格地圖的建立，采用不同的算法驗證發現，原始的貝葉斯推理算法和Dempster融合算法在實時更新柵格地圖和運動目標檢測性能表現更優。文獻[3]提出針對全局環境的完全遍歷柵格法靜態環境建模和針對局部環境的邊走邊測的柵格法動態環境建模，并利用實時更新的信息對模型進行辨識，以提高模型的準確性。文獻[4]首先對柵格地圖進行編號，方便快速獲取障礙物位置，然后建立柵格關聯矩陣對候選柵格進行概率計算，并利用柵格方向向量進行走向引導，有效提高路徑識別能力，提升規劃效率。

1.2 ? 可視圖法

可視圖環境建模法，是將外界環境中的障礙物轉換為凸多邊形物體，將障礙物位置的頂點、本車當前位置、目標點這些節點用直線連接，若兩點連接的線段不與任何障礙物多邊形相交，則稱兩點“可視”，該線段稱為可視線[5]。基于此原理構建路線圖的方法，稱為可視圖法。但是應對于復雜場景時，運算效率不佳。

基于此，文獻[5]基于A*路徑搜索算法來構建可視圖，并建立可視圖節點判斷機制，僅需構建與最優路徑匹配度較高的可視邊，從而提高了算法的運行效率。文獻[6]將路徑規劃中的障礙物進行規則化篩選，排除相關度較低的障礙物，并通過簡化可視圖的邊數，減少候選參考路徑的數量，從而提高算法的運算效率和可靠性。針對于復雜場景中的多目標障礙工況，文獻[7]提出了一種基于小型障礙物進行分組、重新組合的路徑規劃方法，對并行處理的運行環境進行劃分，如圖2所示，大大地縮短算法的計算量，提高運算效率。文獻[8]采用可視圖法生成多邊形規則體，并通過最優控制算法來合并多邊形作為中間目標，從而減少規劃目標受到局部極小值影響。

2 ? ?路徑搜索算法

路徑搜索作為路徑規劃的主要步驟，負責在建立好的環境模型中計算最優的軌跡方案。目前研究較為廣泛局部路徑規劃算法主要包括：人工勢場法、A*算法、快速搜索隨機數法、蟻群算法。

2.1 ? 人工勢場法

人工勢場法是將無人駕駛車輛的運動簡化為在受力場中的運動，如圖3所示，由于受斥力的作用，可規避周圍的障礙物。此外，在引力的激勵下向目的位置移動，從而構成的合力控制的運動方向[9]。該種算法無須對全局進行搜索，且魯棒性較強，被廣泛應用于路徑規劃中。但是，當斥力大于引力時，方向矢量會無法進行判別，導致無法到達目的地;當斥力和引力相等，即合力為零時，無人駕駛車輛無法繼續前進，即陷入局部最小點。

為解決斥力與引力之間的沖突問題，文獻[10]引入調節因子來計算無人駕駛汽車與目標位置的相對距離，并建立的斥力勢場函數來緩解引力和斥力沖突。此外，針對于車輛被困在局部最小值問題，提出了APF-FC融合算法，有效地解決了傳統人工勢場法的相關缺陷。文獻[11]通過建立障礙物和車輛約束的目標函數，并采用高斯組合隸屬函數調節系數修正路徑曲率，從而避免汽車陷入局部最小點。文獻[12]將人工勢場法和最優控制結合，提出一種模型預測路徑規劃控制器，利用車輛動力學規劃最優路徑的同時，對不同的障礙物和道路結構進行分布處理。文獻[13]采用人工勢場法對障礙物和道路邊界建立勢場函數，對可行區域進行網格劃分并分配電阻值，然后根據起點和終點之間各節點的局部最大電流方向，選擇無碰撞路徑。

2.2 ? A*算法

A*算法作為一種啟發式的搜索算法，主要通過建立節點估價函數來決定搜索方向，估價函數f（i）表達式[14]為：

f（i）=g（i）+h（i） ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（1）

g（i）表示從起始節點到i節點的實際代價，主要決定搜索范圍，搜索節點增多，效率越低。h（i）表示從i節點到目標節點的估計代價，當估價代價與實際代價相近時，節點數將會減少，搜索效率便會提高。

A*算法的估價函數決定open list中各節點的次序，將會自動選擇代價最小的節點作為下一個擴展節點，用open list記錄所有的被考慮的最小代價節點。但是，考慮到在搜索路徑時訪問節點的更新頻率較快，當遇到較復雜場景時，會加大計算量，嚴重消耗內存，影響搜索效率。針對此問題，文獻[15]基于A*算法提出了一種跳點搜索方法，從而減少在環境地圖中的擴展節點，提高搜索效率。文獻[16]通過優化分割A*算法規劃的路徑中的步長，將當前位置的各節點相連接，并剔除沒有交集的冗余點，從而縮短了路徑長度，減小了轉折角度。文獻[17]以電動車能耗為平臺，建立車輛總能耗的實際代價函數和估計代價函數，并綜合考慮電動車剩余電量和充電樁位置，尋找可達目的地能耗最小的路徑。文獻[18]通過計算碰撞前的計算估價函數值來優化A*算法，根據起點和目標點間的直線斜率進行算法切換，縮減了目標位置的距離和算法的運算時間。文獻[19]提出了矩形展開算法（REA*），以無障礙矩形為單位探索地圖，將矩形的邊界用作搜索節點，剔除矩形內不必要的點，相應訪問的節點比A*少，優化了運算效率。

2.3 ? 快速搜索隨機樹算法

快速搜索隨機樹（Rapidly exploring Random Tree，RRT）算法，是基于增量采樣的樹結構算法，以起始點為隨機樹的根節點，向四周環境搜索隨機節點，當葉子節點包含了目標點或進入了目標區域，便求解出一條由從起始點到目標點的最優路徑[20]。此算法省略了環境建模，搜索范圍全、速度快;但在搜索時，均勻分配的隨機采樣點利用率低，且搜索缺乏導向性，規劃路徑的耗費時間長且不規則。

文獻[21]針對人機交互時連續曲率的路徑問題，提出一種基于RRT*算法的代價函數來調整路徑曲率的方法，去除路徑冗余點，從而獲得連續路徑，并實時更新路徑以防環境突變，避免了重復計算。文獻[22]提出了基于駕駛員視覺行為的快速搜索隨機樹算法（DV-RRT），根據駕駛員視覺的近點和遠點，在高斯分布引導采樣過程中考慮節點間距離、轉角的度量函數及b樣條的連續曲率平滑度，通過實車試驗，如圖4所示，驗證了實時性、穩定性和舒適性的要求。文獻[23]通過高斯分布函數建立隨機采樣區域，使其分散在期望路徑周圍，并采用啟發式搜索來增加調節因子，對采樣點施加導向，使其向目標點靠近，從而改善了算法的泛化性。文獻[24]提出一種基于神經網絡的最優的RRT算法（NoD-RRT）來解決具有非線性動力約束的路徑規劃問題，并根據隨機搜索樹重構方法，實現了狀態空間的近似最優解。

2.4 ? 蟻群算法

蟻群算法（Ant Colony Algorithm，ACA）是根據螞蟻群體的覓食行為的一種正反饋智能優化算法[25]，將規劃問題的可行路徑用螞蟻的行走路徑表示，螞蟻通過感知環境的信息素濃度，會以較大的概率優先選擇信息素濃度較高的路徑，并釋放一定量的信息素，整個螞蟻群會在正反饋的作用下集中到最佳的路徑上，此時對應的便是路徑規劃問題的最優解。蟻群算法在搜索過程采用并行計算方式，但算法的計算能力較差限制了它在求解最短路徑問題上的應用。

基于此，文獻[26]提出螞蟻回退策略來避免算法陷入局部最優點，通過改進啟發式搜索信息和釋放的信息素，來判斷兩者優先級和節點信息，根據臨時規避或重新尋路策略來解決沖突和避碰問題。文獻[27]通過設計搜索的區域信息素初始值，引入自適應調節因子，對優質螞蟻和劣質螞蟻所經路徑的信息素進行判別，同時增加避障因子，改進轉移概率，避免盲目搜索，提高算法的全局性和搜索效率。文獻[28]通過非均勻分配初始信息素，引入帶有方向的選擇策略，減少搜索的盲目性，并采用信息素覆蓋和更新規則，對蒸發系數進行分割和調整，有效地提高算法的收斂速度和搜索能力。文獻[29]通過改進的激勵函數和信息素更新策略，調節螞蟻對目標節點的感知時分泌的信息素濃度，有效引導螞蟻移動，減少搜索時間。

2.5 ? 多種算法融合

面對復雜的交通狀況和無人駕駛汽車多源異構的需求，通過對比各算法的特點，單一的軌跡規劃算法難以滿足目前的安全和速率需求。因此，各算法之間的融合能有效提高規劃能力和運算速率。

文獻[30]將模糊決策樹算法與人工勢場法進行融合，首先通過引入環境矩陣改進勢場法，并利用勢場法提供的權值，然后應用模糊決策樹算法來尋求局部最優值。文獻[31]提出了一種基于A*算法和勢場法相結合的路徑規劃方法，利用模糊邏輯控制器對地形進行特征描述，根據A*算法確定的全局路徑，并使用勢場法作為局部規劃器進行反饋修正，從而保證在動態粗糙地形下的魯棒性和靈活性。文獻[32]將模糊圖像處理算法、細菌算法、遺傳算法和A*算法四種算法進行融合，首先利用模糊圖像處理算法對圖像邊緣進行檢測;然后根據細菌算法規則對隸屬函數和模糊規則進行優化，最后通過改進的遺傳算法和A*算法生成最優路徑，該方法具有良好的邊緣檢測，安全性高。

2.6 ? 算法對比分析

本文采用加權分析法對各種路徑規劃算法的性能指標（規劃效率、簡便性、泛化能力、路徑效果、搜索能力）進行分析：

其中，E表示算法的綜合評價;Le表示算法規劃效率等級;Lc表示算法簡便性等級;Lg表示算法泛化性等級;Lr表示算法路徑效果等級;Ls表示算法搜索能力等級;λ表示各個指標的權重值，均為20%。

如表1所示，依據綜合分析評價結果，融合算法綜合評分為90分，搜索能力強，規劃路徑效果好，在針對于復雜場景，擁有較好的算法泛化能力，并有利于提高軌跡規劃的魯棒性。

3 ? ?結論

本文重點分析了目前主流的路徑規劃算法，并具體分析了不同算法之間優劣性，得出結論：融合算法雖較為繁瑣，但憑借其良好的魯棒性及泛化能力，已經成為目前路徑規劃中的最重要的研究方法。此外，目前的研究仍然面臨著嚴峻的挑戰，主要包括易陷入局部最小值、路徑的連續曲率問題、收斂速度慢、未考慮系統的振動和噪聲影響，及復雜環境中的導航問題等等。

為實現安全、魯棒的自主車輛路徑規劃，提出以下幾點建議：在未來的研究中，應考慮車輛的動力學和可能影響規劃的系統性或非系統性錯誤;注意系統振動和噪聲對可靠性和執行方法產生影響;此外，環境感知的設備，如雷達，傳感器和攝像頭的局限性也需要加以考慮;最后，為了使無人駕駛車輛能夠快速決策，應先考慮各算法的優點和局限性，采用各種算法融合方法，也需考慮算法的計算復雜度，減少執行時間。

參考文獻：

[1]Wang C Y， Banitaan S. A Partitioning-Based Approach for Robot Path Planning Problems[C]//2018 18th International Conference on Control， Automation and Systems （ICCAS）. IEEE， 2018： 178-182.

[2]周俊靜，段建民. 基于柵格地圖的智能車輛運動目標檢測[J]. 系統工程與電子技術，2015，37（02）： 436-442.

[3]劉曉磊，蔣林，金祖飛，郭晨. 非結構化環境中基于柵格法環境建模的移動機器人路徑規劃[J]. 機床與液壓，2016，44（17）： 1-7.

[4]程向紅，祁藝. 基于柵格法的室內指示路徑規劃算法[J]. 中國慣性技術學報，2018，26（02）： 236-240.

[5]呂太之，趙春霞，夏平平. 基于同步可視圖構造和A*算法的全局路徑規劃[J].南京理工大學學報： 自然科學版，2017，41（3）： 313-321.

[6]張琦，馬家辰，馬立勇. 基于簡化可視圖的環境建模方法[J]. 東北大學學報 （自然科學版），2013， 34（10）： 1383-1386.

[7]Toan T Q， Sorokin A A， Trang V T H. Using modification of visibility-graph in solving the problem of finding shortest path for robot[C]//2017 International Siberian Conference on Control and Communications （SIBCON）. IEEE， 2017： 1-6.

[8]Ma Y， Zheng G， Perruquetti W. Cooperative path planning for mobile robots based on visibility graph[C]// Control Conference. IEEE， 2013： 4915-4920.

[9]安林芳，陳濤，成艾國等. 基于人工勢場算法的智能車輛路徑規劃仿真[J]. 汽車工程，2017， 39（12）： 1451-1456.

[10]Gu X， Han M， Zhang W， et al. Intelligent Vehicle Path Planning Based on Improved Artificial Potential Field Algorithm[C] //2019 International Conference on High Performance Big Data and Intelligent Systems （HPBD&IS）. IEEE， 2019： 104-109.

[11]修彩靖，陳慧. 基于改進人工勢場法的無人駕駛車輛局部路徑規劃的研究[J]. 汽車工程，2013 （9）： 808-811.

[12]Rasekhipour Y， Khajepour A， Chen S K， et al. A potential field-based model predictive path-planning controller for autonomous road vehicles [J]. IEEE Transactions on Intelligent Transportation Systems， 2016， 18（5）： 1255-1267.

[13]Huang Y， Ding H， Zhang Y， et al. A Motion Planning and Tracking Framework for Autonomous Vehicles Based on Artificial Potential Field-Elaborated Resistance Network （APFE-RN） Approach [J]. IEEE Transactions on Industrial Electronics， 2019.

[14]譚雁英，李洋，周軍等. 復雜環境下基于A*算法的無人機路徑再規劃[J]. 系統工程與電子技術， 2017，39（6）： 1268-1273.

[15]趙曉，王錚，黃程侃，等. 基于改進A*算法的移動機器人路徑規劃[J].機器人，2018，40（06）： 903-910.

[16]孫煒，呂云峰，唐宏偉等. 基于一種改進A*算法的移動機器人路徑規劃[J]. 湖南大學學報： 自然科學版，2017，44（4）： 94-101.

[17]顧青，豆風鉛，馬飛. 基于改進 A* 算法的電動車能耗最優路徑規劃[J]. 農業機械學報，2015， 46（12）： 316-322.

[18]Guruji A K， Agarwal H， Parsediya D K. Time-efficient A* algorithm for robot path planning [J]. Procedia Technology， 2016， 23： 144-149.

[19]Zhang A， Li C， Bi W. Rectangle expansion A? pathfinding for grid maps[J]. Chinese Journal of Aeronautics， 2016， 29（5）： 1385-1396.

[20]杜明博，梅濤，陳佳佳，趙盼，梁華為，黃如林，陶翔. 復雜環境下基于RRT的智能車輛運動規劃算法[J]. 機器人，2015，37（04）：443-450.

[21]Lan X， Di Cairano S. Continuous curvature path planning for semi-autonomous vehicle maneuvers using RRT[C]//2015 European Control Conference （ECC）. IEEE， 2015： 2360-2365.

[22]Du M， Mei T， Liang H， et al. Drivers visual behavior-guided RRT motion planner for autonomous on-road driving[J]. Sensors， 2016， 16（1）： 102.

[23]宋曉琳，周南，黃正瑜，曹昊天. 改進RRT在汽車避障局部路徑規劃中的應用[J]. 湖南大學學報（自然科學版），2017，44（04）：30-37.

[24]Li Y， Cui R， Li Z， et al. Neural network approximation based near-optimal motion planning with kinodynamic constraints using RRT[J]. IEEE Transactions on Industrial Electronics， 2018， 65（11）： 8718-8729.

[25]許凱波，魯海燕，黃洋等.基于雙層蟻群算法和動態環境的機器人路徑規劃方法[J]. 電子學報， 2019，47（10）： 2166-2176.

[26]郭保青，郝樹運，朱力強等. 基于改進蟻群算法的多AGV泊車路徑規劃[J]. 交通運輸系統工程與信息，2018，18（06）：55-62.

[27]江明，王飛，葛愿等.基于改進蟻群算法的移動機器人路徑規劃研究[J].儀器儀表學報，2019（2）： 13.

[28]Zhao J， Cheng D， Hao C. An improved ant colony algorithm for solving the path planning problem of the omnidirectional mobile vehicle [J]. Mathematical Problems in Engineering， 2016： 452.

[29]Wang Y， Lu X， Zuo Z. Autonomous vehicles path planning with enhanced ant colony optimization[C]//2019 Chinese Control Conference （CCC）. IEEE， 2019： 6633-6638.

[30]Iswanto I， Wahyunggoro O， Cahyadi A I. Path planning based on fuzzy decision trees and potential field [J]. International Journal of Electrical and Computer Engineering， 2016， 6（1）： 212.

[31]Raja R， Dutta A. Path planning in dynamic environment for a rover using A? and potential field method[C]//2017 18th International Conference on Advanced Robotics （ICAR）. IEEE， 2017： 578-582.

[32]Al-Jarrah R， Al-Jarrah M， Roth H. A novel edge detection algorithm for mobile robot path planning [J]. Journal of Robotics， 2018.