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

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

1 引言

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

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

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

2.1 A*算法

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

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

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

2.2 遺傳算法

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

圖1 遺傳算法框圖

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

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

2.3 蟻群算法

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

圖2 蟻群覓食行為簡(jiǎn)圖

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

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

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

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

圖3 粒子群算法框圖

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

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

2.5 對(duì)比分析

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

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

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

3 局部路徑規(guī)劃

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

3.1 滾動(dòng)窗口算法

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

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

3.2 人工勢(shì)場(chǎng)算法

人工勢(shì)場(chǎng)算法是指人為建立一個(gè)虛擬力場(chǎng)，如圖4所示。

圖4 人工勢(shì)場(chǎng)示意圖

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

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

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

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

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

3.4 對(duì)比分析

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

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

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

4 研究發(fā)展趨勢(shì)

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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