周寅飛, 張立華,2*, 賈帥東,2, 戴澤源, 劉翔

(1.海軍大連艦艇學(xué)院 軍事海洋與測繪系, 遼寧 大連 116018;2.海軍大連艦艇學(xué)院 海洋測繪工程軍隊重點實驗室, 遼寧 大連 116018)

0 引言

水面艦艇具備良好的對潛探測和遂行打擊能力,是重要的反潛兵力[1]。區(qū)域搜潛是水面艦艇所擔(dān)負(fù)的搜潛任務(wù)之一,是指在一定時間和范圍內(nèi),為保護(hù)海軍港口、艦艇編隊等目標(biāo)不受敵方潛艇攻擊所進(jìn)行的作戰(zhàn)活動[2-3]。

搜潛航路規(guī)劃是水面艦艇進(jìn)行區(qū)域搜潛前需要進(jìn)行的基礎(chǔ)性工作[4],其規(guī)劃目標(biāo)是在最短時間內(nèi)完成對搜潛區(qū)域的全覆蓋搜索[5]。敵方潛艇力量一般在開闊海域出沒,為便于檢查搜潛的分析和實施,一般只考慮在開闊海域的規(guī)則矩形區(qū)域搜潛這種簡單情形,如圖1所示,并主要采用平行線式的航路進(jìn)行搜潛[5]。針對這種簡單情形,眾多學(xué)者結(jié)合聲吶的使用特性與搜索論,對搜潛航路布設(shè)的改進(jìn)方法進(jìn)行了諸多探索[6-10]。

隨著近年來海上形勢的逐漸加劇,不明潛艇力量出沒重要海峽、重要港口等復(fù)雜海域的次數(shù)急劇增多,面臨的水下威脅陡然增大,而規(guī)則矩形搜潛區(qū)難以對海峽、港口形成有效封鎖。因此,研究不規(guī)則區(qū)域的檢查搜潛,成為了一種急切的現(xiàn)實需求。

目前國內(nèi)外關(guān)于水面艦艇在不規(guī)則區(qū)域搜潛的航路自動規(guī)劃研究還相對較少,但不規(guī)則區(qū)域的無人測量船覆蓋路徑規(guī)劃研究已經(jīng)取得了較為豐碩的成果。當(dāng)前無人測量船覆蓋路徑規(guī)劃算法可主要分為兩類:

1)經(jīng)典算法。Pang等[11]采用隨機(jī)游走方法實現(xiàn)了區(qū)域覆蓋路徑規(guī)劃,并對搜索效率進(jìn)行了定量計算;基于混沌運(yùn)動原理,Sridharan等[12]規(guī)劃路徑實現(xiàn)了對作業(yè)區(qū)域的高效率覆蓋;Dong等[13]提出一種加權(quán)的生成樹算法來生成覆蓋掃描路徑,確保了搜索效率和算法魯棒性;Khan等[14]結(jié)合經(jīng)典的Boustrophedon方法,建立起覆蓋路徑規(guī)劃的優(yōu)化回溯機(jī)制,原理清晰且規(guī)劃效果較好。

2)啟發(fā)式算法。為實現(xiàn)無人船在水質(zhì)檢測點間的自主巡邏,Zhang等[15]提出一種改進(jìn)遺傳算法來實現(xiàn)全覆蓋路徑規(guī)劃;趙紅等[16]對原生物激勵神經(jīng)網(wǎng)絡(luò)算法進(jìn)行改進(jìn),有效實現(xiàn)了對無人船區(qū)域覆蓋路徑規(guī)劃;Xiong等[17]通過Voronoi圖劃分搜索區(qū),然后使用改進(jìn)蟻群優(yōu)化算法進(jìn)行無人船的覆蓋路徑規(guī)劃。

以上算法可基本實現(xiàn)對不規(guī)則復(fù)雜區(qū)域的覆蓋路徑規(guī)劃,但是,無人測量船測量作業(yè)與水面艦艇搜潛活動存在一定的區(qū)別:1)無人船轉(zhuǎn)向半徑較小且易于轉(zhuǎn)向,而水面艦艇轉(zhuǎn)向半徑較大且不易于轉(zhuǎn)向;2)無人船轉(zhuǎn)向?qū)y量設(shè)備工作影響較小,而水面艦艇轉(zhuǎn)向會對聲吶正常工作造成較大影響;3)無人船測量工作區(qū)域一般為沿岸或島礁區(qū),外部輪廓較為復(fù)雜,而在搜潛任務(wù)中的不規(guī)則搜潛區(qū)域大多情況下可以設(shè)定或分割為不規(guī)則凸區(qū)域。因此,其算法規(guī)劃出的路徑與水面艦艇搜潛需求存在不相配適的問題。無人測量船覆蓋路徑規(guī)劃算法很少顧及船舶轉(zhuǎn)向代價,并且由于該類算法主要關(guān)注于對不規(guī)則區(qū)域的分割和多區(qū)域間的遍歷,故針對凸區(qū)域規(guī)劃出的路徑可能并非最優(yōu)路徑。

綜上所述,如何綜合考慮水面艦艇轉(zhuǎn)向代價、為水面艦艇在不規(guī)則凸區(qū)域搜潛規(guī)劃出一條最短搜潛航路,尚且沒有針對性研究。

本文針對不規(guī)則凸區(qū)域的特殊性,分析論證搜潛航路總長度與轉(zhuǎn)向次數(shù)的線性關(guān)系,挖掘最優(yōu)搜潛航向與不規(guī)則凸區(qū)域邊界的內(nèi)在關(guān)聯(lián)規(guī)律,設(shè)計最優(yōu)搜潛航向的求取算法,提出最短搜潛航路自動規(guī)劃方法。

1 不規(guī)則凸區(qū)域的水面艦艇最短搜潛航路自動規(guī)劃

1.1 最短區(qū)域搜潛航路的長度計算模型

1.1.1 區(qū)域搜潛航路的構(gòu)成

水面艦艇進(jìn)行搜潛的示意圖如圖2所示,w為聲吶的有效探測寬度。由圖2可以看出,搜潛航路由有效搜潛航路(長度為Le)和轉(zhuǎn)向調(diào)整航線(長度為Lt)兩部分組成,且航線總長度L為

L=Le+Lt

(1)

圖2 水面艦艇搜潛示意圖Fig.2 Schematic diagram of surface warship submarine search

1.1.2 有效搜潛航路的長度求解

艦船在轉(zhuǎn)向調(diào)整過程中搜潛能力較弱。水面艦艇搜潛主要使用艦殼聲吶和拖曳聲吶等主被動搜潛設(shè)備,利用聲波對水下目標(biāo)進(jìn)行探測。然而,很多干擾因素都會對聲吶正常工作造成影響,艦艇的轉(zhuǎn)向就是其中之一[18-19]。艦艇大幅轉(zhuǎn)向產(chǎn)生的自噪聲會嚴(yán)重影響艦殼聲吶的目標(biāo)識別與定位;且轉(zhuǎn)向時會造成拖曳聲吶陣列的陣型畸變,對拖曳聲吶探測能力產(chǎn)生較大的衰弱[20-21]。水面艦艇的轉(zhuǎn)向半徑也相對較大,使得轉(zhuǎn)向的時間較長,而聲吶在該過程中持續(xù)地受到干擾,會嚴(yán)重削弱艦艇的搜潛能力。因為轉(zhuǎn)向?qū)λ褲搸砹酥T多的不良影響,故在進(jìn)行區(qū)域搜潛的過程中,轉(zhuǎn)向調(diào)整航線不計入有效搜潛航路。

根據(jù)區(qū)域搜潛的戰(zhàn)術(shù)目標(biāo)要求,水面艦艇的有效搜潛航路應(yīng)實現(xiàn)對搜潛區(qū)域的全覆蓋搜索。故設(shè)搜潛區(qū)域面積為S,有

S=Lew

(2)

則可得

(3)

對于一個確定的搜潛區(qū)域,其搜索面積S為定值;對于某型聲吶而言,其有效探測寬度w也可以視為定值。由此可以推斷出:在一個確定的區(qū)域內(nèi),無論以怎樣的方式進(jìn)行搜潛,其有效搜潛航路的長度Le是一定的。

1.1.3 轉(zhuǎn)向調(diào)整航線的長度求解

由式(1)可知,航線總長度L為有效搜潛航路長度Le和轉(zhuǎn)向調(diào)整航線長度Lt之和,由式(3)可知,有效搜潛航路的長度Le為定值,則可以推導(dǎo)出:在不規(guī)則凸區(qū)域內(nèi),檢查搜潛的最短航線為轉(zhuǎn)向調(diào)整航線長度Lt最小的航線。

在搜潛過程中,轉(zhuǎn)向調(diào)整航線是為了指引艦船進(jìn)行轉(zhuǎn)向調(diào)整,因此轉(zhuǎn)向調(diào)整航線的長度Lt與轉(zhuǎn)向次數(shù)x具有線性關(guān)系:

Lt=ltx

(4)

式中:lt為每次的轉(zhuǎn)向代價?？捎墒?4)推導(dǎo)出,若使轉(zhuǎn)向次數(shù)x最小,即可使轉(zhuǎn)向調(diào)整航線長度Lt最短,進(jìn)而使搜潛航路總長度L最短。

為求取總的轉(zhuǎn)向調(diào)整航線長度Lt,在轉(zhuǎn)向次數(shù)x確定后,需求解每次轉(zhuǎn)向的代價lt。艦船在轉(zhuǎn)向過程中會降速而導(dǎo)致航行時間增加,可以將增加的時間轉(zhuǎn)換為等效航程,并作為轉(zhuǎn)向代價。轉(zhuǎn)向半徑相對與聲吶有效作用范圍而言較大,在現(xiàn)有聲吶裝備條件下,難以進(jìn)行忽略,且是計算轉(zhuǎn)向代價的重要參數(shù)。根據(jù)文獻(xiàn)[22],定常回轉(zhuǎn)階段艦船的航速v與直航航速v0之比為

(5)

式中:K′為旋回性指數(shù);Cn為舵的法向力系數(shù);θ為轉(zhuǎn)向角。進(jìn)而可根據(jù)文獻(xiàn)[23-24],求得轉(zhuǎn)向代價:

(6)

式中:R為轉(zhuǎn)向半徑。

1.1.4 最短搜潛航路的長度計算模型

綜合式(1)、式(4),可得

L=Le+ltx

(7)

由式(3)已經(jīng)證明得到,在同一個區(qū)域內(nèi),有效搜潛航路Le是定值,因此,可由式(7)證明得到航線總長度L與轉(zhuǎn)向次數(shù)x存在線性關(guān)系,可進(jìn)一步得到最短搜潛航路Lmin的數(shù)學(xué)模型:

Lmin=Le+ltxmin

(8)

式中:xmin為最小轉(zhuǎn)向次數(shù)。

由式(8)可知,轉(zhuǎn)向次數(shù)最少可使搜潛航路總長度最短,且轉(zhuǎn)向次數(shù)最少的航向為最優(yōu)搜潛航向。

1.2 最優(yōu)搜潛航向的求解算法

1.2.1 搜潛航向確定的轉(zhuǎn)向次數(shù)求取

對一個固定的搜潛區(qū)域而言,假設(shè)搜潛航向確定,該區(qū)域可與搜潛航向平行的兩條直線相切,如圖3 所示。設(shè)兩平行直線的垂直距離ds為搜潛帶整體的寬度,則該航向?qū)?yīng)的轉(zhuǎn)向次數(shù)x為

x=ds/w

(9)

圖3 搜潛帶示意圖Fig.3 Diagram of the search zone

水面艦艇的聲吶有效作用距離在戰(zhàn)術(shù)問題研究中根據(jù)可設(shè)為常數(shù),聲吶的有效探測寬度w也可根據(jù)聲吶參數(shù)設(shè)置為常數(shù)。因此可以從式(9)推導(dǎo)出,若想轉(zhuǎn)向次數(shù)最小,則需選擇合理的航線方向,使得在該航向上,搜潛帶整體的寬度ds最窄。

1.2.2 具有最少轉(zhuǎn)向次數(shù)的搜潛航向選取

在區(qū)域搜潛任務(wù)中,搜潛帶需實現(xiàn)對搜潛區(qū)域的全覆蓋,則可從圖3看出,對于一個凸區(qū)域,搜潛帶邊界必過凸區(qū)域的某頂點。在經(jīng)過某頂點的搜潛帶中,搜潛航向與凸區(qū)域邊界平行時寬度最窄,分析論證如下:

1)過指定點做任意方向的搜潛帶和與凸區(qū)域邊界平行的搜潛帶。其基本步驟為:首先,在最優(yōu)搜潛航路方向選取示意圖(見圖4)中,設(shè)定搜潛凸區(qū)域;然后在凸區(qū)域上做一個任意方向搜索帶,并將其逆時針旋轉(zhuǎn)至與凸區(qū)域邊平行,如圖4(a)所示;最后,在凸區(qū)域上做一個任意方向搜索帶,并將其順時針旋轉(zhuǎn)至與凸區(qū)域邊平行,如圖4(b)所示。過凸區(qū)域頂點P4做一個任意方向(設(shè)該方向為方向1)的搜潛帶,如圖4(a)、圖4(b)所示。在圖4(a)中,該搜潛帶逆時針旋轉(zhuǎn)直至與直線P1P2平行,如圖4(a)所示,設(shè)該方向為方向2,可以看出,P4是凸多邊形頂點中離直線P1P2垂直距離最遠(yuǎn)的點;在圖4(b)中,搜潛帶順時針旋轉(zhuǎn)直至與直線P3P4平行,如圖4(b)所示,設(shè)該方向為方向3,可以看出,P1是凸多邊形中離直線P4P3垂直距離最遠(yuǎn)的點。

2)搜潛帶寬度的比較。在圖4(a)中,過P4向兩條搜潛帶分別做垂線,可以得到方向1搜潛帶的寬度為P4V2,其與凸區(qū)域邊界P1P2相交于點V2,方向2搜潛帶的寬度為P4V1;在圖4(b)中,過P1向兩條搜潛帶分別做垂線,可以得到方向1搜潛帶的寬度為P1I2,其與凸區(qū)域邊界PaP4相交于點I1,方向3搜潛帶的寬度為P1I3。由圖4(a)三角形P4V1V3、圖4(b)三角形P1IaI1斜邊和直角邊的長度關(guān)系,可得

(10)

圖4 最優(yōu)搜潛航路方向選取示意圖Fig.4 Schematic diagram of optimal search route direction selection

由式(10)可知,方向1搜潛帶的寬度比方向2、方向3搜潛帶的寬度都要長。

通過上述證明過程可得,最窄搜潛帶必然與凸區(qū)域的某條邊平行。

根據(jù)此結(jié)論,可通過以下步驟找到最窄搜潛帶,進(jìn)而得到搜潛帶所對應(yīng)的最優(yōu)搜潛航向:

步驟1以凸區(qū)域邊P1P2作為起始遍歷邊,比較各頂點到P1P2的垂直距離,因搜潛帶需實現(xiàn)對區(qū)域的全覆蓋,故需找到距離邊P1P2最遠(yuǎn)的頂點P4。

步驟2記錄P4到邊P1P2的垂直距離,作為邊P1P2所對應(yīng)的最窄搜潛帶寬度。

步驟3遍歷凸區(qū)域的所有邊,重復(fù)步驟1～步驟3,直至完成對凸區(qū)域所有邊的遍歷。

步驟4比較各邊所對應(yīng)的最窄搜潛帶寬度,在其中選擇最窄的作為凸區(qū)域整體的最窄搜潛帶寬度,整體最窄搜潛帶對應(yīng)的邊的方向為最優(yōu)搜潛航路方向。

1.3 最短搜潛航路自動規(guī)劃的實現(xiàn)

在1.1節(jié)中,證明了轉(zhuǎn)向次數(shù)最少可使搜潛航路總長度最短,且轉(zhuǎn)向次數(shù)最少的航向為最優(yōu)搜潛航向;在1.2.1節(jié)中,提出最優(yōu)搜潛航向的求解算法。在此基礎(chǔ)上,基于貪婪思想,進(jìn)一步實現(xiàn)最短搜潛航路的自動規(guī)劃。

1.3.1 基于空間拓?fù)浞椒ㄇ蠼庥行褲摵铰?/p>

最優(yōu)搜潛方向是有效搜潛航路的方向,因此可沿1.2節(jié)算法求得的最優(yōu)搜潛航路方向,以搜潛帶寬度w為間隔做直線,如圖5(a)所示,可用搜潛區(qū)域?qū)λ芍本€進(jìn)行拓?fù)洳眉暨\(yùn)算,得到區(qū)域內(nèi)的有效搜潛航路P1P2、P3P4、P5P6、P7P8。

圖5 基于優(yōu)化算法的最短搜潛航路自動生成示意圖Fig.5 Automatic generation schematic diagram of shortest underwater searching route based on optimization algorithm

1.3.2 基于貪婪思想的航線自動生成

基于貪婪思想的自動生成方法主要分為4步:

1)搜索得到離水面艦艇所在位置距離最近的搜潛航路上的點,作為搜潛起始點;

2)計算得到各搜潛航路點Pi、Pj兩兩間的距離lij,生成航路點距離表,如表1所示;

3)為使得后續(xù)算法能夠優(yōu)先遍歷未通過的有效搜潛航路,在此人為設(shè)定有效搜潛航路的距離為虛擬值0;

4)基于貪婪思想進(jìn)行最短搜潛航路的自動生成,即不斷搜索距離當(dāng)前航路點最近且未遍歷過的航路點,作為下一個航行的航路點,并且將遍歷過的航路點設(shè)置為不可搜索的航路點,直至遍歷完所有的搜潛航路點。

具體過程為:首先,從起點位置P2出發(fā)搜尋距離最近的點,由表1得知,P1點與P2的距離為0 m,因此選擇接下來通過P1P2到達(dá)P1位置,如圖5(c)所示,并將P1、P2點設(shè)置為不可搜索的點;然后,從P1點出發(fā),搜尋得到未通過且距離最近的航路點P3,如圖5(d)所示;隨后從P3出發(fā),由表1得知P3點與P4的距離為0 m,則選擇通過P3P4到達(dá)P4位置,如圖5(e)所示,并將P3、P4設(shè)置為不可搜索的點。不斷按上述過程進(jìn)行航線生成,直至完成對所有搜潛航路點的遍歷,最終得到的最短搜潛航路為圖5(f)所示藍(lán)色虛線。

表1 搜潛航路點距離Table 1 Distance between waypoints in submarine search

2 實驗與分析

為驗證本文所提最短搜潛航路自動規(guī)劃方法的有效性,在實驗1中,分別通過本文方法與經(jīng)典的Boustrophedon方法[14]生成航路進(jìn)行對比,以驗證本文方法相較于現(xiàn)有方法,更適用于水面艦艇區(qū)域搜潛航路的規(guī)劃;在實驗2中,將本文方法生成的搜潛航路,與以1°為最小分割角度遍歷得到的搜潛航路進(jìn)行對比,以驗證本文方法規(guī)劃出的搜潛航路具備全局最優(yōu)性。

2.1 實驗1

本實驗選取某海峽附近海域進(jìn)行實驗,假設(shè)潛艇可能在30 m以上水深的海域活動,艦艇搜潛的有效搜潛帶寬度為500 m,可根據(jù)該水道的30 m等深線設(shè)定搜潛區(qū)域,如圖6(a)所示;通過Boustrophedon方法生成的航路如圖6(b)所示;通過本文方法生成的搜潛航路如圖6(c)所示。兩種方法所規(guī)劃航路的長度、轉(zhuǎn)向次數(shù)以及對搜潛區(qū)域的覆蓋率統(tǒng)計如表2所示。

圖6 對比方法實驗結(jié)果示意圖Fig.6 Schematic diagram of comparison method results

從圖6(b)中可以看到:Boustrophedon方法在凸區(qū)域中生成的航線是與坐標(biāo)軸方向平行的,并不具備顧及不規(guī)則凸區(qū)域的形狀與艦船轉(zhuǎn)向代價,自適應(yīng)生成最優(yōu)搜潛航線的功能;本文方法生成的航路能夠根據(jù)不規(guī)則凸區(qū)域的具體形狀選擇最優(yōu)搜潛航線方向,進(jìn)而生成最短搜潛航路。從表2對比數(shù)據(jù)中可以看出,本文方法生成的航路總長度、轉(zhuǎn)向次數(shù)比Boustrophedon方法生成的航路更短,且有效覆蓋率更高。

2.2 實驗2

本實驗選取某港附近海域進(jìn)行實驗,進(jìn)出該港的水道水深基本在35 m以上,潛艇在此坐底后,魚雷打擊范圍可覆蓋該水道,能夠?qū)M(jìn)出的艦船造成極大威脅。

假設(shè)潛艇可能在30 m以上水深的海域活動,艦艇搜潛的有效搜潛帶寬度為500 m,可根據(jù)水道的30 m等深線,設(shè)定搜潛區(qū)域如圖7(a)所示,通過本文最短搜潛航路自動規(guī)劃方法生成的搜潛航路如圖7(b)所示,所對應(yīng)的航路總長度、轉(zhuǎn)向次數(shù)和對搜潛區(qū)域的覆蓋率如表3所示。為驗證采用本文方法生成的搜潛航路總長度最短,對0°～180°的搜潛航向以1°為最小分割角度遍歷得到對比搜潛航路,并將每5°的搜潛航路長度、轉(zhuǎn)向次數(shù)以及對搜潛區(qū)域的覆蓋率統(tǒng)計到表3中。

表2 對比方法搜潛航路實驗數(shù)據(jù)統(tǒng)計Table 2 Statistical table of experimental data of comparison methods

從表3的統(tǒng)計數(shù)據(jù)中可以看出:最短搜潛航路的搜潛航向是60.39°,遍歷得到的航路從0°/180°的搜潛方向開始,方向越接近最優(yōu)搜潛航向,其航線總長度越小;遍歷得到的航路從搜潛航向大于60.39°的方向開始,隨著與該方向夾角的增大,其航路總長度逐漸增大;搜潛航路總長度與轉(zhuǎn)向次數(shù)存在相關(guān)性,轉(zhuǎn)向次數(shù)越多,搜潛航路總長度越長。

圖7 搜潛區(qū)域與最優(yōu)搜潛航路實驗結(jié)果Fig.7 Experimental results of search area and optimal search route

表3 搜潛航路實驗數(shù)據(jù)統(tǒng)計

實驗結(jié)果表明,通過本文最短搜潛航路自動規(guī)劃方法求得的搜潛航路具備全局最優(yōu)性,其搜潛方向是最優(yōu)搜潛方向,航路總長度最短。同時,從表3中可以看出,搜潛航路對搜潛區(qū)域的有效覆蓋率基本達(dá)到了99.5%以上,能夠滿足水面艦艇復(fù)雜區(qū)域檢查搜潛應(yīng)基本不存在盲區(qū)的戰(zhàn)術(shù)要求。

3 結(jié)論

本文通過經(jīng)理論推導(dǎo)和實驗對比分析,對不規(guī)則凸區(qū)域的水面艦艇最短搜潛航路自動規(guī)劃進(jìn)行了研究。得出以下主要結(jié)論:

1)搜潛航路總長度與轉(zhuǎn)向次數(shù)存在線性關(guān)系,轉(zhuǎn)向次數(shù)最少可使搜潛航路總長度最短,且轉(zhuǎn)向次數(shù)最少的航向為最優(yōu)搜潛航向。

2)最優(yōu)搜潛航向必然與凸區(qū)域的某條邊平行,故與凸區(qū)域邊平行的搜潛航向中,搜潛帶總體寬度最窄的即為最優(yōu)搜潛航向。

3)所提方法規(guī)劃出的搜潛航路,與通過遍歷方法所得到的各搜潛航路相比,總航程最短。

雖然本文方法對區(qū)域搜潛實際中最常見的凸區(qū)域搜潛最短航線自動生成方法進(jìn)行了研究,然而如何依據(jù)本文證得的結(jié)論,在搜潛區(qū)域為更復(fù)雜凹區(qū)域等情況下求解得到全局最優(yōu)解,還有待于下一步研究。