一種基于改進(jìn)PSO的無人機航路規(guī)劃方法*

韓 超 王 贏

(1.海軍駐426廠軍事代表室 大連 116005)(2.武漢數(shù)字工程研究所 武漢 430074)

一種基于改進(jìn)PSO的無人機航路規(guī)劃方法*

韓 超1王 贏2

(1.海軍駐426廠軍事代表室 大連 116005)(2.武漢數(shù)字工程研究所 武漢 430074)

針對無人機航路規(guī)劃問題,提出了一種改進(jìn)的粒子群的無人機航路規(guī)劃方法。該方法將UAV的航路規(guī)劃問題通過目標(biāo)轉(zhuǎn)換,形成一個考慮威脅優(yōu)先,路徑優(yōu)化其次的單目標(biāo)航路優(yōu)化問題,并引入局部搜索改進(jìn)粒子群算法求解該問題的收斂性。仿真結(jié)果證明了該方法對解決無人機的航路規(guī)劃問題高效可行。

航路規(guī)劃; 無人機; 粒子群算法; 局部搜索

ClassNumberTP391.9

1 引言

無人機(Uninhabited CombatAerial Vehicle,UAV)是當(dāng)前國內(nèi)外熱門研究的武器裝備,通常可進(jìn)行自主任務(wù)控制或者由操作人員進(jìn)行遠(yuǎn)程地面遙控進(jìn)行使用,可執(zhí)行空對空、空對地、空對海等多種作戰(zhàn)任務(wù)。與傳統(tǒng)的有人作戰(zhàn)飛機相比,無人機具備多項優(yōu)勢,如:作戰(zhàn)零傷亡、制空時間長、隱身性能好、戰(zhàn)斗準(zhǔn)備時間短、研發(fā)維護費用相對較低等。無人機的這些優(yōu)勢能縮短作戰(zhàn)應(yīng)用中的觀察、定位、決策、行動周期,在針對敵方的高風(fēng)險目標(biāo)突防、防空系統(tǒng)能力壓制、縱深目標(biāo)攻擊等多種作戰(zhàn)中發(fā)揮多種獨特的作用。由于無人機的這些顯著優(yōu)勢,國內(nèi)外越來越多重視其研究與發(fā)展,歐美國家都把軍用UAV的發(fā)展置于優(yōu)先地位,先后制定了UAV發(fā)展計劃,投入了巨資開展UAV技術(shù)研究和作戰(zhàn)應(yīng)用原型驗證,尤其是美國的UAV已進(jìn)入作戰(zhàn)實用階段[1]。面對未來的多樣化戰(zhàn)爭技術(shù)發(fā)展趨勢,迫切需要我國發(fā)展UAV相關(guān)技術(shù),為打贏未來信息化條件下非對稱戰(zhàn)爭提供支撐。

無人機航路(航跡)規(guī)劃是無人機作戰(zhàn)使用中的重要部分。航路規(guī)劃的目的是在限定的條件下,選擇一條到達(dá)任務(wù)地點的最優(yōu)或次優(yōu)路徑。無人機在進(jìn)行作戰(zhàn)使用時,首先對作戰(zhàn)任務(wù)進(jìn)行規(guī)劃,確定完成任務(wù)的各個目標(biāo)地點,航路規(guī)劃則是通過分析各個目標(biāo)地點之間的關(guān)系,尋找每兩個目標(biāo)地點之間的優(yōu)選航路,在飛行過程中,還需要規(guī)避敵方防空火力、偵測雷達(dá)、地形等多種威脅源,以最大限度的保障飛行的可靠性。目前,已存在較多的航路規(guī)劃算法,如A*算法、蟻群算法、遺傳算法、粒子群算法等。特別是粒子群算法為代表的智能優(yōu)化方法在應(yīng)用于求解航路規(guī)劃問題具備實現(xiàn)簡單、優(yōu)化效果好、運算速度快的優(yōu)點,但是,運用智能優(yōu)化算法求解航路規(guī)劃問題也存在一些不足,如容易陷入局部最優(yōu),早熟收斂等問題。

UAV航路規(guī)劃問題由于包含威脅、路徑等多個目標(biāo),是一個典型的多目標(biāo)優(yōu)化問題。傳統(tǒng)的粒子群算法[2]、遺傳算法[3]、蟻群算法[4]等隨機進(jìn)化算法都是針對單目標(biāo)問題而提出,無法直接應(yīng)用于該類問題的求解。因此,在本文中將UAV的多目標(biāo)優(yōu)化問題通過目標(biāo)轉(zhuǎn)換,形成一個考慮威脅優(yōu)先,路徑優(yōu)化其次的航路優(yōu)化問題,采用了高效的粒子群算法對該問題進(jìn)行求解,并引入混沌搜索對粒子群算法的收斂性提出改進(jìn),實現(xiàn)保證UAV飛行安全前提下的完成任務(wù)的可能性,以此提高UAV到達(dá)指定地點完成任務(wù)的效率。

2 UAV航路規(guī)劃模型

2.1 UAV威脅模型

UAV所受到的威脅包括有防空火力、雷達(dá)、復(fù)雜的氣候地形等。UAV在起飛后,通常保持一定的高度飛行。考慮到UAV的飛行高度通常較高,本文中不考慮地形和氣候的影響,只考慮雷達(dá)的威脅。由于UAV反射雷達(dá)回波的強度與當(dāng)前位置與雷達(dá)的距離的四次方成反比,因此,UAV的雷達(dá)威脅近似認(rèn)為如式(1)所示[5]:

(1)

其中,Jthreat表示總威脅的大小,n為威脅的編號,li為航路位于第i個威脅范圍內(nèi)的長度,di(l)表示為航路上某一點與第i個威脅的距離。在仿真研究的過程中,通常簡化為在該航段在威脅范圍內(nèi)劃分為五段進(jìn)行計算[5]。并作簡化后得到式(2):

(2)

圖1 UAV雷達(dá)威脅描述

在式(2)中,Li為UAV的航路位于第i個威脅區(qū)域的長度,d0.1,i、d0.3,i、d0.5,i、d0.7,i、d0.9,i分別為位于第i個威脅的UAV航路中為,位于0.1、0.3、0.5、0.7、0.9位置與第i個威脅的距離,無人機的威脅代價計算各變量描述如圖1所示。ti表示第i個威脅的威脅權(quán)重。

2.2 威脅環(huán)境下的UAV航路規(guī)劃模型

因為UAV的飛行速度通常在一定的較小范圍內(nèi)調(diào)整,UAV飛行的航路越長,UAV的燃油消耗越大,所以可以用航路的長度作為評價指標(biāo),以代替UAV的燃油消耗指標(biāo)。UAV的燃油代價可描述為

Jfuel=L

(3)

由此可以得出考慮威脅環(huán)境下的UAV航跡規(guī)劃模型,既要滿足燃油的總消耗最小,亦要滿足UAV受到的威脅最小。即:

(4)

3 粒子群算法描述

粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)是一種新型的進(jìn)化計算技術(shù),由Eberhart和Kennedy于1995年提出[6]。PSO算法已經(jīng)被證明是一種有效的全局優(yōu)化方法。在PSO算法中,粒子的位置代表被優(yōu)化問題在搜索空間中的潛在解。所有的粒子都有一個被適應(yīng)度函數(shù)決定的適應(yīng)值,每個粒子還有一個速度決定它們飛翔的方向和距離。粒子們追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。PSO算法初始化為一群隨機粒子(隨機解),然后通過迭代找到最優(yōu)解,在每一次迭代中,粒子通過跟蹤兩個“極值”來更新自己:一個是粒子本身所找到的最優(yōu)解,稱為個體極值;另一個極值是整個粒子群目前找到的最優(yōu)解,稱為全局極值。基本思路依據(jù)如式(5)所示:

(5)

其中:i=1,2,…,m,m為粒子的個數(shù);d=1,2,…,D,D為每個粒子的維數(shù);xid為第i個粒子第d維的位置值;ω為非負(fù)數(shù),稱為慣性權(quán)值,其值較大有利于全局搜索最優(yōu),其值較小有利于最終結(jié)果的收斂;c1、c2為非負(fù)常數(shù),稱為加速因子,根據(jù)經(jīng)驗通常取c1=c2=2;rand(0,1)為介于0～1之間的隨機數(shù);Vi為第i個粒子的移動速度,Vid∈[-Vmax,Vmax],Vmax是常數(shù),用以限制Vid的值。Vid為第i個粒子第d維的移動速度值;Vi為這一部分表示粒子有擴展搜索空間的趨勢,即代表有全局搜索能力;pi為第i個粒子自身找到的最優(yōu)值,它代表粒子具有記憶和認(rèn)識能力。如果沒有這一項c1×rand(0,1)×(pid-xid),在微粒的相互作用下,算法也有能力到達(dá)新的搜索空間,且它的收斂速度更快,但對復(fù)雜問題則容易陷入局部最優(yōu)點;pg為所有粒子找到的最優(yōu)值,它表示所有粒子具有信息共享的能力,如果沒有這一項c2×rand(0,1)×(pgd-xid),相當(dāng)于粒子個體間沒有交互,一個規(guī)模為m個粒子的群體等價于運行了m個單個微粒的運行,因而得到解的幾率非常小[7]。

PSO算法中粒子位置的迭代過程如圖2所示。其中,xk為當(dāng)前時刻某個粒子的位置(圖中假設(shè)恰好位于原點);gbest為所有粒子經(jīng)歷的最優(yōu)位置;pbest為該粒子經(jīng)歷的最優(yōu)位置;Vk為該粒子當(dāng)前時刻的速度;Vk+1為該粒子改進(jìn)后的速度;xk+1為該粒子改進(jìn)后的位置。可見,粒子改進(jìn)后的位置更加靠近全局的最優(yōu)位置。

圖2 粒子位置迭代改進(jìn)示意圖

標(biāo)準(zhǔn)粒子群的算法流程如下:

步驟1:初始化一群粒子X={xi},i=1,2,…,m,其中m為粒子的個數(shù),包括隨機的粒子位置和速度;

步驟2:利用適應(yīng)度函數(shù)計算每個粒子的適應(yīng)值;

步驟3:對每個粒子,將其適應(yīng)值與其經(jīng)歷過的最好位置pi作比較,如果較好則將其作為當(dāng)前的最好位置pi;

步驟4:對每個粒子,將其適應(yīng)值與全局所經(jīng)歷的最好位置pg作比較,如果較好,則重新設(shè)置pg的索引號;

步驟5:根據(jù)公式更新粒子的速度和位置;

步驟6:如未達(dá)到結(jié)束條件(通常為足夠好的適應(yīng)值或達(dá)到一個預(yù)設(shè)的最大迭代次數(shù)),則返回步驟2,得到最優(yōu)粒子的位置。

4 算法實現(xiàn)

由于傳統(tǒng)的粒子群算法只適用于單目標(biāo)問題的求解,由于無人機航跡規(guī)劃存在大量的個體比較操作,而無人機航跡規(guī)劃問題同時包含了威脅和路徑兩種指標(biāo)。通常情況下,可采用罰函數(shù)法來解決此類問題,通過懲罰因子將兩種目標(biāo)轉(zhuǎn)換成單目標(biāo)進(jìn)而進(jìn)行比較,但是罰函數(shù)在應(yīng)用過程中需要反復(fù)試算,以確定懲罰因子,從而增加了實現(xiàn)的難度[9]。因此,針對無人機的航路規(guī)劃問題提出一種優(yōu)先考慮威脅,次考慮路徑目標(biāo)的比較方法,以保證無人機能夠在最安全的前提條件下,以最優(yōu)的路徑到達(dá)目的地。

4.1 目標(biāo)模型轉(zhuǎn)換

本文考慮了一種威脅目標(biāo)優(yōu)先的模型轉(zhuǎn)換方法,該方法作用于在兩個或多個無人機航路規(guī)劃方案中選擇更優(yōu)方案。該方法比較兩個航路規(guī)劃方案的過程描述如下:

1)若兩套方案都超出了無人機的飛行最大航程限制。超出最大航程短的方案優(yōu)于超出最大航程長的方案。

2)未超出最大航程的方案,優(yōu)于超出最大航程約束的方案。

3)對于未超出最大航程的兩個方案,威脅代價小的方案優(yōu)于威脅代價大的方案;威脅代價相同的個體,總航程短的個體更優(yōu)。

4.2 個體編碼

由于無人機航路規(guī)劃問題是一個三維路徑,為簡化計算采用最小威脅曲面方法,將三維規(guī)劃空間映射到二維平面,在二維平面內(nèi)對飛行路徑點進(jìn)行編碼,然后根據(jù)得到二維航路曲線以最小威脅曲面對其進(jìn)行相應(yīng)的抬高調(diào)整,即可得到最終的三維航路規(guī)劃方案[9]。因此,本文針對二維航路曲線進(jìn)行編碼,以求得無人機的二維航路曲線。由于二維平面內(nèi)的無人機航跡規(guī)劃,不考慮相應(yīng)的高程信息與地形跟隨,將包含N個航跡點的粒子個體X以及對應(yīng)的速度V分別設(shè)計如下:

(6)

其中(xi,yi)為航跡中第i個的路徑點;(x1,y1)為航跡的起點;(xN,yN)為航跡的終點;(Vxi,Vyi)表示粒子第i維的速度向量。將個體X中的各航跡點按照順序連起來,即表示為一條帶求的航路。

4.3 算法流程

針對無人機航路規(guī)劃提出的粒子群算法流程如下:

步驟1:隨機初始化種群、粒子群算法各參數(shù)。各粒子的歷史最優(yōu)解初始化為與自身相同、全局最優(yōu)解初始化為當(dāng)前種群中的最優(yōu)解。置進(jìn)化代數(shù)g=0。

步驟2:對種群進(jìn)行進(jìn)化。使用粒子群算法對群體空間每個粒子的速度和位置進(jìn)行更新。對于個體Xi更新速度和位置的公式如式(7)所示:

(7)

步驟3:更新每個粒子的歷史最優(yōu),還有種群的全局最優(yōu)。

步驟4:判斷是否啟動局部搜索,若rand()>(1-ε),則選擇當(dāng)前搜索到的最優(yōu)解進(jìn)行局部搜索,否則轉(zhuǎn)下一步。其中ε為用戶定義局部搜索系數(shù),表示進(jìn)行局部搜索的概率。

步驟5:判斷是否達(dá)到最大進(jìn)化代數(shù)MaxGen,如果g≥MaxGen,輸出當(dāng)前最優(yōu)解,算法結(jié)束,否則,g=g+1,轉(zhuǎn)步驟2。

其中,為了增強算法的收斂效果,對粒子群算法的參數(shù)ω采用式(8)計算:

ω=(ωmax-ωmin)×e-β×Gen+ωmin

(8)

其中ωmax和ωmin是ω的初始權(quán)重和最終權(quán)重因子;Gen是當(dāng)前的進(jìn)化代數(shù);β為常數(shù),決定了ω隨著進(jìn)化代數(shù)的變化速度。在算法的計算初期,一個較大的ω使算法在一個大的范圍內(nèi)搜索,提高搜索的全局性,在算法的后期,較小的ω使算法能夠在一個小范圍內(nèi)尋優(yōu),提高解的收斂精度。

4.4 局部搜索策略

在4.3節(jié)算法的計算流程中,為增強算法的搜索效果,提出一種局部搜索方法。該方法針對航路中的某個航跡點進(jìn)行局部隨機尋優(yōu)。其原理如圖3所示。

圖3 局部搜索原理示意圖

針對一個方案X的局部搜索具體過程描述如下:

步驟1:對第k維變量進(jìn)行隨機擾動,擾動的表達(dá)式如式(9)所示:

(9)

步驟2:評價得到的臨時方案X′,其中:

(10)

步驟3:如果方案X′優(yōu)于方案X,則令X=X′,局部搜索過程結(jié)束。否則,新重復(fù)循環(huán)步驟1和步驟2,若多次循環(huán)都無更優(yōu)方案,也結(jié)束循環(huán)過程。

5 仿真結(jié)果與分析

為了驗證提出算法的可行性與有效性,采用如下航跡規(guī)劃模型進(jìn)行仿真[10]:

無人機起點為(11,11),目標(biāo)點位(75,75)。中間包含一系列的威脅,威脅的數(shù)據(jù)如表1所示。

表1 威脅數(shù)據(jù)

在Intel E4600 CPU、Windows XP、JAVA環(huán)境下,采用提出的算法求解該仿真應(yīng)用運行結(jié)果如圖4所示。

圖4 算法求解航跡規(guī)劃問題結(jié)果

算法求得的最短路徑為96,威脅已經(jīng)全部避開,算法的計算耗時為0.12s,該算法不僅能夠在有效的時間范圍內(nèi)取得優(yōu)秀解,所求得的無人機航路結(jié)果中,無人機航路還避開了全部威脅源,并找到了優(yōu)化的路徑。充分證明了該方法求解無人機航跡規(guī)劃問題的可行性與高效性。

6 結(jié)語

本文提出了一種適用于無人機航路規(guī)劃問題的改進(jìn)粒子群優(yōu)化算法,該方法采用了高效的粒子群算法對該問題進(jìn)行求解,將UAV的航路規(guī)劃問題通過目標(biāo)轉(zhuǎn)換,形成一個考慮威脅優(yōu)先,路徑優(yōu)化其次的航路優(yōu)化問題,并引入混沌搜索對粒子群算法的收斂性提出改進(jìn),仿真結(jié)果表明提出的方法容易實行,求解效率高,能夠保證UAV的完成任務(wù)的安全性,并提高UAV的作戰(zhàn)效率。

[1]柳煌,夏學(xué)知.無人機航路規(guī)劃[J].艦船電子工程,2008,28(5):47-51.

[2]單敏瑜,劉以安,倪天權(quán).QPSO在無人機偵察航路規(guī)劃中的應(yīng)用研究[J].計算機工程與設(shè)計,2009,30(20):4690-4692.

[3]馬云紅,周德云.基于遺傳算法的無人機航路規(guī)劃[J].電光與控制,2005,12(5):24-27.

[4]孟祥恒,王社偉,陶軍.基于改進(jìn)蟻群算法的多無人機航路規(guī)劃研究[J].計算機仿真,2008,25(11):56-59.

[5]葉文,范洪達(dá),朱愛紅.無人飛行器任務(wù)規(guī)劃[M].北京:國防工業(yè)出版社,2011:27-29.

[6]Kennedy J, Eberhart R C. Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks. Piscataway: IEEE Press,1995:1942-1948.

[7]吳欽,許曉飛,張晶煒,等.粒子群算法在巡航導(dǎo)彈航路規(guī)劃中的應(yīng)用[J].艦船電子工程,2010,30(11):18-20.

[8]Ying Wang, Jianzhong Zhou, Hui Qin, et al. Improved Chaotic Particle Swarm Optimization Algorithm for Dynamic Economic Dispatch Problem with Valve-Point Effects[J]. Energy Conversion and Management,2010,51(12):2893-2900.

[9]唐上欽,黃長強,胡杰,等.基于威脅等效和改進(jìn)PSO算法的UCAV實時航路規(guī)劃方法[J].系統(tǒng)工程與電子技術(shù),2010,32(8):1706-1710.

[10]Chunfang Xu, Haibin Duan, Fang Liu. Chaotic artificial bee colony approach to Uninhabited Combat Air Vehicle(UAV)path planning[J]. Aerospace Science and Technology,2010(14):535-541.

PathPlanningofUAVBasedonAnImprovedPSOAlgorithm

HAN Chao1WANG Ying2

(1. Military Representative Office of Navy in No.426 Factory, Dalian 116005)

(2. Wuhan Digital Engineering Institute, Wuhan 430074)

Focus on the path planning problem of UAV, an improved particle swarm optimization algorithm is proposed in this paper. This method transforms the multi-object problem to a single one, which takes the threat-object in consideration firstly, then, the length of flying route. What’s more, a local search is imported to improve the convergence of proposed algorithm. Finally, the high efficiency and feasibility of proposed algorithm is proved by the simulation result.

path planning, UAV, particle swarm optimization algorithm, local search

2013年10月5日,

:2013年11月25日

韓超,男,工程師,研究方向:指控裝備應(yīng)用。王贏,男,工程師,研究方向:指控裝備運用。

TP391.9DOI:10.3969/j.issn1672-9730.2014.04.015