引入改進(jìn)蝠鲼覓食優(yōu)化算法的水下無人航行器三維路徑規(guī)劃

黃鶴,李瀟磊,楊瀾,王會峰,茹鋒

(1.長安大學(xué)電子與控制工程學(xué)院,710064,西安;2.長安大學(xué)西安市智慧高速公路信息融合與控制重點實驗室,710064,西安;3.長安大學(xué)信息工程學(xué)院,710064,西安)

水下無人航行器(unmanned underwater vehicle,UUV)可用于水下偵查敵情、海域巡邏、反擊敵方潛艇等[1-2]。在UUV的研究中,路徑規(guī)劃問題非常重要,其目的是完成從航程起點到終點的規(guī)劃,躲避障礙物和威脅物,同時盡量選擇行駛路徑短的路線。近年來關(guān)于UUV的路徑規(guī)劃問題,各國學(xué)者做了大量的研究工作,提出了很多UUV路徑規(guī)劃的算法,經(jīng)典算法有人工勢場法[3]、A*算法[4]和D*算法[5]等。王健等[6]提出了一種基于混合勢場法的UUV路徑規(guī)化方法,用于UUV航向保持和避障,但是所設(shè)計的虛擬力比較難實現(xiàn)。相對于經(jīng)典算法,智能算法收斂速度快,魯棒性強,尤其采用群體智能優(yōu)化算法求解UUV路徑規(guī)劃問題是目前的研究熱點,常用的智能算法有粒子群算法[7]、遺傳算法[8]、蟻群算法[9]、灰狼算法(grey wolf optimizer,GWO)[10]等。徐煒翔等[11]針對靜態(tài)的地形和復(fù)雜環(huán)境下UUV的路徑規(guī)劃問題,提出了基于飛蛾撲火算法的UUV三維全局路徑規(guī)劃,但是搜索時間過長。張汝波等[12]針對水下可能存在不同等級的威脅源,提出了一種基于改進(jìn)蟻群算法的UUV航路避障任務(wù)規(guī)劃方法,但是搜索范圍過大,搜索耗時較長。以上研究雖然能夠?qū)崿F(xiàn)UUV的路徑規(guī)劃,但是改進(jìn)效果有待于進(jìn)一步提高。在三維UUV路徑規(guī)劃中,地形和威脅的信息量比較大,更使得群體智能優(yōu)化算法尋求最優(yōu)路徑時復(fù)雜程度會呈現(xiàn)指數(shù)上升[13]。蝠鲼覓食優(yōu)化算法(manta ray foraging optimization algorithm,MRFO)[14]是2020年提出的一種新型群體智能優(yōu)化算法,該算法模仿蝠鲼在海洋中覓食的過程,針對蝠鲼的鏈?zhǔn)揭捠?、螺旋覓食以及翻滾覓食進(jìn)行相應(yīng)的數(shù)學(xué)建模,描述了蝠鲼個體位置更新方式,具有收斂速度快,尋優(yōu)能力強等特點。MRFO算法因具有尋優(yōu)能力強,收斂速度快等特點[15],在復(fù)雜環(huán)境下也可以保持良好的尋優(yōu)能力,適用于三維UUV的路徑規(guī)劃,但是MRFO算法有時會陷入局部最優(yōu),需要進(jìn)一步改進(jìn)。因此,本文結(jié)合蝠鲼的海洋生物特性,提出了一種改進(jìn)的蝠鲼覓食優(yōu)化算法,并應(yīng)用于UUV三維路徑規(guī)劃中,可以避免陷入局部最優(yōu),提高UUV尋優(yōu)精度,有效避開水下威脅物和障礙物,快速獲得最優(yōu)路徑。

1 水下無人航行器三維路徑規(guī)劃環(huán)境建模

1.1 地形約束

水下海拔為負(fù)數(shù),但是為了計算方便,這里仿照同類研究文獻(xiàn)[16],將水下海拔都以海底為0開始按正數(shù)賦值,根據(jù)水下海拔的不同,可以將水下地形分為多種地區(qū)。這里面影響比較大的因素是山峰。首先,水下山峰建模如下式

(1)

式中:(X,Y)為水底平面以上山峰對應(yīng)的坐標(biāo);(X0,Y0)為山峰中心點對應(yīng)的坐標(biāo);h為高度參數(shù);m1和m2為山峰的陡峭程度。規(guī)劃的路徑用航跡點來表示。第i個航跡點對應(yīng)的地形威脅代價表示為

(2)

式中:Kz為地形威脅系數(shù);hi為第i個航跡點對應(yīng)的海拔高度;Zi為第i個航跡點距離海底的垂直高度。此外,UUV路徑規(guī)劃需考慮下潛的深度,下潛的深度必須處于最大和最小下潛深度之間,即為深度約束,第i個航跡點對應(yīng)的深度威脅代價函數(shù)表示為

(3)

式中:hmin和hmax分別表示UUV相對海底的最小高度和最大高度;Kw表示深度威脅系數(shù)。

1.2 威脅模型約束

(1)聲吶威脅。聲吶通過聲波探測敵方目標(biāo)的距離、速度和相對位置等信息,UUV路徑規(guī)劃過程中必須避開其探測范圍。聲吶威脅區(qū)近似由一個橢球形表示,在三維平面上表示的范圍如下

Sth=

(4)

式中:Sth表示聲吶威脅區(qū);X、Y、Z分別指三維平面的X軸、Y軸和Z軸;X1、Y1、Z1為對應(yīng)的球心坐標(biāo);a、b分別為橢球體的長半徑和短半徑;R為相應(yīng)的球體的半徑。

(2)洋流威脅。UUV在水下航行時,要盡量避免航線經(jīng)過強洋流地帶。本文強洋流地帶可以用下式表示

So=

(5)

式中:So表示洋流威脅區(qū)。

(3)水雷威脅。敵方水雷的威脅范圍內(nèi)被稱作禁游區(qū),可以近似為一個半球體,表示為

PM=PvPk/v

(6)

(7)

式中:Pk/v表示UUV在禁游區(qū)半徑內(nèi)被摧毀的概率,是常數(shù);K0為比例系數(shù);RS為水雷威脅中心與UUV之間的斜距;θ為視線俯視角。則

PM=K0sinθ·Pk/v

(8)

在三維模型創(chuàng)建的過程中,威脅源半徑比較大,因此可以將所有的威脅源等效為圓柱地形處理。威脅代價表示如下

(9)

式中:KTj為威脅源j的威脅系數(shù);rij為第i個航跡點到威脅源j的直線距離;RTj表示的是威脅源的威脅半徑。

1.3 UUV自身物理約束

UUV航行過程中會受到自身轉(zhuǎn)彎角α0和爬升角β0的約束。同時,還有自身的燃油代價,可以用路程來表示。設(shè)最大轉(zhuǎn)彎角為αmax,最大爬升角為βmax。轉(zhuǎn)彎角、爬升角物理約束分別表示如下

(10)

(11)

式中:Kh和Kv分別為轉(zhuǎn)彎角和爬升角威脅系數(shù);Ja和Jv為第i個航跡點對應(yīng)α0和β0的代價函數(shù)。綜合各代價函數(shù),可得出第i個航跡點的UUV物理約束代價函數(shù)為

fJi=Ja+Jv+JLi

(12)

路程代價物理約束為

(13)

1.4 航跡代價函數(shù)

將所有地形約束、深度代價、威脅模型約束以及UUV的自身物理約束加權(quán)綜合起來,構(gòu)成最終UUV的代價函數(shù),如下式

(14)

式中:F(R)就是整條航跡的代價;ω1、ω2、ω3、ω4為各代價的權(quán)重。

2 改進(jìn)的蝠鲼覓食算法

2.1 經(jīng)典MRFO算法

2.1.1 鏈?zhǔn)揭捠砙17]

鏈?zhǔn)揭捠掣路绞降臄?shù)學(xué)模型如下

(15)

(16)

2.1.2 螺旋覓食[18]

螺旋覓食更新方式的數(shù)學(xué)模型如下。

(1)當(dāng)t/T>r時,蝠鲼螺旋覓食方程為

(17)

(18)

式中:T為總迭代次數(shù);t為當(dāng)前迭代次數(shù);r和r1都表示在[0,1]上的隨機數(shù)。

(2)當(dāng)t/T≤r時,蝠鲼螺旋覓食方程為

(19)

(20)

2.1.3 翻滾覓食

翻滾覓食時,蝠鲼個體會以當(dāng)前最優(yōu)解的位置作為翻滾的支點,數(shù)學(xué)表達(dá)式如下

i=1,2,…,N

(21)

S=2

(22)

式中:r2和r3都是在[0,1]上的隨機數(shù);S為翻滾因子;N為個體的數(shù)量。

2.2 改進(jìn)的蝠鲼覓食優(yōu)化算法

2.2.1 局部反向?qū)W習(xí)

反向?qū)W習(xí)是一種群體智能的改進(jìn)策略,隨機初始化所生成的種群可能位置不夠好,不利于全局搜索。因此,初始化過程中需加入反向解搜索[19],增加種群的多樣性,有利于尋找全局最優(yōu)解。

(23)

在實際搜索過程中,如果對所有初始化的種群都生成其反向解,會增加迭代搜索的時間,因此在經(jīng)典反向?qū)W習(xí)的基礎(chǔ)上,本文設(shè)計了一種局部反向?qū)W習(xí)方法,只對初始化位置較差的一半種群進(jìn)行反向?qū)W習(xí),其余的保持不變。

局部反向?qū)W習(xí)策略的具體公式為

(24)

(25)

局部反向?qū)W習(xí)策略的具體步驟為:

(2)計算所生成種群的適應(yīng)度;

這樣相比于經(jīng)典的反向?qū)W習(xí),提出的局部反向?qū)W習(xí)不僅能夠獲得位置較優(yōu)的種群,提高全局搜索能力。同時,只對適應(yīng)度較差的一半種群進(jìn)行反向求解,使得搜索時間更短,提高了尋優(yōu)速度。

2.2.2 自適應(yīng)翻滾

MRFO算法中翻滾覓食是一個比較頻繁的動作,可以提高蝠鲼的覓食效率。在其數(shù)學(xué)模型中有一個翻滾因子S,決定了翻滾的距離。在傳統(tǒng)的MRFO算法中S一般取2,但是因為翻滾因子S在蝠鲼的迭代更新過程中不會發(fā)生變化,所以搜索過程中易陷入局部最優(yōu)。因此,本文提出一種新的自適應(yīng)翻滾方式,根據(jù)每次迭代后種群的適應(yīng)度不同,在翻滾因子中加入一個變化的翻滾系數(shù)ρ,翻滾系數(shù)ρ隨著蝠鲼種群位置的適應(yīng)度變化而變化,使得翻滾因子S能夠隨著種群適應(yīng)度的變化而做出動態(tài)調(diào)整,有效地擴大了搜索范圍,有利于跳出局部最優(yōu)。加入ρ后蝠鲼種群的變化方式變得更靈活,有利于尋求全局最優(yōu),提升尋優(yōu)精度。翻滾系數(shù)的更新方式如下式

(26)

圖1 翻滾因子S的變化

從圖1可以看出,翻滾因子S隨著迭代的進(jìn)行不斷變化,在迭代前期、中期,因種群個體適應(yīng)度與最優(yōu)種群適應(yīng)度差異較大,賦予翻滾系數(shù)ρ一個變化較大的值,導(dǎo)致翻滾因子S波動劇烈,擴大了蝠鲼種群的翻滾幅度,可以使蝠鲼種群在下一次迭代過程中位置多樣性增強,有利于尋找全局最優(yōu)。隨著迭代的進(jìn)行,蝠鲼種群逐漸搜索到最優(yōu)解,這樣適應(yīng)度的變化幅度也相應(yīng)減小,S也逐漸趨于穩(wěn)定,蝠鲼聚集在最優(yōu)解周圍增強了局部的搜索能力。加入翻滾系數(shù)ρ后蝠鲼翻滾覓食的更新方式轉(zhuǎn)換為

i=1,2,…,N

(27)

2.2.3 融合萊維飛行-柯西變異策略

本文提出一種融合萊維飛行-柯西變異的策略,首先在蝠鲼的螺旋覓食中加入萊維飛行策略,增加了種群位置的多樣性,擴大了搜索范圍。萊維飛行是一種隨機游走策略[20-21],結(jié)合長距離游走和短距離游走。執(zhí)行過程中,通過長距離游走擴大搜索范圍,跳出局部最優(yōu);通過短距離搜索加快收斂速度。這樣,在蝠鲼的螺旋覓食中加入萊維飛行,可以擴大搜索范圍,同時也加快了收斂速度。相較于其他的改進(jìn)方法,萊維飛行的隨機游走性更強[22]。同時在翻滾覓食后,對當(dāng)前蝠鲼的最優(yōu)位置進(jìn)行柯西變異,柯西函數(shù)因為其分布范圍廣,可以進(jìn)一步提升蝠鲼的全局搜索能力。萊維飛行的具體描述如下

(28)

式中:δ=1.5;μ和ν則服從正態(tài)分布

(29)

(30)

(31)

式中:Γ(·)為伽馬函數(shù);σν=1。

增加萊維飛行后,式(17)和(19)可轉(zhuǎn)換為

(32)

(33)

采用的柯西分布[23]和變異函數(shù)如下式

(34)

xnewbest=xbest+Cauchy(x0)xbest

(35)

式中:xnewbest為更新后蝠鲼的位置;xbest為更新前蝠鲼的位置;柯西函數(shù)中x0取值為0～1的隨機數(shù)?？挛鞣植己瘮?shù)的中間峰值比較小而兩邊分布的范圍比較廣,可以使蝠鲼在當(dāng)前范圍產(chǎn)生較大的擾動,幫助跳出局部最優(yōu)。

2.2.4 本文算法流程

本文算法流程如圖2所示。

圖2 本文算法流程圖

2.3 性能仿真實驗

2.3.1 測試函數(shù)

根據(jù)路徑規(guī)劃需要,利用測試函數(shù)對本文算法的性能進(jìn)行分析比較。其中,單峰值函數(shù)可以測試算法的收斂精度,多峰值函數(shù)可以測試算法的尋優(yōu)能力。分別選取3個單峰值函數(shù)和3個多峰值函數(shù)進(jìn)行測試。

(1)Schwefel 1.2函數(shù)表達(dá)式為

(36)

式中:n=30;xj∈[-100,100];全局最小值為0。

(2)Schwefel 2.21函數(shù)表達(dá)式為

f(x)=maxi{|xi|,1≤i≤n}

(37)

式中:n=30;xi∈[-100,100];全局最小值為0。

(3)Step函數(shù)表達(dá)式為

(38)

式中:n=30;xi∈[-100,100];全局最小值為0。

(4)Ackley函數(shù)表達(dá)式為

(39)

式中:n=30;xi∈[-32,32];全局最小值為0。

(5)Griewank函數(shù)表達(dá)式為

f(x)=

(40)

式中:n=30;xi∈[-600,600];全局最小值為0。

(6)Shekel 10函數(shù)表達(dá)式為

(41)

式中:xki為矩陣Xk中第i行的向量;aki為矩陣Ak中第i行的向量;cki為向量Ck的第i個元素;矩陣Xk和矩陣Ak均為10行4列的矩陣;xki∈[0,10];aki∈[0,10];cki∈[0,1];該函數(shù)的全局最小值為-10.53。

2.3.2 實驗驗證

采用上述測試函數(shù)評估MRFO算法、GWO算法[24]及本文算法的尋優(yōu)性能。其中,種群規(guī)模為100,迭代次數(shù)為800。圖3為各函數(shù)的三維參數(shù)空間以及各算法在不同測試函數(shù)上的適應(yīng)度曲線,表1為經(jīng)過30次測試的適應(yīng)度均值和最優(yōu)值。

(a)Schwefel 1.2函數(shù)

由圖3和表1可知,在Schwefel 1.2函數(shù)和Schwefel 2.21函數(shù)中,MRFO算法的收斂精度不如GWO算法,但是本文算法收斂精度卻是最好的,強于GWO算法。在Step函數(shù)中MRFO算法的收斂精度優(yōu)于GWO算法,本文算法在MRFO算法基礎(chǔ)上有了一定提升。在Ackley函數(shù)中,本文算法尋優(yōu)能力和速度都優(yōu)于GWO和MRFO算法。說明本文算法可以有效地跳出局部最優(yōu),尋找全局最優(yōu)。在Griewank函數(shù)中,GWO和本文算法尋優(yōu)能力大致相同,但是尋優(yōu)速度不如本文算法。在Griewank函數(shù)中,GWO算法的尋優(yōu)能力和尋優(yōu)速度都不如MRFO算法,本文算法最高?？傮w來說改進(jìn)后的本文算法可以提高M(jìn)RFO算法的尋優(yōu)精度、尋優(yōu)能力以及尋優(yōu)的速度,有利于跳出局部最優(yōu)。

表1 3種算法在測試函數(shù)上的實驗對比

3 引入改進(jìn)蝠鲼覓食優(yōu)化算法的UUV三維路徑規(guī)劃

航跡點數(shù)n對于UUV的路徑規(guī)劃很重要,相關(guān)研究表明,路徑的精度隨著n的增加變得更精確,但是如果n的數(shù)量過多,不僅會提高計算復(fù)雜度,還影響路徑優(yōu)化的效率[25]。本文設(shè)置了航跡點數(shù)分別為5、10、15、20,結(jié)合本文提出的改進(jìn)蝠鲼覓食優(yōu)化算法對路徑進(jìn)行預(yù)先規(guī)劃,以確定合適的航跡點數(shù)。圖4為不同航跡點下利用改進(jìn)蝠鲼覓食優(yōu)化算法所規(guī)劃的路徑。

(a)航跡點為5 (b)航跡點為10

從圖4中可以看出,當(dāng)航跡點為5時,規(guī)劃路徑不能有效規(guī)避水下山脈等障礙物,與理想路徑有較大差距。當(dāng)航跡點為10時,比航跡點為5時規(guī)劃的路徑避障能力更強,但是精度仍然不夠,不能規(guī)避所有障礙物。航跡點為15時,規(guī)劃的路徑準(zhǔn)確,可以較好地實現(xiàn)水下避障,尋找較短的路徑,實現(xiàn)較理想的路徑規(guī)劃。航跡點為20時,規(guī)劃路徑效果相比于航跡點為15時規(guī)劃的路徑并沒有明顯的提升,但是耗時增加很多,因此綜合比較可以看出,選擇航跡點為15、可以在耗時較少的情況下,規(guī)劃出精準(zhǔn)的路徑。

4 路徑規(guī)劃仿真實驗及分析

仿真環(huán)境中采用CPU為Intel Core i7-10750H CPU 2.60 GHz、內(nèi)存為16 GB的計算機,操作系統(tǒng)為Windows10,編譯軟件為Matlab R2018b。為了測試本文算法在UUV路徑規(guī)劃中的效果,采用兩種不同的地形。地形1中地形區(qū)域大小為100 km×100 km,測試中UUV距離海底的最大高度為4 km。UUV的起始點與終止點分別為(1,3,0.5) km及(99,98,0.5) km,敵方水雷距離中心為(20,13.5,0) km、(85,60,0) km、(40,59,0) km,分布在半徑為9 km的區(qū)域。聲吶距離中心為(65,30,0) km、(50,90,0) km,作用半徑為9 km。路徑規(guī)劃過程中的主要參數(shù)如表2所示。地形1中UUV路徑軌跡、代價曲線分別如圖5和圖6所示,UUV的航程和最優(yōu)代價如表3所示。地形2中區(qū)域大小和地形1相同,UUV的起始點為(1,93,0.5) km,終止點為(99,8,0.5) km。水下水雷的位置為(30,13.5,0) km、(85,55,0) km、(40,55,0) km。聲吶的位置為(65,30,0) km、(50,90,0) km。用正方形、星號和圓圈分別表示MRFO、GWO和本文算法求得3條UUV路徑的航跡點。在實驗?zāi)M中各算法種群數(shù)設(shè)為100,最大迭代次數(shù)為800次。地形2中UUV的路徑軌跡、代價曲線分別如圖7和圖8所示,UUV的航程和最優(yōu)代價如表4所示。

表2 路徑規(guī)劃過程中的主要參數(shù)

表3 地形1中UUV的航程及最優(yōu)代價

圖5 地形1中UUV的路徑軌跡

圖6 地形1中最優(yōu)路線代價變化

圖7 地形2中UUV的路徑軌跡

圖8 地形2中最優(yōu)路線代價變化

表4 地形2中UUV的航程及最優(yōu)代價

在圖5和圖7中,兩種地形中各有相應(yīng)的威脅源和障礙物。根據(jù)航跡代價函數(shù)式(14)可知,UUV路徑規(guī)劃時,需要對各地形及水雷、洋流等威脅源同步規(guī)避,而最終路徑取決于航跡代價函數(shù)及優(yōu)化算法的尋優(yōu)能力。如果優(yōu)化算法尋優(yōu)能力較弱,路徑點易陷入局部最優(yōu),導(dǎo)致UUV進(jìn)入威脅區(qū)或者與障礙物發(fā)生碰撞。從圖5可以看出,地形1中GWO算法的規(guī)劃路徑會與水下的山脈相撞;MRFO算法的規(guī)劃路徑在迭代初期可以繞過山脈,但是迭代過程中無法跳過威脅區(qū)尋到一條更優(yōu)的路徑,而且后續(xù)路徑還是會與山脈相撞,這是因為MRFO算法尋優(yōu)能力不足所導(dǎo)致的。本文算法的路徑可以有效地避開水下聲吶、水雷等威脅區(qū)域,同時也能避開水下山脈等障礙物,主要原因是本文算法的尋優(yōu)能力更強。相對于GWO和MRFO算法,本文算法規(guī)劃的路線最優(yōu)。由表3可以看出,GWO算法的航程最長,代價最大,MRFO算法相對有所減小,而本文算法的航程和代價最小。相對于GWO和MRFO算法,本文算法航程分別減少了32.49 km和23.88 km,代價損失分別減小了9.68和4.04。由圖7可知,UUV按照GWO和MRFO算法在地形2中規(guī)劃的路徑會與水下山脈相撞,同時不能規(guī)避聲吶和水雷威脅,而采用本文算法所規(guī)劃的路徑則可以有效規(guī)避障礙物和水下威脅,不會與山脈等相撞。由表4可以看出,地形2中本文算法的航程最短,相對于GWO和MRFO算法所規(guī)劃的航程分別減少了20.83 km和29.95 km,代價損失分別減小了10.14和3.18。同時,由圖6和圖8還可以看出,GWO和MRFO算法收斂過快,易陷入局部最優(yōu),本文算法則可以有效地跳出局部最優(yōu),尋優(yōu)能力更強。這是由于本文算法采用自適應(yīng)翻滾和萊維飛行-柯西變異策略,面對復(fù)雜地形時各路徑點尋優(yōu)能力較強,在威脅源中或者發(fā)生碰撞前,可迅速規(guī)避并尋得最優(yōu)路徑。

5 結(jié) 論

針對UUV的路徑規(guī)劃問題,構(gòu)建了相關(guān)的水下地形、威脅以及自身約束組成的三維模型;提出了一種改進(jìn)的蝠鲼覓食優(yōu)化算法,解決了MRFO算法容易陷入局部最優(yōu),收斂精度低的問題;將改進(jìn)的蝠鲼覓食優(yōu)化算法應(yīng)用到UUV三維路徑規(guī)劃中,可以有效地減小UUV路徑規(guī)劃的航程和代價,躲避水下障礙物和威脅,選擇最優(yōu)路徑。