改進麻雀搜索算法的飛行器航跡規劃

雷 剛, 李云舒, 張宏強, 羅 煒, 賴燦輝

(1.火箭軍工程大學,西安 710000; 2.火箭軍裝備部某軍代室,武漢 430000)

0 引言

飛行器航跡規劃是考慮飛行器狀態約束和環境約束條件下,為完成飛行任務而設計的飛行軌跡。從20世紀70～80年代開始,許多學者對航跡規劃問題進行了探索,根據規劃層次不同,可分為離線航跡規劃和在線航跡規劃。在離線航跡規劃中,環境約束是已知或者部分已知,需要對飛行環境中固定的障礙物、禁飛區等進行規避。為了使飛行器與規劃系統實現精確的交互,往往通過規劃航跡節點[1]來實現。而一個航跡節點通常包括當前的位置坐標、俯仰角、滾動角以及偏航角[2],可將航跡規劃問題轉化成一個多目標節點優化選擇問題。當不考慮其他條件約束或者飛行環境已知時,初始點到目標點的航跡優化似乎并不復雜,但是在實際的航跡規劃過程中,往往需要考慮當前環境下的很多不確定性因素,比如移動雷達車的監測、強對流天氣的影響等。這時往往不能按照之前的航跡點進行飛行,需要優先保證飛行器的安全性,在安全的條件下完成剩余的航程。

當前對于航跡規劃的研究過程中,常用的有兩類規劃算法,一類是傳統航跡規劃算法[3],另一類是群智能優化算法[4]。在傳統航跡規劃算法中,王殿君等利用Dijkstra算法[5]和A*[6]算法基于多叉樹理論,以起點作為根節點,采用節點回溯的方式,向目標點探尋最優路徑,但是由于搜索算法會隨著搜索維度的升高而出現組合爆炸的問題,在三維的航跡規劃問題中計算速度較慢;文獻[7-8]基于A*算法,采取稀疏搜索空間的方式,結合D*算法進行逆向搜索,在飛行過程中環境發生變化時,算法能根據新的環境信息刪除原來的航跡節點,重新進行航跡規劃,具有較好的實時性;人工勢場法[9]的算法模型相對簡單,路徑規劃過程中只需要通過傳感器獲取局部環境信息,在引力場和斥力場的共同作用下向目標點移動,但是在航跡中出現多個連續禁飛區時,會導致計算的路徑收斂效果不穩定,出現局部震蕩,在實際飛行中存在一定難度。群智能優化算法由于其具有內在的并行性和隨機性,在多目標約束問題中展現出了優良的尋優能力。文獻[10]融合快速搜索隨機樹(RRT)算法和人工勢場法的優點,將目標點與禁飛區的合力方向作為過程樹的搜索方向,利用改進的RRT算法生成航跡點作為初始種群,利用遺傳算法對飛行器航跡進行了快速規劃;湯安迪等[11]針對無人機航跡求解中計算復雜、收斂性差的問題,在二維任務空間模型與航跡代價模型的基礎上,將立方映射混沌算子引入麻雀搜索算法(SSA),提高了初始種群的均勻性及多樣性,同時采用高斯游走策略算法可以有效保證算法能跳出局部最優。

1 航跡規劃環境模型建立

1.1 問題描述

飛行器在執行飛行任務時,需要考慮環境中的地形障礙、火力范圍和雷達等干擾,因此在對任務環境的建模中,需要建立各類威脅區[12]。本文建立的三維地形描述如下

Φ={Xmin

(1)

式中,*min,*max分別是*的下界和上界。在飛行器的避障過程中為了保證飛行器的穩定性以及隱蔽性,往往通過低空轉彎進行障礙規避,本文主要考慮飛行器的離線靜態規劃。

1.2 性能約束

飛行器在飛行過程中,受自身性能參數和氣動特征的限制,需要考慮油耗、機動性、最小飛行高度等因素的約束,保證飛行器進行基本的飛行任務。航跡規劃的準確性主要受飛行器自身的性能影響,主要考慮以下約束。

1.2.1 最大航程

飛行器通常攜帶的燃料一定,所以航跡的長短一定意義上決定了能否完成任務,記飛行器的任務航程為L,則L應該滿足

(2)

1.2.2 最大轉彎角度約束

角度約束包括了飛行器的偏航角約束和俯仰角約束兩個參數,飛行器在轉彎的過程中受到自身氣動外形和慣性特征的限制,所以在轉彎過程中,兩個連續航點的轉彎角不能超過最大轉彎角,記最大轉彎角為αmax,則αmax應滿足

(3)

1.2.3 飛行高度約束

最小飛行高度是飛行器與當前地面的最小相對高度,較低飛行時,受益于地形提供的掩護,以及其他雜波會對雷達的探測產生一定干擾,所以為了提高飛行器的生存性,飛行高度應盡可能的低。設定一個最小高度ΔHmin和最大高度ΔHmax,飛行高度h應滿足

ΔHmin

(4)

1.2.4 最大爬升角約束

爬升角是速度方向與當前航跡點水平面的夾角,需要考慮最大爬升角約束來確定合適的起飛速度和起飛重量等參數,以確保飛機可以順利地起飛并達到安全高度。設置最大爬升角為γmax,規劃過程中的爬升角應滿足-γmax≤γ≤γmax,且有

(5)

1.3 航跡評價指標

評價航跡算法優劣性的前提是建立良好的航跡評價指標,其中主要包括飛行器自身的性能約束、算法的優劣性以及航跡代價,在綜合考慮飛行器的全程航跡規劃下,建立如下航跡評價函數

minJcost=ω1·J1+ω2·J2+ω3·J3

(6)

式中:Jcost表示總的航跡目標;J1,J2,J3分別表示油耗代價、威脅代價、高度代價。

1.3.1 油耗代價

由于飛行器自身攜帶的燃料有限,相應任務的時間配比有限,假設飛行器在航跡規劃的過程中保持勻速運動,油耗代價函數J1可以表示為

(7)

式中,c為油耗系數。

1.3.2 威脅代價

規避威脅區域實現安全突防是航跡規劃的主要任務,威脅區主要分為地形、雷達探測、氣象等。本文中將威脅區域簡化為圓柱體區域,規定飛行器不能通過該區域。威脅代價函數表示為

(8)

式中:N-1表示式(3)中Ai的路徑段數目;Ti為第i個威脅區域對航跡的威脅代價。

1.3.3 高度代價

當飛行器的飛行高度低于規劃區域或者高于規劃區域時,不利于任務規劃過程,高度代價函數簡化為

(9)

式中,p1、p2均為比例系數。

2 多策略改進麻雀算法的飛行器航跡規劃

2.1 麻雀搜索算法

麻雀搜索算法(SSA)是根據麻雀覓食并逃離捕食者的行為而提出的群智能優化算法,該算法的尋優過程屬于發現者-跟隨者模型[13],在該算法中,容易搜索到豐富食物的個體稱為發現者,其他的個體則稱為跟隨者,種群中會有一定比例的個體進行預警,稱之為警戒者。如果警戒者發現危險時,就會發出預警,發現者就會將其他個體帶到安全區域,當個體中有新的加入者發現了更好的食物來源,那么就會成為新的發現者,而之前的發現者則變為跟隨者,在此過程中種群發現者和跟隨者所占種群數量的比例是不變的。

2.2 SSA流程

(10)

SSA中發現者的位置迭代更新規則如下

(11)

(12)

(13)

2.3 SSA的改進

SSA航跡規劃問題的尋優過程可以簡單地解釋為:每只麻雀個體代表一條可能航跡,麻雀的維度代表這條航跡上的航跡點個數,其個體的適應度代表了該航跡評價函數式(6)的適應度,發現者代表了當前航跡點處的較優個體,跟隨者代表了當前航跡點處的次優個體,警戒者則代表了當前航跡點的約束,當約束超過臨界值時放棄該航跡。按照SSA的更新迭代策略,不斷更新t時刻下的較優位置,進行航跡點的優化選擇。

經過多次驗證,發現SSA和其他智能優化算法一樣,受初始值的影響較大,而一組好的初始可行解往往可以加速種群收斂、提高解的精度,所以初始化種群的操作是非常有必要的。

2.3.1 佳點集優化初始種群

目前常用的種群初始化采用混沌映射、佳點集和反向學習等方法[14]。通過設置取值范圍為[0,1],用piecewise map映射混沌算子和佳點集隨機產生若干個點并進行統計,采用佳點集進行初始化種群處理,種群個數為5000和500的概率分布直方圖分別如圖1、圖2所示。

圖1 兩種算法5000個點的分布圖

圖2 兩種算法500個點的分布圖

在迭代次數足夠大的情況下,piecewise map映射處理和佳點集法處理的初始化種群均可以達到分散程度很高的水平。但是在小樣本條件下,佳點集法處理的結果分布更加均勻,由于本文中采用的小樣本,為了使分散更均勻,采用佳點集法進行種群初始化。

2.3.2 自適應權重的位置迭代更新

SSA的位置更新屬于一種有導向性的搜索策略,全局搜索能力依賴于發現者的位置,對于發現者來說,原步長q服從正態分布,使算法整體的局部搜索能力變強,獲得不錯的適應度及精度,但是前期的全局探索過程中,較小的步長不利于全局搜索。在鯨魚優化算法中,個體的位置更新迭代呈螺旋式上升,可以獲取較好的全局搜索能力[15]。本文借鑒鯨魚優化算法中迭代尋優的螺旋式上升搜索方式,引入自適應權重因子ζ,使得SSA中發現者在位置更新,探索下一次區域時前期以較大步長搜索,后期進行小步長收斂探索,改善后發現者的位置迭代式如下

(14)

(15)

2.3.3 柯西-高斯變異

槍聲定位系統中，節點檢測的槍聲信息中主要包括槍聲到達聲傳感器陣列的時間，準確的時間信息能夠優化系統的測試結果。在（DMTS）算法[12]的基礎上，通過兩次廣播簇頭的時鐘信息來估算簇頭和節點之間的相對頻率偏差，并修正接收節點的本地時鐘，時間同步算法流程如圖6所示。

SSA在迭代后期,種群會逐漸地向著最好的個體靠攏,減弱了種群的多樣性,方差可以很好地表示種群整體的波動情況,較大方差的變異因子可以讓算法具備更好的突變能力,能更好地跳出局部特性,同時帶來的弊端是會影響局部尋優的精度和速度。而局部尋優過程中方差較小的變異因子能更快速地收斂函數,使其達到極值,缺點是容易使算法陷入早熟。

本文模擬生物交叉、變異的特性,在算法中加入變異因子的種群進化機制[16]。高斯分布又名正態分布,表達式為

(16)

柯西分布與高斯分布類似,表達式為

(17)

兩種分布如圖3所示。

圖3 高斯分布和柯西概率密度函數

由圖3可知,柯西分布比高斯分布的分布范圍廣,容易產生距原點更遠的隨機數,有更大的概率跳出局部最優,但是柯西分布的期望和方差不存在,本文結合高斯分布和柯西分布的優點,考慮不同搜索階段的變異需求,設計柯西-高斯變異機制,方便保留較好適應度位置的麻雀個體,進入下一次迭代,即

(18)

2.4 算法實現

將本文改善后的算法用于飛行器的航跡規劃問題,算法流程如圖4所示。

圖4 修正的WSSA流程圖

3 仿真實驗與結果分析

3.1 仿真環境初始化

表1 禁飛區位置分布

z軸坐標數據由Global Mapper 20軟件處理的高程數據用仿真軟件插值產生,加入禁飛區約束后的三維模型環境如圖5所示。

圖5 加入禁飛區約束后的三維模型環境

3.2 較少威脅區域的航跡規劃仿真實驗

3.2.1 算法適應度

根據上述條件,使用SSA、WSSA以及加入柯西-高斯算子修正的3種算法分別在此三維模型環境進行離線航跡規劃,設置仿真次數為100,在每次實驗過后記錄3種算法的計算用時、適應度等。3種算法的適應度尋優過程如圖6(a)～6(c)所示,適應度的平均值對比如圖6(d)所示。

圖6 3種算法適應度尋優過程與平均適應度曲線

3.2.2 結果分析

如圖6(c)、6(d)所示修正的WSSA由于加入了柯西-高斯變異因子,導致算法前期適應度曲線的顛簸程度較大,但是搜索中后期能夠快速集中收斂。這也從側面驗證了算法前期和后期都具有良好的全局搜索能力,優化結果如表2、圖7所示。

表2 航跡規劃結果比較

圖7 3種算法的收斂箱式圖

WSSA在平均適應度值、最差值、最優值等方面都是較優于原SSA的,而修正的WSSA則適應度最優最劣值的范圍波動較小,更有利于快速收斂到較優的可行解。航跡規劃結果如圖8所示。

圖8 航跡規劃結果

3.3 較多威脅區域的航跡規劃仿真實驗

為探尋算法在其他環境條件下是否依舊具有優勢,本文基于同地圖不同禁飛區約束下和不同地理環境進行了測試。

3.3.1 不同禁飛區位置測試

保持地理三維模型不變,更新禁飛區的位置和數量,更新后的禁飛區位置如表3所示。

表3 新的禁飛區位置分布

設置仿真次數為100,依次用3種算法進行路徑尋優,優化結果如圖9和表4所示。

表4 多禁飛區下航跡規劃結果比較

圖9 多禁飛區下的俯視圖

如表4所示,受到多個禁飛區的影響,適應度值隨著仿真次數的增加而出現波動較大,總體的適應度方差大的情況,但是修正后算法的方差波動相對較小,且航跡長度和適應度都相對更小。

3.3.2 不同起點、不同禁飛區位置測試

引用表4禁飛區位置的同時,改變起始點和目標點的位置。設置任務起點(15 km,15 km),目標點(125 km,80 km),仿真次數為100,依次用3種算法進行路徑尋優,優化結果如圖10和表5所示。

表5 多禁飛區下航跡規劃結果比較(起始點不同)

圖10 多禁飛區下的俯視圖(起始點不同)

受到多個禁飛區的影響,適應度值隨著仿真次數的增加而出現波動較大,但是修正后算法的方差波動、航跡長度和適應度都相對更小。

綜上所述,3種算法都可以對禁飛區以及地形進行有效規避,隨著地形復雜程度變高、禁飛區的數量變多,修正的WSSA依然在計算時間、適應度值以及航跡的平滑程度具有優勢。

4 總結

本文基于禁飛區的規避問題,建立了三維環境模型以及航跡評價指標。采用智能優化算法探尋其最優航跡。為避免不好的初始解會影響算法的尋優效率和種群多樣性,采用佳點集法進行了種群初始化處理;為提高算法搜索能力的同時保證算法的收斂性,借助鯨魚算法中螺旋式搜索因子形成自適應權重迭代因子,有助于算法的過程尋優;為防止算法早熟,陷入局部最優解,在跟隨者位置更新中加入柯西-高斯變異因子提高算法的全局尋優能力。實驗表明,修正的WSSA在考慮禁飛區約束的航跡規劃問題研究中展現出了較好的適用性和魯棒性。