基于改進粒子群算法的無人機路徑規(guī)劃*

王翼虎，王思明

(蘭州交通大學(xué)自動化與電氣工程學(xué)院,甘肅 蘭州 730070)

1 引言

近年來，無人機技術(shù)發(fā)展迅猛，路徑規(guī)劃問題是無人機自動控制的關(guān)鍵問題之一。目前路徑規(guī)劃的常用方法有粒子群PSO(Particle Swarm Optimization)算法、A*算法[1]、蟻群算法[2,3]、人工勢場法[4]等。粒子群算法應(yīng)用于無人機路徑規(guī)劃時，易于實現(xiàn)且收斂速度快，但是由于其進行路徑規(guī)劃這類高維復(fù)雜問題的優(yōu)化時極易出現(xiàn)早熟現(xiàn)象，這嚴(yán)重限制了算法的實際應(yīng)用。

針對粒子群算法的問題，國內(nèi)外學(xué)者進行了諸多嘗試。文獻[5,6]采用自適應(yīng)原理調(diào)整參數(shù)，在算法的不同時期采用不同的慣性權(quán)重和學(xué)習(xí)因子，能夠在一定程度上改善粒子群算法的早熟收斂，但是對參數(shù)的選擇需要更多的數(shù)據(jù)實驗，同時參數(shù)對于環(huán)境規(guī)模的適應(yīng)性不足，算法靈活性不高。文獻[7]提出一種自適應(yīng)混沌粒子群優(yōu)化算法并應(yīng)用于三維路徑規(guī)劃，采用自適應(yīng)logistic混沌映射優(yōu)化全局最優(yōu)粒子的方法引導(dǎo)種群跳出局部最優(yōu)，該算法可以有效地使種群快速跳出局部極值點，但是對于算法總體尋優(yōu)效率并沒有提升。文獻[8]提出一種基于粒子群優(yōu)化和極坐標(biāo)機器人路徑規(guī)劃方法，用概率論方法分析了該方法的收斂性，并分析了參數(shù)選擇對收斂性的影響，對于粒子群路徑規(guī)劃參數(shù)選擇具有一定指導(dǎo)意義，但是該方法本身規(guī)劃質(zhì)量和效率并不高。文獻[9]在粒子群算法中引入模擬退火算法，使得種群能夠跳出局部極值點，提高了粒子群算法的全局尋優(yōu)能力，但在局部搜索能力上仍存在局限性。

本文根據(jù)無人機路徑規(guī)劃任務(wù)建立三維高程環(huán)境模型，構(gòu)造基于路徑長度、障礙危險以及高程代價的適應(yīng)度函數(shù)。針對傳統(tǒng)PSO算法的缺陷，本文在傳統(tǒng)粒子群算法中引入BFO(Bacteria Foraging Optimization)算法的趨化算子和遷徙算子進行改進，提出了PSO-BFO混合算法，最后通過Matlab對2種算法進行三維全局路徑規(guī)劃仿真，驗證了改進算法的有效性。

2 無人機路徑規(guī)劃環(huán)境建模

本文研究在已知環(huán)境下的無人機的全局路徑規(guī)劃，建立模擬城市環(huán)境的三維高程數(shù)字地圖模型?？紤]無人機飛行安全裕度后用圓柱體模擬建筑物，用半球體模擬其他樹木等障礙及禁飛區(qū)，其三維高程數(shù)學(xué)模型表示為[10]：

z1(x,y)=hi,r

z(x,y)=max(z1(x,y),z2(x,y))

(1)

3 適應(yīng)度函數(shù)

在采用粒子群算法進行路徑規(guī)劃時，適應(yīng)度函數(shù)用以評價生成路徑的優(yōu)劣程度，也是算法種群迭代進化的依據(jù)，適應(yīng)度函數(shù)的優(yōu)劣決定著算法執(zhí)行的效率與質(zhì)量。為了更好地進行路徑質(zhì)量判斷，本文綜合考慮路徑的長度代價、障礙危險代價以及路徑平滑度幾個方面來構(gòu)造適應(yīng)度函數(shù)。假設(shè)有C條路徑，每條路徑由n個點組成，環(huán)境中共存在g個球形和柱形障礙。

3.1 路徑長度代價

路徑長度是評價路徑優(yōu)劣最重要的指標(biāo)之一，路徑越短，其耗時和耗能都越少。引入路徑長度代價如下：

(2)

其中，Tm代表第m,m∈{1,2,…,M}條路徑中所有相鄰節(jié)點之間的距離總和，(xj,yj,zj)為路徑中第j個節(jié)點的坐標(biāo)。

3.2 障礙危險代價

則第m條路徑的障礙威脅代價為：

(3)

其中，rk為球形障礙或柱形障礙的半徑。

3.3 航跡高程代價

無人機的穩(wěn)定飛行高度也是無人機航跡規(guī)劃過程中的重要環(huán)節(jié)。對于大多數(shù)飛行器來說，飛行高度不應(yīng)該發(fā)生太大的變化。穩(wěn)定飛行高度有助于減輕控制系統(tǒng)的負(fù)擔(dān)，節(jié)省更多的燃料。故引入航跡高程代價：

(4)

高程代價為航跡每個相鄰航跡點高度差之和，其中hj表示路徑節(jié)點j的高度。

綜合Tm、danm和Cm得到路徑適應(yīng)度函數(shù)為：

f=w1·Tm+w2·danm+w3Cm

(5)

其中，w1、w2和w3為[0,1]內(nèi)的權(quán)重系數(shù)，用來靈活配置Tm、danm和Cm之間的關(guān)系。

4 改進粒子群算法

粒子群算法用搜索空間中的點模擬自然鳥群中個體，將其覓食行為的過程類比為可行解變換優(yōu)化的迭代過程。其搜索過程基本不利用外部信息，僅以適應(yīng)度函數(shù)作為進化依據(jù)，每個個體根據(jù)個體極值和全局極值接近最優(yōu)解。本文以粒子群算法為基礎(chǔ)進行迭代尋優(yōu)，并且引入細菌覓食算法對粒子群算法進行改進。

4.1 粒子群算法

假設(shè)存在一個規(guī)模為M的粒子種群，具有N維空間搜索區(qū)域，記為X=[x1,…,xi,…,xM]T，其中第i個粒子的位置表示為xi=[xi1,xi2,…,xiN]T，其速度即粒子在每次迭代中移動的距離表示為vi=[vi1,vi2,…,viN]T,粒子i當(dāng)前經(jīng)過的適應(yīng)度最佳的位置即個體極值表示為Pi=[pi1,pi2,…,piN]T，用Pg=[pg1,pg2,…,pgN]T表示整個種群搜索到的適應(yīng)度最佳的位置即全局極值。優(yōu)化問題的可行解即為優(yōu)化粒子的位置。粒子每次迭代按式(6)更新其位置與速度[11]。

(6)

4.2 細菌覓食算法

細菌覓食算法BFO是群體智能算法的一種，模擬細菌種群覓食行為進行建模，通過迭代來產(chǎn)生最優(yōu)解。在BFO算法中，算法尋優(yōu)由趨化、繁殖和遷移3個操作的三層嵌套循環(huán)構(gòu)成，最內(nèi)層是趨化，中間層是繁殖，最外層是遷移，下面對以上操作分別做簡要介紹[12]。

(1)趨化操作。

細菌趨化算子的操作描述為:細菌首先向隨機方向游走一個步長單位的距離，如式(7)所示；然后計算該位置適應(yīng)度，如果新位置的適應(yīng)度優(yōu)于上一個位置的，則沿翻轉(zhuǎn)方向再前進單位步長，若適應(yīng)度劣于該細菌所在上一個位置的，或者達到最大游動次數(shù)則退出該次趨化操作。

P(i,j+1,k,l)=P(i,j,k,l)+C(i)φ(i)

(7)

其中，P(i,j+1,k,l)為細菌位置，i為細菌的序號，j，k，l分別為趨化、復(fù)制、遷徙操作次數(shù)，C(i)為細菌執(zhí)行一次趨化操作向前游動的單位步長，φ(i)表示細菌隨機翻轉(zhuǎn)中生成的隨機單位方向向量。

(2)繁殖操作。

在細菌完成一定次數(shù)的趨化過程后，進行繁殖操作，定義細菌的繁殖能量為細菌在整個趨化過程內(nèi)的適應(yīng)度之和，高繁殖能量的細菌獲得繁殖機會，低繁殖能量的則被淘汰。

設(shè)淘汰掉的細菌數(shù)量為Sr=S/2,將細菌按照繁殖能量高低排序，然后淘汰低能量的Sr個細菌，剩余細菌進行自我復(fù)制分裂出與自己完全相同的新個體，取代被淘汰的個體，保持細菌種群大小不變。

(3)遷徙操作。

完成種群的繁殖操作后，細菌個體以一個固定概率Ped進行遷移，對任何細菌個體隨機生成一個[0,1]的隨機數(shù)Rand。若Rand

4.3 PSO-BFO混合算法

粒子群算法早期搜索速度較快，但同時也帶來一個問題，粒子搜索過程中PSO算法會因為粒子速度過大而錯過最優(yōu)解[13]，而且由于所有粒子在“跟隨”思想的引導(dǎo)下，都向著一個方向飛行，導(dǎo)致粒子趨向同一化，喪失種群多樣性，導(dǎo)致算法陷入局部最優(yōu)，且算法在后期缺乏跳出局部最優(yōu)的能力。

針對以上問題，本文在粒子群算法中引入BFO的趨化和遷徙算子。BFO算法的趨化過程實質(zhì)就是細菌在解空間中搜索其所在位置的鄰域，由適應(yīng)度函數(shù)決定其搜索方向。趨化過程的引入將增強PSO的局部搜索能力，改善PSO中粒子在搜索過程中由于速度過大而錯過最優(yōu)解區(qū)域的問題。而引入遷徙算子會在粒子群陷入局部最優(yōu)時使得算法有跳出局部最優(yōu)的能力，將有利于算法跳出局部最優(yōu)，但是固定概率的遷移算子會使部分優(yōu)秀解流失，降低尋優(yōu)速度，故將粒子按照適應(yīng)度排序，只賦予低適應(yīng)度的粒子遷移概率Ped。

PSO-BFO算法的具體步驟如下所示：

(1)初始化環(huán)境信息，確定規(guī)劃空間邊界為R=(xmax-xmin,ymax-ymin,zmax-zmin)，提取起始點S(xstart,ystart,zstart)，目標(biāo)點G(xend,yend,zend)。

(2)設(shè)置種群大小pop_size及粒子大小part_size，最大迭代次數(shù)max_gen，粒子最大速度vmax=0.1R，初始化粒子的位置和速度如式(8)和式(9)所示。

(8)

(9)

(3)計算粒子初始適應(yīng)度值f0，將粒子當(dāng)前位置設(shè)為個體極值pbest0，將所有粒子中適應(yīng)度最好的粒子位置設(shè)為全局極值gbest0，設(shè)置慣性權(quán)重wmax，wmin和學(xué)習(xí)因子c1，c2，迭代次數(shù)計數(shù)k=1。

(4)根據(jù)w=wmax-(wmax-wmin)(k/max_gen)線性遞減策略更新慣性權(quán)重，根據(jù)式(6)更新粒子的速度和位置，計算個體適應(yīng)度值fk，如果獲得更優(yōu)的個體極值和全局極值，則更新個體極值pbestk和全局極值gbestk。在全局極值獲得更新時，加入趨化算子進行局部尋優(yōu)，局部尋優(yōu)流程如圖1所示。

σ2計算方法如下所示：

(10)

Figure 1 Flow chart of chemotaxis operator圖1 趨化算子流程圖

(6)判斷是否滿足停止計算條件或達到最大迭代次數(shù)，是則輸出規(guī)劃結(jié)果；否則返回步驟(4)且k=k+1。

5 實驗分析

實驗在三維高程地圖模型下，分別用PSO算法與PSO-BFO混合算法進行無人機路徑規(guī)劃仿真。實驗所用電腦配置為Windows 7 64位系統(tǒng)，8 GB運行內(nèi)存，2.5 GHz頻率CPU，程序在Matlab平臺運行。路徑起終點以及規(guī)劃環(huán)境參數(shù)設(shè)置如表1所示，粒子群算法參數(shù)設(shè)置如表2所示，混合算法中粒子群算法參數(shù)不變，加入細菌覓食算子，游動步長C=0.05|R|，最大趨化次數(shù)Nc=30，遷移概率Ped=0.25。

Table 1 Parameter settings for planning tasks 表1 規(guī)劃任務(wù)參數(shù)設(shè)置

Table 2 Parameter setting of particle swarm algorithm表2 粒子群算法參數(shù)設(shè)置

為驗證混合算法在三維路徑規(guī)劃中的有效性，將PSO-BFO混合算法與基本粒子群算法在相同的環(huán)境模型中進行對比實驗。

圖2～圖4給出基本粒子群算法和本文混合算法的規(guī)劃結(jié)果及其俯視圖和正視圖，圖5給出了2種算法的最優(yōu)適應(yīng)度曲線。從圖2可以看出，傳統(tǒng)PSO算法和混合算法均能在三維環(huán)境中生成一條可行的全局路徑，但是由圖3和圖4可以看出，本文混合算法規(guī)劃結(jié)果的路徑長度和平滑度都要優(yōu)于傳統(tǒng)PSO算法的，且由圖5最優(yōu)適應(yīng)度曲線可以看出，混合算法由于引入趨化算子增強了其局部尋優(yōu)能力，避免其跳過全局最優(yōu)解，加快了收斂速度，適應(yīng)度呈直線下降，適應(yīng)度優(yōu)于傳統(tǒng)粒子群算法，且由于遷徙算子的引入使得算法陷入局部最優(yōu)而停滯時也能夠跳出局部最優(yōu)，恢復(fù)尋優(yōu)能力。

Figure 2 Path planning results of PSO algorithm and hybrid algorithm圖2 粒子群算法和混合算法路徑規(guī)劃結(jié)果

Figure 3 Top view of planning results of PSO algorithm and hybrid algorithm圖3 粒子群算法和混合算法規(guī)劃結(jié)果俯視圖

Figure 4 Front view of planning results of PSO algorithm and hybrid algorithm圖4 粒子群算法和混合算法規(guī)劃結(jié)果正視圖

圖6給出2種算法重復(fù)40次運行的適應(yīng)度值，表3總結(jié)了重復(fù)實驗中2種算法獲得的最優(yōu)適應(yīng)度，以及多次運行的適應(yīng)度平均值及其標(biāo)準(zhǔn)差。從圖6及表3可以看出，傳統(tǒng)PSO算法在進行路徑規(guī)劃時，規(guī)劃路徑適應(yīng)度最優(yōu)值及平均值均較差，且在重復(fù)運行中，規(guī)劃結(jié)果的標(biāo)準(zhǔn)差遠大于改進算法的，規(guī)劃的穩(wěn)定性差，這也使得其很難實際應(yīng)用。而混合算法的多次運行結(jié)果最優(yōu)值、平均值和標(biāo)準(zhǔn)差均大幅優(yōu)于傳統(tǒng)PSO算法的，說明混合算法不但增強了算法尋優(yōu)能力，而且算法的穩(wěn)定性也得到很大的提升。

Figure 5 Optimal fitness curves of PSO algorithm and hybrid algorithm圖5 粒子群算法和混合算法最優(yōu)適應(yīng)度曲線

Figure 6 Simulation results of algorithms running for many times圖6 算法多次運行仿真結(jié)果

表4給出了算法多次運行時的平均迭代總耗時Alltime(迭代次數(shù)達到設(shè)定的最大次數(shù)的時間)、算法收斂時的迭代次數(shù)Iter(最優(yōu)適應(yīng)度連續(xù)100代未更新)以及耗時Time，表中數(shù)值均為平均值。由表4可以看出，從算法總耗時上看，混合算法由于引入了趨化和遷徙算子，增加了一定的計算量，所以總耗時要高于傳統(tǒng)PSO算法的，但是從算

Table 3 Simulation data comparison of PSO algorithm and hybrid algorithm 表3 PSO算法與混合算法仿真數(shù)據(jù)對比

法收斂時間上看，混合算法從開始到收斂的迭代次數(shù)平均值要比傳統(tǒng)PSO算法低112.3，耗時也相應(yīng)更短，這說明混合算法雖然增加了一定計算量，但是加快了算法收斂速度，整體效率優(yōu)于傳統(tǒng)PSO算法。

Table 4 Efficiency comparison of PSO algorithm and hybrid algorithm表4 PSO算法和混合算法效率對比

6 結(jié)束語

在無人機的三維路徑規(guī)劃問題中，傳統(tǒng)PSO算法的尋優(yōu)能力無法滿足需求，本文將BFO算法的趨化算子和遷徙算子引入PSO算法提高了其尋優(yōu)能力。最后分別對PSO算法和改進后的混合算法進行無人機路徑規(guī)劃仿真并對結(jié)果進行對比分析。仿真結(jié)果表明：與傳統(tǒng)PSO算法相比，混合算法在路徑規(guī)劃問題中,尋優(yōu)結(jié)果最優(yōu)值與平均值均大幅優(yōu)于傳統(tǒng)PSO算法的，且多次運行時結(jié)果穩(wěn)定性良好，在無人機的全局路徑規(guī)劃中具有一定的參考性與實用性。