田 闊, 劉 旭

(中國飛行試驗研究院，西安 710089)

基于多策略SSO 和改進A*算法的無人機動態(tài)航跡規(guī)劃

田 闊, 劉 旭

(中國飛行試驗研究院，西安 710089)

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

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

0 引言

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

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

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

1 航跡規(guī)劃建模

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

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

(1)

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

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

(2)

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

(3)

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

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

(4)

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

(5)

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

(6)

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

2.1 極坐標空間處理

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

(7)

(8)

圖1 威脅代價計算與極坐標轉(zhuǎn)換Fig.1 Threat cost calculation and polar transformation

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

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

2.2.1 完全彈性碰撞

(9)

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

(10)

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

(11)

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

(12)

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

推論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*搜索域擴展示意圖Fig.2 Perfect elastic collision and A* search domain extension

2.2.2 自適應跳躍機制

t時刻，選取種群適應度最優(yōu)的前F1個進行跳躍更新，更新公式為

(18)

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

(19)

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

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

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

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

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

定義5對于蜘蛛個體，定義其目標函數(shù)為航跡綜合代價模型，即

(20)

(21)

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

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

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

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

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

3.1 改進A*算法

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

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

(22)

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

3.1.1 最小“彎折”估計代價

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

(23)

3.1.2 搜索鄰域節(jié)點擴展

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

(24)

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

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

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

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

4 實驗仿真

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

為驗證分析MSSSO靜態(tài)航跡規(guī)劃算法性能，采用Matlab仿真平臺對實例進行仿真實驗：在70 km×70 km二維空間內(nèi)，無人機從(15 km,23 km)處起飛執(zhí)行對(47 km,53 km)處敵方指揮中心打擊任務。MSSSO相關(guān)參數(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，無人機飛行性能參數(shù)參考文獻[7]，雷達、高炮、導彈、大氣威脅參數(shù)設置參考文獻[10]，地形威脅采用不規(guī)則圖形進行表示。為進一步分析MSSSO性能，分別采用基本SSO算法、粒子群優(yōu)化算法(PSO)和MSSSO進行對比實驗，每種算法獨立運行50次，對比分析最終航跡結(jié)果(利用K平滑算法對3種算法航跡進行處理)。表1給出了3種算法相關(guān)指標對比結(jié)果，圖5給出了3種算法航跡規(guī)劃以及收斂曲線對比結(jié)果。

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

表1 SSO,MSSSO和PSO性能對比

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

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

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

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

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

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

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

算法統(tǒng)計值突發(fā)威脅1運行時間/s航程/km突發(fā)威脅2運行時間/s航程/km改進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é)束語

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

[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] 方群，徐青.基于改進粒子群算法的無人機三維航跡規(guī)劃[J].西北工業(yè)大學學報，2017，35(1)：66-73.

[3] 齊乃明，孫小雷，董程，等.航跡預測的多無人機任務規(guī)劃方法[J].哈爾濱工業(yè)大學學報，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] 曾國奇,趙民強,劉方圓,等.基于網(wǎng)格PRM的無人機多約束航路規(guī)劃[J].系統(tǒng)工程與電子技術(shù),2016,38(10):2310-2316.

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

[7] 孫小雷，齊乃明，董程，等.無人機任務分配與航跡規(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] 韓攀，陳謀，陳哨東，等．基于改進蟻群算法的無人機航跡規(guī)劃[J].吉林大學學報:信息科學版，2013,31(1)：66-72.

[10] 張帥，李學仁，張建業(yè),等.基于動態(tài)步長的無人機三維實時航跡規(guī)劃[J].北京航空航天大學學報,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] 王艷嬌，李曉杰，肖婧.基于動態(tài)學習策略的群集蜘蛛優(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] 占偉偉，王偉，陳能成，等.一種利用改進A*算法的無人機航跡規(guī)劃[J].武漢大學學報:信息科學版，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 和改進A*算法的無人機動態(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 —),男，河南鄭州人,碩士，工程師，研究方向為探測與制導。

V19

A

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