基于改進狼群算法的無人直升機航跡規劃

王黎文, 邵書義, 吳慶憲, 韓增亮

(南京航空航天大學自動化學院, 江蘇 南京 211106)

0 引 言

由于無人直升機(unmanned autonomous helicopter,UAH)具有垂直起降、空中懸停、可朝任意方向飛行、起飛著陸場地小、體積小且操作靈活等諸多優勢,在偵查、打擊、追蹤、目標截獲、大氣監測、電力監控等軍用、民用領域得到了廣泛應用[1]。UAH航跡規劃,是指在復雜地理環境的地形起伏和障礙物威脅嚴重影響UAH執行偵查任務的效率以及飛行安全問題的情況下,綜合考慮飛行器飛行距離、高度、油耗及區域威脅等因素,結合自身性能約束,為UAH規劃一條從初始位置到任務目標點位置的最滿意的航路[2]。

UAH三維離線航跡規劃問題,本質上是一個多約束多峰高維的最優化問題求解,因此在求解UAH航跡規劃的過程中,群智能算法得到了廣泛應用[3]。針對航跡規劃問題,大量文獻對多種群智能算法進行了深入研究,有傳統的遺傳(genetic algorithm,GA)算法[4-5]、粒子群優化(particle swarm optimization,PSO)算法[6-7]、蟻群算法[8-9]等,還有近些年提出的人工蜂群算法[10-11]、灰狼算法[12]、蝙蝠算法[13]等,這些算法各有優勢和不足。利用傳統群智能算法搜索UAH最優路徑,最突出的缺點是復雜地理環境下的航跡規劃問題,算法本身易陷入局部最優解,收斂過早,導致算法全局尋優能力不足,使得最后規劃出的航跡達不到最優解的情況[14-16]。很多文獻也針對上述問題提出了相應的改進方法,文獻[17]引入模擬退火算法結合傳統遺傳算法,同時采用非線性自適應調節交叉算子和遺傳算子的概率,避免傳統遺傳算法搜索過程易陷入局部最優解的問題,提高了傳統遺傳算法的全局尋優能力;文獻[18]通過在傳統粒子群算法的初始階段、算法處理過程中以及迭代選取的最大值附近分別引入混沌序列、正弦函數和混沌算法,避免了算法陷入局部最優解的情況,提高了算法的整體尋優能力;文獻[19]在新的啟發函數中引入方向性因子,同時設計具有自適應調整的信息素揮發因子和改進的信息素更新規則,提高了傳統蟻群算法的精度,不僅可以提高算法全局尋優能力,而且加快了算法后期的運行效率。上述改進能夠在一定程度上提高算法的全局搜索能力和規劃效率,但也受限于傳統算法本身的特性。

狼群算法(wolf pack algorithm, WPA)[20-21]源于對狼群生態和狼群群體行為的研究,受狼群捕獵行為及獵物分配方式啟發,模擬出游走、召喚和圍攻3種智能行為,及“勝者為王”的頭狼產生規則和“強者生存”的狼群更新機制,以完成在復雜空間中的尋優,具有較好的全局規劃能力,在航跡規劃方向有著廣闊的前景。本文在利用WPA求解UAH航跡規劃問題的基礎上,主要完成的工作包括以下幾點:①首先針對傳統WPA中3種智能行為中移動步長固定及游走方向數人為確定不變導致的算法收斂速度慢、收斂精度不高的缺點,提出自適應步長的動態調整方法,使得每只狼的移動步長可以依靠當前狼與頭狼位置之間的距離動態調整移動步長;②其次,針對游走行為,提出了基于萊維飛行與變方向自適應游走相結合的搜索策略,改善算法易陷入局部最優的問題,保證了狼群搜索的覆蓋性,提高了算法收斂速度和全局尋優能力;③最后,將改進WPA用于求解UAH三維航跡規劃問題,在三維模擬環境下驗證了改進WPA在UAH航跡規劃方面的有效性和優越性。

1 UAH三維航跡規劃模型

1.1 環境建模

UAH航跡規劃需要從環境模型中獲取相關信息,良好的地形環境建模能夠有效提高航跡規劃的效率。本文航路規劃任務環境建模包括基準地形建模、障礙區域建模及雷達威脅區域建模。

任務空間建模設置飛行區域為100 km×100 km×10 km的直角坐標區域,基準地形采用山峰函數模型[22]模擬建模,山峰函數模型的數學描述為

(1)

式中:(xk,yk)是第k個山峰的中心坐標;hk表示第k個山峰的高度;xok和yok分別表示山峰沿x軸和y軸的衰減量,主要控制山峰的坡度。

障礙區域一般是指任務環境中禁飛區、惡劣天氣區域等UAH無法穿越的區域,障礙區域建模可以通過圓柱體模型[23]模擬,圓柱體模型的數學描述為

(2)

式中:Li(x,y,z)表示第i個障礙區域;(xi,yi)表示第i個障礙區域的中心坐標;RLi、hi分別表示第i個障礙區域的半徑和高度。

威脅區域一般是指電磁干擾區域、敵方火力打擊區域和敵方雷達探測區域等,威脅區域建模可以通過半球體模型[23]模擬建模,本文選用敵方雷達探測區域作為威脅區域,半球體的數學描述為

(3)

式中:Wi(x,y,z)表示第i個雷達威脅區域;(xi,yi,zi)表示第i個雷達區域的中心坐標;RWi表示第i個雷達探測范圍半徑。

綜上所述,建模效果圖如圖1所示。其中DEM (digi-tal elevation model)表示數字高程模型,DEM.z表示DEM中對應(x,y)處的地面地形高度。

圖1 空間環境建模Fig.1 Space environment model

1.2 航路約束條件建模

提出航路約束條件的目的是為UAH規劃出可飛路徑,基于UAH自身性能限制以及地形環境約束,UAH的航路規劃需要滿足一系列的約束條件,本文主要考慮以下約束條件:最小離地高度約束、最大轉彎角約束、最大爬升角度約束、最短航跡段約束和邊界約束。

(1)最小離地高度約束。UAH在執行任務時,為了避免與基準地形發生碰撞,UAH的飛行高度應該始終高于地形高度,同時應該與基準地形預留足夠的安全距離,即

Hmin≥DEM.zi(xi,yi)+hmin

(4)

式中:Hmin表示UAH離地最小高度;DEM.zi(xi,yi)表示位置(xi,yi)處的基礎地形高度;hmin表示UAH與基礎地形預留的安全距離。

(2)最大轉彎角約束。考慮此約束條件是為了避免UAH在飛行速度較快時,為避開障礙或威脅區域而需要大角度轉彎時造成UAH不穩定甚至與障礙發生碰撞,故需要對UAH在水平范圍內的最大轉彎角度做出限制,即

(5)

(3)最大爬升角度約束。由于UAH具有可垂直起降的特性,對于UAH的航路規劃,在起飛與著陸階段不必考慮爬升或下降的角度約束,而在飛行過程中考慮這一約束,旨在使選取的相鄰航跡點相對高度適中,從而使規劃出來的航跡相對平滑,提高航跡的適航性。即

(6)

式中:|zi-zi-1|表示第i段航跡的高度差;ai表示第i段航跡的水平投影長度,i=1,2,…,n;θmax表示UAH規定的最大爬升角度。

(4)最短航跡段約束。最短航跡段定義為UAH在飛行過程中保持當前飛行姿態飛行的最短距離,為了避免因頻繁改變飛行姿態而造成UAH不穩定甚至失控,UAH的航路需滿足最短航跡段約束,即

li≥lmin

(7)

式中:li表示第i段航跡的長度;lmin表示最短航跡段距離。

(5)邊界約束。為了提高UAH航路規劃效率,同時降低航路代價,規定UAH需要在指定區域內工作,即

(8)

式中:i=1,2,…,n;(xi,yi,zi)表示第i個航跡點在三維空間中的坐標位置;(xmax,ymax,zmax)表示指定區域的邊界位置;hmin(DEM.z)表示基準地形的最低高度。

1.3 適應度函數建模

在UAH航路規劃過程中,可以通過適應度函數計算航路代價,用于比較選取的航跡點的優劣。對于可選擇的航跡點,本文綜合考慮了UAH航程、障礙區域以及雷達威脅這3項因素,適應度函數可表示為

F=ω1fL+ω2fT+ω3fC

(9)

式中:F表示UAH航跡總代價;fL表示UAH航程成本;fT表示障礙區域碰撞成本;fC表示雷達區域威脅成本;ω1、ω2和ω3為常數,表示不同成本權重值,各項權重的取值與UAH執行的具體飛行任務有關。

1.3.1 航程成本

航程成本決定于UAH從起點到終點的飛行距離,航程成本是評價航跡質量的最重要的指標之一。考慮到UAH自身攜帶的燃料有限以及偵查任務需求,UAH需要盡快到達目標點,航跡越短,UAH的耗時及耗能越少。假設總航跡由N個航跡點組成,那么航程成本可以表示為

(10)

式中:(xi,yi,zi)和(xi+1,yi+1,zi+1)分別表示第i個航跡點與相鄰下一節點的三維坐標。

1.3.2 障礙區域碰撞成本

障礙區域碰撞成本。主要考慮UAH在執行任務過程中的山峰威脅、禁飛區及惡劣天氣區域等UAH無法直接穿越的區域。為使規劃出的航跡滿足需求,規劃的航跡節點需要與障礙區域保持一定距離,障礙區域碰撞成本可以表示為

(11)

(12)

(13)

式中:N和T分別表示航跡節點數和障礙區域數;TDi表示第i個航跡節點的碰撞成本;Di,j和RLj分別表示第i個航跡節點到第j個障礙中心的距離和障礙區域半徑;lmin表示航跡節點距離障礙區域的最小安全距離;(xi,yi,zi)和DEM.zi分別表示第i個航跡節點的三維坐標和對應第i個航跡點的基礎地形山峰高度;(xj,z,yj,z,zi)表示位于障礙區域中軸線上的與第i個航跡點同等高度的障礙中心坐標;MT表示足夠大的常數。

1.3.3 雷達區域威脅成本

雷達區域威脅成本。UAH在執行任務時,若進入雷達探測范圍,易被敵方發現,甚至遭受敵方火力打擊,故UAH需要與雷達探測區域保持一定距離,威脅成本可以表示為

(14)

(15)

(16)

式中:N和R分別表示航跡節點數和雷達區域數;Tci表示第i個航跡節點的威脅成本;Ci,l和RWl分別表示第i個航跡節點到第l個雷達中心的距離和雷達探測半徑;lmin表示航跡節點距離雷達探測區域的最小安全距離;(xi,yi,zi)分別表示第i個航跡節點的三維坐標;Nc表示足夠大的常數。

2 基于改進WPA的UAH航跡規劃

2.1 基本WPA

根據不同職能分工,狼群可分為頭狼、探狼和猛狼3種。對于“勝者為王”的頭狼產生規則和“強者生存”的狼群更新機制[20]不作具體闡述,本文主要針對狼群捕獵過程中的3種智能行為展開介紹。

假設狼群的捕獵空間為一個N×D的可行解空間,其中N表示狼群數量,D表示待尋優的維數。某一匹狼的位置定義為Xi=(xi1,xi2,…,xiD),其中xiD為第i匹狼在待尋優的第d(d=1,2,…,D)維變量空間中所處的位置,相應的目標適應度函數值記為Yi;頭狼的位置定義為Xlead=(xlead1,xlead2,…,xleadD),目標適應度函數值記為Ylead。則3種智能行為描述如下:

(17)

同時,探狼i朝著目標適應度值大于當前位置的方向前進一步,并對探狼i的狀態Xi進行更新。重復以上游走行為,直到探狼的目標適應度值Yi大于Ylead或達到最大游走次數,結束當前游走行為。

(18)

奔襲途中,若猛狼j感知到的目標適應度值Yi>Ylead,則Ylead=Yi,此時猛狼j代替頭狼發起召喚行為;若Yi

(19)

式中:ω表示距離判定因子;Md、md分別表示待尋優的第d維變量空間的最大值和最小值。

(20)

式中:λ表示[-1,1]間均勻分布的隨機數。

(21)

式中:C表示步長因子,代表狼群在解空間中搜索的精細程度。

2.2 改進WPA

本文采用自適應步長為

step=rand×‖xi-Xlead‖2

(22)

式中:rand表示[0,1]之間的隨機數。自適應步長依靠當前狼和頭狼的位置信息作出自適應調整,當狼遠離頭狼位置時,以較大步長快速逼近頭狼;當狼靠近頭狼位置時,以較小步長緩慢逼近頭狼,提高了算法的收斂速度。

2.2.1 基于萊維飛行和變方向的自適應游走行為

萊維飛行[25-26]是服從萊維分布的一種隨機搜索方法,是一種短距離和長距離相間混合的搜索方式,具有較好的全局搜索能力。萊維飛行的位置更新公式為

(23)

(24)

式中:μ和v服從正態分布,定義如下:

(25)

式中:Γ表示伽馬函數;γ通常取值為1.5。

對萊維飛行策略進行仿真實驗,起始位置位于(0,0),仿真步長為1 000,仿真結果如圖2所示。從圖2可以看出,萊維飛行策略本身的特殊位置更新方式,使得其具有搜索的隨機性和更廣的搜索范圍,這在一定程度上提高了算法的全局尋優能力和避免了算法陷入局部最優的情況。

圖2 萊維飛行策略仿真圖Fig.2 Simulation diagram of Levy flight strategy

只采用萊維飛行策略雖然有助于提高算法的搜索范圍,以改善算法陷入局部最優的問題,但是其短距離和偶爾長距離相間的位置更新方式會造成算法整體收斂速度較慢,影響航跡規劃的效率。由此將變方向的自適應游走行為與萊維飛行相結合,以幫助萊維飛行策略在提高全局搜索能力的同時,提高算法的收斂速度。具體變方向游走策略如圖3所示。

圖3 變方向游走策略示意圖Fig.3 Schematic diagram of changing direction migration strategy

依據上述策略,規定當游走次數為奇數次時,探狼i向第p(p=1,2,…,h)個方向前進后,探狼i的位置表示為

(26)

當游走次數為偶數次時,探狼i向第p(p=1,2,…,h,h+1)個方向前進后,探狼i的位置表示為

(27)

依據上述游走行為位置更新公式,探狼按照游走次數的奇偶,搜索方向在h和h+1之間變動,豐富了算法搜索范圍,萊維飛行策略和變游走方向的結合使得算法具有出色的全局搜索能力。同時,自適應步長使得當前狼的前進步長依靠其與頭狼的距離動態調整,彌補了萊維飛行策略收斂速度慢的缺陷。

2.2.2 自適應召喚行為

傳統WPA中頭狼召集距離頭狼最近的M_num匹猛狼向頭狼位置奔襲,經過多次迭代之后,頭狼的位置不斷更替,如果只召集頭狼位置附近的猛狼,易使算法陷入局部最優。針對上述缺點,本文在自適應召喚行為中隨機選取除頭狼的M_num匹狼作為猛狼,通過頭狼召喚以自適應步長向頭狼所在位置奔襲。則猛狼j經歷第k+1次迭代時在第d維空間所處的位置為

(28)

2.2.3 自適應圍攻行為

(29)

2.3 算法描述

UAH的航跡可以定義為一系列三維空間位置點的集合P={Pstart,P1,P2,…,Pn,Pgoal},Pstart和Pgoal分別表示UAH的起始點和目標點,Pi=(xi,yi,zi)(i=1,2,…,n)為中間航跡點。將UAH航路上的航跡點Pi作為人工狼在d維空間上的位置信息,則基于改進WPA的UAH航跡規劃具體步驟為:

步驟 1根據第1.1節內容創建三維環境,并設置UAH的起點和目標點。

步驟 2參數初始化。初始化狼群中狼的位置xi及種群數目N,最大迭代次數Kmax,探狼的比例因子α,最大游走次數Tmax,距離判定因子ω,種群更新比例因子β(參數具體描述詳見文獻[20,28])。

步驟 3計算初始化種群個體的目標函數適應度值,選取其中目標函數值最優的作為初始頭狼,位置記為Xlead,目標適應度值記為Ylead。選取除頭狼的目標適應度值最優的S_num匹狼作為探狼,并按照式(22)、式(23)執行游走行為,直到某匹探狼的適應度值優于當前頭狼的適應度值,或者達到最大游走次數Tmax,轉至步驟4。

步驟 4隨機選取除頭狼的M_num匹狼作為猛狼,并按照式(24)向獵物位置奔襲(即頭狼位置)。奔襲途中,如果猛狼感知到的目標函數值Yi大于頭狼感知到的目標函數值Ylead,則Ylead=Yi,當前猛狼替代頭狼重新發起召喚行為,并重新選取猛狼;如果猛狼感知到的目標函數值Yi小于頭狼感知到的目標函數值Ylead,則繼續奔襲行為,直到猛狼與頭狼的距離小于dnear時,轉至步驟5。

步驟 5猛狼聯合探狼對獵物所在位置(即頭狼位置)進行圍攻行為,并按照式(25)對參加圍攻行為的狼的位置進行更新。

步驟 6按照“勝者為王”的頭狼更新規則更新頭狼位置;按照“強者生存”的狼群更新機制對狼群進行更新[13]。

步驟 7判斷是否達到最大迭代次數Kmax,如果滿足,輸出頭狼位置,即最優航跡點位置,否則轉至步驟2。

綜上所述,可得基于改進WPA的UAH航跡規劃流程圖如圖4所示。

圖4 基于改進WPA的航跡規劃流程圖Fig.4 Flow chart of UAH path planning based on improved WPA

3 仿真實驗及結果分析

3.1 仿真環境和實驗數據準備

為驗證本文所提的改進WPA在UAH航跡規劃中的有效性,將傳統WPA算法和改進WPA算法在相同條件下進行離線三維航跡規劃仿真。仿真實驗環境為Win10 64位操作系統,Intel Core i5-7300 HQ處理器,8GB RAM配置下的計算機,仿真軟件為Matlab R2019B。

航跡規劃任務空間為100 km×100 km×10 km,其中包括基準地形山峰、一個障礙區域、兩個雷達區域。相關參數設置如下:基準地形山峰相關參數設置為(xk,yk)=[(50,80),(60,20)],hk=[10,5],xok=[15,10],yok=[15,10];起點坐標為Pstart=[3,3,1];目標點坐標為Pgoal=[90,90,2];障礙區域參數為:(xj,yj,zj)=[75,50,0],RLj=10,hj=6;雷達區域參數為:(xl,yl,zl)=[(20,50,0),(35,20,0)],RWl=[10,8],WPA參數設置如表1所示。同時,為進一步說明改進WPA用于三維航跡規劃的有效性和優越性,本文增加了改進WPA與傳統PSO算法[29]和傳統GA算法[30]用于三維航跡規劃的對比。傳統PSO基本參數選擇如下:粒子個數為50,慣性因子ω=0.79,兩個學習因子c1=c2=2,ωmax=0.9,ωmin=0.4,Vmax=2;傳統GA參數選擇如下:種群規模為50,染色體長度為5,選擇概率為0.5,交叉概率為0.8,變異概率為0.2。

表1 WPA參數設置Table 1 WPA parameter setting

3.2 平緩地形下的仿真結果與分析

從表2和圖5可以看出,由于WPA自身算法特性的限制,在3種智能行為的每一次迭代中都需要計算并判斷當前狼與頭狼的適應度值,因此WPA相比PSO和GA,運行時間更長。但是改進的WPA與其他3種算法相比,在第3代就逐漸收斂到122.9,全局尋優能力更強,同時在快速收斂的同時,改進WPA在后期也有這樣優越的搜索精度,改進WPA規劃出的航跡長度更短,質量更優。同時,與傳統的GA相比,改進的WPA能夠有效改善群智能算法在尋優過程中易陷入局部最優的問題。由此能夠得出以下結論:改進WPA的收斂速度更快,航跡代價更小,改進WPA能夠有效改善傳統WPA中由固化步長所導致的前期收斂速度慢的問題以及易陷入局部最優的情況,并且改進WPA的全局尋優能力更強。

表2 平緩地形下算法的對比結果Table 2 Comparison results of algorithms in gentle terrain

圖5 平緩地形下適應度值變化曲線Fig.5 Change curve of fitness value in gentle terrain

從圖6和圖7可以看出,改進WPA算法和其余3種算法規劃出的航跡均能躲避障礙區域和雷達探測區域,使UAH能夠順利到達目標點。但是,與其他3種算法規劃出的航跡相比,改進WPA規劃出的航跡長度相對較短,航跡高度變化小,航跡冗余少,從而使得航跡質量更佳。

圖6 平緩地形下三維航跡正視圖Fig.6 Front view of 3D track in gentle terrain

圖7 平緩地形下三維航跡俯視圖Fig.7 Top view of 3D track in gentle terrain

3.3 復雜地形下的仿真結果與分析

為進一步說明改進WPA在三維航跡規劃中的性能,在第3.2節仿真的基礎上將地形復雜化,模擬更為復雜的三維環境。4種算法的基本參數不變,起點與終點相同,三維環境相關參數設置如下:基準地形山峰相關參數設置為(xk,yk)=[(20,20),(30,80),(50,20),(60,50),(60,80)],hk=[8,10,5,8,8],xok=[5,10,10,10,8],yok=[5,10,10,10,8];障礙區域參數為:(xj,yj,zj)=[(80,30,0),(40,55,0)],RLj=[6,6],hj=[6,6];雷達區域參數為:(xl,yl,zl)=[(20,50,0),(80,60,0)],RWl=[10,8]。仿真結果如表3、圖8～圖10所示。

表3 復雜地形下算法的對比結果Table 3 Comparison results of two algorithms in complex terrain

圖8 復雜地形下適應度值變化曲線Fig.8 Change curve of fitness value in complex terrain

圖9 復雜地形下三維航跡正視圖Fig.9 Front view of 3D track in complex terrain

圖10 復雜地形下三維航跡俯視圖Fig.10 Top view of 3D track in complex terrain

從表3和圖8可知,改進WPA在復雜地形中仍然能夠快速尋找到最滿意的航跡,雖然因自身算法性能的限制,其在算法運行時間上稍遜于傳統PSO及GA,但是相比傳統WPA已有較大的改善。從圖8可知,改進WPA在第10次迭代后逐漸收斂到最優值附近,相比其他3種算法,收斂速度快,尋優能力更強,規劃出的航跡更短。同時,與傳統GA相比,其傳統群智能算法易陷入局部最優的問題也有著較大的改善。從圖9～圖10可以看出,改進WPA規劃出的航跡冗余少,沒有頻繁的高度變化,航跡質量更優。

綜合第3.2節和第3.3節的仿真結果,可以得出以下結論:本文所提出的改進WPA在用于UAH三維航跡規劃時有著令人滿意的收斂速度和全局尋優能力,能夠快速搜索到最優航跡,且規劃出的航跡質量更優,能夠避開威脅區域,進而保證UAH安全、快速地到達指定目標區域乙執行任務。

4 結 論

本文針對UAH航跡規劃問題,提出了一種改進WPA算法。利用自適應步長代替傳統WPA算法中的游走步長、奔襲步長和圍攻步長,通過依靠當前狼的位置與頭狼位置之間的距離動態調整步長,克服了傳統WPA算法前期收斂速度慢的缺點。同時,針對探狼游走行為,將萊維飛行策略和變方向的自適應游走相結合,進一步拓展了搜索空間,使改進WPA算法具有較好的全局尋優能力和較快的收斂速度。仿真結果表明,與傳統WPA算法相比,改進WPA算法能夠更快搜索到最優航跡,且規劃出的航跡能夠有效躲避障礙物和雷達,航跡規劃所需代價更小,航跡質量更優,實驗證明了改進WPA算法用于解決UAH航跡規劃問題的有效性和優越性。