基于改進PSO的無人機三維航跡規(guī)劃優(yōu)化算法

巫 茜，羅金彪，顧曉群，曾 青

(1.重慶理工大學(xué) 計算機科學(xué)與工程學(xué)院， 重慶 400054；2.重慶高新區(qū)飛馬創(chuàng)新研究院， 重慶 400039)

1 引言

由于無人機(unmanned aerial vehicle,UAV)具有使用便捷、成本低廉、外形靈活、體積小巧且易于操控以及適應(yīng)性強等諸多優(yōu)勢，在邊境巡邏、偵查監(jiān)視、遙感測繪、農(nóng)林作業(yè)、電力巡檢等眾多軍民領(lǐng)域得到了廣泛應(yīng)用[1-3]。無人機航跡規(guī)劃，是指為順利完成飛行任務(wù)，在綜合權(quán)衡地形地貌、各類威脅、能源油耗等諸多因素下，給無人機規(guī)劃出一條令人滿意的空間飛行航跡。

目前有多種航跡規(guī)劃算法，如蟻群算法、遺傳算法、粒子群算法(particle swarm optimization,PSO)等[4],它們各有優(yōu)勢和不足。其中，PSO因搜索速度快、實現(xiàn)簡單而獲得廣泛應(yīng)用，但在后期運算極易陷入局部最優(yōu)解并且收斂速度慢。文獻[5]提出了一種階梯式慣性權(quán)重與跳出局部最優(yōu)解相結(jié)合的PSO策略，可較好地統(tǒng)籌局部搜索和全局搜索之間的關(guān)系，并使之跳出局部極值，以加快算法的收斂速度，但對最大迭代次數(shù)的依賴性高；文獻[6]借鑒優(yōu)勝劣汰的自然選擇機制，可以獲得無人機航跡規(guī)劃的近優(yōu)解，但由于其降低了PSO種群的多樣性，不利于尋找全局最優(yōu)解；文獻[7]通過差分進化、模擬退火和混沌優(yōu)化3種算法改進PSO，豐富了種群的多樣性，從而提高了航跡品質(zhì)，但該方法復(fù)雜度較高，耗時較長。

本文首先建立了包含地形、障礙物和雷達在內(nèi)的三維環(huán)境模型，然后構(gòu)造了基于航跡長度、障礙物碰撞、雷達威脅和高度變化的適應(yīng)度函數(shù)，最后針對傳統(tǒng)PSO算法和上述改進方案的不足，引入柯西變異算子，提出了自適應(yīng)柯西變異粒子群算法(adaptive cauchy mutation PSO,ACMPSO)，并通過仿真驗證了該算法的有效性。

2 無人機三維航跡規(guī)劃模型

2.1 環(huán)境建模

為研究無人機航跡規(guī)劃問題，首先需要建立三維數(shù)字地圖，該地圖通常包括基準(zhǔn)地形、障礙區(qū)域以及威脅區(qū)域的信息。

基準(zhǔn)地形采用山峰函數(shù)[8]進行模擬，如式(1)所示：

(1)

式中：Z(x,y)為坐標(biāo)點(x,y)處的高度值，N為山峰的數(shù)量，hi為任務(wù)空間中第i座山的高度，xoi、yoi為其中心點坐標(biāo)，xsi、ysi分別為其在x、y軸方向的坡度向量。為便于分析，對無人機設(shè)置一個安全高度hsafe，當(dāng)無人機飛行高度小于該處地形的高度h與安全高度hsafe之和時，將該節(jié)點的高度設(shè)為h+hsafe。

障礙區(qū)域通過圓柱體模擬[9]，如式(2)所示：

(2)

式中：Li(x,y,z)表示第i個圓柱體，(xi,yi)、zi、Ri分別為其中心坐標(biāo)、高度和半徑。

電磁干擾區(qū)域、禁飛區(qū)域和敵方探測等區(qū)域通常被視為威脅區(qū)域，可采用半球模型進行建模[9]，本文選用雷達探測區(qū)域作為威脅區(qū)域，如式(3)所示：

(3)

式中：Wi(x,y,z)表示第i個雷達的探測區(qū)域，(xi,yi,zi)為雷達所在位置，Ri為雷達探測半徑。

2.2 適應(yīng)度函數(shù)建模

適應(yīng)度函數(shù)可以計算出航跡的代價，用于比較不同航跡的代價值以判斷航跡品質(zhì)的好壞。本文綜合權(quán)衡了航跡長度、雷達威脅、障礙物碰撞和高度變化4項因素對適應(yīng)度函數(shù)建模：

F=φ1fL+φ2fR+φ3fC+φ4fH

(4)

式中：F表示航跡代價，fL表示航跡長度成本，fR表示雷達威脅成本，fC表示障礙物碰撞成本，fH表示高度變化成本，φ1、φ2、φ3、φ4為常數(shù)，代表不同成本的權(quán)重值，其比例與無人機執(zhí)行的任務(wù)有關(guān)。

2.2.1航跡長度成本

航跡長度是評價航跡質(zhì)量的重要指標(biāo)之一，考慮到無人機的能源供應(yīng)是有限的，航跡越短，耗時耗能越少，對無人機越有利。假設(shè)航跡節(jié)點數(shù)量為n，經(jīng)插值法平滑后整個航跡由N個節(jié)點組成，(xi,yi,zi)和(xi+1,yi+1,zi+1)分別表示第i個節(jié)點與相鄰下一節(jié)點的三維坐標(biāo)，則航跡長度成本可表示為

(5)

2.2.2雷達威脅成本

若無人機進入雷達探測范圍，則可能會被敵方發(fā)現(xiàn)，甚至遭受攻擊。因此，無人機需要和雷達保持一定距離，二者相隔的空間越長，被檢測到的幾率就越小。雷達威脅成本可表示為[10]

(6)

式中：R表示雷達數(shù)量，N表示航跡平滑后的節(jié)點總數(shù)量，δ表示雷達強度，Rt表示威脅半徑，Dk,l表示航跡節(jié)點(xl,yl,zl)與雷達中心(xk,yk,zk)之間的距離，如式(7)所示：

(7)

2.2.3障礙物碰撞成本

當(dāng)無人機飛行高度低于障礙物高度且距離障礙物中心點的距離小于障礙物的半徑時，將發(fā)生碰撞。為使航跡節(jié)點和障礙物保持一定距離，需求出障礙物碰撞成本：

(8)

(9)

其中，T表示障礙物的個數(shù)，N表示航跡平滑后的節(jié)點總數(shù)量，Ci, j表示第i個障礙物和第j個航跡節(jié)點間的距離，Robsi表示障礙物i的半徑。

2.2.4高度變化成本

為防止與山體或其他障礙物發(fā)生碰撞，同時躲避雷達搜索，無人機必須升高或降低高度，但是反復(fù)升降也可能危及無人機的安全。因此，有必要對高度變化進行約束，航跡高度的方差可以描述飛行高度的穩(wěn)定性，將其作為高度變化成本：

(10)

式中：N表示航跡節(jié)點總數(shù)量，zk是第k個航跡節(jié)點處的高度值。

3 粒子群算法及其改進

3.1 基本粒子群算法

在本文中，每一個粒子都代表一條航跡。考慮三維空間的航跡規(guī)劃，并假設(shè)航跡節(jié)點數(shù)量為n，對第k個粒子而言，式(11)和式(12)分別表示其位置矢量和速度矢量。

Pk=[(Px,Py,Pz)(k,1),…,(Px,Py,Pz)(k,n)]T

(11)

Vk=[(Vx,Vy,Vz)(k,1),…,(Vx,Vy,Vz)(k,n)]T

(12)

如果粒子群中有S個粒子，那么一定存在S個粒子的個體最優(yōu)位置，而對整個粒子群而言，也一定存在一個如式(13)的全局最優(yōu)位置，其中k∈1，…，S。

(13)

將粒子的位置代入適應(yīng)度函數(shù)F中，可以評價粒子的航跡質(zhì)量，航跡質(zhì)量越高，則對應(yīng)粒子的適應(yīng)度函數(shù)值F越小。對粒子k而言，如果第t次迭代后的F值比前t-1次的值小，則將其更新，否則仍然采用其歷史最佳位置，如式(14)所示。最后，在S個粒子的歷史最佳位置中挑選出F值最小的那個就是全局最優(yōu)位置，如式(15)所示：

(14)

(15)

在下一輪迭代時，每個粒子的速度和位置根據(jù)式(16)更新如下：

(16)

式中：慣性權(quán)重w用于繼承粒子的速度，c1、c2是學(xué)習(xí)因子，分別代表對自身歷史最佳狀態(tài)的學(xué)習(xí)能力和對群體中最優(yōu)個體的學(xué)習(xí)能力，r1、r2都是0～1之間的任意隨機數(shù)。

3.2 粒子群算法的改進方案

3.2.1自適應(yīng)慣性權(quán)重

慣性權(quán)重w直接影響粒子的搜索能力。其值越大，粒子對原始速度的繼承越好，從而獲得較大速度，因此全局搜索能力也更強[13]。借助動態(tài)地改變慣性權(quán)重w的值，可以在不同時段方便地調(diào)整粒子的全局搜索能力和局部搜索能力。本文采用指數(shù)形式的慣性權(quán)重調(diào)整方法以提高收斂速度：

(17)

式中：wmax為w的最大值，wmin為w的最小值，t、Tmax分別為當(dāng)前迭代次數(shù)和最大迭代次數(shù)，α是常系數(shù)，用于控制慣性權(quán)重衰減速率。

3.2.2柯西變異

傳統(tǒng)PSO算法的種群多樣性欠佳，在其算法中引入交叉、變異等進化算子，可有效提高種群的多樣性，從而避免產(chǎn)生局部最優(yōu)解。常用的變異算子有高斯變異算子(Gaussian Mutation,GM)和柯西變異算子(Cauchy Mutation,CM)，由于柯西分布的隨機數(shù)范圍更大、峰值更低，在PSO算法中引入柯西變異算子更有利于粒子快速跳出局部極值和增加種群多樣性[14]。

如果x滿足式(18)給出的條件，則它將成為柯西分布。

(18)

式中：x0是函數(shù)的最大值所在位置，γ是與x0一半有關(guān)的寬度。當(dāng)γ和x0分別為1和0，x滿足概率密度函數(shù)的條件時，式(19)為其累積分布函數(shù)：

(19)

對式(19)進行逆變換，可以求出逆函數(shù)，再通過均勻分布產(chǎn)生的隨機數(shù)，就可生成服從柯西分布的隨機數(shù)：

(20)

式中：CM為柯西變異算子，Rand為均勻分布在(0,1)范圍內(nèi)的任意實數(shù)。

與慣性權(quán)重類似，柯西變異的步長也需要動態(tài)調(diào)整，以便在算法運行的前期以較大步長產(chǎn)生一定擾動，使粒子跳出當(dāng)前位置，避免局部最優(yōu)；后期以較小步長加速收斂。每次迭代中每個粒子的更新規(guī)則為

(21)

3.3 無人機航跡規(guī)劃算法的實現(xiàn)步驟

綜上所述，基于ACMPSO的UAV三維航跡規(guī)劃算法的實現(xiàn)步驟如下：

步驟1：根據(jù)式(1)～式(3)創(chuàng)建三維環(huán)境，并設(shè)置無人機的起點和終點；

步驟2：對粒子位置和各項參數(shù)進行初始化，包括航跡節(jié)點數(shù)量n、粒子總數(shù)S、航跡節(jié)點總數(shù)量N、最大迭代次數(shù)Tmax、最大速度Vmax、慣性權(quán)重最大值wmax和最小值wmin、學(xué)習(xí)因子c1和c2等；

步驟3：通過三次樣條數(shù)據(jù)插值法，對只含有n個航跡節(jié)點的航跡進行平滑，得到一條包含N個航跡節(jié)點的航跡，用于式(4)～式(10)計算粒子的適應(yīng)度值；

步驟5：使用式(20)更新柯西變異算子CM，通過式(21)得到下一次迭代時粒子的位置；

步驟6：使用式(17)更新慣性權(quán)重w；

步驟7：通過式(16)更新粒子速度Vk和位置Pk，其中Vk和Pk若越界，取邊界值即可；

4 仿真實驗及其結(jié)果分析

4.1 仿真環(huán)境與實驗數(shù)據(jù)準(zhǔn)備

為驗證本文提出算法的有效性，參考文獻[15]的對比方法，將ACMPSO算法與傳統(tǒng)粒子群算法BPSO和線性慣性權(quán)重粒子群算法[16]LPSO在相同條件下進行離線航跡規(guī)劃仿真。仿真軟件是Matlab R2014a，仿真實驗在Win10 64位操作系統(tǒng)，Intel Core i7-8750H處理器， 16GB RAM配置下的計算機上運行。

建模任務(wù)空間為100 km×100 km×10 km，其中包含4座山峰，3個雷達，2個障礙物。山峰相關(guān)參數(shù)設(shè)置為：hi=[6,4,10,8]，xoi=[25,40,70,30]，yoi=[25,45,40,70]，xsi=[6,8,12,7]，ysi=[12,6,18,5]。起點、終點、雷達與障礙物的位置如表1所示。BPSO、LPSO、ACMPSO算法的參數(shù)設(shè)置如表2所示，其中α和β是ACMPSO算法特有的參數(shù)。

表1 任務(wù)空間物體位置信息

表2 算法參數(shù)

根據(jù)上述條件，使用BPSO、LPSO、ACMPSO算法分別進行離線航跡規(guī)劃，仿真次數(shù)為100次。在每一次仿真實驗后，記錄3種算法各自的算法用時、二維航跡、三維航跡和適應(yīng)度值等數(shù)據(jù)。

4.2 仿真結(jié)果及其分析

待仿真實驗結(jié)束后，統(tǒng)計3種算法的平均用時、適應(yīng)度值、適應(yīng)度平均值和適應(yīng)度方差，如表3所示。BPSO、LPSO、ACMPSO算法100次仿真實驗的適應(yīng)度值如圖1所示。取各算法100次仿真實驗中的最優(yōu)航跡，其二維航跡如圖2所示，三維航跡如圖3所示，適應(yīng)度值如圖4所示。

圖2 二維航跡圖

圖3 三維航跡圖

圖4 適應(yīng)度值曲線

表3 100次仿真結(jié)果

圖1 100次仿真適應(yīng)度值曲線

由表3和圖1可知，BPSO算法的適應(yīng)度和穩(wěn)定性均較差；LPSO算法和ACMPSO算法均能提升BPSO算法的效果；但相較于LPSO算法，ACMPSO算法的適應(yīng)度平均值更小，且穩(wěn)定性更好，更有可能得到最佳航跡；而導(dǎo)致ACMPSO算法平均用時最久的原因是引入柯西變異后，計算量變大。

分析圖2和圖3，可以比較出3種不同算法的航跡規(guī)劃效果。顯然，3種算法生成的航跡均能躲避障礙物和雷達，使無人機順利到達終點，但BPSO算法規(guī)劃的航跡長度最長且高度變化最大，LPSO算法和ACMPSO算法規(guī)劃的航跡長度相近，但ACMPSO算法規(guī)劃的航跡離山峰更遠，因此高度變化更小，從而使航跡質(zhì)量更佳。

由圖4可知：ACMPSO算法能取得最小適應(yīng)度值。BPSO算法到55次迭代接近收斂，LPSO算法到60次迭代接近收斂，ACMPSO算法到45次迭代接近收斂，分別耗時6.368 s、6.955 s、5.277 s。由此可見ACMPSO算法雖然計算量稍大，但收斂速度快，能有效改進航跡質(zhì)量，耗時短、穩(wěn)定性好。

5 結(jié)論

針對UAV三維航跡規(guī)劃問題，提出了一種改進的ACMPSO算法。利用柯西變異的隨機性，使粒子的位置產(chǎn)生突變，克服了基本粒子群在后期容易陷入局部極值的缺點；通過使用指數(shù)形式的慣性權(quán)重和柯西變異步長調(diào)節(jié)策略，使算法快速收斂。仿真結(jié)果表明：與BPSO和LPSO相比，ACMPSO算法穩(wěn)定性好，能有效躲避障礙物和威脅，所需代價更少，可以更快搜索最優(yōu)航跡。實驗證明了ACMPSO算法的有效性和優(yōu)越性。