基于離散粒子群算法的集群無人機飛行路徑規(guī)劃

摘" 要： 飛行環(huán)境可能隨時發(fā)生變化，如新的障礙物出現(xiàn)、天氣條件變化等，導致集群無人機飛行路徑規(guī)劃難度上升。為此，提出一種基于離散粒子群算法的集群無人機飛行路徑規(guī)劃方法。根據(jù)人工勢場理論與威脅類型繪制Voronoi圖，從而確定Voronoi圖弧權值。結合Voronoi圖弧權值計算結果與無人機飛行航程、威脅、電池效能代價構建適應度函數(shù)，通過離散粒子群算法不斷進行迭代尋優(yōu)，得到集群無人機的最佳飛行路徑。實驗結果表明，所提方法在集群無人機路徑規(guī)劃中具有較高的執(zhí)行效率和成功率，具有良好的實際應用前景。

關鍵詞： 離散粒子群算法； 集群無人機； 路徑規(guī)劃； 人工勢場； Voronoi圖； 適應度函數(shù)

中圖分類號： TN96?34； TP391.4" " " " " " " " " "文獻標識碼： A" " " " " " " " " " "文章編號： 1004?373X（2025）04?0119?04

Clustering UAV flight path planning based on DPSO

GUANG Xin， GENG Zengxian

（Civil Aviation University of China， Tianjin 300300， China）

Abstract： The flight environment may change at any time， such as the appearance of new obstacles， changes in weather conditions， etc.， which increases the difficulty of clustering unmanned aerial vehicle （UVA） flight path planning. Therefore， a method of clustering UVA flight path planning based on discrete particle swarm optimization algorithm （DPSO） is proposed. A Voronoi diagram is drew based on artificial potential field theory and threat types to determine the arc weights of the Voronoi diagram. By combining the calculation results of Voronoi plot arc weight with the UVA flight range， threat， and battery efficiency cost， a fitness function is constructed. The continuous iterative optimization is carried out by means of the theory of DPSO， so as to obtain the optimal flight path for the clustering UVA. The experimental results show that the proposed method has high execution efficiency and success rate in clustering UVA path planning， and has good practical application prospect.

Keywords： discrete particle swarm optimization algorithm; clustering UAV; path planning; artificial potential field theory; Voronoi diagram; fitness function

0" 引" 言

由于實際情況復雜，單架次無人機往往很難獨立完成復雜任務[1?2]。為了確保安全和高效，集群無人機得到了廣泛的應用和推廣[3?4]，而集群無人機飛行路徑規(guī)劃也成為了該領域的研究難題。文獻[5]為優(yōu)化無人機輔助無線傳感器網絡中的無人機飛行軌跡及節(jié)點能耗，提出了混合數(shù)據(jù)路由協(xié)議，采用多目標NSGA?Ⅱ算法優(yōu)化飛行軌跡。但其效果受限于網絡容量及遙感通信狀況，難以實現(xiàn)預期目標。文獻[6]提出一種基于區(qū)塊鏈的無人機飛行路徑規(guī)劃方法，預先分配飛行路徑以降低碰撞概率。但該機制仍面臨技術成熟度、應用場景限制及城市信息保護等挑戰(zhàn)。文獻[7]將粒子群算法（PSO）的粒子按照特定的特征進行分類，以此來避免其在無人機飛行航線計劃上的過度成熟、陷入局部最優(yōu)以及其他的不利影響。但是該方法因為細化分組的過程消耗時間較長，會導致系統(tǒng)響應慢等問題。文獻[8]提出了一種融合改進人工勢場的蟻群算法，利用改進后的算法進行無人機飛行路徑規(guī)劃。但是該算法對施行環(huán)境要求比較高，在業(yè)務適用性和達成率方面具有一定的局限性。

離散粒子群算法（DPSO）可以通過調整離散粒子的位置來搜索最優(yōu)解，因此本文提出一種基于離散粒子群算法的集群無人機飛行路徑規(guī)劃方法。

1" 集群無人機飛行路徑規(guī)劃方法

1.1" 用于路徑規(guī)劃的人工勢場構建

假設集群無人機任務場景為一定海里范圍的矩形區(qū)域，借助笛卡爾坐標系理論，基于式（1）在目標點位置布置了一個目標吸引勢場：

[φpe（x，y）=-h?exp-（x-x0）2t2a-（y-y0）2t2b+h-1] （1）

式中：[φpe（x，y）]表示目標點[（x，y）]處的勢能強度；[h-1]和[h]分別表示參照勢能強度和基底勢能強度；[（x0，y0）]表示無人機初始位置坐標；[ta]、[tb]表示不同的勢場偏斜率。

考慮到當前任務場景中存在的障礙/威脅物，基于式（2）函數(shù)在目標點位置布置了一個障礙物斥力勢場：

[φobs（x，y）=ihi?exp-（x-xt，i）2t2ai-（y-yt，i）2t2bi+h-1] （2）

式中：[φobs（x，y）]表示[（x，y）]處的障礙物勢能強度；[hi]表示在目標勢場內第[i]個障礙物所形成的峰值勢場頂端所具備的勢能大??；[（xt，i，yt，i）]表示[t]時刻第[i]個障礙物所處在的位置坐標；[tai]和[tbi]代表第[i]個障礙物不同勢場的偏斜率。

匯總兩個局部勢場中較大的兩個數(shù)值，可得無人機集群路徑規(guī)劃的總勢場。則用于路徑規(guī)劃的人工勢場公式如下：

[φ（x，y）=φpe（x，y）+φobs（x，y）] （3）

1.2" 基于威脅類型的Voronoi圖弧權值計算

根據(jù)人工勢場構建的Voronoi圖如圖1所示。

依據(jù)海岸線地形的起伏狀態(tài)，選用函數(shù)模擬法構建水平區(qū)域模型，具體如下：

[t1x，y=ρsin（ρx2+y2）+ωcos（ωx2+y2）] （4）

式中：[t1]表示水平區(qū)域的海拔；[ω]表示區(qū)域地表特征的權重系數(shù)；[ρ]表示起伏狀態(tài)的描述參數(shù)。

障礙區(qū)域模型表示為：

[t2x，y=j=1mωj·exp-（x-oj）2-（y-pj）2β2j] （5）

式中：[t2]表示障礙區(qū)域的海拔；[m]表示高山與礁石總量；[ωj]、[βj]表示第[j]個障礙物的坡度以及高度；[oj]、[pj]表示障礙物處于水平面投影點的橫縱坐標。

環(huán)境海域的威脅模型公式如下：

[Ob（x，y）=T-τri=1nmaxt1x，y，t2x，yφ（x，y）] （6）

式中：[T]、[r]、[n]分別表示威脅源中心點強度、到威脅源中心的海域聚類以及威脅源數(shù)量；τ表示衰減因子。

威脅點到弧的距離計算公式如下：

[Larci，obsk=arci1x+arci2x2-obskx2+arci1y+arci2y2-obsky2] （7）

式中：[arci1=arci1x，arci1y]、[arci2=arci2x，arci2y]分別表示Voronoi圖中與弧相關的節(jié)點坐標對；[obskx，obsky]表示威脅點的坐標。

考慮到集群無人機的威脅障礙與航線距離的4次冪成反比，威脅點對弧產生的威脅權值的表達式如下：

[t_cellarci，obsk=Ob（x，y）Larci，obsk4] （8）

假設Voronoi圖中弧的距離為[Larci]，通過預設威脅點距離弧兩端的權重值[f1]和[f2]，以及上面得到的威脅點對弧造成的威脅權值，最終計算得到Voronoi圖弧權值為：

[twarci=f1·k=1nt_cellarci，obsk+f2·Larci] （9）

1.3" 基于離散粒子群算法的最優(yōu)路徑規(guī)劃

以離散粒子群算法為基礎，根據(jù)人工勢場以及Voronoi圖弧權值進行最優(yōu)路徑規(guī)劃，以此保證規(guī)劃質量與效率。

在PSO算法規(guī)劃集群無人機飛行路徑的過程中，適應度函數(shù)作為粒子群迭代進化的標準，直接影響著算法的執(zhí)行質量和效率[9?11]。適應度函數(shù)具體如下：

[Hi=σdisn+αtern+λeffn·twarci] （10）

式中：[disn]、[tern]、[effn]分別表示航程代價模型、飛行威脅代價模型、電池效能代價模型；[σ]、[α]、[λ]分別表示各個代價模型的權重系數(shù)。

DPSO算法是基于PSO算法[12]發(fā)展而來，但其專注于離散問題的優(yōu)化，具體過程如下。

1） 個體最優(yōu)值置換

為了獲取個體最優(yōu)值，需要根據(jù)以下公式更新粒子速度以及位置：

[vt+1i=wvti+s1ra1pts-xti+s2ra2ptg-xti] （11）

[xt+1i=xti+vt+1i] （12）

式中：[w]表示慣性權重；[ps]、[pg]分別表示個體以及全局最優(yōu)解；[s1]、[s2]分別表示不同的學習因子；[ra1]和[ra2]表示兩個（0，1）之間的隨機數(shù)；[t]表示當前迭代值。

為了在離散領域內有效計算個體最優(yōu)值，用[ra]表示優(yōu)化粒子個體最優(yōu)值的權重系數(shù)，進而完成對概率[s1]的置換操作，具體形式如下：

[kit=s1?HiXit，Pit=HiXit，Pit，" ralt;s1Xit，" ra≥s1] （13）

式中：[Xi（t）=（xt+1i，xt+2i，…，xt+Ni）]、[Pit=（pi1，pi2，…，piN）]表示粒子[i]在第[t]次迭代的坐標以及最優(yōu)值；[kit]表示置換函數(shù)，用于記錄個體最優(yōu)值的尋優(yōu)過程。

2） 全局最優(yōu)值變異

為了能在離散領域內正確計算出全局最優(yōu)值[13]，使用[rz]來定義優(yōu)化粒子個體最優(yōu)值的權重系數(shù)，進而完成對概率[s2]的置換操作，具體形式如下：

[λi（t）=s2?Hi（ki（t），Pg（t））=Hi（ki（t），Pg（t）），" rzlt;s2ki（t），" rz≥s2] （14）

式中：[ki（t）=（ki1，ki2，…，kiN）]和[Pg（t）=（Pi1，Pi2，…，PiN）]分別表示粒子[i]在第[t]次迭代時個體極值位置信息以及全局極值；[λi（t）]表示變異函數(shù)，用于記錄全局最優(yōu)值的尋優(yōu)過程。解決無人機任務規(guī)劃問題的離散粒子群算法具體求解步驟如圖2所示。

2" 實驗分析

2.1" 有效性驗證

實驗所選機型為大疆DJI MINI4 PRO，數(shù)量為10臺，每臺機身搭載6 GB內存，其他配置參數(shù)如表1所示。

本實驗設定了一個240×160像素的數(shù)字地圖，設置威脅源數(shù)量是13個，用[Pi（i=1，2，…，13）]描述。利用Matlab中的Voronoi（）函數(shù)生成實驗集群無人機飛行路徑規(guī)劃環(huán)境的Voronoi圖，如圖3所示，圖中節(jié)點編號是2～19， 起始點（220，120）預設值為1，目的地（10，18）預設值為20。本文方法采用DPSO算法函數(shù)在Voronoi圖中尋找最優(yōu)路徑時，設置粒子群數(shù)量為30，粒子在搜索空間中的特征維度D=20，慣性權重[w=0.65]，獲取的實驗集群無人機最優(yōu)航跡路徑如圖3所示。

從圖3中可以看出，本文方法規(guī)劃出的集群無人機最優(yōu)航跡路徑完美地避開了全部的障礙區(qū)域。

2.2" 優(yōu)越性驗證

在眾多的快速搜索算法中，分別應用蟻群算法、粒子群算法、離散粒子群算法進行集群無人機飛行路徑規(guī)劃的適應度值變化對比，結果如圖4所示。

從圖4中可以看出，相對于其他算法，本文采用的離散粒子群算法在無人機集群路徑規(guī)劃問題上的收斂性和求解質量最佳。實驗統(tǒng)計不同算法的集群無人機規(guī)劃效果，結果如表2所示。

根據(jù)表2實驗結果可知：傳統(tǒng)粒子群算法的成功率最低，僅為82.40%，表明傳統(tǒng)粒子群算法的尋優(yōu)性較差，規(guī)劃結果較差；相比之下，蟻群算法雖然將成功率提高了8.60%，但是適應度值升高，收斂性變差；DPSO算法在各個性能指標上較其他兩種算法有較大提升，說明了集群無人飛行路徑規(guī)劃具有優(yōu)越性。

3" 結" 論

本文提出一種基于DPSO的無人機集群路徑規(guī)劃方法，以解決傳統(tǒng)PSO在路徑規(guī)劃時易陷入非全局最優(yōu)、局部精度不足的問題。實驗結果證明，DPSO算法在保證規(guī)劃質量的同時，降低了計算成本和時間消耗，提升了無人機集群性能。DPSO算法在無人機集群路徑規(guī)劃領域具有競爭優(yōu)勢和廣闊前景，可為無人機集群的智能化、高效化提供支持。

注：本文通訊作者為耿增顯。

參考文獻

[1] 孫雪瑩，易軍凱.無人機三維路徑規(guī)劃的粒子群混合算法[J].電訊技術，2023，63（3）：335?341.

[2] 趙飛虎，李哲，王寧，等.面向戰(zhàn)場的多無人機協(xié)同打擊航跡規(guī)劃[J].電光與控制，2023，30（9）：9?14.

[3] 黃志濱，陳桪.基于PSO?GA算法的無人機集群森林火災探查方法[J].計算機工程與應用，2023，59（9）：289?294.

[4] 鐘偉杰，李小兵，常昊天，等.基于嵌套PSO算法的反無人機集群防空部署模型[J].電光與控制，2021，28（12）：6?10.

[5] SINGH M K， CHOUDHARY A， GULIA S， et al. Multi?objective NSGA?Ⅱ optimization framework for UAV path planning in an UAV?assisted WSN [J]. Journal of supercomputing， 2023， 79（1）： 832?866.

[6] RAHMAN M S， KHALIL I， ATIQUZZAMAN M. Blockchain?powered policy enforcement for ensuring flight compliance in drone?based service systems [J]. IEEE network， 35（1）： 116?123.

[7] 藺文軒，謝文俊，張鵬，等.基于分組優(yōu)化改進粒子群算法的無人機三維路徑規(guī)劃[J].火力與指揮控制，2023，48（1）：20?25.

[8] 孔維立，王峰，周平華，等.改進蟻群算法的無人機三維路徑規(guī)劃[J].電光與控制，2023，30（3）：63?69.

[9] 單文昭，崔乃剛，黃蓓，等.基于PSO?HJ算法的多無人機協(xié)同航跡規(guī)劃方法[J].中國慣性技術學報，2020，28（1）：122?128.

[10] 葉梓菁，魏文紅，李環(huán)，等.基于改進粒子群算法的無人機路徑規(guī)劃[J].東莞理工學院學報，2023，30（3）：18?23.

[11] 趙棣宇，鄭賓，殷云華，等.改進粒子群算法的UAV突防路徑規(guī)劃[J].電光與控制，2023，30（4）：12?16.

[12] 趙玉花，石永康，萬曉燕.基于粒子群優(yōu)化的多無人機區(qū)域覆蓋航跡規(guī)劃[J].農機化研究，2024，46（6）：63?67.

[13] 王飛，楊清平.基于改進粒子群算法的城市物流無人機路徑規(guī)劃[J].科學技術與工程，2023，23（30）：13187?13194.

作者簡介：廣" 鑫（1998—），男，重慶人，碩士研究生，研究方向為計算機路徑規(guī)劃、無人機路徑規(guī)劃等。

耿增顯（1976—），男，陜西咸陽人，博士研究生，講師，研究方向為UTM/UAM的運營管理技術和方法、控制技術和方法等，以及無人機運行軌跡分析和管理。