韓 超 王 贏

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

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

韓 超1王 贏2

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

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

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

ClassNumberTP391.9

1 引言

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

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

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

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

2.1 UAV威脅模型

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

(1)

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

(2)

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

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

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

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

Jfuel=L

(3)

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

(4)

3 粒子群算法描述

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

(5)

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

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

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

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

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

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

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

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

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

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

4 算法實(shí)現(xiàn)

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

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

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

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

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

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

4.2 個(gè)體編碼

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

(6)

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

4.3 算法流程

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

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

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

(7)

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

步驟4:判斷是否啟動(dòng)局部搜索,若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。

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

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

(8)

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

4.4 局部搜索策略

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

圖3 局部搜索原理示意圖

針對(duì)一個(gè)方案X的局部搜索具體過(guò)程描述如下:

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

(9)

步驟2:評(píng)價(jià)得到的臨時(shí)方案X′,其中:

(10)

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

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

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

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

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

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

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

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

6 結(jié)語(yǔ)

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

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

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

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

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

[5]葉文,范洪達(dá),朱愛(ài)紅.無(wú)人飛行器任務(wù)規(guī)劃[M].北京:國(guó)防工業(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]唐上欽,黃長(zhǎng)強(qiáng),胡杰,等.基于威脅等效和改進(jìn)PSO算法的UCAV實(shí)時(shí)航路規(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)用。王贏,男,工程師,研究方向:指控裝備運(yùn)用。

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