不規則凸區域的水面艦艇最短搜潛航路自動規劃

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

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

0 引言

水面艦艇具備良好的對潛探測和遂行打擊能力,是重要的反潛兵力[1]。區域搜潛是水面艦艇所擔負的搜潛任務之一,是指在一定時間和范圍內,為保護海軍港口、艦艇編隊等目標不受敵方潛艇攻擊所進行的作戰活動[2-3]。

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

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

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

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

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

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

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

本文針對不規則凸區域的特殊性,分析論證搜潛航路總長度與轉向次數的線性關系,挖掘最優搜潛航向與不規則凸區域邊界的內在關聯規律,設計最優搜潛航向的求取算法,提出最短搜潛航路自動規劃方法。

1 不規則凸區域的水面艦艇最短搜潛航路自動規劃

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

1.1.1 區域搜潛航路的構成

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

L=Le+Lt

(1)

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

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

艦船在轉向調整過程中搜潛能力較弱。水面艦艇搜潛主要使用艦殼聲吶和拖曳聲吶等主被動搜潛設備,利用聲波對水下目標進行探測。然而,很多干擾因素都會對聲吶正常工作造成影響,艦艇的轉向就是其中之一[18-19]。艦艇大幅轉向產生的自噪聲會嚴重影響艦殼聲吶的目標識別與定位;且轉向時會造成拖曳聲吶陣列的陣型畸變,對拖曳聲吶探測能力產生較大的衰弱[20-21]。水面艦艇的轉向半徑也相對較大,使得轉向的時間較長,而聲吶在該過程中持續地受到干擾,會嚴重削弱艦艇的搜潛能力。因為轉向對搜潛帶來了諸多的不良影響,故在進行區域搜潛的過程中,轉向調整航線不計入有效搜潛航路。

根據區域搜潛的戰術目標要求,水面艦艇的有效搜潛航路應實現對搜潛區域的全覆蓋搜索。故設搜潛區域面積為S,有

S=Lew

(2)

則可得

(3)

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

1.1.3 轉向調整航線的長度求解

由式(1)可知,航線總長度L為有效搜潛航路長度Le和轉向調整航線長度Lt之和,由式(3)可知,有效搜潛航路的長度Le為定值,則可以推導出:在不規則凸區域內,檢查搜潛的最短航線為轉向調整航線長度Lt最小的航線。

在搜潛過程中,轉向調整航線是為了指引艦船進行轉向調整,因此轉向調整航線的長度Lt與轉向次數x具有線性關系:

Lt=ltx

(4)

式中:lt為每次的轉向代價?？捎墒?4)推導出,若使轉向次數x最小,即可使轉向調整航線長度Lt最短,進而使搜潛航路總長度L最短。

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

(5)

式中:K′為旋回性指數;Cn為舵的法向力系數;θ為轉向角。進而可根據文獻[23-24],求得轉向代價:

(6)

式中:R為轉向半徑。

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

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

L=Le+ltx

(7)

由式(3)已經證明得到,在同一個區域內,有效搜潛航路Le是定值,因此,可由式(7)證明得到航線總長度L與轉向次數x存在線性關系,可進一步得到最短搜潛航路Lmin的數學模型:

Lmin=Le+ltxmin

(8)

式中:xmin為最小轉向次數。

由式(8)可知,轉向次數最少可使搜潛航路總長度最短,且轉向次數最少的航向為最優搜潛航向。

1.2 最優搜潛航向的求解算法

1.2.1 搜潛航向確定的轉向次數求取

對一個固定的搜潛區域而言,假設搜潛航向確定,該區域可與搜潛航向平行的兩條直線相切,如圖3 所示。設兩平行直線的垂直距離ds為搜潛帶整體的寬度,則該航向對應的轉向次數x為

x=ds/w

(9)

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

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

1.2.2 具有最少轉向次數的搜潛航向選取

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

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

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

(10)

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

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

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

根據此結論,可通過以下步驟找到最窄搜潛帶,進而得到搜潛帶所對應的最優搜潛航向:

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

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

步驟3遍歷凸區域的所有邊,重復步驟1～步驟3,直至完成對凸區域所有邊的遍歷。

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

1.3 最短搜潛航路自動規劃的實現

在1.1節中,證明了轉向次數最少可使搜潛航路總長度最短,且轉向次數最少的航向為最優搜潛航向;在1.2.1節中,提出最優搜潛航向的求解算法。在此基礎上,基于貪婪思想,進一步實現最短搜潛航路的自動規劃。

1.3.1 基于空間拓撲方法求解有效搜潛航路

最優搜潛方向是有效搜潛航路的方向,因此可沿1.2節算法求得的最優搜潛航路方向,以搜潛帶寬度w為間隔做直線,如圖5(a)所示,可用搜潛區域對所生成直線進行拓撲裁剪運算,得到區域內的有效搜潛航路P1P2、P3P4、P5P6、P7P8。

圖5 基于優化算法的最短搜潛航路自動生成示意圖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)為使得后續算法能夠優先遍歷未通過的有效搜潛航路,在此人為設定有效搜潛航路的距離為虛擬值0;

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

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

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

2 實驗與分析

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

2.1 實驗1

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

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

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

2.2 實驗2

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

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

表2 對比方法搜潛航路實驗數據統計Table 2 Statistical table of experimental data of comparison methods

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

圖7 搜潛區域與最優搜潛航路實驗結果Fig.7 Experimental results of search area and optimal search route

表3 搜潛航路實驗數據統計

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

3 結論

本文通過經理論推導和實驗對比分析,對不規則凸區域的水面艦艇最短搜潛航路自動規劃進行了研究。得出以下主要結論:

1)搜潛航路總長度與轉向次數存在線性關系,轉向次數最少可使搜潛航路總長度最短,且轉向次數最少的航向為最優搜潛航向。

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

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

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