基于改進人工蜂群算法的無人機實時航跡規(guī)劃

張洛兵, 徐流沙, 吳梅

(1.中國航空工業(yè)集團公司 防務(wù)工程部, 北京 100022;2.西北工業(yè)大學(xué) 自動化學(xué)院, 陜西 西安 710072)

基于改進人工蜂群算法的無人機實時航跡規(guī)劃

張洛兵1, 徐流沙2, 吳梅2

(1.中國航空工業(yè)集團公司 防務(wù)工程部, 北京 100022;
2.西北工業(yè)大學(xué) 自動化學(xué)院, 陜西 西安 710072)

為了適應(yīng)現(xiàn)代戰(zhàn)爭戰(zhàn)場環(huán)境的復(fù)雜性,針對所建立的突發(fā)威脅模型,提出了一種基于改進人工蜂群算法的無人機航跡規(guī)劃方法,對無人機進行動態(tài)航跡尋優(yōu),并通過MATLAB進行了仿真驗證。仿真結(jié)果表明,所設(shè)計的方法能夠根據(jù)實時出現(xiàn)的威脅狀況進行動態(tài)航跡規(guī)劃、評價和選優(yōu),同時滿足實時性要求。

人工蜂群算法; 航跡規(guī)劃; 無人機

0 引言

航跡規(guī)劃是根據(jù)地形、天氣和威脅等信息,尋找飛行器從起始點到目標(biāo)點之間最優(yōu)運行軌跡的新一代低空突防技術(shù)[1]。因此無人飛行器飛行前,一般會根據(jù)其飛行性能、任務(wù)和已獲得的威脅信息,設(shè)計多條離線飛行航跡。一般情況下,在沒有遇到突發(fā)威脅或改變執(zhí)行任務(wù)的情況下,無人機會按照規(guī)劃好的離線航跡飛行。然而隨著現(xiàn)代戰(zhàn)爭復(fù)雜性的增強,傳統(tǒng)的航跡規(guī)劃算法已不能滿足高復(fù)雜度戰(zhàn)場環(huán)境的需求,動態(tài)航跡規(guī)劃已成為提高飛行器環(huán)境適應(yīng)性和生存能力的重要方法。該方法應(yīng)盡可能地依靠機載計算機,實時、高效地在線規(guī)劃出較優(yōu)的航跡,以規(guī)避突發(fā)的威脅狀況,從而使其具備對突發(fā)威脅的自主決策能力。因此,研究面向突發(fā)威脅的實時航跡規(guī)劃,對提高無人飛行器的戰(zhàn)場生存能力具有非常重要的價值。

人工蜂群(Artificial Bee Colony,ABC)算法是一種基于群體智能理論[2]的全局優(yōu)化算法,已經(jīng)在函數(shù)優(yōu)化組合優(yōu)化和工程領(lǐng)域得到了大量的應(yīng)用。人工蜂群是在2005年由Karaboga[2]基于蜂群的智能采蜜行為及自治、分工和自組織模型提出的。在人工蜂群算法中,人工蜂群由三部分組成:采蜜蜂、偵察蜂和跟隨蜂。蜜源的位置代表優(yōu)化問題的可行解,蜜源質(zhì)量對應(yīng)于該解的優(yōu)劣,通常用一個適應(yīng)度函數(shù)來評價。目前ABC算法作為一種新的隨機優(yōu)化算法,在接近全局最優(yōu)解時,仍存在搜索速度變慢、過早收斂、個體多樣性減少,甚至陷入局部最優(yōu)解等難題。

本文提出了一種改進人工蜂群算法,并應(yīng)用于無人機實時航跡規(guī)劃中,同時提出了航跡點“勢能”概念,使得各個航跡點的“搜索優(yōu)先級”存在差異?；谶@種差異,改進ABC算法中采蜜蜂采蜜的方式,從而在無人機實時航跡規(guī)劃過程中,在不增加搜索時間的基礎(chǔ)上,規(guī)劃出全局較優(yōu)的航跡。最后,通過仿真試驗驗證了改進算法的有效性。

1 威脅模型

航跡規(guī)劃需要回避一些禁飛區(qū)域和威脅區(qū)域,而各種威脅模型簡化為具有一定形狀的幾何體組合,可以降低規(guī)劃的復(fù)雜度。然后以適當(dāng)?shù)牡匦胃采w威脅或障礙的作用區(qū)域,則可把威脅障礙模型等效為相應(yīng)的地形模型。在實際應(yīng)用中,可以建立一個表來單獨記錄這些不確定因素,以便當(dāng)環(huán)境發(fā)生改變時,及時更新規(guī)劃環(huán)境,以滿足實時性要求。

1.1 禁飛區(qū)

禁飛區(qū)(No-fly Zone)指某地上空禁止任何未經(jīng)特別申請許可的航空器(包括飛機、直升機、熱氣球等)飛入或飛越的空域。將禁飛區(qū)建為圓柱體或長方體地形,并賦予一個較大高程值,表示若無人機從該區(qū)域通過,將要付出很高的“高度代價”。將圓形禁飛區(qū)表示為(x,y,R),矩形禁飛區(qū)表示為(a,b,c,d),其三維模型如圖1所示。

圖1 禁飛區(qū)三維圖Fig.1 3D no-fly zone

1.2 地形因素

本文引入地形作為威脅。在無人機飛行過程中,地形因素對無人機造成的影響主要有兩方面:一方面對無人機的飛行安全帶來嚴(yán)重威脅,增大碰撞概率;另一方面,回避地形的同時,也可實現(xiàn)地形遮蔽,減小被敵方防空武器發(fā)現(xiàn)的概率。對飛行區(qū)域中某些陡峭的山峰單獨處理,用二維高斯分布來對孤立山峰進行模擬,數(shù)學(xué)表達(dá)式為:

(1)

式中:(x,y)為水平投影面的坐標(biāo);hmi(x,y)為該點的地形高度;Hi為山峰最高點的高度;pi,qi分別為山峰沿x軸和y軸方向與坡度相關(guān)的量,控制山峰的范圍,其值越小山峰越陡峭,其值越大山峰越平坦;(x0i,y0i)為山峰中心位置。

當(dāng)有多個山峰時,則山峰地形表示為:

(2)

式中:i為山峰的個數(shù)。圖2為山峰的三維模擬。

圖2 山峰三維模擬Fig.2 3D simulation of mountain

1.3 雷達(dá)威脅

在航跡規(guī)劃時面臨的主要威脅是雷達(dá)[3],分為預(yù)警雷達(dá)和火控雷達(dá)。預(yù)警雷達(dá)通過防空系統(tǒng)將探測到的目標(biāo)數(shù)據(jù)傳送給火控雷達(dá),然后火控雷達(dá)根據(jù)這些數(shù)據(jù)跟蹤和鎖定目標(biāo),之后火力系統(tǒng)才能打擊目標(biāo)。因此,避開敵方的雷達(dá)探測區(qū)域是無人機航跡規(guī)劃中的重要因素之一。

設(shè)雷達(dá)的最大作用范圍為Rm,且雷達(dá)位置(xr,yr,hr)固定,則無人機在某一位置(x,y,h)時受雷達(dá)的威脅可量化為:

(3)

其中:

式中:KR為威脅系數(shù)。而無人機在安全曲面上飛行,即有h=hs(x,y),所以式(3)只與(x,y)有關(guān)。考慮到無人機從進入雷達(dá)區(qū)域到距雷達(dá)很近這段過程,不被發(fā)現(xiàn)的概率很小,且突防中也需要與雷達(dá)探測區(qū)域保持一段安全距離,因此可采用如下等效高程:

(4)

式中:a<1,如取為0.5;b>1,如取為1.1;HR為一很大常值。三維等效高程如圖3所示。

圖3 雷達(dá)等效高程Fig.3 Radar equivalent elevation

2 基于改進人工蜂群算法的航跡規(guī)劃

2.1 算法改進

2．1．1 初始蜜源生成

為了加快實時航跡規(guī)劃的收斂速度,加入離線規(guī)劃出的最優(yōu)蜜源,即無人機的參考航跡。由于離線規(guī)劃的最終蜜源群仍含有豐富的模式,因此可以直接引用為初始蜜源。

初始蜜源的生成采取小區(qū)間生成法:先將第j(j=1,2,…,D)個參數(shù)的取值范圍分成蜜源總數(shù)NP個等值小區(qū)間,分別記作I1j,I2j,…,INPj,再生成一個NP×D矩陣E={eij},其中E的每列為1,2,…,NP的隨機排列,則第i個蜜源的各個參數(shù)分別在小區(qū)間Iiei1,Iiei2,…,IieiD中隨機生成,如這樣生成的初始個體將會均勻地分布在整個解空間上,保證了初始群體含有較豐富的模式,增強了搜索收斂于全局最優(yōu)點的可能。

2．1．2 選擇機制

ABC算法中,跟隨蜂是以輪盤賭的機制選擇蜜源,這是一種基于貪婪策略的選擇方式,會使種群多樣性降低,從而引起過早收斂和提前停滯的現(xiàn)象。

對于一處蜜源(航跡),采蜜蜂負(fù)責(zé)局部搜索,采蜜時隨機生成要改變的蜜源分量(航跡點),根據(jù)上文所述的思想,可以對每一個分量(航跡點)賦一個權(quán)值,采蜜蜂依據(jù)這些權(quán)值來決定要改變的蜜源分量,就像跟隨蜂選擇要開采的蜜源一樣。為此,引入人工勢場的思想,設(shè)想威脅源中心為一斥力源,航跡點離威脅源越近,所受斥力就越大,航跡點“勢能”也就越大,因此越容易被“改變”。設(shè)航跡點Pk+i(i=1,2,…,D-k)到威脅源中心的距離為Ri,則“勢能”為:

(5)

按輪盤賭原則,被改變的概率為:

(6)

之后,采蜜蜂按概率選擇要改變的分量。

2．1．3 偵察蜂尋找新的蜜源

引入差分進化法的變異和交叉操作尋找新的蜜源,差分進化(Differential Evolution,DE)算法是一種采用浮點矢量編碼在連續(xù)空間中進行隨機搜索的優(yōu)化算法。DE的原理簡單、受控參數(shù)少,實施隨機、并行、直接的全局搜索,易于理解和實現(xiàn)。算法的基本思想是:對當(dāng)前種群進行變異和交叉操作,產(chǎn)生另一個新種群;然后利用基于貪婪思想的選擇操作對這兩個種群進行一對一的選擇,從而產(chǎn)生最終的新一代種群。

(1)變異操作

為加速收斂,在變異操作中,選擇全局最優(yōu)蜜源Xbest作為父代基向量,即

(7)

式中:Vi=(vi1,vi2,…,viD),i=1,2,…,NP,D為優(yōu)化參數(shù);Xbest為當(dāng)前全局最佳蜜源;F為縮放比因子;(Xr2-Xr3)為父代差分向量;參數(shù)r1,r2,r3∈{1,2,…,NP}互異且不等于i[4]。

(2)交叉操作

將Xi與Vi交叉產(chǎn)生子代個體Ui=(ui1,ui2,…,uiD)。為保證第i個蜜源的演化,首先通過隨機選擇使得Ui至少有一位由Vi貢獻,而對其他位,可利用一個交叉概率因子CR∈[0,1]決定Ui中哪些位由Xi貢獻,哪些位由Vi貢獻。如果rand

(8)

式中,rand(j)為[0,1]之間的均勻分布隨機數(shù);rnbr(i)為(i=1,2,…,D)之間的隨機量。

最后,將Ui替代Xi成為第i個蜜源進入下一次循環(huán),并更新相應(yīng)蜜源質(zhì)量信息。

2.2 航跡規(guī)劃的約束條件

由于無人機有自身特殊的物理限制和使用要求,所以其航跡規(guī)劃不同于路面機器人的路徑規(guī)劃,還需要滿足一定的航跡基本約束條件。無人機受到的約束條件很多,包括飛行環(huán)境、自身的物理性能及戰(zhàn)術(shù)要求等。在構(gòu)造航跡規(guī)劃地圖時引入安全曲面的概念,利用無人機的縱向約束(最大爬升/俯沖角、法向過載和最小離地飛行高度)構(gòu)造安全曲面,水平方向要考慮的約束[5]主要有:最大航程、最小轉(zhuǎn)彎半徑。

2．2．1 最大航程

(9)

2．2．2 最小轉(zhuǎn)彎半徑

要實現(xiàn)規(guī)劃的航跡可飛,必須滿足最小轉(zhuǎn)彎半徑。半徑越小,轉(zhuǎn)彎曲率越大,將導(dǎo)致過載過大。轉(zhuǎn)彎半徑如圖4所示。

圖4 轉(zhuǎn)彎半徑Fig.4 Turning radius

規(guī)劃航跡由航跡點組成,采用不過點的航跡點轉(zhuǎn)換控制飛行方式,當(dāng)無人機距Pk的距離為Lc時,開始勻速水平轉(zhuǎn)彎。則有:

(10)

式中：φk為Pk處的轉(zhuǎn)彎角。因此,只需控制Lc和φk的大小,則可滿足最小轉(zhuǎn)彎半徑條件,即與最小水平航跡段長度和最大轉(zhuǎn)彎角有關(guān)。轉(zhuǎn)換控制應(yīng)依據(jù)飛行控制系統(tǒng)控制律計算結(jié)果確定,由導(dǎo)航計算機給出。

2.3 目標(biāo)函數(shù)

2.3.1 威脅代價

無人機在空間中的點x處受第j個威脅的影響指數(shù)主要與無人機和威脅間的距離dxj有關(guān),具體計算可采用如下公式:

(11)

式中:Kj為反映第j個威脅的強度參數(shù),默認(rèn)為1;a>1;b>1。將規(guī)劃空間相對于威脅j劃分成三個區(qū)域:危險區(qū)、次安全區(qū)和安全區(qū)。

要計算第i段航跡的威脅指數(shù)需沿第i段進行積分。為了減少計算量,只計算該段航跡若干個點威脅指數(shù)的平均值,再乘以該航跡段的長度。則:

式中:Nthr為已知威脅源的個數(shù);li/6為第i段航跡的1/6處,如圖5所示。

圖5 航跡威脅示意圖Fig.5 Route threat

2.3.2 油耗代價

假設(shè)無人機飛行速度為常值,則油耗可簡單地認(rèn)為與航跡長度成正比。

2.3.3 轉(zhuǎn)彎代價

為限制轉(zhuǎn)彎角過大,需要在代價函數(shù)中加入對轉(zhuǎn)彎角的懲罰項,航跡點Pi處的轉(zhuǎn)彎角為:

(12)

當(dāng)φi大于水平轉(zhuǎn)彎角φ時,做出懲罰。只考慮轉(zhuǎn)彎代價的情況下,有：

(13)

式中:k3為懲罰因子,設(shè)為10。因此轉(zhuǎn)彎角代價為:

(14)

綜合以上,目標(biāo)函數(shù)為:

(15)

航跡規(guī)劃問題的數(shù)學(xué)描述即為:

當(dāng)無人機的機載雷達(dá)在參考航跡周圍探測到威脅和障礙,就需要不斷地更新地圖信息并重新規(guī)劃一條航跡。在線航跡規(guī)劃需要充分利用離線航跡規(guī)劃的結(jié)果,應(yīng)用局部再規(guī)劃將新終點后的離線航跡引用過來,與規(guī)劃出來的局部航跡相組合,作為無人機的當(dāng)前航跡,因此實時規(guī)劃時間更少,能夠滿足實時性要求。

3 仿真算例及結(jié)果分析

采用Global Mapping軟件截取秦嶺一塊90 km×

90 km的規(guī)劃區(qū)域,設(shè)置橫向與縱向采樣間隔為100 m×100 m,保存為.tif格式,通過MATLAB讀取并顯示。為方便計算,將該數(shù)字高程模型(Digital Elevation Model,DEM)減去最低采樣高度,基準(zhǔn)海拔為0。原始數(shù)字高程如圖6所示。

圖6 原始數(shù)字高程Fig.6 3D original elevation

依據(jù)航跡規(guī)劃參數(shù),對無人機設(shè)定了飛行約束條件和威脅源,并基于ABC算法完成離線航跡優(yōu)化,優(yōu)化軌跡如圖7所示。

圖7 離線航跡優(yōu)化Fig.7 Route optimization off-line

(1)起始點

起點S:(0, 0, 1.7) km;

目標(biāo)點G:(90,90,0.6) km。

(2)無人機約束條件

最小水平航跡段長度3 km;最大轉(zhuǎn)彎角60°;最大爬升俯沖角30°;最小離地距離100 m;最大航跡長度250 km。

(3)威脅參數(shù)

①禁飛區(qū)

矩形1:(20, 10, 40, 20) km,等效高度5 km;

矩形2:(70, 65, 85, 75) km,等效高度5 km;

圓形1:中心(20, 20) km,半徑8 km。

②等效山峰

山峰1:中心(30, 50) km,a1=b1=5 km,H1=6 km;山峰2:中心(60, 15) km,a2=b2=4 km,H2=6 km。

③雷達(dá)

a=0.5,b=1.1,HR=5 km,Rm=100 m;

雷達(dá)1:中心(60, 50) km;

雷達(dá)2:中心(40, 75) km。

(4)ABC算法參數(shù)

控制參數(shù)為SN=30,Limit=30,MCN=2 500,由于航跡代價都為正值,則可令適應(yīng)度值為:

fit(X)=1/J(X)

(16)

DE參數(shù)F=0.5,CR=0.8。

當(dāng)無人機遇到突發(fā)威脅時,應(yīng)用改進的ABC算法進行實時航跡再規(guī)劃。迭代100次,運行時間在5.5 s左右。仿真結(jié)果如圖8、圖9所示。

圖9 收斂趨勢Fig.9 Convergent tendency

從圖8可以看出,在線航跡規(guī)劃在充分利用離線航跡規(guī)劃計算結(jié)果的基礎(chǔ)上,可以對實時出現(xiàn)的威脅快速計算出新的航跡。圖中，虛線為修正航跡,在參考航跡基礎(chǔ)上,除了在突發(fā)威脅附近外,還在其他區(qū)域都有些小修正,計算時間短,規(guī)劃的航跡有效地避開了新出現(xiàn)的威脅,驗證了算法的有效性。

4 結(jié)束語

本文提出了航跡點“勢能”概念,使得各個航跡點的“搜索優(yōu)先級”存在差異,基于這種差異,改進了ABC算法中采蜜蜂采蜜的方式。改進后的ABC算法搜索效率大大提高,與局部重規(guī)劃相比,在不增加搜索時間的基礎(chǔ)上,能規(guī)劃出全局較優(yōu)的航跡。

[1] 杜萍,楊春.飛行器航跡規(guī)劃算法綜述[J].飛行力學(xué),2005,23(2):10-14.

[2] Karaboga D.An idea based on honey bee swarm for numerical optimization [R].Kayseri:Computer Engineering Department,Engineering Faculty Erciyes University,

2005.

[3] 郝震,張健,朱凡,等.雷達(dá)威脅環(huán)境下的無人機三維航跡規(guī)劃 [J].飛行力學(xué),2010,28 (1):47-52.

[4] 謝曉鋒,張文俊,張國瑞,等.差異演化的實驗研究 [J].控制與決策,2004,19(1):49-52.

[5] Szczerba R J,Galkowski P,Glicktein I,et al.Robust algorithm for real-time route planning [J].Aerospace and Electronic Systems,IEEE Transactions on,2000,36(3):869-878.

(編輯：李怡)

Real-time route planning of UAV based on improved ABC algorithm

ZHANG Luo-bing1, XU Liu-sha2, WU Mei2

(1.Department of Defense Engineering, AVIC, Beijing 100022;2.School of Automation, NWPU, Xi’an 710072, China)

In order to adapt to the complex nature of modern warfare battlefield environment, for the unexpected threat model established, a UAV flight route planning method based on improved artificial bee colony(ABC)algorithm was put forward for optimization of dynamic trajectory of UAV. The method was simulated with MALTAB. Simulation results show that this method can be used to dynamically perform dynamic flight route planning, evaluation and optimization of the emerging threats based on real-time status, and it can meet the real-time requirements.

artificial bee colony algorithm; route planning; unmanned aerial vehicle

2014-05-19;

2014-11-10;

時間:2014-11-18 16:57

張洛兵(1967-)，男，山西高平人，工程師，碩士，主要從事工程管理研究。

V279; V249.1

A

1002-0853(2015)01-0038-05