基于自適應t分布變異麻雀搜索算法的無人機航跡規(guī)劃

李 楠， 薛建凱， 舒慧生

(東華大學 a. 信息科學與技術(shù)學院, b. 數(shù)字化紡織服裝技術(shù)教育部工程研究中心,c. 理學院， 上海 201620)

無人機(unmanned aerial vehicles, UAVs) 由于具有可以使人類完全遠離生命危險的巨大優(yōu)勢，被用于執(zhí)行各種高風險的任務[1]。隨著各類無人機的廣泛使用,無人機的航跡規(guī)劃問題得到了充分研究。航跡規(guī)劃允許無人機根據(jù)任務要求和約束，自主計算起點至目標點的最佳路徑。但在優(yōu)化過程中，隨著問題復雜度的增加，很難找到一種有效的規(guī)劃方法?？梢妼o人機的三維航跡進行優(yōu)化具有實際意義和挑戰(zhàn)性。

在對無人機的路徑進行優(yōu)化的過程中，最大的技術(shù)難點是如何避開障礙物和威脅區(qū)域。因為大多數(shù)的無人機飛行事故主要是由撞上障礙物或被敵方擊落而造成的。例如，在救援或地質(zhì)勘探中，無人機在飛行過程中所遇到的樹木、巖石甚至鳥類都極有可能干擾無人機的飛行甚至造成無人機墜毀。當無人機用于交通運輸時，如何避開高樓大廈也是至關重要的。甚至在當今信息化戰(zhàn)爭中，無人機如何快速躲避敵人的雷達、導彈的威脅也具有重要研究意義。因此在環(huán)境建模中有必要考慮障礙物和威脅區(qū)域。

群智能優(yōu)化算法已成為求解無人機航跡優(yōu)化問題的常用方法。Sujit 等[2]提出一種基于粒子群優(yōu)化(particle swarm optimization, PSO)的實時規(guī)劃算法，并應用于多無人機航跡規(guī)劃問題；Zhang等[3]提出一種基于蟻群優(yōu)化(ant colony optimization, ACO)算法的無人機路徑優(yōu)化方法，并成功規(guī)劃出有效的航跡路線。Chen等[4]針對無人機的三維路徑規(guī)劃問題，提出一種改進的狼群搜索(wolf pack search, WPS)算法，改進算法的性能優(yōu)于原始算法和遺傳算法(genetic algorithm, GA)。群智能優(yōu)化算法具有易實現(xiàn)及擴展性好、參數(shù)少等特點，極大地滿足了無人機在進行航跡優(yōu)化時對算法的穩(wěn)定性、實時性需求。

隨著科學技術(shù)的發(fā)展，更多優(yōu)化算法被提出。麻雀搜索算法(sparrow search algorithm, SSA)[5]具有參數(shù)少、收斂速度快、易實現(xiàn)等優(yōu)點, 成功應用于多個領域。例如：Liu等[6]提出一種改進的SSA用以解決再生能源系統(tǒng)優(yōu)化的問題；Zhu等[7]提出一種自適應SSA對質(zhì)子交換膜燃料電池的模型進行參數(shù)優(yōu)化識別，仿真結(jié)果表明所提算法具有較好的優(yōu)化效果；Liu等[8]提出一種增強型 SSA 優(yōu)化卷積神經(jīng)網(wǎng)絡，實現(xiàn)高效、穩(wěn)定的腦腫瘤優(yōu)化診斷；Yuan等[9]提出一種改進SSA來優(yōu)化光伏微電網(wǎng)系統(tǒng)，得到了理想的效果；歐陽城添等[10]提出多策略改進SSA，成功應用于主動懸架控制優(yōu)化問題。

綜上所述，對SSA的研究大致分為3類：算法本身的改進；與其他算法的融合；算法的實際應用。本文重點關注第1類和第3類的研究，提出一種基于自適應t分布變異的SSA用以優(yōu)化無人機的三維路徑。

1 數(shù)學模型

1.1 無人機飛行環(huán)境建模

環(huán)境模型的建立是檢驗無人機是否可以完成預期規(guī)劃效果的基礎和前提，其中障礙物的出現(xiàn)會對算法的性能提出更高的要求。采用函數(shù)模擬法[11]對地貌特征進行模擬，其數(shù)學表達式如式 (1)所示。

(1)

式中：(x,y) 為點坐標；z為對應的高度。通過改變a,b,c,d,e,f,g這些常系數(shù)的數(shù)值可以得到不同的地貌特征，能滿足不同環(huán)境的建模需求。在此基礎上還需疊加山峰模型構(gòu)建障礙物，山峰模型[12]表達式如式(2)所示。

(2)

式中：ho為基準地形，hi為第i座山峰的高度；(xoi,yoi) 為第i座山峰的中心坐標位置；ai和bi分別為第i座山峰沿x軸和y軸方向的坡度。聯(lián)立式(1)和(2)得到式(3)。

Z(x,y)=max[z(x,y),h(x,y)]

(3)

最終得到如圖1所示的地形效果圖。

圖1 地形仿真圖Fig.1 The terrain simulation map

為了讓無人機的飛行環(huán)境更加真實，在存在障礙物的前提下增加對無人機構(gòu)成威脅的區(qū)域。威脅區(qū)域用半徑為r的圓柱形表示，圖2中的柱形體即是威脅區(qū)域。

圖2 威脅區(qū)域示意圖Fig.2 Schematic diagram of threat area

1.2 無人機航跡規(guī)劃建模

在無人機路徑規(guī)劃過程中，航路越短，飛行所需的時間和消耗的燃料越少。路徑長度的計算公式如式(4)所示。

(4)

式中：g(i)和g(i+1)分別為第i個航路點和第i+1個航路點的坐標，記作(xi,yi,zi)，(xi+1,yi+1,zi+1)；li為第i個航路點和第i+1個航路點之間的距離；n為航路點個數(shù)；Lpath為路徑長度函數(shù)。

合適的飛行高度對無人機航路規(guī)劃具有重要影響。對于大多數(shù)類型的無人機而言，飛行高度的變化不能太頻繁和劇烈。穩(wěn)定的飛行高度可以節(jié)省很多燃料，安全指數(shù)更高。此外，當無人機在較低高度飛行時，其可利用周圍地形進行自身掩蓋，以此降低遇到未知危險的概率。飛行高度代價函數(shù)[4]定義如式(5)所示。

(5)

式中：hheight為飛行高度代價函數(shù)。

無人機的穩(wěn)定性和可控性受轉(zhuǎn)角代價的約束，并且在無人機路徑規(guī)劃過程中，轉(zhuǎn)彎角度不應大于預先設定的最大轉(zhuǎn)角[13]。轉(zhuǎn)角代價函數(shù)的定義如式(6)所示。

(6)

式中：ai和ai+1為第i,i+1段航路段向量；|ai|和|ai+1|為ai和ai+1的長度；Ф為最大轉(zhuǎn)角；δ為當前轉(zhuǎn)角；Jturn為轉(zhuǎn)角代價函數(shù)。

將無人機航路規(guī)劃問題定義為一系列優(yōu)化準則和約束條件。通過建立路徑長度函數(shù)、飛行高度代價函數(shù)及轉(zhuǎn)角代價函數(shù)，得到多目標代價評估函數(shù)，其表達式如下：

Jcost=w1Lpath+w2hheight+w3Jturn

(7)

式中：Jcost為總的代價函數(shù)；參數(shù)wi(i=1,2,3)需滿足如下條件：

(8)

通過對總的代價評估函數(shù)進行優(yōu)化，規(guī)劃出一條路徑。但是得到的路徑很容易形成折線形導致無人機無法按規(guī)劃路線飛行，需對這部分路線作平滑處理,因此采用B樣條曲線對航路點進行平滑處理。B樣條曲線表達式如下：

(9)

式中：m為節(jié)點ei的個數(shù)；ei的取值范圍為{e0,e1,…,em-1}；Pi為控制節(jié)點；Ci,n(e)為n階B樣條基數(shù)，形式如下：

(10)

(11)

2 麻雀搜索算法

SSA主要是受麻雀群體覓食過程的啟發(fā)而提出的，根據(jù)麻雀的覓食特點，其種群中的個體身份被分為發(fā)現(xiàn)者和加入者。麻雀種群中個體的身份(發(fā)現(xiàn)者或加入者)取決于自身的適應度值。對適應度值進行排序，其中適應度值較優(yōu)的個體被認為是發(fā)現(xiàn)者。加入者在發(fā)現(xiàn)者周圍獲取食物，也可通過爭奪獲得食物。與此同時群體中的一些麻雀感知到危險后，也會進行相應位置的更新。研究[14]表明，麻雀能夠在發(fā)現(xiàn)者和加入者兩種身份中任意轉(zhuǎn)換。

在SSA中，將待優(yōu)化的函數(shù)視為食物，函數(shù)變量視為麻雀的位置。在d維解空間中發(fā)現(xiàn)者的位置更新描述如下：

(12)

加入者的位置更新公式如下：

(13)

式中：Xp為所有發(fā)現(xiàn)者中最優(yōu)麻雀個體的位置；Xworst為整個種群中麻雀個體最劣的位置；N為麻雀個體總數(shù)；A為1×d的矩陣，元素為1或-1，并且A+=AT(AAT)-1。

在SSA 中，麻雀種群在意識到危險時會表現(xiàn)出反捕食行為，其數(shù)學模型描述如下:

(14)

3 改進麻雀搜索算法

3.1 自適應t分布變異

t分布又稱學生分布，其含有自由度參數(shù)m的概率密度函數(shù)為

(15)

t(m→∞)→N(0,1),t(m→1)=C(0,1)

(16)

式中：N(0,1)為高斯分布；C(0,1)為柯西分布。從式(16)中可以看出，高斯分布和柯西分布是t分布的兩個邊界特例分布[15]，三者的函數(shù)分布如圖3所示。

圖3 高斯分布、t 分布和柯西分布密度函數(shù)Fig.3 Density functions of Gaussian distribution,t distribution, and Cauchy distribution

為進一步提高SSA的尋優(yōu)性能以及防止在迭代后期算法陷入局部最優(yōu)，對麻雀個體的位置采取如式(17)所示的自適應t分布變異策略。

(17)

式中：Xi*為變異后的麻雀位置；Xi為第i個麻雀個體的位置；t(M)是以SSA迭代次數(shù)為自由度的t分布。自適應t分布變異策略充分利用當前的種群信息。在迭代初期，迭代次數(shù)較小，t分布變異類似柯西分布變異，使得算法具有較強的全局探索能力；在迭代后期，迭代次數(shù)較大，t分布變異類似高斯分布變異，使得算法具有較好的局部開發(fā)能力。

3.2 改進麻雀搜索算法優(yōu)化流程

基于改進SSA的無人機三維航跡優(yōu)化流程如下：

(1)參數(shù)及種群初始化，如最大迭代次數(shù)、變異概率P、最大轉(zhuǎn)角、無人機飛行區(qū)域大小的設置等。

(2)設置威脅區(qū)域中心的平面坐標、半徑和無人機的起始點、目標點等。

(3)運用改進SSA對式(7)進行優(yōu)化與更新，并對候選路徑進行保存。

(4)更新發(fā)現(xiàn)者、加入者以及意識到危險的麻雀的位置。

(5)如果隨機數(shù)rand小于給定的P值，根據(jù)式(17)對麻雀個體位置進行變異。

(6)更新路徑。如果當前航路點優(yōu)于之前，覆蓋之前的航路點。

(7)判斷終止條件。如果已滿足預期要求則停止運行，否則，返回(3)繼續(xù)執(zhí)行。

(8)輸出最佳路線。

4 試驗仿真

4.1 試驗環(huán)境及參數(shù)設置

為驗證所提算法的有效性和可行性，同原始SSA和PSO算法進行比較。在MATLAB 2014a的試驗環(huán)境下運行，電腦配置：3.40 GHz的英特爾i7處理器和4 GB內(nèi)存。PSO、SSA以及改進SSA的種群大小均設置為50，最大迭代次數(shù)為200。SSA和改進SSA參數(shù)設置：安全閾值T=0.8，發(fā)現(xiàn)者的數(shù)量為10，變異概率P=0.5。PSO算法的參數(shù)設置為c1=c2=1.494 45，w=0.729。無人機的起點和終點坐標分別為(5, 100, 1.14)和(150, 50, 1.54)。最大轉(zhuǎn)角Φ設置為90o，w1～w3分別設置為0.5、0.2、0.3。表1給出了威脅區(qū)域中心的平面坐標和半徑。

表1 威脅區(qū)域分布Table 1 The distribution of threat area km

4.2 測試與分析

圖4～6分別給出了基于PSO算法、SSA和改進SSA的無人機三維航跡路線規(guī)劃出的一條合理化路線。但是從圖5可以看出，原始SSA在優(yōu)化過程中陷入了局部最優(yōu)而無法跳出，導致尋優(yōu)精度降低。PSO算法在此類問題上也出現(xiàn)“早熟”現(xiàn)象，因而無法獲取最優(yōu)值。由此可見，PSO算法和原始SSA在搜索到整個種群的較優(yōu)區(qū)域時，個體會逐步向當前最優(yōu)解靠攏而發(fā)生聚集現(xiàn)象，最終導致整個群體陷入局部最優(yōu)而無法找到全局最優(yōu)解。

圖4 基于PSO算法的最佳路線Fig.4 The best route based on PSO algorithm

圖5 基于SSA的最佳路線Fig.5 The best route based on SSA

圖6 基于改進SSA的最佳路線Fig.6 The best route based on improved SSA

基于自適應t分布變異的SSA可以很好地平衡全局搜索和局部開發(fā)能力，增加了種群的多樣性，尋優(yōu)精度及收斂速度均得到了提高,由此可知，改進SSA求解的質(zhì)量更高,收斂速度更快，能夠有效縮短任務執(zhí)行時間?？偠灾谧赃m應t分布變異的SSA在無人機三維航跡優(yōu)化問題上具有更好的性能。對算法生成的路徑進行平滑處理，最終得到符合預期要求無人機飛行路線。

5 結(jié) 語

研究了無人機航跡規(guī)劃問題，包括環(huán)境模型和航跡規(guī)劃模型的構(gòu)建,其目標是最小化多目標代價函數(shù)，包括航跡長度函數(shù)、飛行高度代價函數(shù)、轉(zhuǎn)角代價函數(shù)。提出基于自適應t分布變異的SSA的優(yōu)化方法，并同SSA和PSO算法進行了比較。仿真試驗表明，與PSO算法和SSA相比,改進SSA在收斂速度、尋優(yōu)精度方面均得到了提高。

后續(xù)研究中可在無人機建模中引入更多的約束和模型設計，如飛行速度約束、不同類型的環(huán)境約束和動態(tài)威脅等，也可將改進SSA進一步拓展到無人機的任務分配、編隊控制等其他優(yōu)化問題上。