無人車輛路徑規(guī)劃算法發(fā)展現(xiàn)狀?

王 濤 黎玉康 劉文學(xué)

（陸軍炮兵防空兵學(xué)院 合肥 230000）

1 引言

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

2 全局路徑規(guī)劃算法

全局路徑規(guī)劃是在對環(huán)境整體布局完全已知的條件下的路徑規(guī)劃方法，意在找出滿足某些條件的最優(yōu)解。全局路徑規(guī)劃算法有很多，大致可分為傳統(tǒng)算法、智能算法，隨著路徑規(guī)劃的發(fā)展也逐漸衍生出傳統(tǒng)算法與智能算法相結(jié)合的混合算法。傳統(tǒng)算法較為基礎(chǔ)，但作為其代表的A*算法歷久彌新，是一大研究熱門。智能算法多是人們?yōu)榱私鉀Q自然問題，模擬自然的產(chǎn)物。本文挑選了作為進(jìn)化智能算法代表的的遺傳算法，集群智能算法的蟻群算法，以及綜合了進(jìn)化和集群智能的粒子群算法。

2.1 A*算法

A*算法Dijkstra算法的基礎(chǔ)上加入了啟發(fā)函數(shù)和預(yù)估代價的一種啟發(fā)式算法，廣泛應(yīng)用于靜態(tài)環(huán)境下的最短路徑直接搜索。公式表示為

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

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

2.2 遺傳算法

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

圖1 遺傳算法框圖

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

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

2.3 蟻群算法

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

圖2 蟻群覓食行為簡圖

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

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

2.4 粒子群優(yōu)化法

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

圖3 粒子群算法框圖

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

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

2.5 對比分析

全局路徑規(guī)劃算法還有優(yōu)缺點以及其當(dāng)前的改進(jìn)方式如表1所示。

表1 全局路徑規(guī)劃算法的優(yōu)缺點以及其改進(jìn)方式

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

3 局部路徑規(guī)劃

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

3.1 滾動窗口算法

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

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

3.2 人工勢場算法

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

圖4 人工勢場示意圖

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

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

3.3 基于強化學(xué)習(xí)的路徑規(guī)劃算法

強化學(xué)習(xí)是無人車輛通過傳感器與環(huán)境進(jìn)行信息交互試錯學(xué)習(xí)，對無人車輛應(yīng)對不同環(huán)境的行為作出獎懲評判，從而不斷優(yōu)化行動方案達(dá)到最佳。強化學(xué)習(xí)可較好地應(yīng)對復(fù)雜動態(tài)環(huán)境，但其學(xué)習(xí)能力難以提升，面對復(fù)雜環(huán)境往往計算收斂速度慢，限制了其實時局部路徑規(guī)劃的實際表現(xiàn)。

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

3.4 對比分析

局部路徑規(guī)劃算法的優(yōu)缺點及改進(jìn)方法如表2。

表2 局部路徑規(guī)劃算法的優(yōu)缺點及改進(jìn)方法

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

4 研究發(fā)展趨勢

隨著技術(shù)發(fā)展，人們對路徑規(guī)劃算法提出了更進(jìn)一步的要求，希望有更迅速、更精確、自適應(yīng)性更好的規(guī)劃算法。面對實際情況中，復(fù)雜多變的環(huán)境，尤其是復(fù)雜的動態(tài)環(huán)境，現(xiàn)階段算法的適應(yīng)性較弱。因此，算法的發(fā)展呈現(xiàn)出以下趨勢。

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

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

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

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

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

6）云端數(shù)據(jù)共享，算法自我學(xué)習(xí)進(jìn)化。當(dāng)前大數(shù)據(jù)時代，大量無人駕駛車輛在實際運行中積累了大量的數(shù)據(jù)，建立實時數(shù)據(jù)共享平臺，對算法進(jìn)行在線升級，通過強化學(xué)習(xí)的方式，對算法進(jìn)行長期跟蹤優(yōu)化。

5 結(jié)語

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