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

韓 超 王 贏

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

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

韓 超1王 贏2

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

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

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

ClassNumberTP391.9

1 引言

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

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

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

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

2.1 UAV威脅模型

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

(1)

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

(2)

圖1 UAV雷達威脅描述

在式(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的燃油消耗越大,所以可以用航路的長度作為評價指標,以代替UAV的燃油消耗指標。UAV的燃油代價可描述為

Jfuel=L

(3)

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

(4)

3 粒子群算法描述

粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)是一種新型的進化計算技術,由Eberhart和Kennedy于1995年提出[6]。PSO算法已經(jīng)被證明是一種有效的全局優(yōu)化方法。在PSO算法中,粒子的位置代表被優(yōu)化問題在搜索空間中的潛在解。所有的粒子都有一個被適應度函數(shù)決定的適應值,每個粒子還有一個速度決定它們飛翔的方向和距離。粒子們追隨當前的最優(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維的位置值;ω為非負數(shù),稱為慣性權(quán)值,其值較大有利于全局搜索最優(yōu),其值較小有利于最終結(jié)果的收斂;c1、c2為非負常數(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)值,它代表粒子具有記憶和認識能力。如果沒有這一項c1×rand(0,1)×(pid-xid),在微粒的相互作用下,算法也有能力到達新的搜索空間,且它的收斂速度更快,但對復雜問題則容易陷入局部最優(yōu)點;pg為所有粒子找到的最優(yōu)值,它表示所有粒子具有信息共享的能力,如果沒有這一項c2×rand(0,1)×(pgd-xid),相當于粒子個體間沒有交互,一個規(guī)模為m個粒子的群體等價于運行了m個單個微粒的運行,因而得到解的幾率非常小[7]。

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

圖2 粒子位置迭代改進示意圖

標準粒子群的算法流程如下:

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

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

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

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

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

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

4 算法實現(xiàn)

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

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

本文考慮了一種威脅目標優(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ù)得到二維航路曲線以最小威脅曲面對其進行相應的抬高調(diào)整,即可得到最終的三維航路規(guī)劃方案[9]。因此,本文針對二維航路曲線進行編碼,以求得無人機的二維航路曲線。由于二維平面內(nèi)的無人機航跡規(guī)劃,不考慮相應的高程信息與地形跟隨,將包含N個航跡點的粒子個體X以及對應的速度V分別設計如下:

(6)

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

4.3 算法流程

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

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

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

(7)

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

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

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

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

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

(8)

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

4.4 局部搜索策略

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

圖3 局部搜索原理示意圖

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

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

(9)

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

(10)

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

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

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

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

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

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

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

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

6 結(jié)語

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

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

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

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

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

[5]葉文,范洪達,朱愛紅.無人飛行器任務規(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]吳欽,許曉飛,張晶煒,等.粒子群算法在巡航導彈航路規(guī)劃中的應用[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]唐上欽,黃長強,胡杰,等.基于威脅等效和改進PSO算法的UCAV實時航路規(guī)劃方法[J].系統(tǒng)工程與電子技術,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日

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

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