于鴻達(dá)， 王從慶， 賈 峰， 劉 陽(yáng)

(南京航空航天大學(xué)，南京 211100)

0 引言

多無(wú)人機(jī)航跡規(guī)劃是無(wú)人機(jī)自主執(zhí)行任務(wù)以及順利完成任務(wù)的先決條件之一[1]。因此無(wú)人機(jī)飛行前，一般會(huì)根據(jù)其飛行性能、任務(wù)和已經(jīng)獲得的威脅信息設(shè)計(jì)出多條離線飛行航跡[2]。遺傳算法[3]、蟻群算法[4]、人工蜂群算法[5]以及粒子群算法[6]等群體智能算法越來(lái)越多地應(yīng)用于多無(wú)人機(jī)航跡規(guī)劃問(wèn)題。文獻(xiàn)[7]運(yùn)用Voronoi圖的方法并采用協(xié)同策略實(shí)現(xiàn)了滿足時(shí)間約束的多無(wú)人機(jī)航跡規(guī)劃；文獻(xiàn)[8]分別對(duì)兩目標(biāo)決策和三目標(biāo)決策運(yùn)用多目標(biāo)優(yōu)化算法得到了所需要的結(jié)果；文獻(xiàn)[9]運(yùn)用數(shù)學(xué)方法實(shí)現(xiàn)了滿足多約束的多無(wú)人機(jī)航跡規(guī)劃；文獻(xiàn)[10]將NSGA-II算法與Nash Equilibrium方法相結(jié)合實(shí)現(xiàn)無(wú)人機(jī)從起始位置到目標(biāo)位置，再由目標(biāo)位置到終止位置的航跡規(guī)劃；文獻(xiàn)[11]通過(guò)遺傳算法得到了多無(wú)人機(jī)的航跡，并對(duì)其進(jìn)行了平滑處理。

但是目前的多無(wú)人機(jī)航跡規(guī)劃都存在一些問(wèn)題：考慮目標(biāo)單一、航跡規(guī)劃約束分析不全面或是最后只生成了二維的航跡規(guī)劃[12]。所以本文為了解決多無(wú)人機(jī)航跡規(guī)劃存在的問(wèn)題，對(duì)航跡空間進(jìn)行了建模以及對(duì)多無(wú)人機(jī)航跡規(guī)劃進(jìn)行了約束分析，同時(shí)在航跡規(guī)劃空間設(shè)計(jì)和規(guī)劃了多個(gè)航點(diǎn)，并對(duì)航點(diǎn)進(jìn)行了分配，最后使用一種混合粒子群算法完成了多無(wú)人機(jī)三維航跡規(guī)劃且進(jìn)行了仿真驗(yàn)證。

1 地圖環(huán)境建模

本文中，航跡規(guī)劃的環(huán)境為城市環(huán)境，所以采用的地圖模型劃分為基準(zhǔn)地形模型、樓房建筑等障礙區(qū)域的建模以及威脅區(qū)域3個(gè)部分。

基準(zhǔn)地形建模時(shí)，將飛行區(qū)域設(shè)為500 m×500 m的直角坐標(biāo)區(qū)域，并且生成隨機(jī)地表來(lái)表達(dá)城市環(huán)境中的地形起伏。

樓房建筑等障礙區(qū)域的建模采用了圓柱形模型，圓柱形模型的數(shù)學(xué)描述為

(1)

式中：Li(x,y,z)表示第i座建筑；(xi,yi)表示第i座建筑的中心坐標(biāo)；Ri表示第i座建筑的半徑；Zi表示第i座建筑的高度；ε表示建筑物之間的最小安全距離。

對(duì)于威脅區(qū)域，一般是指電磁干擾區(qū)域、禁飛區(qū)域以及一些軍事探測(cè)區(qū)域等，本文采用了半球形模型來(lái)對(duì)威脅區(qū)域建模，其數(shù)學(xué)描述為

(2)

式中：Wi(x,y,z)表示第i個(gè)威脅區(qū)域；(xi,yi,0)表示第i個(gè)威脅區(qū)域的中心；ri表示威脅區(qū)域半徑。

用上述方法對(duì)航跡規(guī)劃空間進(jìn)行建模，結(jié)果如圖1所示。

圖1 航跡規(guī)劃空間建模Fig.1 Modeling of path planning space

2 多無(wú)人機(jī)航跡規(guī)劃約束分析及代價(jià)函數(shù)

2.1 子無(wú)人機(jī)約束分析

(3)

2) 剩余飛行時(shí)間約束。無(wú)人機(jī)在執(zhí)行一次任務(wù)過(guò)程中，其剩余飛行時(shí)間也是評(píng)價(jià)無(wú)人機(jī)飛往航跡節(jié)點(diǎn)Pi的代價(jià)因素之一，可以用數(shù)學(xué)公式表示為

(4)

3) 飛行地形約束。地形約束可以是地理上的不可飛區(qū)域、未經(jīng)允許的禁飛區(qū)域以及雷達(dá)等電磁干擾威脅區(qū)域。

對(duì)于樓房建筑類地形約束區(qū)域，地形約束可表示為

(5)

電磁干擾威脅區(qū)域約束可以表示為

(6)

s.t.DkPi

2.2 多無(wú)人機(jī)約束分析

1) 無(wú)人機(jī)數(shù)量約束。多無(wú)人機(jī)航跡規(guī)劃需要對(duì)多個(gè)無(wú)人機(jī)進(jìn)行有效分配,實(shí)現(xiàn)無(wú)人機(jī)利用價(jià)值的最大化，選取合理的無(wú)人機(jī)派出數(shù)量,同時(shí)也不能超出最大無(wú)人機(jī)使用數(shù)量，即

N

(7)

式中，Nmax為可用無(wú)人機(jī)的最大數(shù)量。

2) 航跡節(jié)點(diǎn)間距約束。無(wú)人機(jī)執(zhí)行任務(wù)的區(qū)域是在某一個(gè)確定的范圍內(nèi)，因此,當(dāng)航跡節(jié)點(diǎn)間距過(guò)小時(shí),di-dj<ε，就會(huì)出現(xiàn)航跡節(jié)點(diǎn)冗余的情況，即兩個(gè)相聚較近的航跡節(jié)點(diǎn)中有一個(gè)航跡節(jié)點(diǎn)是無(wú)效的,因此需要對(duì)航跡節(jié)點(diǎn)間距進(jìn)行約束，即

Dij∈[Dmin,Dmax]

(8)

式中，Dij為第i個(gè)節(jié)點(diǎn)和第j個(gè)節(jié)點(diǎn)的間距。

2.3 代價(jià)函數(shù)

本文中,航跡代價(jià)函數(shù)的確定是根據(jù)航跡節(jié)點(diǎn)距離、無(wú)人機(jī)剩余飛行時(shí)間、任務(wù)執(zhí)行效率、環(huán)境地形等因素評(píng)價(jià)的，同時(shí)也考慮了多無(wú)人機(jī)間的約束關(guān)系，最終確定飛行航跡。

綜上所述，可構(gòu)造無(wú)人機(jī)k航跡節(jié)點(diǎn)分配后的代價(jià)函數(shù)為

(9)

s.t.N

3 航跡規(guī)劃算法

3.1 航跡節(jié)點(diǎn)規(guī)劃方法

設(shè)航跡節(jié)點(diǎn)總數(shù)為B，每一個(gè)航點(diǎn)代表需要搜索的目的地。多無(wú)人機(jī)的出發(fā)地點(diǎn)與搜索結(jié)束后無(wú)人機(jī)降落地點(diǎn)均相同，分別稱為起點(diǎn)Ps與終點(diǎn)Pf。除去起點(diǎn)與終點(diǎn)，應(yīng)有B-2個(gè)航跡節(jié)點(diǎn)被N個(gè)無(wú)人機(jī)訪問(wèn)，構(gòu)造維數(shù)為B-3+N的解空間，其解序列可寫(xiě)為

Pi=(Pi1,Pi2,Pi3,…,Pi(B-2),Pi(B-1),…,Pi(B-3+N))

(10)

式中，Pi1,…,Pi(B-2)代表不同的中間航跡節(jié)點(diǎn)編號(hào)，Pi(B-1),…,Pi(B-3+N)為插入的分割點(diǎn)，用于分割不同無(wú)人機(jī)將要走過(guò)的航跡節(jié)點(diǎn)序列。當(dāng)產(chǎn)生一個(gè)可行解時(shí)，分割點(diǎn)Pi(B-1),…,Pi(B-3+N)插入Pi1,…,Pi(B-2)中，所以由Pi(B-1),…,Pi(B-3+N)分割出來(lái)的N個(gè)序列代表了N個(gè)不同無(wú)人機(jī)所要飛行的路線，通過(guò)變換分割點(diǎn)在序列中的不同位置與航跡節(jié)點(diǎn)序列的排序方式就可改變不同無(wú)人機(jī)所經(jīng)過(guò)的航跡節(jié)點(diǎn)，從而尋找最優(yōu)路線，簡(jiǎn)化了無(wú)人機(jī)群目標(biāo)搜索規(guī)劃問(wèn)題的計(jì)算難度。其變換過(guò)程如圖2所示。

圖2 分割點(diǎn)插入航跡節(jié)點(diǎn)示意圖Fig.2 Inserting of segmentation point into path nodes

3.2 粒子群算法

假設(shè)在D維空間中投放N個(gè)粒子，第i個(gè)粒子的位置和速度分別為Xi=(xi1,xi2,…,xiD)和Vi=(vi1,vi2,…,viD)，該粒子所經(jīng)歷的歷史最優(yōu)位置記作Pi=(pi1,pi2,…,piD),整個(gè)種群所經(jīng)歷的最優(yōu)位置記作G=(g1,g2,…,gD)。

粒子根據(jù)下面的公式來(lái)更新其速度和位置，即

Vi(t+1)=ω·Vi(t)+c1·r1·(Pi(t)-Xi(t))+
c2·r2·(G(t)-Xi(t))

(11)

Xi(t+1)=Xi(t)+Vi(t+1)

(12)

式中：ω為慣性權(quán)重；c1和c2為加速系數(shù)；r1和r2為[0,1]之間的隨機(jī)數(shù)；t為當(dāng)前迭代次數(shù)；粒子速度設(shè)置限制閾值Vmax，將粒子速度控制在[-Vmax,Vmax]內(nèi)。

針對(duì)PSO算法可能出現(xiàn)早熟現(xiàn)象的問(wèn)題，通過(guò)引入適應(yīng)度方差來(lái)跟蹤算法當(dāng)前的狀態(tài)。

粒子群適應(yīng)度方差σ2反映的是種群中全體粒子的離散程度，可以表示為

(13)

(14)

3.3 差分進(jìn)化操作

為了解決粒子早熟問(wèn)題，通過(guò)引入差分進(jìn)化操作，對(duì)早熟的粒子進(jìn)行一系列操作來(lái)維持群體的多樣性，改善算法的全局搜索性能，防止算法陷入局部最優(yōu)。

對(duì)早熟的粒子進(jìn)行變異操作，即

ui=xr1(t)+F[xr2(t)-xr3(t)]

(15)

式中：t為當(dāng)前迭代次數(shù)；xr1,xr2,xr3分別為從粒子種群中選取的互不相同的3個(gè)個(gè)體；F為縮放比例因子。

在交叉操作中，新的種群Ni由隨機(jī)矢量Ui和目標(biāo)矢量Ti共同產(chǎn)生。

(16)

式中：j=1,2,…,D，D為空間維數(shù)；Pc∈[0,1]，為交叉概率，rand(0,1)為0到1之間的隨機(jī)數(shù)。選擇操作采用貪婪策略，即

(17)

式中,fitness為適應(yīng)度函數(shù)，將差分進(jìn)化操作完成后得到的粒子作為新的粒子，完成了粒子的進(jìn)化。

3.4 自適應(yīng)調(diào)整策略

慣性權(quán)重ω的取值對(duì)算法的尋優(yōu)性能有很大的影響。在迭代初期，一般選用較大的慣性權(quán)重來(lái)加快算法全局搜索速度，而在迭代后期則取較小的慣性權(quán)重來(lái)增強(qiáng)局部尋優(yōu)能力，通過(guò)這樣的策略可以增強(qiáng)粒子群算法全局搜索與局部最優(yōu)搜索之間的協(xié)調(diào)性。所以在原算法的基礎(chǔ)上增加自適應(yīng)調(diào)節(jié)策略，即

(18)

式中：tmax為最大迭代次數(shù)；λ為控制因子。由于式中含有負(fù)指數(shù)部分，在算法的迭代初期，迭代次數(shù)t值較小，慣性權(quán)重ω較大，粒子的速度和位置在整個(gè)遍歷范圍內(nèi)更新；在迭代后期，t值較大，慣性權(quán)重ω較小，粒子的速度和位置在小范圍內(nèi)更新，所以該調(diào)節(jié)策略增強(qiáng)了算法的全局搜索與局部搜索之間的協(xié)調(diào)性。

4 仿真實(shí)驗(yàn)與分析

通過(guò)建立不同航點(diǎn)間代價(jià)非對(duì)稱的航點(diǎn)規(guī)劃問(wèn)題，與傳統(tǒng)粒子群算法進(jìn)行對(duì)比仿真，來(lái)驗(yàn)證上述算法的有效性。設(shè)定航點(diǎn)數(shù)目為15，航點(diǎn)間間距代價(jià)為非對(duì)稱，無(wú)人機(jī)個(gè)數(shù)為3，N=20,tmax=500,ωmax=0.9,ωmin=0.4,λ=20,c1=c2=1.5,Vmax=10,F=0.97,Pc=0.27。實(shí)驗(yàn)仿真是在同樣實(shí)驗(yàn)條件下對(duì)同一個(gè)航跡規(guī)劃問(wèn)題進(jìn)行10次仿真的平均統(tǒng)計(jì)，其代價(jià)函數(shù)收斂曲線見(jiàn)圖3。

圖3 混合PSO算法與標(biāo)準(zhǔn)PSO算法對(duì)比Fig.3 Comparison of hybrid PSO algorithm with standard PSO algorithm

從圖3可以看到,混合PSO算法在第41次迭代就接近收斂，并且最終于第160次迭代時(shí)收斂于48.9，而標(biāo)準(zhǔn)PSO算法在第205次迭代時(shí)才收斂，最終收斂于50.63。由此能夠得出下面結(jié)論：混合PSO算法的收斂速度比標(biāo)準(zhǔn)PSO算法更快，航跡代價(jià)更小。

本文通過(guò)設(shè)定航點(diǎn)的方式對(duì)多架無(wú)人機(jī)進(jìn)行航跡規(guī)劃。首先在航跡規(guī)劃空間設(shè)定了15個(gè)航跡節(jié)點(diǎn)并且還有若干建筑物以及威脅區(qū)域，設(shè)定多無(wú)人機(jī)航跡規(guī)劃起點(diǎn)為節(jié)點(diǎn)1(20 m，20 m，20 m)，經(jīng)過(guò)若干航點(diǎn)，最終都到達(dá)終點(diǎn)節(jié)點(diǎn)15(450 m,450 m,200 m)，航點(diǎn)間間距代價(jià)為非對(duì)稱，對(duì)算法的參數(shù)進(jìn)行設(shè)置：N=80,tmax=2000,ωmax= 0.9,ωmin=0.4,λ=20,c1=c2=1.5,Vmax=10,F=0.97,Pc=0.27。對(duì)無(wú)人機(jī)設(shè)定了飛行約束條件和威脅源，并基于上述混合粒子群算法進(jìn)行了多無(wú)人機(jī)多航跡節(jié)點(diǎn)的航跡規(guī)劃，本文分別選擇了2架無(wú)人機(jī)和3架無(wú)人機(jī)進(jìn)行了航跡規(guī)劃。

航跡節(jié)點(diǎn)以及障礙物分布如表1所示，節(jié)點(diǎn)1為起點(diǎn)，節(jié)點(diǎn)15為終點(diǎn)，設(shè)定了15個(gè)航跡節(jié)點(diǎn)，7座建筑物以及2個(gè)威脅區(qū)域，通過(guò)算法仿真最終分別得到如圖4和圖5所示的2架無(wú)人機(jī)和3架無(wú)人機(jī)航跡規(guī)劃。其中，7個(gè)圓柱形區(qū)域?yàn)闃欠拷ㄖ系K物，2個(gè)半球形區(qū)域?yàn)橥{區(qū)域，航跡節(jié)點(diǎn)在圖中1～15處。

表1 航跡節(jié)點(diǎn)與障礙物分布表

圖4 2架無(wú)人機(jī)航跡規(guī)劃圖Fig.4 Path planning of two UAVs

圖5 3架無(wú)人機(jī)航跡規(guī)劃圖Fig.5 Path planning of three UAVs

從圖4和圖5可以看出，兩次仿真實(shí)驗(yàn)都完成了多架無(wú)人機(jī)航跡規(guī)劃，并且成功避開(kāi)了障礙物以及威脅干擾區(qū)域，所以本文混合粒子群算法可以有效地解決多架無(wú)人機(jī)的航跡規(guī)劃問(wèn)題。

5 結(jié)束語(yǔ)

本文針對(duì)多架無(wú)人機(jī)的航跡規(guī)劃問(wèn)題，通過(guò)設(shè)定

多個(gè)中間節(jié)點(diǎn)作為目標(biāo)點(diǎn)并運(yùn)用插入分割點(diǎn)的方法來(lái)簡(jiǎn)化尋優(yōu)過(guò)程,通過(guò)加入差分進(jìn)化操作以及自適應(yīng)調(diào)整慣性權(quán)重來(lái)改進(jìn)混合粒子群算法，最終實(shí)現(xiàn)多無(wú)人機(jī)航跡規(guī)劃，驗(yàn)證了算法的有效性并進(jìn)行了仿真驗(yàn)證。

參 考 文 獻(xiàn)

[1] 鄭昌文,嚴(yán)平,丁明躍,等.飛行器航跡規(guī)劃研究現(xiàn)狀與趨勢(shì)[J].宇航學(xué)報(bào),2007,28(6):7-12.

[2] 孫陽(yáng)光,丁明躍,周成平,等.基于量子遺傳算法的無(wú)人飛行器航跡規(guī)劃[J].宇航學(xué)報(bào),2010,31(3):648-654.

[3] PEHLIVANOGLU Y V.A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of auto-nomous UAV[J].Aerospace Science and Technology,2012,16(1):47-55.

[4] MARTINEZ-ZERON E,ACEVES-FERNANDEZ M A, GORROSTIETA-HURTADO E,et al.Method to improve airborne pollution forecasting by using ant colony optimization and neuro-fuzzy algorithms[J].International Journal of Intelligence Science,2014(4)：81-90．

[5] 張洛兵,徐流沙,吳梅.基于改進(jìn)人工蜂群算法的無(wú)人機(jī)實(shí)時(shí)航跡規(guī)劃[J].飛行力學(xué),2015,33(1)：38-47.

[6] LIN L,GOODRICH M A.Hierarchical heuristic search using a Gaussian mixture model for UAV coverage planning[J].IEEE Transactions on Cybernetics,2017,44(12):2532-2544.

[7] MA P B,FAN Z E,JI J.Cooperative control of multi-UAV with time constraint in the threat environment[C]//The IEEE Chinese Guidance,Navigation and Control Confe-rence,2014:2424-2428.

[8] AHMED F,DEB K.Multi-objective optimal path planning using elitist non-dominated sorting genetic algorithms[J].Soft Computing,2013,17(7):1283-1299.

[9] 白瑞光,孫鑫,陳秋雙,等.基于Gauss偽譜法的多UAV協(xié)同航跡規(guī)劃[J].宇航學(xué)報(bào),2014,35(9)： 1022-1029.

[10] LEE D S,PERIAUX J,GONZALEZ L F.UAS Mission Path Planning System (MPPS) using hybrid-game coupled to multi-objective optimizer[J].Journal of Dynamic Systems,Measurement and Control,2010，132(4):1-11.

[11] SAHINGOZ O K.Flyable path planning for a multi-UAV system with genetic algorithms and Bezier curves[C]//International Conference on Unmanned Aircraft Systems, IEEE,2013:41-48.

[12] 于霜,丁力,吳洪濤.基于改進(jìn)人工蜂群算法的無(wú)人機(jī)的航跡規(guī)劃[J].電光與控制,2017,24(1):19-23.