徐瑞 李軍

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

關鍵詞：無人駕駛汽車;環(huán)境建模;路徑規(guī)劃;搜索算法

中圖分類號：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

引言

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

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

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

1 ? ?環(huán)境建模

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

1.1 ? 柵格法

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

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

1.2 ? 可視圖法

可視圖環(huán)境建模法，是將外界環(huán)境中的障礙物轉(zhuǎn)換為凸多邊形物體，將障礙物位置的頂點、本車當前位置、目標點這些節(jié)點用直線連接，若兩點連接的線段不與任何障礙物多邊形相交，則稱兩點“可視”，該線段稱為可視線[5]?；诖嗽順嫿肪€圖的方法，稱為可視圖法。但是應對于復雜場景時，運算效率不佳。

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

2 ? ?路徑搜索算法

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

2.1 ? 人工勢場法

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

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

2.2 ? A*算法

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

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

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

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

2.3 ? 快速搜索隨機樹算法

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

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

2.4 ? 蟻群算法

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

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

2.5 ? 多種算法融合

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

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

2.6 ? 算法對比分析

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

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

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

3 ? ?結論

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

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

參考文獻：

[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]. 系統(tǒng)工程與電子技術，2015，37（02）： 436-442.

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

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

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

[6]張琦，馬家辰，馬立勇. 基于簡化可視圖的環(huán)境建模方法[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]安林芳，陳濤，成艾國等. 基于人工勢場算法的智能車輛路徑規(guī)劃仿真[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]修彩靖，陳慧. 基于改進人工勢場法的無人駕駛車輛局部路徑規(guī)劃的研究[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]譚雁英，李洋，周軍等. 復雜環(huán)境下基于A*算法的無人機路徑再規(guī)劃[J]. 系統(tǒng)工程與電子技術， 2017，39（6）： 1268-1273.

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

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

[17]顧青，豆風鉛，馬飛. 基于改進 A* 算法的電動車能耗最優(yōu)路徑規(guī)劃[J]. 農(nóng)業(yè)機械學報，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]杜明博，梅濤，陳佳佳，趙盼，梁華為，黃如林，陶翔. 復雜環(huán)境下基于RRT的智能車輛運動規(guī)劃算法[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在汽車避障局部路徑規(guī)劃中的應用[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]許凱波，魯海燕，黃洋等.基于雙層蟻群算法和動態(tài)環(huán)境的機器人路徑規(guī)劃方法[J]. 電子學報， 2019，47（10）： 2166-2176.

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

[27]江明，王飛，葛愿等.基于改進蟻群算法的移動機器人路徑規(guī)劃研究[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.