自主水下航行器多終點(diǎn)航路規(guī)劃的距離正則化混合水平集算法研究

盛亮， 邱志明， 于邵禎， 焦俊杰

(1.海軍航空大學(xué) 航空基礎(chǔ)學(xué)院， 山東 煙臺(tái) 264001；2.海軍工程大學(xué) 兵器工程學(xué)院， 湖北 武漢 430033；3.海軍研究院， 北京 102442；4.南京理工大學(xué) 機(jī)械工程學(xué)院， 江蘇 南京 210094)

0 引言

自主水下航行器(AUV)的多終點(diǎn)航路規(guī)劃是對(duì)AUV單一航路規(guī)劃的自然延伸，是指在復(fù)雜海洋環(huán)境下尋求從航行起點(diǎn)到多個(gè)終點(diǎn)的最優(yōu)航路集。適用于AUV單一航路規(guī)劃的算法，如A*算法、快速搜索隨機(jī)樹(shù)(RRT)算法、蟻群優(yōu)化算法(簡(jiǎn)稱(chēng)蟻群算法)、粒子群優(yōu)化算法(簡(jiǎn)稱(chēng)粒子群算法)、差分進(jìn)化算法、人工勢(shì)場(chǎng)法等，理論上也能用于多終點(diǎn)的航路規(guī)劃，但需要通過(guò)多次重復(fù)調(diào)用算法的整個(gè)計(jì)算周期來(lái)實(shí)現(xiàn)，無(wú)法一次性規(guī)劃出所有最優(yōu)航路。理論上，隨著終點(diǎn)數(shù)的增多，占用的資源和規(guī)劃耗時(shí)會(huì)成倍增加。針對(duì)多終點(diǎn)的航路規(guī)劃問(wèn)題，探索一次規(guī)劃出到所有終點(diǎn)的最優(yōu)航路集的可能性，成為值得關(guān)注的研究課題。

Yigit[1]在2011年首次提出利用水平集算法開(kāi)展考慮海流和固定障礙物影響的AUV航路規(guī)劃；Lolla等[2]在此基礎(chǔ)上驗(yàn)證了水平集算法用于多終點(diǎn)航路規(guī)劃的可行性和有效性。相比其他算法，水平集算法的優(yōu)勢(shì)在于：一是可以通過(guò)一次演化計(jì)算找到至多終點(diǎn)的所有最優(yōu)航路；二是能夠?qū)⒑Ａ魉俣戎苯蛹{入演化方程，理論上能夠得到考慮海流影響的AUV航路規(guī)劃最優(yōu)解析解。文獻(xiàn)[3-4]將水平集算法應(yīng)用于時(shí)變的真實(shí)海洋環(huán)境中并開(kāi)展了實(shí)時(shí)海上試驗(yàn)，取得了較好的效果。文獻(xiàn)[5]結(jié)合隨機(jī)正交分解方法，提出一種用于在時(shí)間最優(yōu)航路集中尋求最優(yōu)能耗航路的新的隨機(jī)正交水平集算法，并基于半實(shí)物模型進(jìn)行了算法驗(yàn)證。在此基礎(chǔ)上，基于隨機(jī)的AUV自身速度大小和方向，文獻(xiàn)[6]推導(dǎo)出可用于動(dòng)態(tài)變化海流場(chǎng)中的隨機(jī)動(dòng)態(tài)正交水平集方程，并給出了數(shù)值實(shí)現(xiàn)的簡(jiǎn)化形式，結(jié)果表明新的算法是精確和有效的。在國(guó)內(nèi)，劉廠(chǎng)等[7]提出了一種用于AUV航路規(guī)劃的改進(jìn)水平集算法。通過(guò)采用八鄰域方式代替?zhèn)鹘y(tǒng)四鄰域方式來(lái)提高計(jì)算精度，再采用雙快速行進(jìn)方法改善傳統(tǒng)的快速行進(jìn)法以加快窄帶的重構(gòu)速度，在一定程度上提升了算法執(zhí)行效率，仿真結(jié)果表明改進(jìn)算法是可靠和有效的。

以上改進(jìn)算法并沒(méi)有在效率方面取得明顯改善，原因在于這些算法都需要重新初始化窄帶，而窄帶的頻繁初始化是占用計(jì)算資源最多、最耗時(shí)的部分。針對(duì)水平集算法的這一缺點(diǎn)，Li等[8]提出一種無(wú)需重新初始化窄帶的距離正則化水平集演化(DRLSE)算法。該算法通過(guò)引入能量懲罰項(xiàng)即距離正則化項(xiàng)，使得水平集在不斷演化過(guò)程中，糾正水平集函數(shù)與符號(hào)距離函數(shù)之間的偏差，使之自動(dòng)約束為符號(hào)距離函數(shù)而無(wú)需再初始化，大大提升了水平集算法的計(jì)算效率。

近年來(lái)，DRLSE思想在圖像分割、拓?fù)鋬?yōu)化得到廣泛應(yīng)用。文獻(xiàn)[9-10]為克服DRLSE算法對(duì)初始輪廓高度敏感的缺點(diǎn)，提出一種結(jié)合C均值聚類(lèi)方法的混合算法，可用于甲狀腺結(jié)節(jié)圖像分割和肝臟腫瘤圖像分割。文獻(xiàn)[11]采用改進(jìn)DRLSE模型把圖像的局部信息結(jié)合到變分能量方程中，用改進(jìn)的能量方程指導(dǎo)曲線(xiàn)的演化。結(jié)果表明，新算法平均消耗時(shí)間只需要DRLSE的2.76%，且具有較高的分割準(zhǔn)確性。文獻(xiàn)[12]基于局部熵提出一種改進(jìn)的結(jié)合邊界信息和區(qū)域信息的水平集圖像分割模型，具備一定的環(huán)境自適應(yīng)能力，增強(qiáng)了抗噪性能和分割不均勻圖像的能力。文獻(xiàn)[13]結(jié)合雙向漸進(jìn)結(jié)構(gòu)優(yōu)化和DRLSE演化思想，提出一種用于拓?fù)鋬?yōu)化的局部水平集組合算法，且通過(guò)實(shí)例驗(yàn)證了算法的收斂性和數(shù)值穩(wěn)定性。

本文通過(guò)結(jié)合局部水平集思想和改進(jìn)后的距離正則化項(xiàng)，提出一種多項(xiàng)式距離正則化局部水平集(P-DRLLSM)算法，用于AUV的多終點(diǎn)航路規(guī)劃，避免了窄帶的重新初始化，進(jìn)一步提升了計(jì)算效率，并能在一次算法計(jì)算周期內(nèi)規(guī)劃出到多終點(diǎn)的所有時(shí)間最優(yōu)航路。

1 距離正則化局部水平集算法

1.1 基于傳統(tǒng)水平集算法的AUV航路規(guī)劃模型

1.1.1 水平集算法

水平集算法求解問(wèn)題的基本思想是：在空間Ω中，構(gòu)造更高一維的水平集函數(shù)φ(x,t)，使得在任意時(shí)刻t，運(yùn)動(dòng)界面Γ(t)就是φ(x,t)的零水平集，即

Γ(t)={x∈Ω:φ(x,t)=0}, ?t∈R+，

(1)

式中：R+表示正數(shù)集合。

為方便表述，水平集函數(shù)簡(jiǎn)寫(xiě)為φ. 從而將不易求解的運(yùn)動(dòng)界面Γ上物理量的問(wèn)題轉(zhuǎn)換為先求解高一維隨時(shí)間演化的水平集函數(shù)，再根據(jù)演化時(shí)間得出零水平集曲線(xiàn)，即運(yùn)動(dòng)界面。以二維空間為例，設(shè)l(t)為一條光滑封閉曲線(xiàn)，其隨時(shí)間而變化，等同于界面Γ. 與之對(duì)應(yīng)的水平集函數(shù)為l(t)，t時(shí)刻l(t)代表的零水平集φ(l,t)=0，對(duì)其求導(dǎo)，得

(2)

(3)

1.1.2 AUV航路規(guī)劃模型

考慮速度為v(x,t)的海流影響，AUV的運(yùn)動(dòng)由零水平集的運(yùn)動(dòng)決定，水平集演化方程中的演化速度則由海流速度和AUV自身速度合成，演化方程為

(4)

式中：FAUV(x,t)為AUV自身速度，即AUV相對(duì)海流的速度。初始條件為φ(x,0)=|x-ys|，其中ys為AUV航路規(guī)劃的起點(diǎn)。為保證所求路徑為時(shí)間最優(yōu)，要求FAUV(x,t)的方向?yàn)樗郊瘮?shù)的梯度方向，則(4)式可進(jìn)一步化為(5)式的Hamilton-Jacobi方程，即基于水平集算法的AUV航路規(guī)劃演化方程：

(5)

當(dāng)AUV到達(dá)終點(diǎn)yf即在t=t(yf)時(shí)，終點(diǎn)也落在了零水平集內(nèi)，即φ(yf,t(yf))=0. 此時(shí)，t(yf)即為海流影響下的AUV最優(yōu)航行時(shí)間。再通過(guò)(6)式進(jìn)行回溯，即可得到一條時(shí)間最優(yōu)的航行路徑：

(6)

1.2 局部水平集算法

為了克服傳統(tǒng)水平集算法計(jì)算效率低的問(wèn)題，有學(xué)者提出了局部水平集算法[14]。局部水平集的方程可以表示為

(7)

式中：φ′(x,t)為局部水平集函數(shù)，簡(jiǎn)寫(xiě)為φ′；c(φ′)為截?cái)嗪瘮?shù)，

(8)

γ為局部水平集的半帶寬，圖1中陰影部分即為局部水平集的窄帶，設(shè)為D0，γ、β為常量，其值取決于數(shù)值計(jì)算中模板的寬度，通常設(shè)為網(wǎng)格間距Δx的2～6倍，0<β<γ；若采用3階WENO格式進(jìn)行偏微分的數(shù)值逼近，可取β=2Δx，γ=4Δx；若采用3階WENO格式，可取β=3Δx，γ=6Δx；F(x,t)為水平集函數(shù)的演化速度。設(shè)Fk為水平集函數(shù)的法向演化速率，則由(1)式可得

(9)

圖1 局部水平集模型Fig.1 Model of LLSM

1.3 距離正則化及其改進(jìn)

(10)

式中：div(·)表示散度算子；ρ(φ′)=μdp(|φ′|)為擴(kuò)散速率，μ為擴(kuò)散系數(shù)，dp(φ′)為擴(kuò)散函數(shù)。擴(kuò)散函數(shù)[15]可為

(11)

Wu等[16]對(duì)擴(kuò)散函數(shù)進(jìn)行了如下改進(jìn)：

(12)

式中：σ為正常數(shù)，按照數(shù)值經(jīng)驗(yàn)一般選為4倍網(wǎng)格尺寸。根據(jù)逼近理論，任何函數(shù)均可由簡(jiǎn)單多項(xiàng)式最佳逼近，而低階的簡(jiǎn)單多項(xiàng)式具有操作方便、運(yùn)算速度快的特點(diǎn)。本文為進(jìn)一步提高計(jì)算效率，將擴(kuò)散函數(shù)簡(jiǎn)單多項(xiàng)式化。多項(xiàng)式化后的距離正則化函數(shù)為

(13)

與局部水平集函數(shù)相結(jié)合，多項(xiàng)式距離正則化(P-DRE)擴(kuò)散函數(shù)局部化，則改進(jìn)后的精簡(jiǎn)化擴(kuò)散函數(shù)為

(14)

2 改進(jìn)的距離正則化局部水平集算法用于AUV多終點(diǎn)航路規(guī)劃

2.1 AUV多終點(diǎn)航路規(guī)劃模型

不失一般性，考慮單一起始點(diǎn)到多終點(diǎn)的多航路規(guī)劃。如圖2所示，以二維空間為例，在空間Ω中，ys為起始點(diǎn)，yf1、yf2、…、yfq為處于不同位置的q個(gè)終點(diǎn)?，F(xiàn)需要找到從起點(diǎn)ys到這q個(gè)終點(diǎn)的最優(yōu)航路。當(dāng)前用于AUV航路規(guī)劃的尋優(yōu)算法，如圖搜索算法中的A*算法、RRT算法、Voronoi圖算法，智能優(yōu)化算法中的神經(jīng)網(wǎng)絡(luò)法、粒子群算法、量子粒子群算法、蟻群算法、遺傳算法以及人工勢(shì)場(chǎng)法等都是在算法的一個(gè)計(jì)算周期或流程內(nèi)只能完成起點(diǎn)ys到某一個(gè)終點(diǎn)的航路尋優(yōu)yfg，如需再規(guī)劃ys到另外終點(diǎn)yfh(其中，1≤g,h≤q，且g≠h)的最優(yōu)航路，則需要再次開(kāi)啟算法的一個(gè)計(jì)算周期。

圖2 AUV多終點(diǎn)航路規(guī)劃模型Fig.2 AUV multi-destination route planning model

本文提出利用改進(jìn)的距離正則化局部水平集算法，在一個(gè)計(jì)算周期內(nèi)完成單一起點(diǎn)到多終點(diǎn)的AUV多航路規(guī)劃，避免了算法計(jì)算周期的反復(fù)調(diào)用，將大大提高計(jì)算效率，減少規(guī)劃用時(shí)。

首先，將基于傳統(tǒng)水平集算法的AUV航路規(guī)劃演化方程(4)式局部化，可得

(15)

即有

(16)

進(jìn)行局部化改進(jìn)以提高計(jì)算效率后，加入改進(jìn)的簡(jiǎn)單P-DRE項(xiàng)以避免重新初始化，從而進(jìn)一步提升計(jì)算效率。本文提出的改進(jìn)后全新的P-DRLLSM方程為

(17)

由(17)式可知，AUV航路規(guī)劃的P-DRLLSM方程右邊由演化項(xiàng)L1(φ′)和正則項(xiàng)L2(φ′)組成，

(18)

(19)

2.2 海流、障礙物及威脅建模

海流會(huì)對(duì)AUV的水下航行產(chǎn)生不可忽視的影響，輕者使之偏航，重者導(dǎo)致迷航、損毀。本文將可能導(dǎo)致AUV傾覆、迷航乃至損毀的流速較大渦流、內(nèi)波等區(qū)域劃定為環(huán)境威脅區(qū)，類(lèi)同障礙物，屬于禁止航行區(qū)域。進(jìn)行二維航路規(guī)劃時(shí)，將渦流形成的禁航區(qū)建模成橢圓，內(nèi)波區(qū)域則建模成不規(guī)則的凸多邊形。禁止航行區(qū)模型如圖3所示。

圖3 禁止航行區(qū)模型示意圖Fig.3 Model of forbidden area

使AUV偏航的較小海流大體可分為風(fēng)海流、梯度流和潮汐流等，在一個(gè)較短時(shí)間段內(nèi)，某一片海域的海流通?？梢岳斫鉃橛刹煌瑴u流和定常流組成。因此，參考文獻(xiàn)[17-18]，本文對(duì)導(dǎo)致AUV偏航的較小海流采用多個(gè)Lamb渦流和定常流的疊加開(kāi)展建模。海流運(yùn)動(dòng)方程可表示為

(20)

式中：vx(r)、vy(r)、vz(r)分別為水平、縱向和垂直方向的渦流速度分量；κ、ξ分別用來(lái)描述渦流強(qiáng)度、渦流半徑坐標(biāo)；rie表示第ie個(gè)渦流中心的位置，仿真過(guò)程中渦流中心位置隨機(jī)生成；ne為疊加的渦流個(gè)數(shù)；vCx、vCy、vCz分別為定常流vC在水平、縱向及垂直方向的速度分量。圖4為海流運(yùn)動(dòng)方程生成的二維海流仿真示意圖。由圖4可知，該方法能夠模擬較為真實(shí)的海流運(yùn)動(dòng)。

圖4 二維海流仿真示意圖Fig.4 2D ocean current simulation

除了海流，障礙物和敵對(duì)威脅也會(huì)對(duì)AUV的航行安全產(chǎn)生很大影響，需要在實(shí)際航行時(shí)避開(kāi)這些區(qū)域。障礙物依照其外形輪廓，按照內(nèi)波建模方法處理成凸多邊形模型(見(jiàn)圖5)，而AUV航行主要的敵對(duì)威脅是水聲探測(cè)設(shè)備。單個(gè)水聲探測(cè)設(shè)備的探測(cè)區(qū)域通常是一種錐型區(qū)域，其水平剖面為圓形，因此二維航路規(guī)劃時(shí)，本文將敵對(duì)威脅區(qū)建模為圓形，三維時(shí)以最大探測(cè)圓為底、探測(cè)距離為高，建模成一個(gè)圓柱形區(qū)域，如圖6所示。多個(gè)水聲探測(cè)設(shè)備形成探測(cè)陣列時(shí)，二維時(shí)建模成長(zhǎng)方形，三維時(shí)處理成長(zhǎng)方體。

圖5 障礙物建模Fig.5 Model of obstacle

圖6 敵對(duì)探測(cè)威脅區(qū)建模Fig.6 Model of hostile detection threat zone

圖7 多邊形規(guī)整化與膨脹處理Fig.7 Regularization and expansion treatments of polygon

2.3 算法數(shù)值求解

二維空間中，笛卡爾網(wǎng)格間距設(shè)為Δx、Δy，演化時(shí)間步長(zhǎng)為Δt. 符號(hào)φ′i,jn代表φ′(iΔx，jΔy，nΔt)，即在nΔt時(shí)刻，水平集函數(shù)在坐標(biāo)(iΔx，jΔy)處的值。采用有限差分的迎風(fēng)格式方法，定義vx、vy為海流速度v(x，t)在笛卡爾坐標(biāo)系下的分量，則有

(21)

式中：φ′x、φ′y分別為水平集函數(shù)在x軸、y軸方向的差分形式。則演化項(xiàng)可離散化為

(22)

式中：

(23)

式中：

為保持?jǐn)?shù)值迭代過(guò)程中的穩(wěn)定性，(23)式需滿(mǎn)足CFL條件，即

(24)

由(17)式、(22)式及(23)式，可得改進(jìn)的距離正則化水平集數(shù)值迭代方程為

(25)

(25)式中時(shí)間步長(zhǎng)Δt、網(wǎng)格間距Δx和Δy需滿(mǎn)足：

迭代演化從ys開(kāi)始，初始條件為φ′(ys,0)=0. 經(jīng)過(guò)tg=T(yfg)演化到第1個(gè)終點(diǎn)yfg時(shí)，φ′(yfg,tg)=φ′(yfg,T(yfg))=0. 以此點(diǎn)為回溯起始點(diǎn)，通過(guò)(6)式反向迭代尋找當(dāng)前點(diǎn)前一時(shí)間步長(zhǎng)的零水平集中的對(duì)應(yīng)點(diǎn)，直至起始點(diǎn)，從而得到一條從ys到y(tǒng)fg的時(shí)間最優(yōu)路徑；然后，從T(yfg)時(shí)刻的水平集繼續(xù)迭代演化，每至一終點(diǎn)yfh(h≠g)就通過(guò)回溯找到一條最優(yōu)路徑，直至找到起點(diǎn)到所有終點(diǎn)的最優(yōu)路徑集，算法終止。

2.4 基于P-DRLLSM的AUV多終點(diǎn)航路規(guī)劃實(shí)現(xiàn)

基于P-DRLLSM的AUV多終點(diǎn)航路規(guī)劃實(shí)現(xiàn)步驟如下：

1)初始化水平集函數(shù)為符號(hào)距離函數(shù)，并將AUV航行起點(diǎn)ys置于零水平集上。設(shè)置AUV的航行速度FAUV、柵格間距Δx和Δy以及迭代時(shí)間步長(zhǎng)；設(shè)置m個(gè)終點(diǎn)yfg，g∈N+且g≤m；設(shè)置航路計(jì)數(shù)器f=0，每找到一條最優(yōu)航路，則f++.

2)構(gòu)建考慮海流影響的AUV航路規(guī)劃局部水平集方程(15)式，海流速度由(20)式給出，其中3個(gè)渦流中心位置隨機(jī)生成。設(shè)置障礙物、環(huán)境威脅、敵對(duì)威脅區(qū)域，將其全部設(shè)為禁航區(qū)，這些區(qū)域內(nèi)海流速度均設(shè)為0 m/s，且當(dāng)水平集方程演化到這些區(qū)域時(shí)，AUV的速度也設(shè)為0 m/s. 從而達(dá)到自動(dòng)避開(kāi)禁航區(qū)的目的。

3)加入P-DRE項(xiàng)，形成P-DRLLSM方程(17)式，依據(jù)此方程的離散形式(25)式，在局部區(qū)域內(nèi)沿著零水平集的梯度方向和海流速度的合方向演化水平集函數(shù)。每次演化時(shí)新加入局部區(qū)域外圍的點(diǎn)的水平集函數(shù)值采用最鄰近插值法求得。演化過(guò)程中存儲(chǔ)每個(gè)時(shí)間步長(zhǎng)的零水平集界面。

4)判斷終點(diǎn)集中是否有終點(diǎn)已落入局部水平集的區(qū)域內(nèi)。如果有，則檢測(cè)新的零水平集界面是否到達(dá)終點(diǎn)，如果未到達(dá)終點(diǎn)，則返回步驟3，否則轉(zhuǎn)步驟5.

5)后向位置回溯，尋找最優(yōu)路徑。一旦零水平集到達(dá)某一終點(diǎn)yfg，則將該終點(diǎn)作為初始點(diǎn)；初始時(shí)間t=0 s，通過(guò)不斷求解方程(6)式，直至在起點(diǎn)ys處收斂，從而獲得一條AUV從起點(diǎn)到終點(diǎn)Yfg的時(shí)間最優(yōu)航路。存儲(chǔ)該航路，航路計(jì)數(shù)器f=f+1. 若f

新算法總流程如圖8所示。

圖8 P-DRLLSM流程圖Fig.8 Flow chart of P-DRLLSM

3 實(shí)驗(yàn)結(jié)果與分析

為檢驗(yàn)本文所提新算法的性能，分別在模擬海流和真實(shí)海流環(huán)境下進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)平臺(tái)采用數(shù)學(xué)仿真軟件MATLAB R2016a，在Intel Xeon(R)CPU E3-1505M主頻3.0 GHz計(jì)算機(jī)上進(jìn)行仿真。

3.1 模擬海流下的仿真實(shí)驗(yàn)

3.1.1 二維環(huán)境下的仿真實(shí)驗(yàn)

仿真環(huán)境設(shè)定如下：AUV航行空間為二維笛卡爾坐標(biāo)系下的離散柵格空間，大小為100 m×100 m，柵格間距1 m. 海流由(20)式給出，由3個(gè)位置隨機(jī)生成的渦流和定常流構(gòu)成，其中每個(gè)渦流強(qiáng)度κ和半徑ξ的值分別從5～10和3～6中隨機(jī)選?。欢ǔＡ魉俣?.2 m/s，航向60°. AUV速度2.5 m/s.

本文提出的P-DRLLSM算法中，μ為0.5，Δx、Δy均為1 m. 局部化方程(8)式中，γ、β分別設(shè)為4和2. 初始化零水平集函數(shù)為以起點(diǎn)為圓心、以2 m為半徑的圓。量子粒子群算法參照文獻(xiàn)[18-19]、蟻群算法參照文獻(xiàn)[20-21]開(kāi)展仿真實(shí)驗(yàn)。單終點(diǎn)時(shí)，起點(diǎn)坐標(biāo)為(10 m，15 m)，終點(diǎn)坐標(biāo)為(65 m，75 m)。本文算法規(guī)劃結(jié)果如圖9所示。

從圖9中可以看出，采用本文所提P-DRLLSM算法進(jìn)行規(guī)劃時(shí)，AUV盡可能地“騎”著海流航行至終點(diǎn)，且都能避開(kāi)障礙物和威脅區(qū)。規(guī)劃用時(shí)為2.02 s，航行長(zhǎng)度為83.55 m，航行時(shí)長(zhǎng)為29.86 s. 單終點(diǎn)時(shí)，3種算法的規(guī)劃結(jié)果對(duì)比如圖10所示。

圖9 二維模擬環(huán)境中的單終點(diǎn)航路規(guī)劃Fig.9 Route planning with single deatination in 2D simulated ocean

圖10 二維模擬環(huán)境中單終點(diǎn)航路規(guī)劃對(duì)比Fig.10 Comparison of single deatination route plannings in 2D simulated ocean

仿真環(huán)境不變對(duì)3種算法分別進(jìn)行100次航路規(guī)劃，對(duì)規(guī)劃時(shí)間、航行時(shí)長(zhǎng)和航行長(zhǎng)度取平均，得到數(shù)據(jù)如表1所示。

表1 二維模擬環(huán)境中單終點(diǎn)時(shí)算法性能比較Tab.1 Comparison of the single destination route planning performances of the algorithms in 2D simulated ocean

從表1中可以看出：本文算法規(guī)劃用時(shí)最短，且遠(yuǎn)低于量子粒子群算法的規(guī)劃用時(shí)，蟻群算法規(guī)劃速度最慢；航行時(shí)長(zhǎng)決定算法求得的最優(yōu)航路質(zhì)量，航路質(zhì)量性能基本相當(dāng)，本文算法規(guī)劃的航路質(zhì)量最高，量子粒子群算法次之，蟻群算法最差；在航路長(zhǎng)度方面，本文算法規(guī)劃的最短，量子粒子群算法次之，蟻群算法最長(zhǎng)。綜上所述可知，本文提出的P-DRLLSM算法在二維模擬環(huán)境中，不僅計(jì)算效率很高，而且規(guī)劃的最優(yōu)航路質(zhì)量也最高。

單終點(diǎn)航路規(guī)劃時(shí)，3種算法分別規(guī)劃多次，圖11給出了算法的魯棒性對(duì)比情況。

圖11 3種算法多次規(guī)劃所得航路對(duì)比Fig.11 Comparison of planned routes of three algorithms

從圖11中可以看出，蟻群算法和量子粒子群算法幾乎每次規(guī)劃所得航路都不同，但本文算法每次規(guī)劃所得最優(yōu)航路不變，是唯一的，因此本文算法魯棒性要遠(yuǎn)好于蟻群算法和量子粒子群算法。

多終點(diǎn)時(shí)起點(diǎn)位置不變，終點(diǎn)分別為終點(diǎn)1：(40 m，80 m)，終點(diǎn)2(80 m，40 m)，終點(diǎn)3(70 m，70 m)，終點(diǎn)4(60 m，80 m)。3種算法規(guī)劃結(jié)果對(duì)比如圖12所示，AUV都能利用海流且避開(kāi)障礙物順利抵達(dá)終點(diǎn)。

圖12 二維模擬環(huán)境中多終點(diǎn)航路規(guī)劃對(duì)比Fig.12 Comparison of multi-deatination route plannings in 2D simulated ocean

對(duì)3種算法也分別進(jìn)行100次該條件下的航路規(guī)劃，對(duì)規(guī)劃時(shí)間、航行時(shí)長(zhǎng)和航行長(zhǎng)度取平均，得到數(shù)據(jù)如表2所示。

從表2中可以看出：與單終點(diǎn)時(shí)相比，航路質(zhì)量和航路長(zhǎng)度上變化不大，本文算法性能最好，量子粒子群算法次之，蟻群算法最差；從總規(guī)劃時(shí)間來(lái)看，由于本文算法無(wú)需重復(fù)調(diào)用計(jì)算周期，隨著終點(diǎn)數(shù)的增多，規(guī)劃時(shí)間變化不明顯，但蟻群算法和量子粒子群算法近乎成倍增加，變化劇烈。由此可見(jiàn)，在4個(gè)終點(diǎn)情況下，相比蟻群算法和量子粒子群算法，本文算法計(jì)算效率更高，是量子粒子群算法的約14倍、蟻群算法的約34倍。

表2 二維模擬環(huán)境中多終點(diǎn)時(shí)算法性能比較Tab.2 Comparison of the multi-deatination route planning performances of the algorithms in 2D simulated ocean

3.1.2 三維環(huán)境下的仿真實(shí)驗(yàn)

三維仿真環(huán)境設(shè)定如下：以電子海圖東經(jīng)121°30′、北緯20°為坐標(biāo)原點(diǎn)，以經(jīng)度增加方向?yàn)閄軸正方向，維度增加方向?yàn)閅軸正方向，水深增加方向?yàn)閆軸負(fù)方向建立三維規(guī)劃空間坐標(biāo)系，范圍為0～-100 m. 空間柵格化為100×100×100，X軸、Y軸網(wǎng)格間距為0.03°，Z軸網(wǎng)格間距為1 m.

海底地形建模：取東經(jīng)121°30′至東經(jīng)124°30′、北緯20°至北緯23°區(qū)域的水深數(shù)據(jù)，經(jīng)插值后生成規(guī)劃空間。

模擬三維海流由(20)式生成，渦流位置隨機(jī)生成，渦流強(qiáng)度與半徑、AUV速度與定常流速度設(shè)置與3.1.1節(jié)中相同，不同的是渦流有了豎直方向的速度分量。本文算法、蟻群算法、量子粒子群算法的參數(shù)設(shè)置與3.1.1節(jié)中的相同。

單終點(diǎn)時(shí)，起點(diǎn)坐標(biāo)為(122°3′E，21°30′N(xiāo)，-50 m)、終點(diǎn)坐標(biāo)為(123°39′36″E，22°24′N(xiāo)，-40 m)下3種算法規(guī)劃結(jié)果對(duì)比如圖13所示。圖13中，紅色圓柱為經(jīng)過(guò)規(guī)整、膨脹處理后的敵方探測(cè)威脅區(qū)，紅色長(zhǎng)方體為處理后的障礙物或環(huán)境威脅區(qū)。

圖13 三維模擬環(huán)境中單終點(diǎn)航路規(guī)劃對(duì)比Fig.13 Comparison of single destination route plannings in 3D simulated ocean

從圖13可以看出，在模擬環(huán)境下的單終點(diǎn)航路規(guī)劃時(shí)，3種算法都能在避開(kāi)障礙物和威脅區(qū)的情況下找到時(shí)間最優(yōu)的安全航路。對(duì)3種算法分別進(jìn)行100次航路規(guī)劃，對(duì)規(guī)劃時(shí)間、航行時(shí)長(zhǎng)和航行長(zhǎng)度取平均，得到如表3所示的數(shù)據(jù)。

表3 三維模擬環(huán)境中單終點(diǎn)航路規(guī)劃時(shí)算法 性能比較Tab.3 Comparison of the single destination route planning performances of the algorithms in 3D simulated ocean

從表3中可知，與二維模擬環(huán)境中所得結(jié)論相同，本文算法在規(guī)劃時(shí)間和所求航路質(zhì)量上最佳，量子粒子群算法次之，蟻群算法最差。

多終點(diǎn)時(shí)，起點(diǎn)坐標(biāo)不變，起點(diǎn)坐標(biāo)為(122°3′E，21°30′N(xiāo)，-40 m)，共設(shè)4個(gè)終點(diǎn)，各終點(diǎn)坐標(biāo)分別為終點(diǎn)1(123°39′36″E，22°24′36″N，-45 m)、終點(diǎn)2(123°54′E，22°12′30″N，-30 m)、終點(diǎn)3(122°24′E，22°24′N(xiāo)，-40 m)、終點(diǎn)4(123°54′E，21°54′30″N，-25 m)。規(guī)劃結(jié)果對(duì)比如圖14所示。

從圖14中可以看出，模擬環(huán)境下的多終點(diǎn)航路規(guī)劃時(shí)，3種算法都能在避開(kāi)障礙物和威脅區(qū)情況下找到至各個(gè)終點(diǎn)時(shí)間最優(yōu)的安全航路集。對(duì)3種算法分別進(jìn)行100次航路規(guī)劃，對(duì)規(guī)劃時(shí)間、航行時(shí)長(zhǎng)和航行長(zhǎng)度取平均，得到數(shù)據(jù)如表4所示。

圖14 三維模擬環(huán)境中多終點(diǎn)航路規(guī)劃對(duì)比Fig.14 Comparison of multi-destination route plannings in 3D simulated ocean

表4 三維模擬環(huán)境中多終點(diǎn)航路規(guī)劃時(shí)算法性能比較Tab.4 Comparison of the multi-destination route planning performances of the algorithms in 3D simulated ocean

從表4中可知：在三維模擬環(huán)境中進(jìn)行多終點(diǎn)的航路規(guī)劃時(shí)，本文算法的規(guī)劃時(shí)間和所求航路質(zhì)量仍然最佳；蟻群算法所求最優(yōu)航路質(zhì)量性能要稍?xún)?yōu)于量子粒子群算法；計(jì)算效率方面，量子粒子群算法要優(yōu)于蟻群算法。

3.2 真實(shí)海流下的仿真驗(yàn)證

為了驗(yàn)證本文算法在真實(shí)環(huán)境下的性能，在3.1.2節(jié)三維規(guī)劃空間建模基礎(chǔ)上，將模擬海流替換成真實(shí)三維海流，從某海流分析系統(tǒng)中提取出東經(jīng)121°30′至東經(jīng)124°30′、北緯20°至北緯23°范圍某一時(shí)間區(qū)間的真實(shí)海流數(shù)據(jù)文件，此范圍的海流速度范圍為0～0.7 m/s，平均海流速率為0.5 m/s.

單一終點(diǎn)的航路規(guī)劃實(shí)驗(yàn)中，AUV速度為1.5 m/s，起點(diǎn)設(shè)為：123°39′36″E，21°48′N(xiāo)，-40 m；終點(diǎn)為：122°15′E，20°15′N(xiāo)，-50 m. 本文算法的規(guī)劃結(jié)果如圖15所示。

圖15 真實(shí)海流中單終點(diǎn)三維航路規(guī)劃Fig.15 3D single deatination route planning in real ocean current

圖15中紅色長(zhǎng)方體為經(jīng)過(guò)規(guī)整、膨脹處理后的障礙物區(qū)，紅色圓柱體為經(jīng)過(guò)處理后的敵對(duì)探測(cè)威脅區(qū)。從圖15中可以看出：AUV能夠順流航行且能夠很好地避開(kāi)障礙物和威脅區(qū)，以最優(yōu)時(shí)間到達(dá)終點(diǎn)；算法規(guī)劃用時(shí)18.89 s，航行長(zhǎng)度為165 km，航行時(shí)長(zhǎng)33.34 h.

真實(shí)海流環(huán)境下單一終點(diǎn)航路規(guī)劃時(shí)，本文算法與量子粒子群算法及蟻群算法規(guī)劃結(jié)果對(duì)比如圖16所示。

圖16 實(shí)際環(huán)境中單終點(diǎn)航路規(guī)劃對(duì)比Fig.16 Comparison of single destination route plannings in real ocean

對(duì)3種算法分別進(jìn)行100次航路規(guī)劃，對(duì)規(guī)劃時(shí)間、航行時(shí)長(zhǎng)和航行長(zhǎng)度取平均，得到數(shù)據(jù)如表5所示。

表5 真實(shí)海流中單終點(diǎn)航路規(guī)劃時(shí)算法 性能比較Tab.5 Comparison of the single destination route planning performances of the algorithms in real ocean current

從表5中可以看出，在單終點(diǎn)航路規(guī)劃時(shí)，本文算法與蟻群算法和粒子群算法的規(guī)劃時(shí)間、航行時(shí)間和航行長(zhǎng)度雖然都在一個(gè)數(shù)量級(jí)上，但是本文算法規(guī)劃時(shí)間和航行時(shí)間均最短，說(shuō)明本文算法單終點(diǎn)航路規(guī)劃時(shí)的計(jì)算效率與所求最優(yōu)航路質(zhì)量均優(yōu)于蟻群算法和粒子群算法。

單終點(diǎn)航路規(guī)劃時(shí)，對(duì)3種算法分別規(guī)劃3次，各得到真實(shí)海流環(huán)境下的3條航路，航路性能數(shù)據(jù)對(duì)比如表6所示。

從表6中可以看出，蟻群算法和量子粒子群算法幾乎每次規(guī)劃所得航路都不同，但本文算法每次規(guī)劃所得最優(yōu)航路不變，是唯一的，因此在真實(shí)海流環(huán)境下，本文算法魯棒性也遠(yuǎn)好于蟻群算法和量子粒子群算法。

表6 3種算法多次規(guī)劃所得航路對(duì)比Tab.6 Comparison of routes in multi-planning by three algorithms

多終點(diǎn)航路規(guī)劃時(shí)，起點(diǎn)坐標(biāo)為(124°12′E，21°39′N(xiāo)，-40 m)，共設(shè)4個(gè)終點(diǎn)，各終點(diǎn)坐標(biāo)分別為終點(diǎn)1(123°54′E，20°18′N(xiāo)，-50 m)、終點(diǎn)2(123°27′E，20°27′N(xiāo)，-30 m)、終點(diǎn)3(122°51′E，20°54′N(xiāo)，-30 m)、終點(diǎn)4(123°36′E，21°42′36″N，-50 m)。3種算法的航路規(guī)劃結(jié)果如圖17所示。

圖17 實(shí)際環(huán)境中多終點(diǎn)航路規(guī)劃對(duì)比Fig.17 Comparison of multi-destination route planning in real ocean

多終點(diǎn)航路規(guī)劃時(shí)，對(duì)各個(gè)算法分別進(jìn)行100次航路規(guī)劃，對(duì)規(guī)劃時(shí)間、航行時(shí)長(zhǎng)和航行長(zhǎng)度取平均，得到如表7中所示數(shù)據(jù)。

表7 真實(shí)海流中多終點(diǎn)航路規(guī)劃時(shí)算法性能比較Tab.7 Comparison of the multi-destination route planning performances of the algorithms in real current

從表7中可看出：真實(shí)海流環(huán)境下的多終點(diǎn)航路規(guī)劃時(shí)，蟻群算法規(guī)劃的航行長(zhǎng)度最長(zhǎng)，量子粒子群算法和本文算法規(guī)劃航行長(zhǎng)度基本相當(dāng)；本文算法航行時(shí)間最短，量子粒子群算法次之，蟻群算法最長(zhǎng)；蟻群算法規(guī)劃時(shí)長(zhǎng)是量子粒子群算法的約1.6倍，是本文算法的約6.4倍。這也進(jìn)一步驗(yàn)證了前文中的理論分析，本文算法不僅所求航路質(zhì)量更優(yōu)，更為重要的是，隨著終點(diǎn)數(shù)增多，蟻群算法和量子粒子群算法總的規(guī)劃時(shí)間近乎成倍增長(zhǎng)，而本文算法總的規(guī)劃時(shí)間增加很慢，從單終點(diǎn)的18.89 s增加到4個(gè)終點(diǎn)的21.8 s. 由此可見(jiàn)，不論模擬海流環(huán)境下還是真實(shí)海流環(huán)境下，在多終點(diǎn)航路規(guī)劃中，終點(diǎn)數(shù)越多，相較于蟻群算法和量子粒子群算法，本文算法的計(jì)算效率越高，算法性能得到了進(jìn)一步驗(yàn)證。三維環(huán)境中的多次航路規(guī)劃也表明，本文算法魯棒性好于蟻群算法和量子粒子群算法。

4 結(jié)論

傳統(tǒng)的水平集算法用于航路規(guī)劃時(shí)需要周期性地重新初始化窄帶，導(dǎo)致規(guī)劃效率不高；典型的智能算法，如蟻群算法和量子粒子群算法進(jìn)行多終點(diǎn)的航路規(guī)劃時(shí)，只能通過(guò)反復(fù)調(diào)用算法的整個(gè)計(jì)算周期來(lái)實(shí)現(xiàn)，占用資源多、規(guī)劃時(shí)間長(zhǎng)。本文將傳統(tǒng)水平集函數(shù)局部化，引入P-DRE項(xiàng)，推導(dǎo)了新的離散迭代方程，省去了重新初始化過(guò)程，提高了水平集算法的計(jì)算效率；此外，多終點(diǎn)的多條最優(yōu)航路獲得是通過(guò)水平集函數(shù)的不斷演化、在一個(gè)計(jì)算周期中實(shí)現(xiàn)的，進(jìn)一步提高了多終點(diǎn)航路規(guī)劃的計(jì)算效率，且都能找到避開(kāi)障礙物和威脅區(qū)的最優(yōu)安全航路。仿真結(jié)果表明，同等條件下，相比于蟻群和量子粒子群算法，本文提出的新航路規(guī)劃算法尋優(yōu)質(zhì)量更高、規(guī)劃時(shí)間更少、魯棒性更好，尤其適用于多終點(diǎn)的多航路規(guī)劃場(chǎng)景。