基于A*算法的無人機攻擊編隊航跡規(guī)劃

曹　棟，王　瑞，曹　越

(1.海軍航空兵學(xué)院 a.司令部;b.飛行理論系，遼寧 葫蘆島 125001； 2.中航工業(yè)無線電電子研究所 軍機系統(tǒng)部，上海 200233)

?

基于A*算法的無人機攻擊編隊航跡規(guī)劃

曹棟1a，王瑞1b，曹越2

(1.海軍航空兵學(xué)院 a.司令部;b.飛行理論系，遼寧 葫蘆島 125001； 2.中航工業(yè)無線電電子研究所 軍機系統(tǒng)部，上海 200233)

提出了一種改進的A*算法，對無人機編隊飛行的航跡進行規(guī)劃。根據(jù)無人機在編隊飛行時對油耗、航跡長短、編隊隊形及目標威脅等約束條件來設(shè)計合適的評估函數(shù)。采取對規(guī)劃點前后段航跡評估進行加權(quán)的方法對A*算法進行改進，從而在優(yōu)化航跡與減少計算時間之間找到平衡點。改進在Open表中插入與刪除節(jié)點的方式，提高計算效率。仿真結(jié)果表明，設(shè)計的A*算法可以快速、有效地為無人機編隊飛行規(guī)劃出合理的航跡。

無人機；航跡規(guī)劃；編隊飛行；A*算法

無人機(Unmanned Aerial Vehicle，UAV)能夠自主進行航跡的選擇與設(shè)定，是實現(xiàn)全自主、全任務(wù)飛行能力的必要前提條件，所以UAV航跡規(guī)劃成為當(dāng)前無人機研究的一個熱點[1-6]。與單架UAV相比，多UAV協(xié)同作戰(zhàn)具有任務(wù)能力強、靈活性高、容錯性好等優(yōu)點，因此UAV編隊執(zhí)行作戰(zhàn)任務(wù)將成為未來戰(zhàn)爭的一種重要模式[7-8],UAV編隊飛行的航跡生成是多UAV協(xié)同作戰(zhàn)的關(guān)鍵技術(shù)[9]。

UAV編隊的航跡規(guī)劃包括2個方面[10]：一方面，編隊整體的航跡規(guī)劃包括規(guī)避已知和未知的危險、臨時任務(wù)的調(diào)整等問題；另一方面，是編隊內(nèi)部各UAV間的約束，包括各機通信、隊形控制、各機航跡最優(yōu)化等問題。對于第一個問題，可以借助單架UAV的航跡設(shè)計與優(yōu)化方法，采用A*算法、Voronoi圖法、概率地圖法、遺傳算法等[1-6,11]，在設(shè)計編隊航跡的同時，引入編隊飛機之間的約束條件，從而實現(xiàn)對編隊航跡的規(guī)劃[12]。目前，通過以上方法雖然能夠?qū)崿F(xiàn)對多UAV編隊的航跡規(guī)劃和任務(wù)分配，但是普遍存在實時性不強的缺點。其原因是由于采用的航跡規(guī)劃算法效率不高，最優(yōu)化時選取的評估函數(shù)過于復(fù)雜所造成的。

本文基于改進的A*算法進行設(shè)計，選取較為簡單的評估函數(shù)，從而提高了UAV編隊航跡規(guī)劃的時效性。

1　評估函數(shù)的選定

編隊航跡的評估函數(shù)既需要考慮整體航跡的優(yōu)化也需要考慮編隊內(nèi)部成員之間的優(yōu)化限制問題。對于前者，可以將之視為有向圖的最優(yōu)路線問題[6]。通過使公式(1)所示的評估函數(shù)最小來得到最優(yōu)解[13]。

(1)

式(1)中，L(μ)為編隊規(guī)劃航跡μ的長度，lij為航跡μ上相鄰兩點的弧線長度。為使評估最小，選取的性能指標可以用以下的廣義評估函數(shù)W表示[14]。

(2)

式(2)中，ωi為航路的威脅評估，ωf為航路的油耗評估，k為油耗與威脅之間的權(quán)重系數(shù)。

但是對于編隊內(nèi)部多UAV隊形的控制問題，需要對以上的評估函數(shù)進行改造。在進行編隊飛行時，UAV的距離既要保證在安全距離之外，也要保證在可通信的范圍之內(nèi)，同時還需要避免被敵方雷達探測，如圖1所示。

圖1中，RC表示UAV的探測通信距離，RS表示UAV的最小安全間距，RT表示目標的探測距離。在飛行時，UAV的間距應(yīng)該保持在RC和RS之間，如U1和U2所示，即需要遵循以下的限制條件：

(3)

式(3)中，(xm，ym)是編隊中第m個UAV在時刻t處的平面坐標。假定采用三機編隊并考慮到隊形的緊湊，在某段航跡lij處可以選取以下的評估函數(shù)。

圖1　UAV編隊

(4)

W′=∑[k′Wij+(1-k′)W]

(5)

式(5)中，k′為權(quán)重系數(shù)，W為離散形式，如式(6)所示。

W=∑[kωi(i,j)+(1-k)ωf(i,j)]

(6)

2　A*算法及其改進

A*算法是一種基于啟發(fā)函數(shù)的搜索算法。通過定義并滿足相容性條件(評估函數(shù))，進而在已知地圖中生成一條最優(yōu)路徑[15]，如式(7)所示。

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

(7)

式(7)中，g′(n)表示當(dāng)前節(jié)點(第n個節(jié)點)與起點之間航跡的估計評估，h′(n)表示當(dāng)前節(jié)點與終點之間航跡的估計評估。A*算法加入了與航跡規(guī)劃有關(guān)的啟發(fā)函數(shù)，對航跡點的搜索方向更加趨向于最終點，從而減小了搜索深度和節(jié)點數(shù)，提高了效率。但為滿足A*算法的可接納性[16]，任一時刻的h′(n)不能超過從網(wǎng)格上的方格移動到終點的實際移動耗費h(n)，這樣A*算法的效率提高，航跡卻優(yōu)化不夠。因此，需要考慮對A*算法進行改進。

2.1A*算法的改進

通過調(diào)整g′(n)和h′(n)在啟發(fā)函數(shù)f(n)中的權(quán)重，來減少估價函數(shù)中前后段航跡所占的比例，以在效率和最優(yōu)化之間找到一個平衡點，即調(diào)整啟發(fā)函數(shù)，如式(8)所示。

f(n)=q·g′(n)+(1-q)h′(n)

(8)

式(8)中，q為權(quán)重比，考慮到g′(n)和h′(n)的權(quán)重比不小于1∶1，其取值范圍為0.5～1，當(dāng)q取1時，相當(dāng)于Dijkstra算法。當(dāng)q逐步減小即增大h′(n)的權(quán)重時，效率提高；反之，效率降低，航跡最優(yōu)。通過調(diào)整q，可使航跡最優(yōu)的同時，提高A*算法的時效性和可接納性。

根據(jù)式(5)和式(8)可將評估函數(shù)列寫為A*算法的形式。

(9)

(10)

h′(n)為節(jié)點n以后的飛行路線的估計值(假定UAV采用大圓線飛行)。

2.2A*算法的步驟

編寫A*算法程序時,需要構(gòu)造Open表和Closed表分別用于存儲待擴展的節(jié)點和已擴展的節(jié)點[17]。由于傳統(tǒng)Open表的節(jié)點插入速度和刪除速度相互制約，不能同時提升，難以整體提高算法效率，所以根據(jù)文獻[13]的方法，采用改進的雙向鏈表的Open表標記插入排序方法，有效地提高了算法的計算速度。

A*算法改進之后的流程如圖2所示。

3　編隊仿真

根據(jù)設(shè)計的A*航跡規(guī)劃算法，針對三架UAV編隊飛行時的航跡進行仿真，仿真環(huán)境為Matlab7.6。仿真過程中，需要對每架UAV的航跡進行計算，最后結(jié)果統(tǒng)一在圖示中給出。選擇的編隊有兩種形式，分別為“△”形和“─”形，飛行環(huán)境為二維平面。

規(guī)劃的航跡起始點設(shè)定為(100,100)，目標點為(110,120)和(120,110)，目標點周圍5格范圍內(nèi)為危險區(qū)域，到達目標后需經(jīng)(120,100)返回起始點。UAV的安全防撞區(qū)域設(shè)定為2，探測距離設(shè)定為10。進行仿真計算時，q的取值分別設(shè)定為0.5、0.7和1，所得到的仿真結(jié)果如圖3和圖4所示。

圖2　改進A*算法流程圖

圖3　“△”編隊總體航跡

圖4　“─”編隊總體航跡

圖5為在q=0.7時“△”隊形和“─”隊形中所有UAV的規(guī)劃航跡。從圖5中可以看出，按照本文所提出的算法規(guī)劃編隊航跡，雖然在局部地方隊形的航跡有所波動，但是整體與預(yù)期的設(shè)定要求相符，這也說明了算法的有效性。

圖5　編隊內(nèi)部UAV航跡

對比以上的仿真圖形，可以看出，采用“△”編隊時，由于兩目標間距過小，需要繞過兩個目標點。而采用“─”隊形時，可從兩目標中間穿過，所以前者規(guī)劃的航跡比后者的長。同時，可以看出采用不同的q值對航跡的影響。隨著h′(n)權(quán)重的增加，航跡優(yōu)化效果變差，當(dāng)q取中間的某一值時(待驗證)，可以在優(yōu)化效果與計算時間之間取得平衡，不同q值所對應(yīng)的計算時間如表1所示。

表1　計算耗費

從表1可以看出，隨著q取值增大，所用計算時間逐漸增大，耗費資源增多。同時，采用雙向Open鏈表所用的計算時間比單向Open鏈表所用時間短，說明根據(jù)文獻[13]提出的Open表計算方法具有一定優(yōu)勢。

綜合仿真數(shù)據(jù)可以看出，在權(quán)值q取0.5時相當(dāng)于原A*算法，從圖3-5可看出據(jù)此規(guī)劃出的航跡較優(yōu)，但據(jù)表1可見其計算時間較長。而q取1時，相當(dāng)于Dijkstra算法，航跡較差但計算效率較高。因此，綜合兩種算法的優(yōu)勢，對原A*算法進行改進，使q取值為0.7，就可以得到較優(yōu)的航跡和較高的計算效率，雙向Open鏈表的計算時間分別為6.2s和6.05s。但q的最優(yōu)取值還需對航跡優(yōu)劣的評估方法進行研究之后才能綜合確定。

4　結(jié)論

相對于單架UAV執(zhí)行任務(wù)，多架UAV協(xié)同執(zhí)行任務(wù)具有更多的優(yōu)勢。針對UAV編隊飛行的航跡規(guī)劃問題，本文設(shè)計了相應(yīng)的評估函數(shù)，通過調(diào)整啟發(fā)函數(shù)前后段所占權(quán)重以及采用雙向Open鏈表的方法對A*算法進行改進。最后的仿真結(jié)果表明，通過調(diào)整啟發(fā)函數(shù)前后段的權(quán)重可以在航跡優(yōu)化效果和計算時間之間得到平衡，在保證航跡可行的情況下提高計算效率。同時采用雙向鏈表的方法可以節(jié)省計算時間，提升效率。但是在飛行中，如果UAV編隊隊形改變，航跡也會相應(yīng)改變，而相關(guān)的航跡規(guī)劃問題需要進一步的研究。

[1]高暉,陳欣,夏云程.無人機航路規(guī)劃研究[J].南京航空航天大學(xué)學(xué)報,2001,33(2):135 -138.

[2]周煒，魏瑞軒，董志興.基于層次分解策略無人機編隊避障方法.系統(tǒng)工程與電子技術(shù)[J]，2009，31(5)：1152-1157.

[3]安玉嬌，江輝軍，鄭根營，等.無人機低空突防航跡規(guī)劃算法研究[J].測控技術(shù)，2011，30(12)：86-90.

[4]王緒芝，姚敏，趙敏，等.基于蟻群算法的無人機航跡規(guī)劃及其動態(tài)仿真[J].指揮控制與仿真，2012，34(1):29-32.

[5]任波，周燾，于雷.基于改進A*算法的飛行器三維航跡規(guī)劃算法.系統(tǒng)工程與電子技術(shù)[J]，2008，30(2)：324-326.

[6]ALEXY，SANJIVS，ANTHONYS.Anefficientonlinepathplannerforoutdoormobilerobots[J].RoboticsandAutonomousSystems,2000,32:129-143.

[7]王國強，羅賀，胡笑旋，等.無人機編隊管理的研究綜述[J].電光與控制，2013，20(8)：48-53.

[8]劉小雄，章衛(wèi)國，王振華.無人機自適應(yīng)編隊飛行控制設(shè)計與仿真[J].系統(tǒng)仿真學(xué)報，2009，21(5):1420-1422.

[9]胡中華.基于智能優(yōu)化算法的無人機航跡規(guī)劃若干關(guān)鍵技術(shù)研究[D].南京:南京航空航天大學(xué)，2011.

[10]朱艷萍.多無人機協(xié)同攻擊策略研究[D].南京:南京航空航天大學(xué)，2012.

[11]何平川，戴樹嶺.一種改進的UAV三維航跡實時規(guī)劃算法[J].北京航空航天大學(xué)學(xué)報，2010，36(10)：1248-1251.

[12]王慶江，高曉光，符小衛(wèi).無威脅情況下任意兩點間的無人機路徑規(guī)劃[J].系統(tǒng)工程與電子技術(shù)，2009，31(9)：2157-2162.

[13]FENGLILIAN,RICHARDMURRAY.Real-timetrajectorygenerationforcooperativepathplanningofmulti-vehiclesystems[C].2002ConferenceonDecisionandControl.California,2002:1-4.

[14]張大巧，鮮勇，許立軍，等.基于改進A*的三維航跡快速規(guī)劃方法[J].彈箭與制導(dǎo)學(xué)報,2010，30(5)：59-62.

[15]史輝，曹聞，朱述龍，等.A*算法的改進及其在路徑規(guī)劃中的應(yīng)用[J].測繪與空間地理信，2009，32(6)：208-211.

[16]趙真明，孟正大.基于加權(quán)A*算法的服務(wù)型機器人路徑規(guī)劃[J].華中科技大學(xué)學(xué)報(自然科學(xué)版)，2008，36(SupⅠ)：196-198.

[17]HENNEBRYMICHAE,JIANKUOD,NYGARDKENDALL.Dynamicnetworkrefinementinautomatedaircraftrouteplanning[C].IEEEEIT2007Proceedings.Chicago:IEEE,2007:373-377.

[18]馮乃勤，王歲花，鄭延斌，等.OPEN表和CLOSED表的合一[J].計算機工程與應(yīng)用，2003(16):100-102.

(責(zé)任編輯：吳萍英文審校：趙亮)

Trajectory planning for flight formation of Unmanned Aerial Vehicle based on A*algorithm

CAO Dong1,WANG Rui1,CAO Yue2

(1.a.Headquarters;b.Department of Flight Thoery,Naval Air Institute,Huludao 125001, China;2.System Department of attle Aircraft,China Aeronautical Radio Electronics Research Institute Shanghai 200233,China)

An improved A*algorithm was proposed to plan the trajectory for Unmanned Aerial Vehicle formation in the paper.First the cost function was designed on the basis of fuel consumption,length of trajectory,formation shape and dangers of targets while unmanned aerial vehicles were flying in formation.Then the A*algorithm was used by adding-weight to the evaluations of trajectory before or after the knot being expanded.As a result,the balance between trajectory optimization and computing time was found.Meanwhile the computing efficient was also improved by changing the method of deleting and adding knot in the open list.The simulation results show that the A*algorithm can plan optimized trajectories for unmanned aerial vehicles flying in formation quickly and efficiently.

unmanned aerial vehicle;trajectory planning;flight formation;A*algorithm

2016-02-16

曹棟(1962-)，男，江蘇南通人，教授，主要研究方向：航空電氣與控制，E-mail:hfcd39325@sina.com。

2095-1248(2016)04-0061-05

V249.4

A

10.3969/j.issn.2095-1248.2016.04.011