張洛兵, 徐流沙, 吳梅

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

基于改進(jìn)人工蜂群算法的無(wú)人機(jī)實(shí)時(shí)航跡規(guī)劃

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

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

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

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

0 引言

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

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

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

1 威脅模型

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

1.1 禁飛區(qū)

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

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

1.2 地形因素

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

(1)

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

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

(2)

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

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

1.3 雷達(dá)威脅

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

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

(3)

其中:

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

(4)

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

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

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

2.1 算法改進(jìn)

2．1．1 初始蜜源生成

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

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

2．1．2 選擇機(jī)制

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

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

(5)

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

(6)

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

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

引入差分進(jìn)化法的變異和交叉操作尋找新的蜜源,差分進(jìn)化(Differential Evolution,DE)算法是一種采用浮點(diǎn)矢量編碼在連續(xù)空間中進(jìn)行隨機(jī)搜索的優(yōu)化算法。DE的原理簡(jiǎn)單、受控參數(shù)少,實(shí)施隨機(jī)、并行、直接的全局搜索,易于理解和實(shí)現(xiàn)。算法的基本思想是:對(duì)當(dāng)前種群進(jìn)行變異和交叉操作,產(chǎn)生另一個(gè)新種群;然后利用基于貪婪思想的選擇操作對(duì)這兩個(gè)種群進(jìn)行一對(duì)一的選擇,從而產(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)生子代個(gè)體Ui=(ui1,ui2,…,uiD)。為保證第i個(gè)蜜源的演化,首先通過(guò)隨機(jī)選擇使得Ui至少有一位由Vi貢獻(xiàn),而對(duì)其他位,可利用一個(gè)交叉概率因子CR∈[0,1]決定Ui中哪些位由Xi貢獻(xiàn),哪些位由Vi貢獻(xiàn)。如果rand

(8)

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

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

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

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

2．2．1 最大航程

(9)

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

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

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

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

(10)

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

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

2.3.1 威脅代價(jià)

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

(11)

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

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

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

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

2.3.2 油耗代價(jià)

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

2.3.3 轉(zhuǎn)彎代價(jià)

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

(12)

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

(13)

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

(14)

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

(15)

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

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

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

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

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

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

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

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

(1)起始點(diǎn)

起點(diǎn)S:(0, 0, 1.7) km;

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

(2)無(wú)人機(jī)約束條件

最小水平航跡段長(zhǎng)度3 km;最大轉(zhuǎn)彎角60°;最大爬升俯沖角30°;最小離地距離100 m;最大航跡長(zhǎng)度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,由于航跡代價(jià)都為正值,則可令適應(yīng)度值為:

fit(X)=1/J(X)

(16)

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

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

圖9 收斂趨勢(shì)Fig.9 Convergent tendency

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

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

本文提出了航跡點(diǎn)“勢(shì)能”概念,使得各個(gè)航跡點(diǎn)的“搜索優(yōu)先級(jí)”存在差異,基于這種差異,改進(jìn)了ABC算法中采蜜蜂采蜜的方式。改進(jìn)后的ABC算法搜索效率大大提高,與局部重規(guī)劃相比,在不增加搜索時(shí)間的基礎(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)境下的無(wú)人機(jī)三維航跡規(guī)劃 [J].飛行力學(xué),2010,28 (1):47-52.

[4] 謝曉鋒,張文俊,張國(guó)瑞,等.差異演化的實(shí)驗(yàn)研究 [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;

時(shí)間:2014-11-18 16:57

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

V279; V249.1

A

1002-0853(2015)01-0038-05