田 闊, 劉 旭

(中國(guó)飛行試驗(yàn)研究院，西安 710089)

基于多策略SSO 和改進(jìn)A*算法的無(wú)人機(jī)動(dòng)態(tài)航跡規(guī)劃

田 闊, 劉 旭

(中國(guó)飛行試驗(yàn)研究院，西安 710089)

針對(duì)無(wú)人機(jī)遇到突發(fā)威脅動(dòng)態(tài)航跡規(guī)劃問(wèn)題，提出了一種基于多策略SSO和改進(jìn)A*算法的無(wú)人機(jī)動(dòng)態(tài)航跡規(guī)劃方法。該方法將無(wú)人機(jī)航跡規(guī)劃劃分為靜態(tài)航跡規(guī)劃和突發(fā)威脅實(shí)時(shí)規(guī)避兩個(gè)階段:首先，對(duì)于靜態(tài)航跡規(guī)劃階段，采用多策略SSO優(yōu)化算法對(duì)極坐標(biāo)航跡規(guī)劃模型進(jìn)行求解，通過(guò)引入完全彈性碰撞、自適應(yīng)跳躍等機(jī)制，在有效滿足飛行性能約束的同時(shí)，提高了航跡規(guī)劃結(jié)果的可行性;其次，對(duì)于突發(fā)威脅實(shí)時(shí)規(guī)避階段，采用改進(jìn)A*算法對(duì)局部區(qū)域進(jìn)行航跡重規(guī)劃，通過(guò)拓展A*算法搜索鄰域個(gè)數(shù)和引入最小“彎折”估計(jì)代價(jià)函數(shù)，在保證實(shí)時(shí)性要求的同時(shí)，能夠規(guī)劃出更加平滑的最優(yōu)航跡。仿真結(jié)果表明，提出的方法能夠有效地給出更為滿意的無(wú)人機(jī)動(dòng)態(tài)航跡規(guī)劃路線。

航跡規(guī)劃； 無(wú)人機(jī)； 群居蜘蛛優(yōu)化； 改進(jìn)A*算法

0 引言

近年來(lái)，隨著無(wú)人機(jī)(UAV)技術(shù)的迅猛發(fā)展，其在救援搜索、精確打擊、追蹤偵察、低空突防等領(lǐng)域得到了越來(lái)越多的應(yīng)用[1]。但從實(shí)戰(zhàn)角度來(lái)看，無(wú)人機(jī)在航跡規(guī)劃、信息交換、協(xié)同配合等方面還有很多難關(guān)需要突破[2]。特別地，無(wú)人機(jī)航跡規(guī)劃作為實(shí)現(xiàn)UAV自主控制的重要環(huán)節(jié)[3]，吸引了學(xué)者們的廣泛關(guān)注。

無(wú)人機(jī)航跡規(guī)劃是指在綜合考慮外部環(huán)境因素和自身飛行性能的基礎(chǔ)上，為UAV規(guī)劃出從起飛點(diǎn)到目標(biāo)點(diǎn)且滿足各種約束條件的最優(yōu)可行航路[4-5]。PRM,A*算法,人工勢(shì)場(chǎng)以及智能優(yōu)化算法等是目前應(yīng)用較為廣泛的航跡規(guī)劃算法。文獻(xiàn)[5]提出了一種基于網(wǎng)格概率地圖法的快速航跡規(guī)劃算法，在高效實(shí)現(xiàn)航跡規(guī)劃的同時(shí)有效滿足了實(shí)際飛行需求，但是該算法無(wú)法保證得到較優(yōu)航跡；文獻(xiàn)[6]針對(duì)航跡規(guī)劃實(shí)時(shí)性問(wèn)題，設(shè)計(jì)了一種基于RRT的實(shí)時(shí)航跡規(guī)劃算法，仿真實(shí)驗(yàn)也證明了該算法的有效性，但是算法需要實(shí)時(shí)更新外部環(huán)境等信息，導(dǎo)致算法計(jì)算量相對(duì)較大；文獻(xiàn)[7]在A*算法的基礎(chǔ)上設(shè)計(jì)了一種分級(jí)規(guī)劃策略航跡規(guī)劃算法，通過(guò)初始規(guī)劃和精細(xì)規(guī)劃，可以得到最終的多條可行航跡，但是該算法以網(wǎng)格頂點(diǎn)為搜索領(lǐng)域，使得航跡“彎折”較多，導(dǎo)致航跡可飛行性降低；文獻(xiàn)[8-9]通過(guò)將進(jìn)化算法、蟻群優(yōu)化等智能優(yōu)化算法應(yīng)用于航跡規(guī)劃，進(jìn)而能夠得到最優(yōu)航跡，但是智能算法易于陷入局部最優(yōu),仍是亟需解決的問(wèn)題。研究表明UAV航跡規(guī)劃是一個(gè)NP-Hard難題，并且實(shí)際戰(zhàn)場(chǎng)三維航跡規(guī)劃可以轉(zhuǎn)化為多個(gè)二維平面航跡規(guī)劃[10]，因此研究二維突發(fā)威脅動(dòng)態(tài)航跡規(guī)劃具有重要意義。

為此，本文提出一種基于多策略SSO(Multi-Strategy Social Spider Optimization,MSSSO)[11]和改進(jìn)A*算法的無(wú)人機(jī)動(dòng)態(tài)航跡規(guī)劃算法：利用多策略SSO對(duì)航跡規(guī)劃模型進(jìn)行求解，得到靜態(tài)最優(yōu)航跡，并在此基礎(chǔ)上采用改進(jìn)A*算法對(duì)突發(fā)威脅區(qū)域進(jìn)行局部航跡再規(guī)劃。該算法通過(guò)引入完全彈性碰撞、自適應(yīng)跳躍機(jī)制、最小“彎折”估計(jì)代價(jià)函數(shù)以及拓展A*算法搜索鄰域個(gè)數(shù)，從而得到滿足飛行性能約束、有效規(guī)避突發(fā)威脅和航跡代價(jià)最小的可行飛行航跡。

1 航跡規(guī)劃建模

二維平面無(wú)人機(jī)航跡規(guī)劃具有典型研究意義，這不僅是因?yàn)榭梢詫⑷S空間航跡規(guī)劃轉(zhuǎn)為水平和垂直剖面進(jìn)行分析[2,5,10]，而且在實(shí)際應(yīng)用環(huán)境中，通常為無(wú)人機(jī)設(shè)定最小安全曲面，即無(wú)人機(jī)以一定高度進(jìn)行飛行。無(wú)人機(jī)航跡規(guī)劃的目的是尋找一條能夠滿足各種飛行約束條件，并且有效規(guī)避各種威脅的航程P{S,X1,X2,…,Xm,T}，其中,S,T分別為航跡起點(diǎn)和目標(biāo)點(diǎn)，Xi(i=1,…,m)為航跡節(jié)點(diǎn)。

定義1定義航跡節(jié)點(diǎn)Xi為多維向量，即

(1)

式中：Peri，Thri，F(xiàn)li分別表示無(wú)人機(jī)性能約束條件(Lmax，Lmin，Rmin，Hsafe分別為最大航程、最小航程、最小拐彎半徑和最低飛行高度);無(wú)人機(jī)威脅約束(pr，pm，pg，pa，pe分別為雷達(dá)威脅、導(dǎo)彈威脅、高炮威脅、大氣威脅和地形威脅)和無(wú)人機(jī)狀態(tài)信息((xi,yi);Hi，Oi，Ri，vi分別為無(wú)人機(jī)當(dāng)前位置、高度、油耗、曲率半徑和飛行速度信息)。

定義2定義無(wú)人機(jī)航跡規(guī)劃模型為航跡綜合代價(jià)最低，即

(2)

∑f(s)=ωOfO+ωHfH+ωrfr+ωmfm+
ωgfg+ωafa+ωefe

(3)

式中,fO，fH，fr，fm，fg，fa和fe分別表示油耗代價(jià)、高度代價(jià)、雷達(dá)威脅代價(jià)、導(dǎo)彈威脅代價(jià)、高炮威脅代價(jià)、大氣威脅代價(jià)和地形威脅代價(jià)。

威脅代價(jià)計(jì)算如下。由于油耗代價(jià)和高度代價(jià)分別與航程及飛行高度成正比，因此有

(4)

式中：c1，c2為比例系數(shù)；hi為第i段航程高度。對(duì)于fr，fm，fg，fa和fe，由于這些威脅與無(wú)人機(jī)和威脅中心的距離有關(guān)，因此可以將第j(j=1,2,…,m+1)段航程均分為n段(如圖1a所示)，并取n+1個(gè)分段端點(diǎn)威脅平均值作為該段航程威脅代價(jià)，即K個(gè)同類(lèi)威脅對(duì)第j段航程威脅代價(jià)fK,j為

(5)

式中：fk,j為威脅k對(duì)第j段航程的威脅代價(jià)；p(dk,Xi)為威脅k對(duì)航跡點(diǎn)Xi的威脅。根據(jù)式(5)可以得到威脅K對(duì)整個(gè)航跡的威脅代價(jià)fK(K∈{r,m,g,a,e})，即

(6)

2 靜態(tài)航跡規(guī)劃實(shí)現(xiàn)

2.1 極坐標(biāo)空間處理

對(duì)于無(wú)人機(jī)靜態(tài)航跡規(guī)劃問(wèn)題，外部飛行環(huán)境能夠事先獲取，并且無(wú)人機(jī)在飛前就已經(jīng)完成了靜態(tài)航跡規(guī)劃，因此航跡規(guī)劃模型求解精度成了問(wèn)題關(guān)鍵，本文采用群居蜘蛛優(yōu)化算法(SSO)對(duì)航跡規(guī)劃模型進(jìn)行求解。為了使得SSO更好應(yīng)用于無(wú)人機(jī)航跡規(guī)劃過(guò)程，對(duì)二維空間進(jìn)行極坐標(biāo)處理(如圖1b所示)：將S與T之間距離進(jìn)行M等分，每個(gè)分段長(zhǎng)度為ρ(合理設(shè)定M取值，可以使無(wú)人機(jī)滿足最小航程約束)。對(duì)于航跡節(jié)點(diǎn)Xi，設(shè)其極坐標(biāo)角度為θi，則Xi位置信息描述為(iρ,θi)。設(shè)直線ST與水平直角坐標(biāo)系x軸夾角為α，根據(jù)坐標(biāo)轉(zhuǎn)換公式，可以得到(xi,yi)與(iρ,θi)對(duì)應(yīng)關(guān)系，即

(7)

(8)

圖1 威脅代價(jià)計(jì)算與極坐標(biāo)轉(zhuǎn)換Fig.1 Threat cost calculation and polar transformation

2.2 多策略SSO優(yōu)化算法

研究表明，智能優(yōu)化算法在處理NP-Hard問(wèn)題時(shí)表現(xiàn)出突出優(yōu)勢(shì)，并在實(shí)際工程領(lǐng)域中得到了廣泛應(yīng)用[12]，本文以最近才被提出的SSO算法為基本群體，并引入“完全彈性碰撞”、自適應(yīng)跳躍機(jī)制以改變多策略SSO優(yōu)化算法全局尋優(yōu)能力(SSO基本原理參考有關(guān)文獻(xiàn)，不再贅述)。

2.2.1 完全彈性碰撞

(9)

從式(9)可以看出，新的個(gè)體融合了自身歷史最優(yōu)個(gè)體和當(dāng)前種群最優(yōu)個(gè)體信息，體現(xiàn)了學(xué)習(xí)融合，因此采用b′(t)對(duì)Sj(t)進(jìn)行更新，更新公式為

(10)

σjk(t)=|bk(t)-gjk(t)|

(11)

定義3t時(shí)刻，對(duì)于具有F個(gè)種群個(gè)體且采用完全彈性碰撞更新策略的蜘蛛種群，其種群樣本離散度MDt(F)定義為

(12)

從式(12)可以看出，MDt(F)反映了種群個(gè)體距離樣本中心的離散程度，取值越大，表明種群多樣性越高。

推論2種群樣本離散度MD(F)期望值為E[MDt+1(F)]，即

(13)

式中：MDt(g(t))表示g(t)離散度。

證明根據(jù)式(12)有

(14)

又因

(15)

(16)

聯(lián)立式(12)以及式(14)～式(16)，有

(17)

證畢。

圖2 “完全彈性碰撞”與A*搜索域擴(kuò)展示意圖Fig.2 Perfect elastic collision and A* search domain extension

2.2.2 自適應(yīng)跳躍機(jī)制

t時(shí)刻，選取種群適應(yīng)度最優(yōu)的前F1個(gè)進(jìn)行跳躍更新，更新公式為

(18)

F1=?F1,min+α(F1,max-F1,min)」e(ln 2t/Tmax-1)

(19)

式中：δ為(0,1)隨機(jī)數(shù)；ζ為跳躍指數(shù)；Sj,min，Sj,max和F1,min，F(xiàn)1,max分別為對(duì)應(yīng)變量最小值和最大值。個(gè)體采用式(18)更新后得到新的個(gè)體Snew，若適應(yīng)度優(yōu)于原個(gè)體則取代原個(gè)體，否則保持不變。

從式(18)和式(19)可以看出，F(xiàn)1和個(gè)體更新概率p隨著迭代次數(shù)增加，參數(shù)取值不斷自適應(yīng)調(diào)整，從而有效提高了較優(yōu)個(gè)體擾動(dòng)跳躍概率，為算法尋找到全局最優(yōu)解提供了可能。

2.3 多策略SSO優(yōu)化航跡規(guī)劃模型實(shí)現(xiàn)

采用極坐標(biāo)對(duì)空間進(jìn)行處理，不僅可以滿足最小航程約束條件，而且只需要得到系列θi就可以得到航跡節(jié)點(diǎn)信息，進(jìn)而實(shí)現(xiàn)航跡規(guī)劃。

定義4對(duì)于蜘蛛個(gè)體，定義其編碼方式為Si=(θ1,θ2,…,θM)。

定義5對(duì)于蜘蛛個(gè)體，定義其目標(biāo)函數(shù)為航跡綜合代價(jià)模型，即

(20)

(21)

式中：ΔΨi為航跡節(jié)點(diǎn)偏航角；Ψmax為最大偏航角。

基于MSSSO的靜態(tài)航跡規(guī)劃實(shí)現(xiàn)流程見(jiàn)圖3。

圖3 靜態(tài)航跡規(guī)劃實(shí)現(xiàn)流程Fig.3 Realization process of static route planning

3 突發(fā)威脅動(dòng)態(tài)航跡規(guī)劃實(shí)現(xiàn)

在執(zhí)行設(shè)定任務(wù)飛行時(shí)，無(wú)人機(jī)往往會(huì)受到突發(fā)威脅，這就要求其能夠自主完成突發(fā)威脅航跡重規(guī)劃，因此對(duì)重規(guī)劃實(shí)時(shí)性要求較高。本文采用A*算法[13]執(zhí)行突發(fā)威脅航跡重規(guī)劃過(guò)程，以生成新的局部航跡。

3.1 改進(jìn)A*算法

A*算法隸屬啟發(fā)式搜索算法范疇[14]，其通過(guò)代價(jià)函數(shù)f(n)對(duì)搜索區(qū)域內(nèi)節(jié)點(diǎn)進(jìn)行評(píng)估，從而篩選出最佳路徑節(jié)點(diǎn)列表，進(jìn)而實(shí)現(xiàn)路徑規(guī)劃。代價(jià)函數(shù)f(n)算式為

f(n)=h(n)+g(n)

(22)

式中：n為搜索區(qū)域可擴(kuò)展節(jié)點(diǎn)；h(n)為起始節(jié)點(diǎn)到n的實(shí)際代價(jià)；g(n)為n到目標(biāo)點(diǎn)的估計(jì)代價(jià)。由于基本A*算法設(shè)定擴(kuò)展搜索區(qū)域?yàn)榫W(wǎng)格中心，因此規(guī)劃出的路徑不是最短路徑，而且彎折較多，這無(wú)形中增大了無(wú)人機(jī)飛行難度(如圖2b所示的a→b→…→h路徑)，因此引入最小“彎折”估計(jì)代價(jià)函數(shù)并拓展A*算法搜索鄰域個(gè)數(shù)，從而得到更加平滑的局部航跡。

3.1.1 最小“彎折”估計(jì)代價(jià)

無(wú)人機(jī)局部航跡規(guī)劃在盡量要求航程最短的同時(shí)希望彎折程度最小，為此引入彎折程度代價(jià)，改進(jìn)后的h(n)算式為

(23)

3.1.2 搜索鄰域節(jié)點(diǎn)擴(kuò)展

將網(wǎng)格邊線進(jìn)行H等分，因此得到H+1個(gè)節(jié)點(diǎn)，規(guī)定每條網(wǎng)格邊線上的H+1個(gè)節(jié)點(diǎn)為搜索可擴(kuò)展節(jié)點(diǎn)。為了進(jìn)一步降低f(n)計(jì)算量，提高算法運(yùn)算速度，不需要全部計(jì)算出所有線段點(diǎn)上的代價(jià)函數(shù)值，而是利用網(wǎng)格中心點(diǎn)和邊線交點(diǎn)的代價(jià)值進(jìn)行估算，以圖2b中的c′點(diǎn)為例，d′為其可擴(kuò)展點(diǎn)，c′與d′距離最近邊線交接點(diǎn)w1的距離分別為l1和l2(設(shè)網(wǎng)格邊線長(zhǎng)度為1)，當(dāng)c′向d′擴(kuò)展時(shí)，代價(jià)函數(shù)f(d′)為

(24)

式中,g(c′,d′)為c′，d′所在網(wǎng)格中心的估計(jì)代價(jià)。

3.2 改進(jìn)A*算法突發(fā)威脅動(dòng)態(tài)航跡規(guī)劃實(shí)現(xiàn)

采用改進(jìn)的A*算法對(duì)突發(fā)威脅航跡進(jìn)行重規(guī)劃，分別設(shè)置OPEN和CLOSED存儲(chǔ)已生成且沒(méi)有考察的節(jié)點(diǎn)和已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)。圖4給出了基于改進(jìn)A*算法突發(fā)威脅動(dòng)態(tài)航跡規(guī)劃實(shí)現(xiàn)流程圖。

圖4 突發(fā)威脅動(dòng)態(tài)航跡規(guī)劃實(shí)現(xiàn)流程Fig.4 Realization process of sudden threat dynamic route planning

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

4.1 靜態(tài)航跡規(guī)劃實(shí)例仿真

為驗(yàn)證分析MSSSO靜態(tài)航跡規(guī)劃算法性能，采用Matlab仿真平臺(tái)對(duì)實(shí)例進(jìn)行仿真實(shí)驗(yàn)：在70 km×70 km二維空間內(nèi)，無(wú)人機(jī)從(15 km,23 km)處起飛執(zhí)行對(duì)(47 km,53 km)處敵方指揮中心打擊任務(wù)。MSSSO相關(guān)參數(shù)設(shè)置如下：ωO=0.15,ωH=0.05,ωr=0.30,ωm=0.30,ωg=0.10,ωa=0.05,ωe=0.05,n=10,F=200,F1,min=10,F1,max=30,ρ=2 km，無(wú)人機(jī)飛行性能參數(shù)參考文獻(xiàn)[7]，雷達(dá)、高炮、導(dǎo)彈、大氣威脅參數(shù)設(shè)置參考文獻(xiàn)[10]，地形威脅采用不規(guī)則圖形進(jìn)行表示。為進(jìn)一步分析MSSSO性能，分別采用基本SSO算法、粒子群優(yōu)化算法(PSO)和MSSSO進(jìn)行對(duì)比實(shí)驗(yàn)，每種算法獨(dú)立運(yùn)行50次，對(duì)比分析最終航跡結(jié)果(利用K平滑算法對(duì)3種算法航跡進(jìn)行處理)。表1給出了3種算法相關(guān)指標(biāo)對(duì)比結(jié)果，圖5給出了3種算法航跡規(guī)劃以及收斂曲線對(duì)比結(jié)果。

從圖5可以看出，MSSSO和PSO都能給出合理無(wú)人機(jī)靜態(tài)航跡規(guī)劃結(jié)果，但是SSO規(guī)劃的航跡穿越了地形威脅，會(huì)對(duì)無(wú)人機(jī)帶來(lái)較大威脅。從3種算法性能指標(biāo)和收斂曲線對(duì)比結(jié)果可以看出，無(wú)論是總航程、航跡代價(jià)還是算法運(yùn)算時(shí)間，MSSSO都要優(yōu)于其他兩種算法，這是因?yàn)镸SSSO引入完全彈性碰撞機(jī)制，個(gè)體直接向種群最優(yōu)解和自身歷史最優(yōu)解學(xué)習(xí)，提高了進(jìn)化速率，而且在算法運(yùn)算后期，自適應(yīng)跳躍機(jī)制改善了算法全局深度尋優(yōu)能力，提高了算法收斂精度。

表1 SSO,MSSSO和PSO性能對(duì)比

圖5 3種算法航跡規(guī)劃以及收斂曲線對(duì)比結(jié)果Fig.5 Path planning and convergence curves of 3 algorithms

4.2 突發(fā)威脅動(dòng)態(tài)航跡規(guī)劃實(shí)例仿真

無(wú)人機(jī)按照4.1節(jié)規(guī)劃航跡進(jìn)行飛行，當(dāng)飛行到(19 km,27 km)時(shí)探測(cè)到(25 km,31 km)處出現(xiàn)新的大氣威脅，如果無(wú)人機(jī)仍按照設(shè)定航跡繼續(xù)飛行，將會(huì)進(jìn)入大氣威脅范圍內(nèi)，導(dǎo)致?lián)p毀概率極大，因此無(wú)人機(jī)需要進(jìn)行突發(fā)威脅航跡重規(guī)劃，此時(shí)設(shè)定重規(guī)劃起始點(diǎn)為(19 km,27 km)，終止點(diǎn)為原來(lái)航跡中的(29 km,33 km)，采用改進(jìn)A*算法進(jìn)行求解，圖6給出了重規(guī)劃后的無(wú)人機(jī)航跡以及與A*算法局部航跡動(dòng)態(tài)規(guī)劃對(duì)比結(jié)果。

圖6 突發(fā)威脅1動(dòng)態(tài)航跡規(guī)劃實(shí)例仿真Fig.6 Dynamic path planning for sudden threat 1

從圖6可以看出，無(wú)人機(jī)能夠避開(kāi)大氣威脅，繼續(xù)向前飛行，而且再規(guī)劃航跡相對(duì)平滑，而采用A*算法規(guī)劃后的航跡彎折較多，不利于無(wú)人機(jī)機(jī)動(dòng)飛行。當(dāng)無(wú)人機(jī)飛行到(36 km,41 km)位置時(shí)，發(fā)現(xiàn)(43 km,43 km)處出現(xiàn)了新的導(dǎo)彈威脅，而且無(wú)人機(jī)剛好經(jīng)過(guò)其有效射程，因此需要再次重規(guī)劃，規(guī)劃起始位置設(shè)定為(36 km,41 km)，終止點(diǎn)設(shè)定為目標(biāo)點(diǎn)。圖7給出了再次重規(guī)劃后的無(wú)人機(jī)航跡以及與A*算法局部航跡動(dòng)態(tài)規(guī)劃對(duì)比結(jié)果。從圖7可以看出，與突發(fā)威脅1航跡重歸化結(jié)果一樣，改進(jìn)A*算法得到的動(dòng)態(tài)規(guī)劃結(jié)果能夠避開(kāi)威脅，而且航跡更利于無(wú)人機(jī)在相對(duì)較短范圍內(nèi)機(jī)動(dòng)。

為了進(jìn)一步分析改進(jìn)A*算法性能，分別對(duì)突發(fā)威脅1和突發(fā)威脅2獨(dú)立運(yùn)行50次，表2給出了改進(jìn)A*與A*算法性能指標(biāo)對(duì)比結(jié)果。從表2可以看出，對(duì)于局部規(guī)劃航程，改進(jìn)A*算法要明顯好于A*算法；對(duì)于算法運(yùn)算時(shí)間，A*算法要快于改進(jìn)A*算法，這是因?yàn)楦倪M(jìn)A*算法擴(kuò)展了領(lǐng)域搜索范圍，增加了算法運(yùn)算量，但是以無(wú)人機(jī)最大150 km/h速度為例，在改進(jìn)A*算法運(yùn)算時(shí)間內(nèi)，無(wú)人機(jī)最多移動(dòng)了9.58 m(150×1000×0.23/3600)，約占局部規(guī)劃網(wǎng)格長(zhǎng)度1 km的1%，因此符合實(shí)際飛行環(huán)境。

圖7 突發(fā)威脅2動(dòng)態(tài)航跡規(guī)劃實(shí)例仿真Fig.7 Dynamic path planning for sudden threat 2

算法統(tǒng)計(jì)值突發(fā)威脅1運(yùn)行時(shí)間/s航程/km突發(fā)威脅2運(yùn)行時(shí)間/s航程/km改進(jìn)A*算法最大值0.2314.190.2217.52最小值0.1913.280.1616.08平均值0.2113.670.1916.34A*算法最大值0.017312.510.016619.26最小值0.006211.970.007718.14平均值0.009412.150.010319.07

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

提出了一種基于多策略SSO和改進(jìn)A*算法的無(wú)人機(jī)動(dòng)態(tài)航跡規(guī)劃方法，該方法通過(guò)引入完全彈性碰撞、自適應(yīng)跳躍機(jī)制、最小“彎折”估計(jì)代價(jià)函數(shù)以及拓展A*算法搜索鄰域個(gè)數(shù)等策略，實(shí)現(xiàn)了對(duì)無(wú)人機(jī)動(dòng)態(tài)航跡規(guī)劃，仿真實(shí)例實(shí)驗(yàn)結(jié)果也表明了該方法的有效性，下一步工作重點(diǎn)將圍繞多機(jī)協(xié)同航跡規(guī)劃問(wèn)題展開(kāi)。

[1] KALYANAM K,CHANDLER P,PACHTER M,et al.Opti-mization of perimeter patrol operations using unmanned aerial vehicles[J].Journal of Guidance,Control,and Dynamics,2012,35(2):434-441.

[2] 方群，徐青.基于改進(jìn)粒子群算法的無(wú)人機(jī)三維航跡規(guī)劃[J].西北工業(yè)大學(xué)學(xué)報(bào)，2017，35(1)：66-73.

[3] 齊乃明，孫小雷，董程，等.航跡預(yù)測(cè)的多無(wú)人機(jī)任務(wù)規(guī)劃方法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2016，48(4)：32-36.

[4] LI Q R,WEI C,WU J,et al.Improved PRM method of low altitude penetration trajectory planning for UAVs[C]//Proceeding of the IEEE Chinese Guidance,Navigation and Control Conference,2014:2651-2654.

[5] 曾國(guó)奇,趙民強(qiáng),劉方圓,等.基于網(wǎng)格PRM的無(wú)人機(jī)多約束航路規(guī)劃[J].系統(tǒng)工程與電子技術(shù),2016,38(10):2310-2316.

[6] 尹高揚(yáng)，周紹磊，吳青坡.無(wú)人機(jī)快速三維航跡規(guī)劃算法[J].西北工業(yè)大學(xué)學(xué)報(bào)，2016,34(4)：564-570.

[7] 孫小雷，齊乃明，董程，等.無(wú)人機(jī)任務(wù)分配與航跡規(guī)劃協(xié)同控制方法[J].系統(tǒng)工程與電子技術(shù)，2015，37(12)：2772-2776.

[8] OZALP N,SAHINGOZ O K.Optimal UAV path planning in a 3D threat environment by using parallel evolutionary algorithms[C]//Proceeding of the IEEE International Conference on Unmanned Aircraft Systems,2013:308-317.

[9] 韓攀，陳謀，陳哨東，等．基于改進(jìn)蟻群算法的無(wú)人機(jī)航跡規(guī)劃[J].吉林大學(xué)學(xué)報(bào):信息科學(xué)版，2013,31(1)：66-72.

[10] 張帥，李學(xué)仁，張建業(yè),等.基于動(dòng)態(tài)步長(zhǎng)的無(wú)人機(jī)三維實(shí)時(shí)航跡規(guī)劃[J].北京航空航天大學(xué)學(xué)報(bào),2016,42(12):2745-2754.

[11] CUEVAS E,CIENFUEGOS M,ZALDIVA D R,et al.A swarm optimization algorithm inspired in the behavior of the social spider [J].Expert System with Applications, 2013,40(16):6374-6384.

[12] 王艷嬌，李曉杰，肖婧.基于動(dòng)態(tài)學(xué)習(xí)策略的群集蜘蛛優(yōu)化算法[J].控制與決策，2015，30(9)：1575-1582.

[13] HART P E,NILSSON N J,RAPHAEL B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE Transactions on Systems Science and Cybernetics,1968,4(2):100-107.

[14] 占偉偉，王偉，陳能成，等.一種利用改進(jìn)A*算法的無(wú)人機(jī)航跡規(guī)劃[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版，2015，40(3)：315-320.

DynamicPathPlanningforUAVsBasedonMulti-strategySSOandImprovedA*Algorithm

TIAN Kuo, LIU Xu

(Chinese Flight Test Establishment,Xi’an 710089,China)

In order to solve the problems of dynamic path planning for Unmanned Aerial Vehicles (UAVs) confronted with sudden threats,a dynamic UAV path-planning method is proposed based on multi-strategy SSO (Social Spider Optimization) and the improved A*algorithm.The UAV path planning is divided into two stages: static path planning and real-time evasion under sudden threat.At the stage of static path planning,multi-strategy SSO optimization algorithm is used to solve the polar-coordinate path-planning model,and the mechanisms of perfect elastic collision and adaptive skipping are introduced,which can improve the feasibility of the path-planning results while satisfying the restraints of flight performance.At the stage of real-time evasion under unexpected threat,the improved A*algorithm is used for path planning in local regions for a second time.Through expanding the number of neighborhood for A*algorithm and introducing the minimum “bent” estimation cost function,a smoother optimal path can be obtained while satisfying the real-time requirements.The simulation results show that the proposed method can provide more satisfactory dynamic path-planning for UAVs.

path planning; Unmanned Aerial Vehicle (UAV); social spider optimization; improved A*algorithm

田闊，劉旭.基于多策略SSO 和改進(jìn)A*算法的無(wú)人機(jī)動(dòng)態(tài)航跡規(guī)劃[J].電光與控制，2017，24( 11) : 31-37.TIAN K，LIU X.Dynamic path planning for UAVs based on multi-strategy SSO and improved A*algorithm[J].Electronics Optics & Control，2017，24( 11) : 31-37．

2017-04-22

2017-05-26

田 闊(1984 —),男，河南鄭州人,碩士，工程師，研究方向?yàn)樘綔y(cè)與制導(dǎo)。

V19

A

10.3969/j.issn.1671-637X.2017.11.007