用改進(jìn)變異粒子算法實現(xiàn)突發(fā)威脅下的無人機(jī)航跡規(guī)劃

劉 月，魏瑞軒，劉 敏，周 煒

(1.空軍工程大學(xué)工程學(xué)院，西安 710038;2.中國人民解放軍63650部隊通信總站，新疆 馬蘭 841700)

0 引言

航跡規(guī)劃是無人飛行器任務(wù)規(guī)劃的重要組成部分，近年來各種優(yōu)化算法在航跡規(guī)劃中得到廣泛的應(yīng)用。Denton在動態(tài)規(guī)劃理論的基礎(chǔ)上提出的動態(tài)路徑算法，但這種傳統(tǒng)的算法計算較復(fù)雜，并且具有維數(shù)爆炸特性［1］。隨著各種智能算法理論的日趨成熟，并被運(yùn)用到航跡規(guī)劃中，具有代表性的有模擬退火法、神經(jīng)網(wǎng)絡(luò)、遺傳算法等［2－4］，這類智能算法相對于傳統(tǒng)算法具有搜索速度快、精度高等特點(diǎn)。但是在涉及到突發(fā)威脅下的無人飛行器實時航跡規(guī)劃時，這些智能算法也將不能保證全局最優(yōu)解，并且可能會陷入維數(shù)災(zāi)難，使得計算時間過長，而不能用來解決實時航跡規(guī)劃問題。本文通過研究改進(jìn)PSO粒子群算法［5］，來解決突發(fā)威脅下的無人飛行器航跡規(guī)劃問題。由于PSO算法的搜索過程中，隨著粒子向發(fā)現(xiàn)的最優(yōu)值位置聚集，粒子的速度逐漸下降，當(dāng)速度下降到一定值時，粒子已失去活性，其運(yùn)動趨于停滯，在時間性上無法滿足實時航跡規(guī)劃的要求，本文在此基礎(chǔ)上提出自適應(yīng)變異AMPSO算法，通過引入維量化活性度Ad的概念，當(dāng)種群中所有粒子在某一維的搜索趨于停滯時，觸發(fā)變異，變異措施的對象為全局粒子的位置和速度，有利于算法在該維上的充分搜索，提高搜索速度。

1 問題描述

航跡規(guī)劃的實質(zhì)是在一定的環(huán)境中，在特定的約束條件下，尋找一條從起始點(diǎn)到目標(biāo)點(diǎn)滿足某種性能指標(biāo)的最優(yōu)的或次優(yōu)的飛行軌跡［6］。它的主要目的是根據(jù)飛行器性能和飛經(jīng)的地形及敵情等信息規(guī)劃出生存概率最大的飛行軌跡，從而保證飛行器在給定的時間內(nèi)完成規(guī)定的任務(wù)。

具體地說，航跡規(guī)劃系統(tǒng)要求得到的航跡能夠有效避開敵方雷達(dá)的探測和敵方威脅的攻擊;要求避開可能影響飛行的險要地形等。

突發(fā)威脅下的實時航跡規(guī)劃還要求當(dāng)臨時出現(xiàn)事件未知，并可能會影響飛行的威脅場、惡劣氣候等情況，或者已知的威脅、地形、氣候等發(fā)生變化時，能夠?qū)崟r規(guī)劃出新的飛行航跡［7］。

航跡規(guī)劃需考慮諸多的約束條件，需要對大量的不同的信息進(jìn)行處理，如規(guī)劃區(qū)域內(nèi)地形威脅、實時敵方威脅等，因此規(guī)劃出滿意的航跡實際上是一個多維多模多目標(biāo)的優(yōu)化問題。

2 PSO算法

本文針對上述問題采用了PSO算法，并針對該算法在解決實時航跡規(guī)劃時存在的缺陷，提出具有變異機(jī)制的PSO改進(jìn)算法。

2.1 PSO算法簡介

PSO算法是設(shè)想仿真簡單的社會系統(tǒng)——鳥群覓食過程的模型，研究并解釋復(fù)雜的社會行為。與其他進(jìn)化算法相似，PSO算法也是通過個體之間的協(xié)作與競爭，每個個體遵循一定的規(guī)則運(yùn)動以實現(xiàn)復(fù)雜空間中最優(yōu)解的搜索。由于其采用的是速度—位置搜索模型，因而算法簡單，容易實現(xiàn)。

PSO算法首先生成初始種群，即在可行解空間中隨機(jī)初始化一群粒子，每個粒子都代表了優(yōu)化問題的一個潛在解，由3個指標(biāo)來表征:位置、速度、適應(yīng)度值。其中適應(yīng)值(Fitness Value)由相應(yīng)選定的目標(biāo)函數(shù)確定。每個粒子將在解空間中運(yùn)動，通常粒子將跟蹤兩個極值，一為粒子本身迄今找到的最優(yōu)解Pbest，另一個為整個種群迄今找到的最優(yōu)解Gbest，以此更新自身的速度和位置。通過計算粒子的適應(yīng)度值衡量粒子的優(yōu)劣程度，以優(yōu)劣程度更新每個粒子的Pbest和種群的Gbest，如此逐代搜索。當(dāng)?shù)Ｖ箷r，適應(yīng)度函數(shù)最優(yōu)的解變量即為優(yōu)化搜索的最優(yōu)解。

2.2 自適應(yīng)變異AMPSO算法的變異時機(jī)

借鑒遺傳算法GA的變異思想，在PSO算法通過引入維量化活性度Ad，當(dāng)種群中所有粒子在某一維的搜索趨于停滯時，觸發(fā)變異，從而提高PSO算法在搜索末期的活性。

維量化活性度Ad的定義如下:

式(1)表示的是種群中所有粒子在第d維的量化活性度。

式中:Aid表示的是aid的0－1量化值。

式中:Vid(k)為第k次迭代時第i個粒子在第d維上的速度;Rd為使用者控制的在第d維上的搜索空間范圍，AMPSO中始終取為該維的空間長度(2Xmax);c1為可調(diào)參數(shù)，取值為1;aid(k)表示的是第k次迭代時第i個粒子在第d維上速度的活性度。

式中:Ta0為初始速度閾值，取值為0.001;K1為下降系數(shù);NT為下降次數(shù)標(biāo)記;Ta表示的是粒子在各維上的速度閾值。

當(dāng)?shù)蟹N群在某一維上的維量化活性度Ad(k)小于預(yù)先設(shè)定的閾值NA時，將自動下降各維上的速度閾值Ta(隨NT的增大而減小)，同時標(biāo)記維量化活性度超過范圍的次數(shù)Nc，描述如下:

NT和Nc的初始值均為0，當(dāng)Nc累計超過一定的次數(shù)K2時，觸發(fā)AMPSO的變異，并在變異實施后，使Nc清零，重新計數(shù)。

2.3 AMPSO變異措施

AMPSO的變異措施是當(dāng)Nc累計超過一定的次數(shù)K2時，從維量化活性度低于閾值NA的這Nc維中，隨機(jī)抽取一維，對所有粒子在該維上的位置和速度實施重新初始化，使其獲得新的空間位置和速度，描述如下:

其中:randN()為N維向量，其中任一元素為［0，1］隨機(jī)數(shù);Vd=［V1d，V2d，…，VNd］，Xd=［X1d，X2d，…，XNd］，分別表示所有粒子在第d維上的速度和位置;N、Vmax、Xmax定義如前;R=(R1，R2，…，RN)，其中任一元素 Ri取值為

rand()為［0，1］隨機(jī)數(shù)。

3 突發(fā)威脅下的航跡規(guī)劃

假定飛行器上裝有具有前視探測功能的威脅探測器(設(shè)探測距離d)以及能夠?qū)崟r處理的計算機(jī)，能及時探測到飛行器附近一定范圍內(nèi)的威脅信息，探測到新威脅信息后能及時地將其納入新威脅圖。規(guī)劃方法是當(dāng)未知威脅出現(xiàn)并納入威脅圖后，重新規(guī)劃當(dāng)前位置到目標(biāo)點(diǎn)的新航跡。

3.1 航跡搜索空間構(gòu)造(節(jié)點(diǎn)拓展法)

為了滿足實時動態(tài)規(guī)劃航跡的需要，采用由起點(diǎn)至目標(biāo)點(diǎn)逐步拓展節(jié)點(diǎn)的搜索方式規(guī)劃航跡，即從起點(diǎn)開始的每一次節(jié)點(diǎn)拓展，在現(xiàn)有的威脅圖中，搜索滿足航跡代價最小和步徑要求的下一個節(jié)點(diǎn)。每次節(jié)點(diǎn)開始拓展搜索前，威脅探測器探測到的新威脅信息將和原有已知威脅一起被考慮到威脅計算之中，如此一步步的節(jié)點(diǎn)推進(jìn)，直至到達(dá)目標(biāo)點(diǎn)［8－9］。

3.2 威脅模型與航跡代價指標(biāo)

1)威脅模型。

一個理論威脅突防模型由敷設(shè)在地形模型上的不同威脅模型、地形遮蔽算法和與RCS數(shù)據(jù)有關(guān)的飛行器特征模型組成。對于二維水平航跡規(guī)劃而言，由于不考慮地形因素，故規(guī)劃的主要目的是減少被敵方防空火力攻擊、探測裝置發(fā)現(xiàn)的概率。這里，以威脅的探測概率隨距離增大指數(shù)遞減為例進(jìn)行仿真，形式如下:

其中:ei表示第i個威脅源產(chǎn)生的威脅;ki為其對應(yīng)的威脅幅值;α為威脅衰減系數(shù);di為當(dāng)前航跡上位置與第i個威脅源的距離，航跡上某一位置受到的總威脅為所有威脅源產(chǎn)生的威脅的疊加。突發(fā)威脅為預(yù)先未知的，飛行器只有在飛到其附近時方能探測到。

2)航跡代價指標(biāo)。

對于采用節(jié)點(diǎn)逐步拓展的航跡規(guī)劃，每一個待拓展節(jié)點(diǎn)希望其滿足航路最短、威脅代價最小和步徑長度的要求，為此設(shè)計評價粒子優(yōu)劣的適應(yīng)度函數(shù)如下:

其中:w1、w2、w3為權(quán)重;l為粒子位置到當(dāng)前節(jié)點(diǎn)距離;Δl為步徑長度;k為當(dāng)前所有威脅的個數(shù);L為粒子位置到目標(biāo)點(diǎn)的距離;D為當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的距離。式中第1項和第3項為滿足航跡最短和步徑的要求，中間項為威脅代價。

3)航跡搜索空間的構(gòu)造。

在文獻(xiàn)［10］中采用一個有限項的一元多項式函數(shù)作為水平航跡的逼近，將規(guī)劃問題簡化為在一個一元函數(shù)多項式系數(shù)空間中的搜索尋優(yōu)。由于多項式函數(shù)便于計算和求導(dǎo)，且系數(shù)有限，所以有利于算法收斂速度的提高。航跡可表示為

起點(diǎn)位置和期望的目標(biāo)位置是已知的，分別設(shè)為(x0，y0)和(xt，yt)，則有:

其中:gi是 a3，a4，…，an的函數(shù)(i=1，2，3)，即系數(shù)a0，a1，a2可以由其他系數(shù)表示。于是最優(yōu)航跡的規(guī)劃問題變成了在縮小的多項式系數(shù)空間［a3，a4，…，an］的尋優(yōu)。

需指出的是，采用如上的方式逼近航跡是有較大缺陷的，某些可能的航跡無法直接表示，例如圖1所示的航跡。

圖1 航跡示意圖Fig.1 Sketch map of flight path

圖2 新坐標(biāo)系定義Fig.2 Definition of the new coordinate system

而如果以起點(diǎn)為坐標(biāo)原點(diǎn)，以起點(diǎn)到目標(biāo)點(diǎn)的方向為x軸，以其垂直方向為y軸，在很大程度上可以將航線看成是單值函數(shù)。新的坐標(biāo)系定義如圖2所示，此時，起點(diǎn)與目標(biāo)點(diǎn)可以表示為(0，0)和(xt，0)。同樣在考慮了起點(diǎn)、目標(biāo)點(diǎn)約束和方位角約束下，可推導(dǎo)出新的變量關(guān)系表達(dá)式為

4)算法流程。

針對上述模型，具備了采用變異粒子群算法進(jìn)行搜索的條件，設(shè)計其算法流程如下:

①每次節(jié)點(diǎn)拓展時，首先在搜索空間中隨機(jī)地產(chǎn)生初始化規(guī)模為n的種群，種群中的每個粒子位置xi和速度 vi分別記為(xi1，xi2)和(vi1，vi2);

②利用適應(yīng)度函數(shù)評價每個粒子優(yōu)劣，并計算當(dāng)前節(jié)點(diǎn)拓展時每個粒子的適應(yīng)度值，當(dāng)威脅探測器探測距離內(nèi)出現(xiàn)未知威脅或已知威脅變化時，將其一起納入威脅代價函數(shù)計算;

③記錄和更新粒子的個體極值和全局極值;

④利用AMPSO算法含變異的位置與速度公式更新粒子的位置和速度;

⑤判斷是否達(dá)到最大迭代次數(shù)，如果是，結(jié)束本次節(jié)點(diǎn)的拓展尋優(yōu)，并將當(dāng)前最優(yōu)位置作為下一次搜索的開始節(jié)點(diǎn)，準(zhǔn)備進(jìn)入下次節(jié)點(diǎn)拓展;不是，則返回②。

4 仿真驗證

仿真中，航跡搜索空間設(shè)置為100 km×100 km的區(qū)域，起始點(diǎn)和目標(biāo)點(diǎn)分別設(shè)置在(10，10)和(90，90)，航跡代價中權(quán)重系數(shù) w1、w2、w3分別設(shè)為 100、1、2，每次節(jié)點(diǎn)拓展時最大迭代次數(shù)為500，威脅的設(shè)置如表1所示。

表1 威脅參數(shù)設(shè)置Table 1 Parameter setting of the threats

其中:第5個威脅為預(yù)先未知威脅，威脅探測器探測距離設(shè)為20 km，每次步徑長度取2 km，仿真結(jié)果如圖3和圖4所示，圖中小圓點(diǎn)為每次拓展搜索得到的航跡節(jié)點(diǎn)。

實驗在CPU 1.6 GHz的計算機(jī)上進(jìn)行，軟件環(huán)境為Matlab6.5，完成一次已知威脅下的全部規(guī)劃約需130 s，其中節(jié)點(diǎn)拓展搜索約62～64次，如圖3所示。于是，可計算出每次節(jié)點(diǎn)拓展搜索平均耗時約2 s。

在節(jié)點(diǎn)拓展搜索的第23次加入突發(fā)威脅(即在威脅的邊緣)，通過仿真圖4可以看出，航跡能有效地避開威脅，并能使航跡代價指標(biāo)最小。仿真結(jié)果顯示，完成一次含有突發(fā)威脅下的航跡規(guī)劃約需136 s，其中節(jié)點(diǎn)拓展搜索約66～69次，平均耗時約2 s。

圖3 已知威脅下航跡規(guī)劃圖Fig.3 Path planning without unexpected threats

圖4 存在未知威脅下航跡規(guī)劃圖Fig.4 Path planning with unexpected threats

假設(shè)飛行器速度為200～300 m/s，而規(guī)劃中步徑長度為2 km，即是說一次允許的實際規(guī)劃時間為6.7～10 s。可見，利用AMPSO算法的節(jié)點(diǎn)拓展搜索的規(guī)劃方法，可以滿足應(yīng)對突發(fā)威脅下航跡規(guī)劃的要求，同時可以通過適當(dāng)增大步徑長度，減少每次規(guī)劃時間，以降低對計算機(jī)性能的要求。

5 結(jié)論

本文將PSO算法成功應(yīng)用于解決航跡規(guī)劃問題，根據(jù)實際問題的需要提出了改進(jìn)的AMPSO算法，對存在突發(fā)威脅情況下航跡規(guī)劃問題進(jìn)行了研究。仿真表明，基于AMPSO算法的航跡規(guī)劃具有較快的搜索速度和較高的精度，對于不確定環(huán)境下的實時航跡規(guī)劃，可以滿足要求，不過本文所假設(shè)的威脅模型比較簡單，不需要涉及到復(fù)雜的規(guī)劃決策問題，這一點(diǎn)將在下一步工作中繼續(xù)改進(jìn)。

［1］DENTON R V，JONES J E，F(xiàn)ROEBERG P L.A new technique for terrain following/terrain avoidance guidance command generation［R］.AGARD-CP-387，1985.

［2］任波，何可.改進(jìn)遺傳模擬退火算法的航跡規(guī)劃方法研究［J］.飛行力學(xué)，2008，26(2):85-88.

［3］葛哲學(xué)，孫志強(qiáng).神經(jīng)網(wǎng)絡(luò)理論與實現(xiàn)［M］.北京:電子工業(yè)出版社，2007.

［4］馬云紅，周德云.基于遺傳算法的無人機(jī)航跡規(guī)劃［J］.電光與控制，2005，12(5):24-27.

［5］KENNEDY J，EBERHART R C.Particle swarm optimization［C］//Perth，Western Autralia:IEEE International Conference on Neural Networks，1995:1942-1948.

［6］閔昌萬，袁建平.軍用飛行器航跡規(guī)劃綜述［J］.飛行力學(xué)，1998，16(4):14-19.

［7］唐強(qiáng)，張翔倫，左玲.無人機(jī)航跡規(guī)劃算法的初步研究［J］.航空計算技術(shù)，2003，33(1):125-128.

［8］HWANG J Y，KIM J S，LIM S S.A fast path planning by path graph optimization［J］.IEEE Transactions on System，Man，and Cybernetics，2003，33(1):121-128.

［9］HECKBERT P S，GARLAND M.Survey of polygonal surface simplification algorithms［Z］.SIGGRAPH’97 Course Notes，1997.

［10］唐強(qiáng)，王建元，朱志強(qiáng).基于粒子群優(yōu)化的三維突防航跡規(guī)劃仿真研究［J］.系統(tǒng)仿真學(xué)報，2004，16(9):2033-2036.