基于改進PSO的無人機三維航跡規劃優化算法

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

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

1 引言

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

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

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

2 無人機三維航跡規劃模型

2.1 環境建模

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

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

(1)

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

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

(2)

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

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

(3)

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

2.2 適應度函數建模

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

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

(4)

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

2.2.1航跡長度成本

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

(5)

2.2.2雷達威脅成本

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

(6)

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

(7)

2.2.3障礙物碰撞成本

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

(8)

(9)

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

2.2.4高度變化成本

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

(10)

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

3 粒子群算法及其改進

3.1 基本粒子群算法

在本文中，每一個粒子都代表一條航跡。考慮三維空間的航跡規劃，并假設航跡節點數量為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個粒子的個體最優位置，而對整個粒子群而言，也一定存在一個如式(13)的全局最優位置，其中k∈1，…，S。

(13)

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

(14)

(15)

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

(16)

式中：慣性權重w用于繼承粒子的速度，c1、c2是學習因子，分別代表對自身歷史最佳狀態的學習能力和對群體中最優個體的學習能力，r1、r2都是0～1之間的任意隨機數。

3.2 粒子群算法的改進方案

3.2.1自適應慣性權重

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

(17)

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

3.2.2柯西變異

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

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

(18)

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

(19)

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

(20)

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

與慣性權重類似，柯西變異的步長也需要動態調整，以便在算法運行的前期以較大步長產生一定擾動，使粒子跳出當前位置，避免局部最優；后期以較小步長加速收斂。每次迭代中每個粒子的更新規則為

(21)

3.3 無人機航跡規劃算法的實現步驟

綜上所述，基于ACMPSO的UAV三維航跡規劃算法的實現步驟如下：

步驟1：根據式(1)～式(3)創建三維環境，并設置無人機的起點和終點；

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

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

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

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

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

4 仿真實驗及其結果分析

4.1 仿真環境與實驗數據準備

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

建模任務空間為100 km×100 km×10 km，其中包含4座山峰，3個雷達，2個障礙物。山峰相關參數設置為：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算法的參數設置如表2所示，其中α和β是ACMPSO算法特有的參數。

表1 任務空間物體位置信息

表2 算法參數

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

4.2 仿真結果及其分析

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

圖2 二維航跡圖

圖3 三維航跡圖

圖4 適應度值曲線

表3 100次仿真結果

圖1 100次仿真適應度值曲線

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

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

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

5 結論

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