無人車輛路徑規劃算法發展現狀?

王 濤 黎玉康 劉文學

（陸軍炮兵防空兵學院 合肥 230000）

1 引言

無人駕駛車輛通過傳感器感知周遭環境，并對自身定位，建立起基本的外部環境模型，按照既定的任務目標，控制自身的前向速度和轉向角，達到避開障礙，抵達目標點位的目的。無人駕駛車輛的運行經過以下幾個關鍵步驟：信息感知、決策、控制實施。其中，決策將前后兩個關鍵性的步驟連接起來，為無人駕駛提供了基本條件，而路徑規劃正是決策過程中的重要一環。路徑規劃是指無人駕駛車輛在一定的復雜環境中，根據環境信息規劃出能夠從初始點位到達目標點位的曲線，該曲線應滿足車輛的運動學特性以及其他附加約束。為了更好地（經過路徑最短、消耗功率最小、最安全、最方便實現等）抵達目標點位，發展出了各類不同的路徑規劃算法。根據獲得的環境信息程度，可將路徑規劃算法分為兩類：全局路徑規劃和局部路徑規劃。

2 全局路徑規劃算法

全局路徑規劃是在對環境整體布局完全已知的條件下的路徑規劃方法，意在找出滿足某些條件的最優解。全局路徑規劃算法有很多，大致可分為傳統算法、智能算法，隨著路徑規劃的發展也逐漸衍生出傳統算法與智能算法相結合的混合算法。傳統算法較為基礎，但作為其代表的A*算法歷久彌新，是一大研究熱門。智能算法多是人們為了解決自然問題，模擬自然的產物。本文挑選了作為進化智能算法代表的的遺傳算法，集群智能算法的蟻群算法，以及綜合了進化和集群智能的粒子群算法。

2.1 A*算法

A*算法Dijkstra算法的基礎上加入了啟發函數和預估代價的一種啟發式算法，廣泛應用于靜態環境下的最短路徑直接搜索。公式表示為

其中f（n）是從初始點經由節點n到目標點的估價函數，g（n）是在狀態空間中從初始節點到n節點的實際代價，h（n）是從n到目標節點最佳路徑的估計代價。保證找到最短路徑（最優解的）條件，關鍵在于估價函數f（n）的選?。汗纼r值h（n）＜=n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。并且如果h（n）=d（n），即距離估計h（n）等于最短距離，那么搜索將嚴格沿著最短路徑進行，此時的搜索效率是最高的。如果估價值＞實際值，搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解［1］。

陳鑫鵬［2］等提出了等步長分層拓展的方法，減少車輛后退以及轉彎，采用Dijkstra算法得出的n點到終點的距離作為啟發式，增加了倒退懲罰的代價機制，減少了冗余節點的參與計算，提高了算法效率，路線經過優化擬合，大幅提升了行駛的平穩性以及可行性。劉子豪［3］等結合跳躍點搜索理論，優化子節點的選擇，減少了計算量，在二次計算中消去了轉角區域的不必要節點，縮短了路徑長度，減小了路徑轉彎處的曲率，提高了無人車輛通過的平穩性。李世國［4］等采用了雙向A*算法，從起始點和目標節點同時相向開始搜索直至重合，大大提高了計算效率，并在障礙物周圍設置緩沖區，引入風險系數，越靠近障礙物，系數越高，最高為1，引入預估距離，實際距離，風險系數的權重參數，根據實際情況調整權重，提高了算法的適應性。唐碧君［5］等為了解決傳統A*算法使得無人車輛容易出現不必要的轉向和與障礙物產生碰撞的問題，提出了改進混合A*算法，分三個階段優化路徑，先計算出有可行性的通暢路徑，再構建吸引力與排斥力的航路點環境，最后結合車輛轉彎半徑，對路徑曲線的曲率進行約束，得出更平滑，安全的路徑曲線。閔海濤［6］等根據非結構化環境的特點，提出了全球導航層與局部規劃層相結合的環境描述方法，并提出了基于非結構化環境中自動駕駛車輛A*算法的改進型局部運動規劃算法。在改進的算法中，通過設置安全空間避免了輪廓碰撞，在啟發式功能設計中考慮了路徑曲率的成本。與原始算法相比，它可以提高路徑的平滑性，從而使路徑更符合車輛運動特點。

2.2 遺傳算法

遺傳算法的基本思想脫胎于達爾文的進化論和孟德爾的遺傳論，其流程框圖如圖1所示。

圖1 遺傳算法框圖

假設一個初始解集，將每個解視為染色體不同的個體，將其置于一系列的約束條件之中，按照物競天擇，適者生存的原則，篩選出表現較為良好的個體，將其復制，交叉，變異產生新一代的個體集，通過一代代進化篩選，最終得到最適應約束條件的個體也就是最優解。但是此類算法在環境偏復雜時，結果收斂速度較慢，無法確定精確最優解，算法的參數難以定量等不足。但是它依然具有寬廣的前景和很大的潛力，吸引了眾多學者展開研究。

黃書召［7］等提出了混合無重串選擇算子，使得假設的初始解集有了一定的擴增，增加了適應性好的解的數量，令收斂解更接近于最優解，但同時也使得收斂速度變慢，為了解決這個問題，他們同時提出了非對稱映射交叉算子和啟發多次變異算子。徐夢穎［8］等通過提高傳統遺傳算法免疫克隆性，將解的質量與被復制數相對應，指出了最優解的收斂方向，提高了收斂速度，并加入自適應參數從而避免陷入局部最優解。李昌華［7］等在遺傳算法中采用元胞自動機鄰域模型，利用元胞的隱性遷移機制，使得在進化演變過程中，多樣化的解得以留存，收斂解更加接近最優解，在路徑選擇中增加了平滑因素的影響，使最終路徑更適應車輛行駛特性，提高了路徑質量。Tobias Rainer Schafle［10］等考慮到路徑最短但實際能量消耗不一定最少的情況，在傳統遺傳算法中提出了能量評估適應度函數，對無人車輛按照既定路徑加減速，轉彎掉頭等形式的動作消耗的能量作出估算，給出更符合經濟實際的最優路徑。陳宣剛［11］等令遺傳過程中的交叉概率和變異概率隨著進化個體的變化而變化，加大了優勝劣汰的競爭強度，有效地保存了優勢個體，這種自適應遺傳算法實現了更快的解算速度。

2.3 蟻群算法

蟻群算法于1992年被首次提出，其創始人意大利學者Dorigo等在螞蟻覓食行為中得到靈感，如圖2所示。

圖2 蟻群覓食行為簡圖

螞蟻在覓食的路徑上會留下信息素，當找到食物，螞蟻原路返回，該路徑上的信息素濃度將明顯高于其他沒有找到食物的路徑，后來的螞蟻選擇路徑的概率隨著信息素濃度的增高而增加，且信息素有揮發性，使得有食物的路徑上信息素濃度與沒有食物路徑上的信息素濃度差距越來越大，而有食物的路徑中，路程越短的路徑單位時間內通過的螞蟻越多，信息素濃度越高，導致最終螞蟻的路徑趨向于最近的食物路徑。蟻群算法在全局優化方面效果良好，且魯棒性強，但同時也有計算量大的缺陷，且由于信息素的累計容易導致局部最優解。

王蘇彧［12］等將傳統的定常數信息素揮發因子跟改為隨時間變化的服從Laplace分布的信息素揮發因子，削弱了前期以及后期揮發因子的作用，提升了算法速度，增強了中期揮發因子的作用，加強了算法路徑的多樣性，保證了結果的最優性。在啟發函數中加入加權系數，避免陷入局部最優解。仿真驗證此改進蟻群算法明顯優于傳統算法。徐玉瓊［13］等提出變步長蟻群算法，將傳統蟻群算法中的單步長擴展為除了有障礙存在以外的的全局環境選擇跳點，提高了路徑搜索效率，信息素初始濃度從四周向始末點連線附近逐步增加，減少了無效路徑選擇，通過設置信息素濃度上下限的方式避免了局部最優解，優化了啟發函數，提高了算法的收斂速度，該算法收斂速度較之傳統算法大幅提高，且在復雜環境下也能有較好的表現。桑和成［14］等提出了轉角啟發因子，令路徑選擇的有效性大大提高，減少了轉角過大而產生繞路的情況，引入估價函數思想，對下一節點與目標節點的距離進行評估，縮小了路徑搜索范圍，提高算法效率。王苗苗［15］等先通過A*算法對路徑進行初步搜索，按照得出的初步結果給出信息素的分布，解決了蟻群算法初期盲目發展的問題，加快了整體的收斂速度，建立了信息素的影響系數和揮發系數的自適應模型，使得該系數隨著算法的進行不斷自我調整，推動算法進行且避免了局部最優。周東升［16］等在空間避障規劃中給定蟻群算法的路徑選擇以X軸為主要方向，規定了螞蟻最大的橫向和縱向移動距離，減化了螞蟻搜索下一個節點的搜索空間，對于下一節點的選擇除了信息素影響的確定概率外，加入了增加算法多樣性的隨機概率，信息素的衰減系數以及更新系數通過螞蟻搜索完成路徑的長度進行實時更新。根據仿真結果顯示，該算法運行時間更短，避障效果更好。但是該算法依然無法解決更復雜的環境或者動態非結構化環境下的避障問題。

2.4 粒子群優化法

粒子群優化法起源于人們對鳥類覓食行為的探索，其流程框圖如圖3所示。

圖3 粒子群算法框圖

每只鳥看作一個有速度和位置信息的粒子，每個粒子找到食物后將自己的路徑信息與同類共享，通過與同類比較，選取更近的路徑，多次比較迭代后，得到最優解。粒子群優化算法具有收斂速度快，魯棒性強，精度高等優點，但也容易造成收斂過早，局部最優解的問題。

李學軍［17］提出了反向學習粒子群的方法應用于機器人的多目標路徑選擇，通過調整目標函數與偏差常函數的權重系數來實現最短路徑的同時避免與障礙碰撞，該算法模型簡單，計算速度較快，能夠滿足機器人實時替換目標點并選擇路徑的需求，具有一定的實用價值。付興武［18］等將粒子群優化算法與天牛須算法結合，將每個粒子加入天牛會對環境進行自我判斷的能力，避免了粒子群算法易于陷入局部最優解的問題，規劃效率更高，路徑更優。楊紅果［19］等將傳統粒子群算法與遺傳算法相結合，對每個有完整路徑的粒子的路徑進行編碼，該編碼視為粒子基因，將路徑最短的粒子個體的基因與其他個體交叉，將每個粒子按照一定的概率進行混沌優化，有效克服了傳統粒子群算法易于陷入局部最優以及迭代次數多的缺點。劉曉歡［20］等將慣性權重與迭代次數相關聯，并引入遞減因子，使得慣性權重對最終解的影響逐漸減小，進而產生算法初始解算范圍較大，后期避免局部極值的效果，學習因子的更新公式，使得粒子群在保證良好的路徑規劃能力的同時有著較快的收斂速度。但該算法較為復雜，實際運用中響應較慢。P.K.Das［21］等對粒子群算法中的粒子參考遺傳算法和蜂群算法的進化方式，強化粒子個體的搜索能力，同時計算每個機器人的路徑坐標，在向最優化靠近的同時保證路徑的多樣性。

2.5 對比分析

全局路徑規劃算法還有優缺點以及其當前的改進方式如表1所示。

表1 全局路徑規劃算法的優缺點以及其改進方式

全局路徑規劃普遍顯示出求解效率較低，易于陷入局部最優的問題，但算法的求解能力與收斂速度是一對相互排斥的性質，因此全局規劃的優化改進方法主要集中于在保證算法求解能力的同時提高求解效率，和增大求解過程中解的多樣性以保證最終解的優良性。

3 局部路徑規劃

局部路徑規劃屬于動態規劃，是指無人車輛通過傳感器，實時感知環境信息，對局部環境建模，完成從當前節點到下一子節點路徑的局部最優化。局部路徑規劃令無人車輛能夠有效地應對動態復雜環境，與全局路徑規劃相互配合，大大提升了在實際中的應用效果。局部路徑規劃算法根據其特點可分為采樣方法、條件約束法、機器學習法，挑選出滾動窗口算法、人工勢場算法、強化學習算法分別進行概括。

3.1 滾動窗口算法

滾動窗口算法是指根據傳感器感知環境，通過滾動的方式對路徑作出在線規劃，每滾動一步（按照上一步的規劃路徑），探測到新的環境信息，進而對上一步的規劃作出反饋并用啟發式方法優化下一步子目標的選擇，并做出新的局部路徑規劃。如此循環達到對局部動態環境的實時路徑規劃效果。該算法計算量較小，對環境較為敏感，可有效避開障礙物，具有實時性。

金何［1］等運用滾動窗口法探查局部環境信息，識別障礙，選擇局部子目標，通過不斷接近子目標最終達到終點的目的，但是該方法難以應對更復雜的環境以及運動速度較快的動態障礙，具有較大的局限性，并且由于該方法使用昆蟲算法規劃接近子目標的路徑，使得路徑較長。孫斌［23］等建立了未知環境下，對障礙物存在的判斷方法和動態障礙的預測及處理方式，設計了局部子目標的啟發式函數。通過實驗證明了其在未知動態環境下的良好適應性。陳明建［24］等結合了牛耕遍歷方式與窗口滾動達到對未知環境信息的探測，簡化了模型，提高了探測效率，借助A*算法實現局部子目標的路徑以及跳出死胡同的逃逸路線。在清潔機器人上搭配360°激光傳感器使用，具有算法簡單，效率高，易于實現的優點。

3.2 人工勢場算法

人工勢場算法是指人為建立一個虛擬力場，如圖4所示。

圖4 人工勢場示意圖

車輛在環境中同時受到障礙物的斥力和目標點的吸引力，車輛受到的力的大小與其同障礙物或目標點的距離負相關，即距離越短，受力越大。無人車輛在合力的作用下，前往下一個目標點。然而人工勢場算法還存在許多問題，例如在障礙物附近的目標點，其產生的合力幾乎為零使得無人車難以到達，陷入局部最優；在經過狹窄路徑時易產生左右震蕩的問題等。因此人工勢場算法不宜用于高自由度下的車輛路徑規劃問題。但是人工勢場算法的簡單結構，快速響應，規劃路徑平滑等特點依然吸引了眾多研究學者的探索。

陳麒杰［25］等提出了改進的人工勢場，在斥力函數中加入了斥力影響因子，該影響因子和目標點與障礙物之間的距離相關，避免了目標點位在障礙附近而無法達到的問題，添加了無人機之間的斥力關系，避免無人機相撞，引入了無人機群前置形心作為微弱引力源，在障礙物與目標點位產生的合力為零時，引導無人機群走出該局部最小值區。何乃峰［26］等在斥力場函數中引入位姿閾值增益，使得當無人車目標點位于障礙附近，不可到達時，改變斥力場的線性影響，使得目標點位處的勢能最低，利用退火算法原理，當無人車陷入局部最小值時，重構障礙斥力函數，以一定的概率達到全局最優解。李軍［27］等將傳統斥力場更改為橢圓形使得路徑更平滑，建立道路邊界斥力場使得車輛不會偏離道路，對移動的障礙添加速度斥力場使得環境更符合實際情況。劉夢佳［28］等建立了改進的勢場，該勢場分為三個層次：位置勢場、速度勢場和加速度勢場。在改進位置勢場的基礎上，構造了由相對速度和相對加速度組成的有源濾波器。改進的吸引場函數包括無人艇與目標產生的相對位置、相對速度和相對加速度的勢場，解決了傳統算法在動態障礙中容易產生局部最小值和震蕩的問題。BARUKC? I［29］等結合了人工勢場算法和昆蟲算法的優點，當無人機遇到較大障礙斥力而無法到達目標點時，采用備用的昆蟲算法，令無人機沿著障礙物的邊沿運動，解決了陷入局部最小值的問題，當傳感器短暫失效時，擴大障礙物斥力場影響范圍，隨著無人機與障礙物的距離改變障礙物的斥力場函數，保證了無人機的安全，且減少了無人機因傳感器實效而導致的懸停，增加了無人機的航程。但該方法只適用于簡單、少、靜態障礙物的環境，面對復雜、動態障礙物效果不佳。

3.3 基于強化學習的路徑規劃算法

強化學習是無人車輛通過傳感器與環境進行信息交互試錯學習，對無人車輛應對不同環境的行為作出獎懲評判，從而不斷優化行動方案達到最佳。強化學習可較好地應對復雜動態環境，但其學習能力難以提升，面對復雜環境往往計算收斂速度慢，限制了其實時局部路徑規劃的實際表現。

周彬［30］等提出了根據無人機探索目標源發出信號強弱獲得相應的反饋，并結合玻爾茲曼概率選擇無人機動作以達到路徑選擇的作用，利用“導向強化”原則，加快了算法收斂速度。但該方法躲避動態障礙能力較弱，只適用于單個無人機簡單空曠環境下的路徑規劃。李輝［31］等提出了一種基于DQN的改進算法。該算法以值函數近似法代替Q-learning中的動作值函數，解決了Q-learning在狀態空間較大時產生的維數災難問題；通過構建預測網絡和目標網絡的雙層網絡結構避免模型在訓練時的誤差震蕩和發散，保證了算法的穩定性；引入經驗回放機制減少近似值函數的估計偏差，加快了收斂速度。熊俊濤［32］等引入了人工勢場的思想，建立了目標吸引的獎勵函數以及障礙排斥的懲罰函數，引導機器人在避開障礙的情況下，盡快達到目標點；提出了一種方向懲罰避函數及機器人碰撞分析模型，提高了無人車正確行為的激勵效果，提高了收斂效率。李俊濤［33］等在DQN算法中加入了先驗經驗，令路徑搜索初始階段有了一定的參考；建立了優先級規則，避免了多個無人機對同一區域的過度探索，加快了收斂速度。雷曉云［34］等基于DQN算法建立了一套獎懲機制，制定了在無障礙環境中設置隨機起始點及目標點的智能系統訓練方法，使得訓練經驗足夠多樣化、全面化，加強了該算法復雜環境中的局部路徑規劃適應能力，加快了算法收斂速度。

3.4 對比分析

局部路徑規劃算法的優缺點及改進方法如表2。

表2 局部路徑規劃算法的優缺點及改進方法

局部路徑規劃的對算法的反應速度要求較高，以至于算法的求解能力較弱或增強求解能力的途徑較為困難。但是局部路徑規劃算法可看做一次次基于當前環境的全局路徑規劃，將全局路徑規劃算法同局部路徑規劃算法相結合，克服求解能力弱的缺點。

4 研究發展趨勢

隨著技術發展，人們對路徑規劃算法提出了更進一步的要求，希望有更迅速、更精確、自適應性更好的規劃算法。面對實際情況中，復雜多變的環境，尤其是復雜的動態環境，現階段算法的適應性較弱。因此，算法的發展呈現出以下趨勢。

1）算法強化。各種算法都不可避免地有著一定的缺陷，諸如收斂速度慢，局部最優解等。研究學者們通過優化算法規則，提高算法收斂速度，提高路徑規劃最優解的精確度。簡化算法模型，加快算法反應速度，提高算法實時性。例如遺傳算法中加大優良遺傳個體的復制概率，蟻群算法中非均勻初始信息素濃度分布以及隨時間變化的信息素濃度揮發系數等。

2）算法融合。由于各個算法各有其獨特優點，研究學者們更傾向于結合多種算法的優點，從而克服單個算法的固有缺陷，兩者互補，全面提高算法效能。如粒子群算法與遺傳算法結合，A*算法與蟻群算法結合等在試驗驗證中都有著遠超單獨某種算法的表現。但是算法融合導致算法建模復雜，執行響應慢，實時性低。在實際算法融合中應該考慮到一定的無人車輛行駛速度下，算法執行時間的長短對無人車輛精確位姿控制的影響。

3）自適應動態規劃。人們逐漸不滿足于已知環境下固定軌道的無人車輛的路徑規劃，而希望無人車面對未知環境自主選擇路徑，對動態障礙有自主避障響應的智能化算法。面對更為復雜多變，變量多，隨機性高的外界環境，需要具有自我學習能力，事件啟發性的強自適應性動態路徑規劃算法的支撐。

4）多樣化環境下的避障策略。算法往往依托于環境，傳統環境模型中，障礙主要分為固定障礙與動態障礙。但是無論是應用于城市交通普通無人車輛，還是野外探測的特種無人車輛，面對的障礙類型繁多。如城市交通中交通指揮，交通規則下的虛擬障礙，野外探測中面對前方草叢、淺坑、水坑、陡坡等可通過型障礙，非線性速度，難以預測軌跡的不確定性動態障礙等。因此，如何強化傳感器識別，完善的環境模型，建立多樣化的避障策略將成為新的方向。

5）規劃參考代價多樣化。傳統路徑規劃算法一般以路程為參考代價，力求達到最短路徑。但在實際過程中，最短路徑有時并非最優路徑。引入多樣化的參考代價，例如文獻［10］中以能量消耗為參考代價，取最小耗能為優。還可以根據耗時最短，相對最安全，最適于行駛等來進行路徑規劃。根據不同任務背景選取合適的參考代價規劃路徑對于無人駕駛有著重要的意義。

6）云端數據共享，算法自我學習進化。當前大數據時代，大量無人駕駛車輛在實際運行中積累了大量的數據，建立實時數據共享平臺，對算法進行在線升級，通過強化學習的方式，對算法進行長期跟蹤優化。

5 結語

該文章從全局路徑規劃，局部路徑規劃兩個方面對遺傳算法、蟻群算法、A*算法、粒子群算法、滾動窗口算法、人工勢場算法、強化學習算法進行了基本原理以及當前研究現狀的介紹，對無人車輛路徑規劃算法的發展趨勢做了一定的總結，對無人駕駛車輛技術的發展方向有一定的借鑒參考作用。