基于改進DPSO非退出故障下多無人機任務規劃

邵士凱, 李厚振, 趙淵潔

(河北科技大學電氣工程學院, 石家莊 050018)

隨著技術的進步,無人機在各個行業均得到廣泛的應用。在復雜的戰場上,多機協同執行任務是無人機技術的研究熱門,尤其是多無人機協同執行打擊任務是無人機智能化、多樣化的重要組成部分[1-3]。

當前發展成果中,無人機任務分配的主要控制方式包括集中式、分布式與分層次控制。文獻[4]針對地面目標的動態任務分配問題,建立了兩種分配模型,并與基于合同網算法、智能優化算法、聚類算法等進行對比,分析了其優缺點及研究現狀。文獻[5]提出了一種離散狼群算法的任務分配方式,對高維復雜問題進行功能性優化,并通過正交實驗和方差分析,證明離散狼群算法(discrete wolf swarm algorithm, DWSA)具有較好的收斂性。文獻[6]提出了一種將3種激光掃描數據與無人機航空影像融合的拱橋精細化建模方法,并通過實景三維模型為類似底部脫空建筑的數據采集方法提供了參考。文獻[7]提出了一種差分進化-離散粒子群優化-郭濤-模擬退火(differential evolution-discrete particle swarm optimization-Guo Tao-simulated annealing,DE-DPSO-GT-SA)算法的協同多任務分配,并進行了多種算法的對比,仿真實驗證明該方法具有較好的收斂特性。文獻[8-9]考慮實際環境下無人機任務分配的協同能力,加入了復雜的地形約束。文獻[10]提出了一個由嵌入式硬件和高級別通信協議相結合的系統,作為識別、分發和分配任務的基礎,進而用簡單分散的方式供多無人機使用。文獻[11]提出了一種動態離散鴿群的優化算法,進行處理多無人機協同搜索攻擊任務規劃,集成了任務分配和路徑生成。綜上可知,關于目前多機協同任務分配的研究,僅考慮了算法的改進和一對一的目標分配,而針對無人機發生故障后的多對一任務分配問題考慮不充分。

此外,當任務分配完成后,為保證無人機到達任務目標點,還需要進行無人機軌跡的設計與規劃。當前無人機航跡規劃的研究中,大部分成果僅針對單架無人機的航跡進行了深入的探索,多機的航跡規劃以及與任務分配的耦合程度尚未進行有效研究。運用圖論的方法進行一些路徑規劃是當前研究的一種思路,如A*算法[12]、匈牙利算法[13]、隨機樹算法[14]、Voronoi圖形算法[15]等。這類方法由于均是基于代價圖進行規劃的,需要進行離線存儲好代價圖,從而導致該方法較費時。隨著人工智能技術的發展,仿生物群體捕食技術的算法被廣泛應用于航線規劃中,應用較廣泛的算法如蜂群算法(bee colony algorithm,BCA)[16]、狼群算法(wolf swarm algorithm,WSA)[17]、遺傳算法(genetic algorithm,GA)[18]以及粒子群算法(particle swarm optimization,PSO)[19]等。其中粒子群算法因搜索能力強、易仿真操作等優勢被廣泛應用,文獻[20]提出了將粒子群算法進行航線預規劃,并結合高斯偽譜法進行擬合進行航線規劃的方法,該方法有效提高了收斂速度,航線平滑性更好。文獻[21]考慮無人機航跡在三維空間結構的特點,提出了一種遺傳算法和模擬退火算法相結合的算法,通過三維有限空間仿真驗證了該算法可實現最優航跡的有效縮短,同時迭代次數也得到了相應的減少。

綜上所述,針對多無人機打擊任務規劃,當前研究大都只考慮了一對一的打擊規劃場景,即一個敵方目標只由一架無人機進行打擊,且僅考慮了任務分配的直線距離,不符合實際作戰環境下的航跡規劃,從而造成規劃結果不避障;同時,當前無人機任務規劃研究中僅涉及任務分配或者航跡規劃的一方面內容,沒有考慮現實狀況下二者耦合情況;另一方面,當無人機發生故障后,各機協同執行任務的有效性尚未進行有效探究。

基于此,針對無人機發生故障下多對一的協同打擊任務規劃進行了研究,將任務分配與航跡規劃進行耦合。首先,針對障礙環境下的多無人機-多目標分配場景,進行任務分配算法建模,分配過程中考慮了雷達障礙等因素,同時算法不基于無人機-目標的直線距離,而是耦合基于航線規劃的實際飛行距離;其次,提出一種基于混合改進策略的離散粒子群任務分配算法,利用Sobol序列進行種群初始化,基于柯西算子、非線性時變變異策略,以及自適應交叉學習策略更新優質個體,豐富種群的多樣性;最后,在山峰、雷達等威脅約束下,進行無人機故障前后仿真實驗。為部分無人機發生輕微故障后,多機協同執行任務規劃的問題提供了理論依據。

1 問題描述

假設無人機群在執行打擊任務的過程中,部分無人機發生輕微故障,在不退出戰斗序列的情況下,飛行能力受限,只能對局部范圍內的目標進行打擊,剩余無人機調整狀態,協助故障機重新完成對新目標的打擊任務。因此,為使任務規劃結果最優,需在合理的約束條件下將無人機按照最低損耗成本進行任務分配。

定義存在m架無人機,te個敵方目標,且m>te,執行多對一的打擊任務,即無人機對不同標號的目標進行不同架次的打擊。當有無人機發生故障時,重新協調各機機動性能和飛行成本,在滿足各種約束的情況下,完成任務分配。

在任務分配完成后,各機根據給定的航跡點運用三次樣條插值的方法執行航跡規劃,最終準確打擊目標。

1.1 約束條件

1.1.1 打擊次數約束

假設無人機執行任務分配時,對目標i執行打擊的次數表示為MAttack(i),目標點數集合表示為t,則打擊次數可表示為

(1)

式(1)中:當目標標號t為偶數時,無人機進行A1架次的打擊;當目標標號t為奇數時,進行A2架次的打擊,具體打擊次數根據仿真進行設定。

該約束的優化約束指標函數為

(2)

1.1.2 空間協同約束

對于多無人機協同飛行時,考慮無人機之間因發生碰撞導致任務失敗的情況,建立具有空間協同能力的約束條件,設定任意兩架無人機之間的距離為d,為避免碰撞,d應滿足:

d>dmin

(3)

式(3)中:dmin為機間最小安全距離。

其對應的優化約束指標函數為

(4)

1.1.3 總航程最短約束

當前無人機任務分配的研究中,航程約束僅基于直線距離的規劃,不符合無人機實際飛行軌跡,即基于直線距離的任務分配不一定滿足存在障礙飛行環境下的最優分配結果。故提出的總航程最短約束將無人機實際飛行航程作為約束條件考慮在內。

假設S1表示無人機從起始點到敵方目標點需要付出的航程代價,為更加直觀地表現目標函數的適應值變化,對航程代價約束值進行歸一化處理,具體表示為

(5)

li=sqrt[(xk+1-xk)2+(yk+1-yk)2+

(zk+1-zk)2]

(6)

式中:η為航跡點總數;k為某一航線點;xk、yk、yk+1、xk+1為該航線點在水平面上的坐標;zk、zk+1為航線點的垂直高度;lstr為無人機任務分配完畢后起點與目標點的直線距離。

航線規劃的結果即是在任務空間中,通過搜索一系列的航跡點,經過迭代尋優得到符合最短總航程約束的點,從而構成可飛行航跡。

此外,考慮到無人機在實際作戰環境中,存在山峰和雷達監測的威脅,當無人機進行航跡規劃時,需要將其考慮在內,故引入如下約束條件。

1.1.4 雷達威脅約束

多無人機在執行任務飛行時需避免被敵方目標設置的雷達監測到,假設雷達探測范圍表示為半球形,且不會被周邊地形遮蓋,則多無人機在執行任務的航線規劃過程中,其雷達威脅模型設置為

Lradar=(xk,yk,zk,rk)

(7)

式(7)中:xk、yk、zk為雷達所在的中心位置;rk為其監測半徑。

(8)

其優化約束的指標函數為

(9)

1.1.5 山峰威脅約束

在實際環境中,多無人機協同執行任務分配時,還需要規避飛行區域內的山峰。因此,機群應與山體威脅保持一定航距。則山峰威脅約束的建模形式為

(10)

式(10)中:xu、yu、zu為山峰威脅的三維坐標位置;a、b為山峰的起始位置;c為山峰的高度;d為可調節系數;k′為山峰的面積跨度。

其優化約束的指標函數為

(11)

1.2 評價指標

多機協同任務規劃需滿足上述各約束條件,使各機任務規劃優化性能達到最優。因此,目標函數表示為

S=c1S1+c2f2+c3f3+c4fR+c5fM

(12)

式(12)中:S為總代價值;S1為總航程最短約束代價;f2為打擊次數協同約束懲罰值;f3為空間協同約束懲罰值;fR為雷達威脅懲罰值;fM為山峰威脅懲罰值;c1、c2、c3、c4、c5為各約束指標所占權重值,滿足:

c1+c2+c3+c4+c5=1

(13)

2 求解策略

2.1 改進離散粒子群算法

由于傳統離散粒子群算法求解效率慢,適用性差,提出了一種混合策略改進的離散粒子群算法(mixed strategy improved discrete particle swarm optimization,MSDPSO),有效提升了算法的尋優結果和收斂速度,具體改進如下所示。

2.1.1 基于Sobol序列初始化策略

由于離散粒子群算法(discrete particle swarm optimization, DPSO)采用生成[0,1]之間生成偽隨機數的方式進行種群初始化,組織性和遍歷性差,且個體分布不均勻,從而導致尋優性偏低。采用Sobol序列進行初始化,使得種群分布更為規范、解空間覆蓋率更高,進而提升算法的尋優精度。圖1為偽隨機分布與Sobol序列分布初始化的對比。

圖1 種群初始化方法對比Fig.1 Comparison of population initialization methods

由圖1對比可知,采用Sobol序列進行種群初始化后的解空間覆蓋率比傳統初始化方法更高,且分布更規范。從而提高算法收斂速度。

2.1.2 非線性時變策略

DPSO借鑒遺傳算法的思想,離散化PSO的粒子位置和速度,更新為交叉和變異策略,其變異策略不能及時根據位置的變化做出相應的調整,從而導致尋優性變差,為解決該問題,引入非線性時變策略:

(14)

如式(14)所示,將變異策略分為3個階段,其中,T為最大迭代次數,t′為當前階段的迭代次數,在變異策略處于算法的后期階段,此時解的尋優性較差,故設計非線性時變的變異因子的前兩個階段能夠加強粒子的變異能力,從而及時擺脫局部搜索,提高解的尋優能力,隨著迭代的進行,適應值趨于最優,變異因子隨之進入第三階段的線性環節,從而加快算法的收斂速度。a′、b′分別為不同階段的系數因子,具體數值根據仿真進行設定。此外,交叉因子r1、r2也會影響粒子的更新速度與尋優能力,為進一步提高算法的收斂速度與全局尋優能力,對交叉因子進行線性改進,可表示為

(15)

(16)

交叉因子r1隨著迭代的進行而增加,r2隨迭代次數的累加而減小。

這使得算法在迭代開始階段積極進行全局搜索,進而提升收斂速度,隨著迭代接近尾聲,個體學習能力的加強使得種群不易陷入局部最優,同時,r1與r2的和為1,表示粒子兼顧尋優能力和收斂速度。

2.1.3 柯西變異策略

針對DPSO易陷入局部最優的特點,引入柯西算子能夠有效提升算法的全局搜索能力,增強搜索空間。由于柯西分布函數在中點的步長較小,在兩端的步長較大,從而對粒子個體產生較大擾動,使得粒子能夠及時調整位置,避免陷入局部最優。同時,柯西分布峰值下降的坡率較緩且峰值較小,從而使得粒子經過變異后用于搜索的時間花費較少,進而能夠把更多的時間用于全局尋優上,因此提高了改進算法的收斂速度。

經過離散化的算法采用如下改進的柯西變異公式,進行更新當前個體的最優位置,提高全局尋優能力。

(17)

從而增強全局尋優能力,提高了改進算法的收斂速度。

2.1.4 自適應交叉學習策略

針對傳統離散粒子群算法全局尋優能力差的特點,在迭代前期及后期加入自適應交叉學習策略,將粒子之間的交叉置換擬化為人與人之間交流學習的方式,通過交流比較,粒子不斷進行個體尋優從而改善自身狀態,可表示為

(18)

式(18)中:Xnew為通過加入自適應交叉學習策略,將粒子之間的交叉置換擬化為人與人之間交流學習的方式,通過交流比較,粒子更新得到的新個體;f(x)為通過離散粒子群算法不斷迭代得到的任務序列;x為隨機粒子;xp為相鄰粒子;rand為產生(0,1)之間的隨機數,用于放大個體之間學習的過程,通過不斷迭代,更新個體最優,從而豐富了種群的多樣性,進而提升改進算法的全局尋優能力。

2.2 無人機航跡規劃

2.2.1 粒子群算法

為保證任務分配的合理性,需要為無人機到達目標點制定合理避障的飛行路線。故基于基本粒子群算法進行航線預規劃。其數學模型為

(19)

(20)

2.2.2 三次樣條插值算法

與基于直線距離的任務分配相比,航線預規劃能夠保證更好的任務合理性,然而預規劃得到的航線是一系列相對粗糙的航跡點,導致無人機軌跡不平滑。因此,運用三次樣條插值算法,對PSO的預規劃航線進行再優化,從而得到更加平滑的無人機航線。

假設a=η0<η1<…<ηn=b,其中,ηi為航跡點,i=1,2,…,n,在區間[ηi-1,ηi]上的分段函數s(η)為小于或等于三次的多項式且二階可導。可表示為

s(η)={si(η),η∈[ηi-1,ηi],i=1,2,…,n}

(21)

si(η)=aiη3+biη2+ciη+diη3

(22)

式(22)中:ai、bi、ci、di為待定系數,其和為4n。

一般情況下,為得到三次樣條插值函數s(x)的待定系數ai、bi、ci、di,采用自然邊界條件,即

s″i(xi)=s″i(xn)=0

(23)

綜上,結合式(21)～式(23)進行聯立方程組來確定待定系數值。

2.3 流程設計

根據上述方法的介紹,基于混合策略改進的離散粒子群算法進行故障下多無人機任務規劃的流程步驟如下。

步驟1設定基本參數。給定無人機、目標點位置,設定環境障礙參數,包括雷達威脅的個數及監測中心坐標與半徑,山峰威脅的個數及相關參數。

步驟2初始化種群數量,設置粒子個體極值和全局極值的初值,以及最大迭代次數。

步驟3開始進行迭代尋優,編譯適應值函數并輸入多約束條件,給定相應懲罰值,計算每次的代價值,并畫出代價值函數曲線。

步驟4根據每次迭代的代價值,判斷粒子當前迭代值與個體極值的大小情況,如若連續10次迭代值相等,執行柯西變異策略,幫助跳出局部最優;否則不執行此策略,直接進入下一步驟。

步驟5執行改進離散粒子群算法的交叉策略,并依據改進算法依次執行公式(14)的的非線性時變策略,并將當前迭代次數與最大迭代次數進行比較,直至執行完設定的最大迭代次數。

步驟6依據任務分配得到的分配結果,利用粒子群算法進行航線預規劃。

步驟7根據粒子群算法航線預規劃的結果,運用三次樣條插值算法對航跡進行再優化。

具體仿真流程設計如圖2所示。

圖2 故障下無人機任務規劃算法流程圖Fig.2 Flow chart of UAV task planning algorithm under fault

3 仿真與分析

3.1 仿真參數設定

根據流程設計,在配置為Intel 5,1.19 GHz的計算機上,運用MATLAB2020b進行仿真實驗。設定迭代次數T=200,種群數N=400;航跡點η=10;打擊次數A1=3,A2=2;無人機安全間距d=20 m。

設定三維地形環境為250 km×250 km×70 km的任務區域,包括5個雷達監測區域和2個山峰威脅區域,雷達區域在仿真環境中以半球進行繪制,山峰則用高低起伏不同的曲面進行繪制。其參數設置如表1所示。

表1 威脅參數Table 1 Threat parameters

將無人機擬化為質點,并忽略相關的動力學模型。假設初始狀態下,無人機未發生故障時,以12架無人機打擊5個敵方目標為背景進行仿真實驗,坐標位置如表2所示,目標點位置如表3所示。各無人機從起點出發,滿足各約束條件下打擊所有目標點。

表2 無人機起點位置參數Table 2 UVA starting point position parameters

表3 目標點參數Table 3 Parameters of target point area

3.2 仿真結果分析

3.2.1 改進算法性能對比

根據不同策略方法,分別對傳統的離散粒子群算法進行改進優化,得到以下4種單策略改進的離散粒子群算法:基于Sobol序列初始化改進的離散粒子群算法(sobol discrete particle swarm optimization,SDPSO);基于非線性時變的變異因子改進的離散粒子群算法(nonlinear time-varying discrete particle swarm optimization, NDPSO);基于柯西變異策略改進的離散粒子群算法(Cauchy discrete particle swarm optimization, CDPSO);基于自適應交叉學習策略改進的離散粒子群算法(re-cover discrete particle swarm optimization, RDPSO)。將以上4種改進算法與傳統的離散粒子群算法(discrete particle swarm optimization, DPSO)以及MSDPSO進行仿真對比。

為了驗證改進算法的有效性,分別將MSDPSO與SDPSO、NDPSO、CDPSO、RDPSO和DPSO進行了對比仿真,并同時進行了10次、30次、50次以及100次蒙特卡羅仿真,求其平均值后得到圖3所示算法適應值對比結果。

圖3 改進算法適應值比較Fig.3 Comparison of fitness values of improved algorithms

根據圖3仿真對比結果,經過多次蒙特卡羅仿真,MSDPSO在歷次迭代尋優性能上均優于DPSO和其他單策略改進算法,尋優有效性較好。

此外,為驗證MSDPSO的尋優穩定性和有效性均優于DPSO,分別給出100次仿真下的具體適應度曲線。仿真結果如圖4所示。

圖4 適應值變化曲線Fig.4 Fitness curve

從圖4可以看出,基于MSDPSO的適應值變化曲線較基于DPSO的適應值變化曲線更加穩定且有更好的收斂性,說明MSDPSO具有更穩定的尋優性,且最優值比DPSO更好,驗證了MSDPSO具有更高的全局尋優能力,收斂速度也更快。

3.2.2 基于三次樣條插值航線再優化

由于基于PSO的航跡規劃,航線粗糙且平滑度低,利用三次樣條插值的方法進行航跡再優化,可以使航線更平滑,且與MSDPSO的耦合程度更高。故基于三次樣條插值的航跡再優化與基于PSO的航跡預規劃進行了仿真對比,如圖5、圖6所示。

紅星表示無人機的起始點;不同顏色的虛線是每架無人機基于PSO得到不同的軌跡規劃,通過顏色對比可以更加直觀地看出各無人機滿足各項約束條件,有效躲避障礙物

紅星表示無人機的起始點;不同顏色的實線是基于PSO得到的航線是離散的軌跡點,在此基礎上,利用三次樣條插值的方法對軌跡進行再優化,可以得到更加平滑且連續的無人機軌跡,進而證實運用三次樣條插值算法進行無人機航線再優化更符合無人機實際飛行

通過前后的仿真對比可以看出,基于PSO得到的航線是離散的軌跡點;經過三次樣條插值優化過的無人機軌跡更加平滑且連續,證明運用三次樣條插值算法進行無人機航線再優化更符合無人機實際飛行。

3.2.3 正常狀態下多無人機任務規劃

為與故障后的任務規劃結果進行對比,首先基于MSDPSO進行正常狀態下的多無人機協同任務分配,然后利用三次樣條插值算法進行無人機的航跡優化,在各約束條件下并結合相關參數進行了如圖7所示的仿真實驗。

紅星表示無人機的起始點;不同顏色的實線是為驗證基于MSDPSO在無人機群無故障場景下的有效性,通過仿真實驗得到每架無人機不同的打擊任務規劃,同時與圖8、圖9的故障場景進行對比實驗

根據仿真結果可知,基于MSDPSO各無人機在正常狀態下均優化得到最優打擊任務分配,實現了無人機多對一的打擊場景,且結合多無人機航跡規劃,成功實現了對障礙物的避障,證明了改進算法具有良好的應用有效性。

3.2.4 故障后多無人機任務規劃

假定該12架無人機在執行打擊任務過程中,第2、8號無人機在原航跡規劃的第3個航跡點發生機動故障,喪失部分打擊能力,無法按照原定任務進行打擊,需要整合各無人機重新進行任務規劃。如圖8所示。

紅星表示無人機的起始點;黑星表示無人機發生故障時的航跡點位置;不同顏色的實線表示的含義是第2、8號無人機發生故障前,各無人機原始的任務規劃

根據圖8仿真信息可知,故障前,第2號、8號無人機分對1號、3號目標進行打擊;且故障前已對無人機打擊次數進行了約束,此時第2、8號無人機發生故障而仍保存部分行動能力,剩余無人機的狀態并未受到影響。因此,通過減小對故障機的最短航程約束,允許故障機在能力范圍內對就近目標優先進行打擊,其他約束條件保持不變,基于MSDPSO對各無人機進行任務重規劃,繼續完成打擊任務。具體仿真結果如圖9所示。

表示有無人機發生故障后,剩余的健康無人機基于MSDPSO得到的任務規劃結果;表示第2、8號無人機故障前后的任務規劃結果;紅星表示無人機的起始點;黑星表示無人機發生故障時的航跡點位置

為與故障前無人機的任務分配形成對比,圖9在圖8的數據基礎上進行的仿真實驗,保留了第2、8號無人機故障前的航線信息,即藍實線所表示的航線。通過黑藍實線的對比,并結合仿真圖10所示的故障前后MSDPSO打擊任務分配結果可以看出,故障前,第2號、8號無人機分別對1號、3號目標點進行打擊;故障后,第2號無人機依然針對1號無人機執行打擊任務,說明2號機在故障受損的控制范圍內,基于MSDPSO可以搜索到距離自身故障位置最近的1號目標進行打擊,驗證了MSDPSO具有有效的尋優能力,而8號機轉換為對4號目標點進行打擊,說明無人機協同執行任務規劃過程中,健康無人機可以根據態勢變化,遷就故障機根據其故障狀態優先選擇目標點進行打擊。

黑色三角、黑色圓點分別表示無人機2、8號在故障前后的打擊任務分配結果

根據圖11無人機間距仿真信息,各無人機在執行任務過程中,機間距離均大于設定的最小值,滿足空間協同約束。

4 結論

針對非退出故障下多無人機執行多目標任務規劃的問題,提出了一種混合改進策略的離散粒子群算法進行求解。利用Sobol序列進行種群初始化,基于柯西算子、非線性時變的變異策略,以及引入自適應交叉學習策略,提高了算法尋優能力和收斂速度。為得到公正且信服的評估,將各無人機在多種約束條件下進行了多組蒙特卡羅模擬仿真,并與傳統離散粒子群算法和單策略改進下的算法進行了充分比較,驗證了所提出的MSDPSO的有效性。得出如下主要結論。

(1)MSDPSO比DPSO、SDPSO、NDPSO、CDPSO和RDPSO獲得更好的最優解。

(2)MSDPSO的收斂速度比各DPSO更快。

(3)混合策略改進下的DPSO可以優化得到更佳的分配方案,從而降低任務規劃成本,驗證了所提方法的有效性。