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

李 楠， 薛建凱， 舒慧生

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

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

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

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

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

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

1 數學模型

1.1 無人機飛行環境建模

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

(1)

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

(2)

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

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

(3)

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

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

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

圖2 威脅區域示意圖Fig.2 Schematic diagram of threat area

1.2 無人機航跡規劃建模

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

(4)

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

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

(5)

式中：hheight為飛行高度代價函數。

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

(6)

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

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

Jcost=w1Lpath+w2hheight+w3Jturn

(7)

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

(8)

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

(9)

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

(10)

(11)

2 麻雀搜索算法

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

在SSA中，將待優化的函數視為食物，函數變量視為麻雀的位置。在d維解空間中發現者的位置更新描述如下：

(12)

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

(13)

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

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

(14)

3 改進麻雀搜索算法

3.1 自適應t分布變異

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

(15)

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

(16)

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

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

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

(17)

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

3.2 改進麻雀搜索算法優化流程

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

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

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

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

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

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

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

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

(8)輸出最佳路線。

4 試驗仿真

4.1 試驗環境及參數設置

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

表1 威脅區域分布Table 1 The distribution of threat area km

4.2 測試與分析

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

圖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可以很好地平衡全局搜索和局部開發能力，增加了種群的多樣性，尋優精度及收斂速度均得到了提高,由此可知，改進SSA求解的質量更高,收斂速度更快，能夠有效縮短任務執行時間。總而言之，基于自適應t分布變異的SSA在無人機三維航跡優化問題上具有更好的性能。對算法生成的路徑進行平滑處理，最終得到符合預期要求無人機飛行路線。

5 結 語

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

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