王明明　夏學知

(武漢數(shù)字工程研究所　武漢　430205)

?

復雜環(huán)境下無人飛行器航路規(guī)劃技術(shù)研究*

王明明夏學知

(武漢數(shù)字工程研究所武漢430205)

摘要為解決常用航跡規(guī)劃算法在復雜環(huán)境下飛行時收斂速度慢、容易陷入局部最優(yōu)的問題，論文提出了一種基于模擬退火的復合粒子群優(yōu)化算法。通過對復雜環(huán)境進行建模，生成融合了地形、地物及威脅信息的等效數(shù)字地形圖，并在該地圖上使用該改進算法進行航跡規(guī)劃。實驗結(jié)果表明，基于模擬退火的融合粒子群優(yōu)化算法具有較好的可行性和實時性，能夠有效解決復雜環(huán)境下無人飛行器航跡規(guī)劃的空間復雜度、搜索效率等，加快全局收斂速度，保持標準粒子群算法較強的魯棒性，并能夠?qū)崟r避開障礙和規(guī)劃出最優(yōu)或次優(yōu)的路徑。

關鍵詞無人飛行器; 航跡規(guī)劃; 粒子群算法; 威脅建模與回避

Class NumberV279

1引言

無人飛行器(Unmanned Aerial Vehicles，UAV)航跡規(guī)劃[1]就是指在綜合無人飛行器自身機動性能和飛行空間環(huán)境信息的基礎上，為其提供一條從起始點到目標點安全性較高、航跡代價較小的飛行航跡。無人飛行器航跡規(guī)劃系統(tǒng)作為UAV任務規(guī)劃系統(tǒng)中的關鍵組成部分，為實現(xiàn)無人飛行器自主控制、智能飛行[2]提供了最有力的技術(shù)保障。航跡規(guī)劃一般分為全局航跡靜態(tài)規(guī)劃和局部航跡動態(tài)規(guī)劃[3]：全局航跡規(guī)劃一般是起飛前在地面完成的，并以代碼形式輸入到機載無人機自動駕駛儀中，作為UAV飛行的參考航跡;局部航跡規(guī)劃是指無人飛行器在任務飛行過程中遇到新威脅時對參考航跡所做的局部重規(guī)劃。由目前研究的情況可知：雖然無人飛行器航跡規(guī)劃研究起步較早，可供選擇的算法[4]也很多，但是算法要么具有不錯的魯棒性卻不夠快速，要么基本上能滿足實時性要求卻不夠穩(wěn)定;并且很少將算法擴展到三維航跡實時重規(guī)劃這個問題上。針對上述問題，本文首先采用數(shù)字地圖融合的思想，在地面上預先把飛行區(qū)域內(nèi)已知的地形、地物及威脅信息融合成一種綜合的地形信息，從而使得航跡優(yōu)化過程中信息掃描的時間變短，同時將威脅回避轉(zhuǎn)化為地形回避來處理，簡化了航跡優(yōu)化算法，滿足了實時性的要求。然后吸收作為群體智能算法典型代表粒子群算法的核心思想，對離散域搜索問題在速度進化方程中考慮慣性權(quán)重因子，同時在粒子群優(yōu)化(Particle Swarm Optimization，PSO)算法參數(shù)確定過程中引入模擬退火操作，形成一種改進的粒子群優(yōu)化算法，從而彌補常規(guī)PSO算法參數(shù)取值過程全憑經(jīng)驗和極易陷入局部最優(yōu)(即早熟現(xiàn)象)的不足，改善其全局尋優(yōu)能力，然后用來解決UAV的復雜航路規(guī)劃問題[5～6]。

2復雜環(huán)境下無人機航跡規(guī)劃

無人機航跡規(guī)劃是為無人機規(guī)劃出一條滿意的航跡，而航跡是由許多航跡點描述的，因此真正規(guī)劃的是這些航跡點。無人機飛行的任務環(huán)境簡單時，常用的航跡規(guī)劃方法通?？梢缘玫揭粭l滿意的航跡，但是當環(huán)境復雜時(文中的復雜環(huán)境指的是地形復雜或威脅數(shù)量與種類眾多)，將很難獲得一條滿意航跡。

以復雜地形為例，當需要引導無人機在圖1所示的地形下飛行時，由于無人機的飛行高度需要保持在一定的范圍內(nèi)，因此需要規(guī)劃出較多的航跡點才能實現(xiàn)類似于地形跟蹤的安全飛行航跡。圖中地形有三次起伏，通過七個航跡點(圖中實線連接點)可以較好的滿足高度約束，而若只采取五個航跡點(圖中虛線連接點)，將難以實現(xiàn)在避撞的同時滿足最大飛行高度的約束。復雜地形下的起伏將很多，此時將需要大量的航跡點來描述。另外，環(huán)境中威脅很多時，為了回避威脅也將需要大量的航跡特征點來描述航跡。

圖1　航跡規(guī)劃示意圖

近年來，以隨機搜索為特征的遺傳算法[7～8]，由于其全局搜索能力很強，因此在無人機航跡規(guī)劃中得到極大應用。但隨著航跡點數(shù)越多、規(guī)劃維度越高，遺傳算法的計算量隨優(yōu)化問題的維度將呈指數(shù)增加，算法的收斂時間顯著增加。而粒子群算法[9]相比遺傳算法，其通過粒子間的信息交互，能夠快速收斂于解空間中的某一點，收斂速度很快，但是后期會出現(xiàn)早熟現(xiàn)象而陷入局部最優(yōu)，全局搜索能力很差;尤其是粒子群算法中控制參數(shù)的設定，往往是根據(jù)實際的問題，通過大量的試驗，憑借研究經(jīng)驗做出選擇，操作起來十分困難。針對粒子群算法存在的上述缺點，本文提出一種基于模擬退火思想的復合粒子群改進方法，在PSO中引入模擬退火的思想，在優(yōu)化過程中自動優(yōu)選控制參數(shù)，以此構(gòu)建一種復合粒子群算法。

3航跡規(guī)劃建模

3.1建立數(shù)字地圖

本文在進行環(huán)境建模時，包括了原始地形的建模、障礙區(qū)域的建模和威脅區(qū)域的建模[10]。

在進行原始地形建模時，飛行區(qū)域設為100×100的直角坐標區(qū)域，分別將飛行區(qū)域中每個點所對應的z(x,y)的值設為5×rand，即原始地形點z軸的值是在0～5之間的隨機數(shù)。

(1)

(2)

(3)

將上述地形等效融合成飛行區(qū)域的數(shù)字地形圖，融合算法如式(4)。

z(x,y)=max[z1(x,y),z2(x,y),z3(x,y)]

(4)

式(4)中，(x,y)代表地形中每個點投影到平面上的點坐標，z1(x,y)、z2(x,y)和z3(x,y)則表示地形中每個點的相應地形高度;n代表山峰總數(shù)，hi表示第i座山峰的高度，(xi,yi)為第i座山峰的地理中心坐標，ki表示第i座山峰在x軸和y軸方向的坡度向量;(x0,y0,z0)為球心坐標，r代表球體半徑，r0是距離氣象威脅中心的距離。

在根據(jù)式(4)得到各個點的數(shù)據(jù)后，如果直接進行繪圖得到的圖形還不能滿足要求，圖形棱角比較明顯，需要進行插值來平滑圖形。現(xiàn)在常用的樣條函數(shù)稱為Cubic Spline，即三階樣條函數(shù)。本文在建模時采用了規(guī)格的樣條函數(shù)，用interp2命令進行樣條函數(shù)插值，根據(jù)表1～表3中給出的參數(shù)設置地形和威脅源，最后得到如圖2所示的等效數(shù)字地圖。其中，坐標系水平方向以100m為單位。山體地形的最大高程為110.68m，任務區(qū)域的范圍為10km×10km。

表1　山峰地圖參數(shù)

表2　雷達探測模型參數(shù)

表3　氣象威脅模型參數(shù)

圖2　等效數(shù)字地圖

3.2無人機建模

假設飛行器控制系統(tǒng)理想工作，并忽略它的旋轉(zhuǎn)慣性和旋轉(zhuǎn)角速度對力矩的影響，在求解飛行器軌跡時，由于并不關心它的具體結(jié)構(gòu)，可以把飛行器當作質(zhì)點考慮。飛行器的質(zhì)點動力學模型如下：

(5)

其中，x、y、z為飛行器在地面坐標系中的位置坐標;nx、ny、nz分別為地面坐標系中飛行器的切向過載和法向過載;θ、ψ分別為航跡傾角和航跡偏角。

3.3航跡評價函數(shù)

復雜環(huán)境下無人機航跡規(guī)劃的評價函數(shù)Fmain(xi)包括地形威脅代價Fterrain(xi)、自身性能限制代價Fself_performance(xi)和最短航程代價Fmin_path(xi)，如式(6)所示。

Fmain(xi)=ω1Fterrain(xi)+ω2Fself_performance(xi)

+ω3Fmin_path(xi)

(6)

其中，地形威脅代價Fterrain(xi)又包括山峰地形威脅代價fterrain(xi)、雷達探測威脅代價fradar(xi)和氣象因素威脅代價fdemage(xi)，如式(7)所示。

(7)

而自身性能限制代價Fself_performance(xi)包括最大轉(zhuǎn)彎角度限制代價fturn_angle(xi)、最小步長限制代價fmin_step(xi)、最小飛行高度限制代價fmin_height(xi)、最大爬升角度限制代價fvertical_angle(xi)和最大飛行距離限制代價fmax_distance(xi)，如式(8)所示。

Fself_perform(xi)=β1fturn_angle(xi)+β2fmin_step(xi)

+β3fmin_height(xi)+β4fvertical_angle(xi)

+β5fmax_distance(xi)

(8)

(9)

其中，Rt表示無人機到山體的距離，Rm表示等高線上的山體半徑。由式(9)可知，無人機與山體間的安全距離為10m，最小距離為4m。當無人機與山體間距離大于最大安全距離時，代價為0，而當與山體距離小于最小安全距離時，代價為1。

(10)

其中，dRmax為雷達實際探測的最大水平作用半徑，d為飛行器與雷達的水平距離。

3) 氣象因素威脅代價

(11)

其中，Qi(j)表示無人機在第i條航跡下受第j種氣象因素影響時損毀的概率，Rjmax表示第j種氣象因素的作用范圍，R表示無人機距某氣象因素作用中心的距離，kj為損毀概率。

4) 最短航程代價

(12)

其中，l表示起點和終點之間的直線距離，di表示航跡中每個航段的長度。

5) 最大轉(zhuǎn)彎角度限制代價

(13)

其中，ψ表示無人機在相鄰航段之間的轉(zhuǎn)彎角度。

6) 最小步長限制代價

(14)

其中，i為當前航跡節(jié)點i到上一個航跡節(jié)點i-1的距離。

7) 最小飛行高度限制代價

(15)

其中，ΔH是根據(jù)環(huán)境分析以及任務需要所得出的最優(yōu)的飛行高度。hi為無人機距地面高度。正數(shù)kh為約束值。

8) 最大爬升角度限制代價

(16)

其中，γ為當前航段中無人機的爬升和俯沖角度。

9) 最大飛行距離限制代價

(17)

其中，dmax為無人機的最大飛行距離，d為無人機的航程。

3.4最小威脅曲面

在建立數(shù)字地圖時，將各種威脅等效成地形威脅疊加到數(shù)字地圖[11]上，這樣得到的數(shù)字地圖不僅包含地形的信息，也考慮了威脅的信息，其中威脅的作用相當于抬高了當?shù)氐牡匦巍？紤]了威脅信息對數(shù)字地圖的抬高作用后，定義一個由所有距離地表高度為h的點所構(gòu)成的曲面，當無人機飛行在這個曲面上時具有最小的危險性，則飛行器的最小危險飛行航跡一定位于這個曲面上。設合成后的數(shù)字地圖高程為z(x,y)，則最小威脅曲面為

z(x,y)=T(x,y)+z(x,y)

(18)

4航跡規(guī)劃算法

4.1標準粒子群算法

粒子群優(yōu)化算法是由Kennedy博士和Eberhart于1995年提出的一種新的群體智能優(yōu)化算法。在粒子群優(yōu)化算法中，每個粒子都有自己的位置和速度，還有一個由被優(yōu)化函數(shù)決定的適應度值，而且知道自己當前發(fā)現(xiàn)的最好位置pBest和現(xiàn)在的位置xi，粒子的位置代表被優(yōu)化問題在搜索空間中的潛在解，粒子群追隨當前的最優(yōu)粒子在解空間中搜索。PSO算法初始化為一群隨機粒子(即隨機解)，然后通過迭代尋找最優(yōu)解，在每一次迭代中，粒子通過跟蹤兩個極值來更新自己的位置和速度。對于前面所說的兩個極值，一個是粒子本身所找到的最優(yōu)解，稱為個體極值pBest;另一個極值是整個粒子群目前找到的最優(yōu)解，稱為全局極值gBest。設第i個粒子(i=1,2,…,N)的D維位置矢量為xi=(xi1,xi2,…,xid,…,xiD)，第i個粒子的飛行速度為vi=(vi1,vi2,…,vid,…,viD)，該種群中第i個粒子迄今為止搜索到的最優(yōu)位置記為pid;當前種群中適應度值最大的粒子位置為pgd。標準粒子群算法位置和速度的更新公式為

(19)

(20)

其中i=1,2,…,N；d=1,2,…,D;c1和c2為學習因子，通常C1=C2=2；r1和r2是之間的隨機數(shù);k為迭代次數(shù)。粒子在不斷根據(jù)速度調(diào)整自己位置的時候，為防止粒子由于速度過大而遠離搜索空間，還要受到最大速度Vmax的限制。當Vi超過Vmax時，將被限定為Vmax;粒子位置xid的取值范圍為xmin～xmax。

4.2粒子群算法改進

(21)

針對粒子群算法容易陷入局部最優(yōu)，全局搜索能力差，以及控制參數(shù)設定困難的問題，本文將模擬退火的思想融入到粒子群算法中，使算法可以以一定概率接受使評價函數(shù)適應度“變差”的解，避免陷入局部最優(yōu)，從而增強算法全局搜索的能力;同時在PSO算法參數(shù)確定過程中引入模擬退火操作，如此一來，可省去選取參數(shù)的麻煩，而且在優(yōu)化過程中，參數(shù)能夠自適應的根據(jù)算法進行改變。

5基于改進粒子群算法的無人機航跡規(guī)劃

本文利用基于模擬退火的復合粒子群優(yōu)化算法進行單個無人機的三維航跡規(guī)劃，每個粒子代表一個潛在的可行路徑。該復合算法把粒子群算法作為主要的算法，其參數(shù)慣性權(quán)重ω、學習因子c1和c2的設定作為一個小的優(yōu)化問題，由模擬退火在一定范圍內(nèi)進行優(yōu)化。在每一次的優(yōu)化過程中，粒子群算法中的最優(yōu)適應度函數(shù)既是粒子群的適應度，同時也是模擬退火對參數(shù)優(yōu)化過程中的評價值。由于模擬退火思想可以以一定概率接受“惡化”解，因此，可以幫助粒子跳出局部的極值，從而找到全局最優(yōu)極值。算法具體實現(xiàn)步驟如下所示。

Step1：粒子群的初始化。

2)根據(jù)式(6)計算每個粒子的航跡評價函數(shù)f(xi)，相應地初始化個體極值pBest和群體極值gBest。

Step2：模擬退火的初始化。

1)設置初始溫度T=10000，溫度衰減因子decayScale=0.7，生成初始解S(ω,c1,c2);

2)求評價函數(shù)C(s)：按照式(19)和式(20)更新速度vi和位置xi，并計算出航跡評價函數(shù)f(xi)，根據(jù)航跡評價函數(shù)值相應的更新pBest和gBest，取C(s)=gBest。

Step4：按照式(19)和式(20)更新速度vi和位置xi，其中ω、c1和c2按照S′取值。

Step5：計算航跡評價函數(shù)f(xi)。

Step6：求得C(s′)=min[f(xi),i=1,2，…,m]，ΔC=C(s′)-C(s);如果ΔC<0，則C(s)=C(s′)，S=S′，并接受由S′所更新的速度和位置;如果ΔC>0且exp(-ΔC/T)>rand(0,1)，則C(s)=C(s′),S=S′,T=decayScale*T，仍然接受由S′所更新的速度和位置;如果ΔC>0且exp(-ΔC/T)

Step7：根據(jù)航跡評價函數(shù)值更新pBest和gBest。

Step8：判斷是否達到內(nèi)層循環(huán)迭代次數(shù)或是否滿足內(nèi)層循環(huán)約束條件;若滿足，轉(zhuǎn)Step9;否則，轉(zhuǎn)Step3。

Step9：判斷是否達到外層循環(huán)迭代次數(shù)或是否滿足外層循環(huán)約束條件;若滿足，則輸出最優(yōu)值;否則，轉(zhuǎn)Step2。

6仿真及分析

將圖2所示的數(shù)字地形圖作為無人機航跡規(guī)劃的任務環(huán)境;為了測試本文算法在無人機航跡規(guī)劃方面的性能，分別按標準粒子群優(yōu)化算法(SPSO) (ω=0.7)、線性遞減慣性權(quán)重粒子群優(yōu)化算法(LDPSO)和本文提出的基于模擬退火算法的復合粒子群優(yōu)化算法(SAPSO)進行航路規(guī)劃實驗。設置起始點為(10，50，50)，目標點為(95，50，50)，種群規(guī)模N=40，迭代次數(shù)為100，其中D=9，則每個粒子代表的航跡中包含9個航跡控制節(jié)點。慣性權(quán)重ω取值為0.9到0.4成線性遞減，學習因子c1=c2=[1.8,2.2]，初始溫度T=10000，衰減因子為0.7。適應度函數(shù)如式(6)。在這里無人機完成任務時采取的策略是速度與安全性并重的策略。當?shù)螖?shù)達到最大或連續(xù)五代種群最優(yōu)值標準差小于0.0001時，算法停止。有關適應度函數(shù)的加權(quán)設置如表4所示。

表4　權(quán)重參數(shù)取值

根據(jù)表4中的參數(shù)取值，然后求解適應度函數(shù)。使用Matlab2013a對靜態(tài)航跡規(guī)劃進行仿真。三種算法各運行50次，實驗結(jié)果見表5。

表5　三種算法實驗結(jié)果表

從實驗結(jié)果可以看出，標準粒子群優(yōu)化算法(SPSO)極易陷入局部最優(yōu);而在速度進化方程中考慮隨進化代數(shù)線性遞減的慣性因子后，能明顯增強算法的收斂能力，一定程度地改善早熟現(xiàn)象;當在粒子群優(yōu)化算法參數(shù)確定過程中引入模擬退火操作后，早熟現(xiàn)象得以充分改觀，收斂速度顯著加快(平均80代以內(nèi)即找到最優(yōu)解);但搜索時間略有增加。

綜合改進的粒子群優(yōu)化算法在數(shù)字地圖中規(guī)劃出的可行的航跡示意圖分別如圖3和圖4所示。為使規(guī)劃出的航跡更貼近無人機實際飛行時的路線，本文還使用了點間擬合的方法將兩兩航跡控制點依次擬合起來。

圖3　全局航跡規(guī)劃三維立體圖

圖4　全局航跡規(guī)劃等高線圖

由于本文算法在航跡規(guī)劃的精度和速度上都有較好的效果，不僅適用于全局靜態(tài)航跡規(guī)劃，也可進行局部動態(tài)航跡規(guī)劃，為了檢驗算法在復雜環(huán)境下在線動態(tài)規(guī)劃的能力，本文在上面得到的全局航跡規(guī)劃的路線中增加突發(fā)威脅，如圖5所示，當傳感器探測到前方有突發(fā)威脅時，無人機會以當前航跡控制節(jié)點為起點，出現(xiàn)突發(fā)威脅路段的下一個航跡控制節(jié)點為目標點進行局部動態(tài)航跡規(guī)劃。如圖6所示，無人機可以在該算法的引導下及時避開突發(fā)威脅。

圖5　突發(fā)威脅示意圖

圖6　局部動態(tài)航跡三維立體圖

7結(jié)語

在對UAV飛行復雜環(huán)境建立的等效數(shù)字地圖基礎上，采用本文提出的一種改進的PSO算法，即在速度進化方程中考慮慣性權(quán)重因子，同時在粒子群優(yōu)化算法參數(shù)確定過程中引入模擬退火操作，然后進行航跡規(guī)劃。仿真實驗結(jié)果表明，本文提出的改進PSO算法彌補常規(guī)PSO算法參數(shù)取值過程全憑經(jīng)驗和極易陷入局部最優(yōu)(即早熟現(xiàn)象)的不足，改善其全局尋優(yōu)能力，然后用來解決UAV的復雜航路規(guī)劃問題。

參 考 文 獻

[1] Chao Zhang， Ziyang Zhen， Daobo Wang， Meng Li. UAV Path Planning Method Based on Ant ColonyOptimization[C]//ControI and Decision Conference(CCSC)，2010 China，2010:3790-3792.

[2] Shao P C， Chang Y H， Chen H J. Analysis of an aircraft accident model in Taiwan[J]. Journal of Air Transport Management， 2013， 27: 34-38.

[3] Amin Jayesh N，Boskovic Jovan D，et.al. A fast and efficient approach to path planning for unmanned vehicles [C]// United states: Guidance， Navigation， and Control Conference， 2006:871-879

[4] Pehlivanoglu YV.A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV[J].Aerospace Science and Technology， 2012，16(1):47-55.

[5] Koyuncu E， Garcia E， Inalhan G. Flight deck automation support with dynamic 4D trajectory management for ACAS: AUTOFLY-Aid[C]// Integrated Communications， Navigation and Surveillance Conference (ICNS)， 2012. IEEE， 2012: C4-1-C4-9.

[6] Nikolos I K，Valavanis K P，Tsourveloudis N C.Evolutionary algorithm based offline/online path planner for UAV navigation[J]. IEEE Transaction on Systems， Man， and Cybernetics-PartB，2003，33(6):898-912.

[7] Pehlivanoglu YV.A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV[J].Aerospace Science and Technology， 2012，16(1):47-55.

[8] Fu S Y， Han L W， Tian Y， et al. Path planning for unmanned aerial vehicle based on genetic algorithm. Cognitive Informatics & Cognitive Computing (ICCI* CC)[C]//2012 IEEE 11th International Conference on. IEEE， 2012: 140-144.

[9] Yong Bao， Xiaowei Fu， Xiaoguang Gao. Path Planning for Reconnaissance UAV Based on Particle Swarm Optimization [C]//2010 Second International Conference on Computational Intelligence and Natural Computing (CINC):28-32.

[10] Zhou S， Zhu G， Li H， et al. Real-time route planning for UAV based on weather threat[C]// Remote Sensing， Environment and Transportation Engineering (RSETE)， 2011 International Conference on. IEEE， 2011: 2342-2345.

[11] Ge Y， Yuan L， Zhang W. Path planning based on graphical search ant colony algorithm for unmanned aerial vehicle[C]//Oxide Materials for Electronic Engineering (OMEE)， 2012 IEEE International Conference on. IEEE， 2012: 697-701.

收稿日期：2016年1月10日,修回日期：2016年2月25日

作者簡介：王明明，男，碩士研究生，研究方向：指控系統(tǒng)，航跡規(guī)劃。夏學知，男，研究員，博士生導師，研究方向：指控系統(tǒng)技術(shù)。

中圖分類號V279

DOI：10.3969/j.issn.1672-9730.2016.07.008

UAV Path Planning Technology in Complex Environment

WANG MingmingXIA Xuezhi

(Wuhan Digital Engineering Institute, Wuhan430205)

AbstractIn order to solve the commonly-used route-planning algorithm’s problem of slow convergence and easy to fall into local optimum in a complex flight environment, a composite particle swarm optimization algorithm is presented based on simulated annealing. By modeling complex environment, equivalent digital topographic map combining topography, surface features and threat information is generated. Then route planning on the map can be done with the improved algorithm. Experimental results show that, the optimization particle swarm fusion algorithm based on simulated annealing has better feasibility and real-time, can effectively solve the problem of spatial complexity and the search efficiency in complex environment of UAV route planning, and accelerate global convergence speed, keeping PSO robust, and avoid obstacles in real time and plan an optimal or suboptimal path.

Key Wordsunmanned aerial vehicle, route-planning, particle swarm algorithm, modeling and avoidance of threat