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

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

關(guān)鍵詞： 離散粒子群算法； 集群無(wú)人機(jī)； 路徑規(guī)劃； 人工勢(shì)場(chǎng)； Voronoi圖； 適應(yīng)度函數(shù)

中圖分類號(hào)： TN96?34； TP391.4" " " " " " " " " "文獻(xiàn)標(biāo)識(shí)碼： A" " " " " " " " " " "文章編號(hào)： 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" 引" 言

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

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

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

1.1" 用于路徑規(guī)劃的人工勢(shì)場(chǎng)構(gòu)建

假設(shè)集群無(wú)人機(jī)任務(wù)場(chǎng)景為一定海里范圍的矩形區(qū)域，借助笛卡爾坐標(biāo)系理論，基于式（1）在目標(biāo)點(diǎn)位置布置了一個(gè)目標(biāo)吸引勢(shì)場(chǎng)：

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

式中：[φpe（x，y）]表示目標(biāo)點(diǎn)[（x，y）]處的勢(shì)能強(qiáng)度；[h-1]和[h]分別表示參照勢(shì)能強(qiáng)度和基底勢(shì)能強(qiáng)度；[（x0，y0）]表示無(wú)人機(jī)初始位置坐標(biāo)；[ta]、[tb]表示不同的勢(shì)場(chǎng)偏斜率。

考慮到當(dāng)前任務(wù)場(chǎng)景中存在的障礙/威脅物，基于式（2）函數(shù)在目標(biāo)點(diǎn)位置布置了一個(gè)障礙物斥力勢(shì)場(chǎng)：

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

式中：[φobs（x，y）]表示[（x，y）]處的障礙物勢(shì)能強(qiáng)度；[hi]表示在目標(biāo)勢(shì)場(chǎng)內(nèi)第[i]個(gè)障礙物所形成的峰值勢(shì)場(chǎng)頂端所具備的勢(shì)能大小；[（xt，i，yt，i）]表示[t]時(shí)刻第[i]個(gè)障礙物所處在的位置坐標(biāo)；[tai]和[tbi]代表第[i]個(gè)障礙物不同勢(shì)場(chǎng)的偏斜率。

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

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

1.2" 基于威脅類型的Voronoi圖弧權(quán)值計(jì)算

根據(jù)人工勢(shì)場(chǎng)構(gòu)建的Voronoi圖如圖1所示。

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

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

式中：[t1]表示水平區(qū)域的海拔；[ω]表示區(qū)域地表特征的權(quán)重系數(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]個(gè)障礙物的坡度以及高度；[oj]、[pj]表示障礙物處于水平面投影點(diǎn)的橫縱坐標(biāo)。

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

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

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

威脅點(diǎn)到弧的距離計(jì)算公式如下：

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

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

考慮到集群無(wú)人機(jī)的威脅障礙與航線距離的4次冪成反比，威脅點(diǎn)對(duì)弧產(chǎn)生的威脅權(quán)值的表達(dá)式如下：

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

假設(shè)Voronoi圖中弧的距離為[Larci]，通過(guò)預(yù)設(shè)威脅點(diǎn)距離弧兩端的權(quán)重值[f1]和[f2]，以及上面得到的威脅點(diǎn)對(duì)弧造成的威脅權(quán)值，最終計(jì)算得到Voronoi圖弧權(quán)值為：

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

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

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

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

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

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

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

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

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

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

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

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

為了在離散領(lǐng)域內(nèi)有效計(jì)算個(gè)體最優(yōu)值，用[ra]表示優(yōu)化粒子個(gè)體最優(yōu)值的權(quán)重系數(shù)，進(jìn)而完成對(duì)概率[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]次迭代的坐標(biāo)以及最優(yōu)值；[kit]表示置換函數(shù)，用于記錄個(gè)體最優(yōu)值的尋優(yōu)過(guò)程。

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

為了能在離散領(lǐng)域內(nèi)正確計(jì)算出全局最優(yōu)值[13]，使用[rz]來(lái)定義優(yōu)化粒子個(gè)體最優(yōu)值的權(quán)重系數(shù)，進(jìn)而完成對(duì)概率[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]次迭代時(shí)個(gè)體極值位置信息以及全局極值；[λi（t）]表示變異函數(shù)，用于記錄全局最優(yōu)值的尋優(yōu)過(guò)程。解決無(wú)人機(jī)任務(wù)規(guī)劃問(wèn)題的離散粒子群算法具體求解步驟如圖2所示。

2" 實(shí)驗(yàn)分析

2.1" 有效性驗(yàn)證

實(shí)驗(yàn)所選機(jī)型為大疆DJI MINI4 PRO，數(shù)量為10臺(tái)，每臺(tái)機(jī)身搭載6 GB內(nèi)存，其他配置參數(shù)如表1所示。

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

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

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

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

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

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

3" 結(jié)" 論

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

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

參考文獻(xiàn)

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

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

[3] 黃志濱，陳桪.基于PSO?GA算法的無(wú)人機(jī)集群森林火災(zāi)探查方法[J].計(jì)算機(jī)工程與應(yīng)用，2023，59（9）：289?294.

[4] 鐘偉杰，李小兵，常昊天，等.基于嵌套PSO算法的反無(wú)人機(jī)集群防空部署模型[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)化改進(jìn)粒子群算法的無(wú)人機(jī)三維路徑規(guī)劃[J].火力與指揮控制，2023，48（1）：20?25.

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

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

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

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

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

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

作者簡(jiǎn)介：廣" 鑫（1998—），男，重慶人，碩士研究生，研究方向?yàn)橛?jì)算機(jī)路徑規(guī)劃、無(wú)人機(jī)路徑規(guī)劃等。

耿增顯（1976—），男，陜西咸陽(yáng)人，博士研究生，講師，研究方向?yàn)閁TM/UAM的運(yùn)營(yíng)管理技術(shù)和方法、控制技術(shù)和方法等，以及無(wú)人機(jī)運(yùn)行軌跡分析和管理。