付興武， 胡 洋

(遼寧工程技術(shù)大學(xué)電氣與控制學(xué)院，遼寧 葫蘆島 125105)

0 引言

隨著無人機(UAV)技術(shù)的發(fā)展，其在農(nóng)業(yè)、石油、軍事、氣象、地理測繪等多個領(lǐng)域均有廣泛應(yīng)用。無人機航跡規(guī)劃是在綜合考慮環(huán)境、戰(zhàn)場威脅、飛行時間、油耗等約束條件下，尋找一條從起始點到目標(biāo)點的最優(yōu)或可行的飛行軌跡，是典型的多目標(biāo)優(yōu)化問題[1]。無人機安全實施各項任務(wù)時，好的路徑規(guī)劃是其基本保障。針對這些問題，國內(nèi)外學(xué)者提出了許多優(yōu)化路徑規(guī)劃的算法。主要有A*算法[2]、遺傳算法[3]、蟻群算法[4-5]、人工勢場法[6]以及粒子群算法[7]等，而這些算法都有各自的缺點，不能保障搜索的精度和路徑規(guī)劃的約束條件。1995 年由KENNEDY和EBERHART提出的粒子群(PSO)算法因具有收斂迅速，無需事先知曉尋優(yōu)對象的函數(shù)或系統(tǒng)特性，算法思路清晰、運算簡單、易于實現(xiàn)、高效的特點而被廣泛應(yīng)用于各種尋優(yōu)問題[8]。但是該算法也存在著早熟現(xiàn)象、收斂速度慢，過早陷入局部最優(yōu)等缺陷。針對這些缺陷，本文對該算法進行改進，將粒子群算法和天牛須算法結(jié)合，并將改進的算法應(yīng)用于無人機三維路徑規(guī)劃，最后通過仿真試驗驗證算法的可行性。

1 粒子群算法

1.1 標(biāo)準(zhǔn)粒子群算法

粒子群算法源于對鳥類捕食的研究，通過鳥類隨機捕食的現(xiàn)象，來解決優(yōu)化問題。其中每個粒子都可以看作是一只鳥，鳥類在捕食過程中會有個體與群體信息的反饋，每只鳥都代表優(yōu)化問題的可能解。當(dāng)一只鳥找到食物時，群體中其他鳥就會向其靠攏，粒子群算法就是利用鳥類這種信息共享的特性形成由分散到集中的過程。所有的粒子都有一個由被優(yōu)化的函數(shù)所決定的適應(yīng)值(fitness)，每個粒子還有一個速度決定其飛翔方向和距離，算法初始化—群隨機粒子(隨機解)，然后通過迭代更新尋找最優(yōu)解[9]。在粒子群算法中，每個粒子都有一個記憶，去追蹤上一代粒子的迭代時的最佳位置：一個是粒子本身所找到的最佳位置，稱為粒子個體最佳位置；另一個是整個群體目前找到的最佳位置，稱為粒子全局最佳位置。假設(shè)有N個粒子在D維的搜索空間，即粒子群的種群規(guī)模為N,其中，第i個粒子在D維位置的參數(shù)可以表示為xi(k)={xi1(k),xi2(k),…,xiD(k)}，根據(jù)優(yōu)化問題的代價函數(shù)來判斷這個粒子當(dāng)前位置相比于歷史位置，其他位置是否更優(yōu)。

第i個粒子到現(xiàn)在為止搜索到的個體最優(yōu)值位置參數(shù)pbest為

pbest={pi1,pi2,…,piD}。

(1)

所有粒子到現(xiàn)在為止搜索到的種群最優(yōu)值位置參數(shù)gbest為

gbest={pg1,pg2,…,pgD}。

(2)

速度為

vi(k)={vi1(k),vi2(k),…,viD(k)}。

(3)

第i個粒子第k次迭代進行速度和位置的更新，即

(4)

式中：k為迭代次數(shù);ω為慣性權(quán)重;c1和c2為加速因子，主要是控制粒子個體信息反饋和群體信息交流，使粒子根據(jù)個體和群體尋優(yōu)得到的信息做出判斷，對自身的位置進行調(diào)整，向潛在的最優(yōu)位置靠近;r1和r2為0～1的隨機數(shù)[10]，增加了粒子的容錯性和尋優(yōu)能力。

1.2 天牛須(BAS)算法

BAS算法是基于天牛的覓食原理[11]于2017年提出的，主要依據(jù)天牛的觸角來檢測食物的氣味進而決定其自身的方向。如果觸角一側(cè)檢測到較高濃度的氣味，天牛會向相同方向旋轉(zhuǎn)，否則會轉(zhuǎn)向另一側(cè)。BAS算法的建模流程如下。

1) 隨機生成天牛須的朝向和天牛的位置，并進行標(biāo)準(zhǔn)化處理，即

(5)

2) 左右須之間的關(guān)系與質(zhì)心的空間坐標(biāo)為

(6)

式中：xl-xr=d0·ddir；xl代表搜索區(qū)域的左側(cè),xr代表右側(cè)；ddir表示歸一化處理的隨機向量。

3) 確定天牛的移動方向。根據(jù)選取的適應(yīng)度函數(shù)，確定左右須的適應(yīng)度值的大小，分別用f(xl)和f(xr)表示，比較左右須適應(yīng)度值的大小，確定天牛下一步的移動方向。

4) 迭代更新天牛的位置，即

xt+1=xt+δtbsgn(f(xr)-f(xl))

(7)

式中：f(·)函數(shù)為適應(yīng)度函數(shù)；sgn(·)為符號函數(shù)；δt為第t次迭代的步長。

1.3 基于天牛須的粒子群優(yōu)化算法

改進的粒子群算法集PSO算法和BAS算法于一體。BAS算法在處理高維度問題時，主要依賴天牛個體，迭代的效果和天牛個體的初始位置有很大關(guān)系。受粒子群優(yōu)化算法影響，將個體推廣到群體就形成了改進粒子群算法。在改進粒子群算法中，每個粒子都可以看成是天牛并進行搜索，與粒子群算法類似，每只天牛個體都是優(yōu)化問題的潛在解。改進粒子群算法初始位置和速度的表示與標(biāo)準(zhǔn)粒子群算法類似，不同的是，天牛在進行搜索時，會增加自己對環(huán)境的判斷，這樣就可以解決其局部最優(yōu)的缺陷。

在數(shù)學(xué)形式上，借鑒粒子群的思想。改進粒子群算法的速度和位置更新的算式可以表示為

(8)

式中：Xi={xi1,xi2,…,xid}表示第i只天牛在d維搜索空間的位置，即優(yōu)化問題的潛在解；Vi={vi1,vi2,…,vid}表示第i只天牛的速度；Pi={pi1,pi2,…,pid}T表示天牛個體極值；Pg={pg1,pg2,…,pgd}表示群體極值；s=1,2,3，…，S；i=1,2,3，…，n；k是迭代次數(shù);d表示觸角感知長度。

改進算法步驟：

1) 對所提算法的參數(shù)進行初始化；

2) 評價每只天牛個體的適應(yīng)度；

3) 根據(jù)2)計算每只天牛個體更新后的速度，位置；

4) 更新天牛須的相關(guān)參數(shù)；

5) 判斷是否達到終止條件，直至達到輸出全局最優(yōu)解位置和適應(yīng)度函數(shù)。

2 數(shù)學(xué)模型的建立

2.1 任務(wù)環(huán)境的建模

2.1.1 地形威脅區(qū)域

在無人機任務(wù)地形中，不僅要考慮突起的山體，還要考慮地形的起伏。在本文中，主要采取函數(shù)模擬方法進行地形建模，具體數(shù)學(xué)模型為

(9)

式中：x，y是地形投影在水平面上的點坐標(biāo)，z為水平面點坐標(biāo)對應(yīng)的高程；a，b′，c，d′，e，f，g為常系數(shù)，對數(shù)字地圖中的地表特征進行控制。

2.1.2 障礙區(qū)域建模

障礙區(qū)域主要是建立山峰模型，這樣無人機在躲避障礙區(qū)域中能夠更直觀地在三維模型中觀測，山峰模型[11]采用的數(shù)學(xué)算式為

(10)

式中：i代表第i座山；hi代表山的高度；z為其高程；(xi，yi) 為第i座山的地理中心坐標(biāo)；xsi，ysi控制山峰坡度。

2.2 無人機性能約束

在無人機進行路徑規(guī)劃時，不僅要考慮路徑長度，還要考慮無人機自身性能帶來的約束條件。主要有以下幾個方面。

2.2.1 最大航程約束

無人機在航行過程中攜帶的燃油是有限的，其總航程受到燃油的限制。設(shè)一條航程上有n個節(jié)點，最大航程為Lmax，在路徑節(jié)點的第i段航程可以表示為Li，如圖1所示。

圖1 航程節(jié)點示意圖

整條路線上的總航程可以表示為

(11)

2.2.2 最低高度約束

無人機在山區(qū)執(zhí)行任務(wù)時，要盡可能地使飛行高度降低，但太低的飛行高度會使無人機與復(fù)雜的地形相撞，所以，要選擇一個合適的高度范圍，其代價函數(shù)可以表示為

(12)

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

2.2.3 最大俯仰角約束

在無人機航跡規(guī)劃中，無人機爬升或俯沖角度是其自身性能的一個重要約束。最大俯仰角是從當(dāng)前航跡點飛行到下一個航跡點在垂直方向的角度限制。小于或等于最大俯仰角才能滿足無人機爬升性能的約束。從航節(jié)點(xi-1，yi-1，zi-1)到(xi，yi，zi)的攻角算式為

(13)

(14)

式中：θ為無人機爬升的角度；θmax為無人機最大爬升角度;k為合適的約束值。

由以上對各個適應(yīng)度函數(shù)的分析，可以得到無人機飛行航跡的代價函數(shù)為

(15)

2.3 威脅區(qū)域建模

假設(shè)無人機從坐標(biāo)原點出發(fā)，在到達目的地之前，會受到導(dǎo)彈、高射炮和雷達的威脅。本文用大小不一的圓柱形代表威脅區(qū)域，如圖2所示。

圖2 威脅區(qū)域模型

無人機航跡規(guī)劃就是使無人機在航行過程中，在繞過途中若干個威脅區(qū)域的前提下以最短的路程到達目的地。威脅區(qū)域數(shù)學(xué)表達式為

(16)

3 仿真驗證與結(jié)果分析

為驗證本文所提方法的有效性，在Matlab R2016a環(huán)境下對無人機路徑規(guī)劃進行仿真驗證。飛行起點坐標(biāo)是(10，90，1.115)，目標(biāo)點坐標(biāo)是(130，10，1.367)，任務(wù)區(qū)有4個圓柱形威脅區(qū)，威脅區(qū)的4個坐標(biāo)分別為(10，60)，(40，50)，(60，50)，(100，30)，以上坐標(biāo)單位均為km。飛行航跡代價函數(shù)的加權(quán)系數(shù)ω1,ω2,ω3分別為0.5，0.3，0.2，學(xué)習(xí)因子c1=1.5，c2=2，種群數(shù)為20，慣性權(quán)重ω=1，終止迭代次數(shù)為400。圖3表示算法改進前后的三維航跡圖，圖4表示算法改進前后無人機航跡規(guī)劃圖。

圖3 算法改進前后的三維航跡圖

圖4 算法改進前后無人機航跡規(guī)劃圖

圖5所示為適應(yīng)值收斂情況。從圖5的粒子群和改進粒子群的適應(yīng)值收斂圖中可以看出，粒子群算法的收斂值為73.82，而改進算法的收斂值為72.97，具有更好的收斂性，避免了陷入局部最優(yōu)。

圖5 適應(yīng)值收斂圖

從仿真結(jié)果對比可以很直觀地看出，相比較粒子群算法，采用改進粒子群算法時，無人機能夠在滿足最短路徑的同時，更好地避開任務(wù)區(qū)域中的威脅，進而驗證了改進算法的有效性。

4 結(jié)束語

本文采用改進粒子群算法對無人機路徑規(guī)劃進行研究，首先對無人機任務(wù)地形的原始環(huán)境進行建模，并且以自身性能約束為代價函數(shù)；在粒子群算法的基礎(chǔ)上結(jié)合了天牛須搜索算法，為無人機規(guī)劃了一條安全、更優(yōu)的規(guī)劃路徑；最后，通過仿真進行試驗驗證，結(jié)果表明，改進粒子群算法在無人機路徑規(guī)劃方面更加合理、效率更高，比粒子群算法有著更好的收斂性，避免了陷入局部最優(yōu)，有效縮短了路徑長度。