基于改進(jìn)粒子群優(yōu)化的多無人機(jī)協(xié)同航跡規(guī)劃

杜 云, 彭 瑜, 邵士凱, 劉 冰

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

近年來無人機(jī)在科學(xué)研究領(lǐng)域和市場(chǎng)應(yīng)用中,都得到了越來越多的關(guān)注[1]。隨著技術(shù)的快速發(fā)展,無人機(jī)自身性能不斷增強(qiáng),極大地加速和擴(kuò)展了無人機(jī)在軍事和民事領(lǐng)域的應(yīng)用。作為無人機(jī)應(yīng)用的重要方向之一,多無人機(jī)協(xié)同飛行備受關(guān)注。

在多無人機(jī)協(xié)同飛行過程中,航跡規(guī)劃系統(tǒng)為無人機(jī)飛行提供航跡指引,是實(shí)現(xiàn)無人機(jī)協(xié)同作戰(zhàn)的關(guān)鍵技術(shù)之一。協(xié)同航跡規(guī)劃可得到滿足無人機(jī)性能約束、機(jī)群空間和時(shí)間協(xié)同關(guān)系的最優(yōu)航跡,是無人機(jī)實(shí)現(xiàn)自主飛行的重要保障。

當(dāng)前,有不少學(xué)者對(duì)多無人機(jī)協(xié)同航跡規(guī)劃算法進(jìn)行了研究。文獻(xiàn)[2]提出一種基于“追蹤”思想的改進(jìn)A*算法對(duì)航跡求解并通過仿真實(shí)驗(yàn)驗(yàn)證算法有效性；文獻(xiàn)[3]提出一種改進(jìn)模擬退火算法,將人工蜂群與模擬退火相結(jié)合在二維空間內(nèi)取得較好結(jié)果；文獻(xiàn)[4]提出使用人工勢(shì)場(chǎng)算法描述最優(yōu)控制問題中的約束條件,以降低求解難度,并引入起飛時(shí)間為優(yōu)化變量完成多無人機(jī)系統(tǒng)的協(xié)同,通過仿真驗(yàn)證得到可行方案；文獻(xiàn)[5]采用合作型協(xié)同多種群粒子群優(yōu)化算法規(guī)劃出滿足可飛行要求的路徑,時(shí)間協(xié)同方面是采用五次PH路徑法調(diào)整路徑的距離以達(dá)到近似相等來保證同時(shí)達(dá)到,雖可實(shí)現(xiàn)時(shí)間協(xié)同要求,但破壞了路徑最優(yōu)性；協(xié)同航跡規(guī)劃存在約束條件多、復(fù)雜程度高、計(jì)算量大、實(shí)時(shí)性要求高等特點(diǎn),上述文獻(xiàn)雖可實(shí)現(xiàn)協(xié)同航跡規(guī)劃,但在規(guī)劃實(shí)時(shí)性、尋優(yōu)成功率等方面仍有較大提升空間。

針對(duì)現(xiàn)有航跡規(guī)劃算法過早收斂和易陷入局部最優(yōu)的缺點(diǎn),以及改進(jìn)算法復(fù)雜度高、運(yùn)算時(shí)間較長(zhǎng)的不足,提出一種改進(jìn)粒子群算法,利用參數(shù)調(diào)整策略加強(qiáng)粒子搜索能力；設(shè)置最大速度兼顧搜索的全面性和精度；引入混沌映射改善粒子質(zhì)量；設(shè)計(jì)最優(yōu)位置取代機(jī)制加快收斂速度。最后,將綜合改進(jìn)算法應(yīng)用于多無人機(jī)協(xié)同航跡規(guī)劃仿真實(shí)驗(yàn)中,驗(yàn)證了改進(jìn)算法的優(yōu)越性。

1 航跡規(guī)劃數(shù)學(xué)模型

1.1 航跡表示

航跡規(guī)劃的目的是在三維空間內(nèi)尋找一條滿足各種約束條件的最優(yōu)路徑。在整個(gè)解空間內(nèi)使用三維坐標(biāo)系(x,y,z)來表示搜索到的航跡點(diǎn)位置,航跡點(diǎn)滿足以下條件：

{(x,y,z)|xmin≤x≤xmax,ymin≤y≤ymax,

zmin≤z≤zmax}

(1)

式(1)中：xmin、xmax、ymin、ymax、zmin、zmax表示解空間的邊界值。搜索到的航跡點(diǎn)序列通過平滑的曲線連接起來形成航跡。

1.2 協(xié)同航跡規(guī)劃約束描述

1.2.1 最大航程約束

最大航程約束是根據(jù)無人機(jī)攜帶的燃料總量決定的,最大航程記作Lmax,若整條航跡由n個(gè)航跡點(diǎn)組成,則第i段航程可表示為li,總航程L滿足：

(2)

1.2.2 最大轉(zhuǎn)彎角/俯仰角約束

最大轉(zhuǎn)彎角約束即最小轉(zhuǎn)彎半徑約束是在水平方向上由于無人機(jī)自身機(jī)動(dòng)性能的限制,設(shè)任意一架無人機(jī)第i段航跡的水平投影為ai=(xi-xi-1,yi-yi-1),最大轉(zhuǎn)彎角為θmax,轉(zhuǎn)彎角[6]可表示為

(3)

最大俯仰角是在豎直方向上對(duì)當(dāng)前航跡點(diǎn)到下一個(gè)航跡點(diǎn)做俯仰運(yùn)動(dòng)時(shí)的角度限制,設(shè)最大俯仰角為φmax,兩個(gè)相鄰航跡點(diǎn)豎直高度差為|zi-zi-1|,則俯仰角約束[7]可表示為

(4)

1.2.3 飛行高度約束

為保證無人機(jī)飛行安全,飛行高度不宜過低或過高。設(shè)hi表示第i段航跡的飛行高度,hmin表示最低飛行高度,hmax表示最大飛行高度,該約束表示為

hmin≤hi≤hmax,i=1,2,…,n

(5)

1.2.4 空間協(xié)同約束

空間協(xié)同約束是對(duì)多無人機(jī)協(xié)同飛行時(shí)空間位置關(guān)系的限制,要求無人機(jī)集群之間的距離應(yīng)大于最小安全距離,即空間協(xié)同約束可表示為

s>smin

(6)

式(6)中：s為無人機(jī)之間距離；smin為最小安全距離。

1.2.5 時(shí)間協(xié)同約束

時(shí)間協(xié)同約束是對(duì)無人機(jī)集群到達(dá)目標(biāo)時(shí)間的限制?？煞譃橐韵聝煞N情況：①?gòu)?qiáng)協(xié)同。設(shè)Li為一條航跡的長(zhǎng)度,無人機(jī)速度范圍為[vmin,vmax],則可解出每架無人機(jī)到達(dá)目標(biāo)點(diǎn)的時(shí)間范圍ti=[Li/vmax,Li/vmin],若sj=t1∩t2…∩tn為非空集,則取集合sj中最小值作為達(dá)到時(shí)間。②弱協(xié)同。因無人機(jī)性能原因?qū)е聼o法在同一時(shí)刻達(dá)到,則取一個(gè)可接受的最小時(shí)間間隔[tmin,tmax]作為達(dá)到時(shí)間。

1.3 威脅約束模型

建立飛行環(huán)境模型是完成協(xié)同航跡規(guī)劃的前提,研究考慮的威脅包括雷達(dá)探測(cè)威脅和山峰威脅。

1.3.1 雷達(dá)威脅

雷達(dá)是無人機(jī)主要威脅之一,其探測(cè)能力與周圍復(fù)雜環(huán)境有關(guān)。當(dāng)航跡點(diǎn)在雷達(dá)最大探測(cè)距離內(nèi),則表示無人機(jī)在雷達(dá)威脅范圍內(nèi)。雷達(dá)威脅數(shù)學(xué)模型可表示為

Ldanger=(xk,yk,zk,rk)

(7)

式(7)中：xk、yk、zk表示雷達(dá)威脅源的中心位置；rk表示雷達(dá)探測(cè)半徑。

1.3.2 山峰威脅

無人機(jī)在執(zhí)行任務(wù)時(shí)難免遇到一些不可穿越的山峰障礙,規(guī)劃的航跡需避免與山峰碰撞。單個(gè)山峰威脅可表示[8]為

(8)

式(8)中：xm、ym、zm表示山峰威脅的三維坐標(biāo)；a、b表示山峰的起始位置；c表示山峰的高度系數(shù)；d為高度調(diào)節(jié)參數(shù)；i表示山峰的跨度范圍。調(diào)整上述參數(shù)可改變山峰的位置、跨度和高度。

1.4 適應(yīng)度函數(shù)模型

無人機(jī)飛行代價(jià)包括飛行能量消耗(由航程決定)、山峰碰撞代價(jià)、雷達(dá)威脅、飛行高度、轉(zhuǎn)彎角、俯仰角、無人機(jī)間距等指標(biāo)。定義適應(yīng)度函數(shù)[9]為

F=w1f1+w2f2+w3f3+w4f4+w5f5+w6f6

(9)

式(9)中：F為總代價(jià)；f1為航程代價(jià)；f2為威脅代價(jià),包括雷達(dá)威脅和山峰威脅；f3為飛行高度代價(jià)；f4為轉(zhuǎn)彎角代價(jià),f5為俯仰角代價(jià),f6為機(jī)間距代價(jià)；w表示各項(xiàng)指標(biāo)所占的權(quán)重,且滿足：

w1+w2+w3+w4+w5+w6=1

(10)

2 基本粒子群算法及其改進(jìn)

2.1 基本粒子群算法簡(jiǎn)介

粒子群算法是模擬鳥群搜索食物的方法,假設(shè)在一個(gè)D維的目標(biāo)搜索空間中,有m個(gè)代表問題潛在解的粒子組成一個(gè)種群x=[x1,x2,…,xm],第i個(gè)粒子的信息可以表示為xi=[xi1,xi2,…,xiD]T,速度為vi=[vi1,vi2,…,viD]T。算法先進(jìn)行初始化,然后通過迭代找到最優(yōu)解。每一次迭代中,粒子通過跟蹤個(gè)體極值和群體極值進(jìn)行信息交流,再根據(jù)式(11)和式(12)更新自己的速度vi和位置xi。

(11)

(12)

式中：w為慣性權(quán)重；c1和c2為兩個(gè)學(xué)習(xí)因子；r表示(0,1)的隨機(jī)數(shù)。

2.2 改進(jìn)粒子群算法

基本粒子群算法規(guī)則簡(jiǎn)單、易于仿真。但在多維度優(yōu)化問題求解上存在收斂速度慢、易陷入局部最優(yōu)等缺點(diǎn)。針對(duì)這些不足提出改進(jìn)粒子群算法。

2.2.1 參數(shù)調(diào)整

慣性權(quán)重w和學(xué)習(xí)因子c1和c2在很大程度上影響著粒子速度的更新。已有文獻(xiàn)證明慣性權(quán)重較大時(shí)有助于全局搜索,較小時(shí)有助于加快收斂[10],常采用如下所示線性遞減方式：

wt=wmax-(wmax-wmin)(t/T)

(13)

式(13)中：t表示當(dāng)前迭代次數(shù)；wmax和wmin分別表示慣性權(quán)重的最大值和最小值；T表示最大迭代次數(shù)。分析可知,學(xué)習(xí)因子c1和c2也起到影響粒子搜索方向的作用。為加快粒子群體在迭代學(xué)習(xí)過程中向最優(yōu)解靠近,與此同時(shí)避免種群陷入局部最優(yōu),對(duì)學(xué)習(xí)因子c1和c2進(jìn)行自適應(yīng)調(diào)幅設(shè)計(jì),具體規(guī)律為

c1=cmin+(cmax-cmin)(t/T)

(14)

c2=cmax-(cmax-cmin)(t/T)

(15)

迭代初期c2較大可引導(dǎo)粒子從當(dāng)前位置向全局最優(yōu)解的方向搜索,有助于提升收斂速度,后期c1較大則是為了強(qiáng)化粒子個(gè)體的搜索能力,防止種群堆積在群體最優(yōu)解附近進(jìn)行重復(fù)搜索導(dǎo)致搜索停滯,避免算法陷入局部最優(yōu)。

2.2.2 混沌初始化

粒子群算法的收斂速度和解的好壞受初始粒子分布的影響。考慮到Logistic混沌[11]有較好的均勻分布性,設(shè)計(jì)采用Logistic混沌進(jìn)行粒子群位置初始化,基本公式為

xn+1=μxn(1-xn)

(16)

式(16)中：xn表示第n個(gè)混沌變量；μ為預(yù)先設(shè)定常數(shù)。當(dāng)xn∈(0,1)且μ∈[0,4]時(shí),映射系統(tǒng)處于混沌狀態(tài)。當(dāng)μ=4時(shí),系統(tǒng)在[0,1]處于混沌狀態(tài)。

為說明Logistic混沌映射初始化的優(yōu)越性,做出Logistic混沌映射與rand命令在[0,1]范圍的對(duì)比圖。由圖1可看出混沌映射的取值分布更均勻。混沌映射能提高初始粒子的質(zhì)量,增加粒子種群的多樣化、有效防止種群過早收斂,增強(qiáng)算法的合理性。

圖1 混沌映射與隨機(jī)數(shù)對(duì)比圖

2.2.3 取代策略

遺傳算法中的交叉行為和變異行為可有效提升種群多樣性,增強(qiáng)全局搜索能力。借鑒遺傳算法,提出一種最優(yōu)位置取代策略,具體設(shè)計(jì)過程如下：種群中所有粒子完成某一迭代循環(huán)后,計(jì)算每個(gè)粒子的適應(yīng)度值,并根據(jù)適應(yīng)度大小進(jìn)行排序。適應(yīng)度值較差的粒子說明其位置距離最優(yōu)解較遠(yuǎn)或進(jìn)入威脅區(qū)域,參考價(jià)值不高,對(duì)這些粒子進(jìn)行剔除,用性能較好的粒子位置取代性能較差的粒子。若完全進(jìn)行取代,則會(huì)出現(xiàn)重復(fù)搜索,會(huì)增加陷入局部最優(yōu)和搜索停滯的可能性。故綜合考慮,設(shè)計(jì)在取代的位置和速度小范圍內(nèi)進(jìn)行偏移,從而提升效率,并增加搜索多樣性。具體取代公式為

xbad=xgood+2ρ1(rand-0.5)

(17)

vbad=vbad+2ρ2(rand-0.5)

(18)

式中：xbad為適應(yīng)度較差的粒子位置;xgood為適應(yīng)度較好的粒子位置；ρ1為位置偏移半徑；vbad為被取代的粒子速度；ρ2為速度偏移半徑。

2.2.4 調(diào)速機(jī)制

傳統(tǒng)粒子群算法的最大速度vmax為定值,難以同時(shí)兼顧收斂速度和搜索精度兩項(xiàng)指標(biāo)。因此提出一種調(diào)速機(jī)制改進(jìn)策略,具體過程如下。

將基本粒子群中的最大速度由定值改為“階梯式”。前期最大速度較大,雖搜索粗糙,但可擴(kuò)大粒子的搜索范圍,增強(qiáng)多樣性；中期最大速度適當(dāng)調(diào)小,兼顧收斂速度和精度；后期再次減小,使粒子進(jìn)行更細(xì)致的搜索。調(diào)速機(jī)制公式為

(19)

式(19)中：v1>v2>v3。調(diào)速機(jī)制能兼顧不同迭代階段的全面搜索和精確搜索的要求,前期側(cè)重全局搜索能力,后期側(cè)重搜索精度,中期作為過渡期平衡兩種性能。調(diào)速機(jī)制可靈活調(diào)整參數(shù),加強(qiáng)算法的通用性。

2.3 改進(jìn)算法步驟

基于上述改進(jìn)策略,提出了無人機(jī)協(xié)同航跡規(guī)劃算法,記為RPSO算法。具體步驟如下。

(1)設(shè)置無人機(jī)的起點(diǎn)和終點(diǎn),設(shè)定山峰和雷達(dá)的位置、作用半徑與無人機(jī)最小安全距離。

(2)設(shè)置種群總數(shù)N、求解維度D、最大迭代次數(shù)T,根據(jù)式(13)～式(15)對(duì)慣性權(quán)重和學(xué)習(xí)因子初始化,根據(jù)式(19)對(duì)最大速度進(jìn)行設(shè)定,對(duì)個(gè)體最優(yōu)值和種群最優(yōu)值初始化。使用Logistic混沌映射,對(duì)粒子的位置和速度進(jìn)行初始化。

(3)進(jìn)行迭代搜索,計(jì)算每個(gè)粒子航跡點(diǎn)的代價(jià),與個(gè)體最優(yōu)值和種群最優(yōu)值做比較。若小于個(gè)體最優(yōu)值,則更新個(gè)體最優(yōu)值；若小于種群最優(yōu)值,則更新種群最優(yōu)值。

(4)完成速度位置的更新。若計(jì)算出的速度大于設(shè)定的最大速度vmax,則取值為最大速度。

(5)根據(jù)步驟(4),對(duì)計(jì)算出的航跡代價(jià)進(jìn)行排序,并完成粒子位置和速度的取代更新。

(6)根據(jù)當(dāng)前迭代次數(shù),調(diào)整最大速度。判斷是否到達(dá)最大迭代次數(shù),若未達(dá)到,轉(zhuǎn)到步驟(3),否則向下執(zhí)行。

(7)搜索完成,輸出最優(yōu)解。

3 仿真實(shí)驗(yàn)與結(jié)果分析

針對(duì)提出的算法進(jìn)行仿真實(shí)驗(yàn),并對(duì)結(jié)果進(jìn)行分析。具體仿真環(huán)境：CPU為intel Corei5處理器,主頻2.6 GHz,操作系統(tǒng)為windows7 64位,內(nèi)存為4 GB,在MATLAB R2016a環(huán)境下實(shí)現(xiàn)。

3.1 仿真條件

設(shè)定無人機(jī)速度范圍為[0,10 m/s],相鄰兩個(gè)航跡點(diǎn)之間最大轉(zhuǎn)彎角與最大俯仰角均為45°；設(shè)置地形環(huán)境,具體參數(shù)如表1所示。無人機(jī)數(shù)量8架,每架無人機(jī)的起點(diǎn)位置和終點(diǎn)位置參數(shù)如表2所示。

表1 地形威脅參數(shù)

表2 無人機(jī)起點(diǎn)和終點(diǎn)位置

基本粒子群算法參數(shù)設(shè)定：種群數(shù)N=500,最大迭代次數(shù)T=120,求解維度D=40,慣性權(quán)重w=0.8,學(xué)習(xí)因子c1=c2=2,最大速度vmax=1。RPSO的慣性權(quán)重從2.2遞減至1.5,c1從0.2遞增至2.2,c2從2.2遞減至0.2。V1取(ymax-ymin)/1 000,V2取0.75V1,V3取0.5V1。無人機(jī)飛行過程中的最小安全距離設(shè)置為20 m。

3.2 仿真結(jié)果與分析

分別使用PSO算法、Elhoseny[12]提出的MGA(modified genetic algorithm)和Tian等[13]提出的MPSO(modified particle swarm optimization)以及RPSO算法,進(jìn)行100次仿真實(shí)驗(yàn)。

由實(shí)驗(yàn)得出幾種算法在兩種不同的規(guī)劃算法下的平均運(yùn)行時(shí)間,基本PSO算法用時(shí)17.48 s,RPSO算法用時(shí)17.5 s,表明改進(jìn)方案對(duì)算法求解的運(yùn)行時(shí)間沒有產(chǎn)生明顯影響,且優(yōu)于MGA算法的32.4 s和MPSO算法的21.66 s,表明改進(jìn)算法在快速性方面的優(yōu)勢(shì)。圖2和圖3所示分別為立體航跡對(duì)比和代價(jià)收斂對(duì)比,可見設(shè)計(jì)的RPSO算法收斂速度最快、飛行代價(jià)最低、航線平滑性最佳。

圖2 立體航跡對(duì)比

圖3 迭代收斂對(duì)比

圖4所示為4種算法的平均代價(jià)折線,從圖4中可明顯看出，PSO算法與MGA算法平均代價(jià)波動(dòng)性較大,且最小值偏高,由此可知算法搜索的航線路程較遠(yuǎn)或未成功規(guī)避威脅與障礙。MPSO算法與RPSO算法的代價(jià)折線較小且穩(wěn)定,因RPSO算法的代價(jià)折線整體在MPSO算法的折線圖下,說明RPSO算法性能優(yōu)于MPSO算法,且RPSO算法在實(shí)驗(yàn)中均沒有出現(xiàn)撞山、進(jìn)入雷達(dá)探測(cè)區(qū)域。

圖4 代價(jià)折線

4種算法的性能對(duì)比如表3所示,表3中代價(jià)為100次仿真實(shí)驗(yàn)中航跡代價(jià)的平均值；成功率為仿真結(jié)果中代價(jià)不高于1.3的航跡線所占100次實(shí)驗(yàn)的比重；表中次數(shù)為所有航線代價(jià)達(dá)到收斂所需次數(shù)的平均值,若規(guī)劃結(jié)果碰到障礙物或航線代價(jià)高于1.3,則該次規(guī)劃的收斂次數(shù)取最大迭代次數(shù)T。結(jié)果表明基本粒子群算法的平均代價(jià)為1.401,成功率僅為41%,達(dá)到收斂平均需要迭代116次,而改進(jìn)后的RPSO算法規(guī)劃出航線的平均代價(jià)為1.078,成功率為100%,達(dá)到收斂平均需要43次。

表3 性能對(duì)比

表3說明RPSO算法較PSO算法在代價(jià)性能上提升23.05%,在收斂所需次數(shù)上提升62.93%,成功率提升59%,為4種算法中性能最佳的算法。

規(guī)劃出航跡后可計(jì)算出總航程,根據(jù)設(shè)定的速度范圍可得機(jī)群滿足強(qiáng)協(xié)同要求,預(yù)計(jì)到達(dá)時(shí)間ET=229.6 s,每架無人機(jī)的速度為

(20)

由RPSO算法規(guī)劃出的結(jié)果在20個(gè)航跡點(diǎn)處的轉(zhuǎn)彎角和俯仰角均滿足要求,如圖5所示。此外無人機(jī)之間距離均大于設(shè)定的最小安全距離,如圖6所示，滿足空間協(xié)同要求。

圖5 轉(zhuǎn)彎角與俯仰角

圖6 機(jī)間距

4 結(jié)論

(1)慣性權(quán)重和學(xué)習(xí)因子的調(diào)整,實(shí)現(xiàn)粒子在保持慣性和向最優(yōu)粒子學(xué)習(xí)兩種行為上達(dá)到較好平衡。

(2)混沌映射的引入改善了粒子初始位置的分布；設(shè)計(jì)取代策略加快了算法收斂速度。

(3)調(diào)速機(jī)制的提出兼顧了粒子群算法的全局搜索能力和局部搜索能力。

(4)通過多無人機(jī)協(xié)同航跡規(guī)劃仿真實(shí)驗(yàn),說明RPSO算法能有效規(guī)劃出高質(zhì)量協(xié)同飛行路徑。