復(fù)雜水域船舶避碰路徑規(guī)劃研究

謝新連，何 平，何 傲，辛劍英

(大連海事大學(xué) 綜合運輸研究所, 遼寧 大連 116026)

0 引 言

船舶避碰一直是航海領(lǐng)域的研究熱點，因為在運輸過程中一旦發(fā)生碰撞事故，高價值船舶及其運輸貨物均會遭受損失，且碰撞事故會對海洋環(huán)境造成巨大的污染。避碰路徑規(guī)劃研究是實施船舶避碰的一個關(guān)鍵環(huán)節(jié)，因此研究船舶避碰路徑極為重要。

船舶安全航行時需要避碰的目標(biāo)主要分為靜態(tài)障礙區(qū)和動態(tài)船舶。由于靜態(tài)障礙區(qū)避碰問題較為簡單，其研究相對較少，如：G.ANTONELLI等[1]介紹了一種具有實時路徑規(guī)劃并避開障礙物能力的航海誘導(dǎo)系統(tǒng)。目前，國內(nèi)外學(xué)者對船舶避碰路徑規(guī)劃的研究主要集中于動態(tài)目標(biāo)船舶上。如： CHANG Kiyin等[2]提出了一種能在柵格圖中檢測障礙物并進行障礙物規(guī)避的避碰路徑規(guī)劃算法；C.K.TAM等[3]利用已知的和預(yù)測得到的交通及環(huán)境數(shù)據(jù)，提出了一種近距離會遇船舶的路徑規(guī)劃算法；M.TSOU等[4]基于遺傳算法，結(jié)合《國際海上避碰規(guī)則》(以下簡稱《規(guī)則》)和船舶安全領(lǐng)域來求取最短避碰路徑，并提供了安全避碰轉(zhuǎn)彎角度、復(fù)航時機及復(fù)航角度等參數(shù)；W.NAEEM[5]等基于《規(guī)則》提出了一種反應(yīng)性的無人船避碰路徑規(guī)劃算法；XU Wen等[6]研究了在不考慮風(fēng)、浪、流等因素下，利用動態(tài)船舶對開闊海域上航行的兩艘船舶路徑進行規(guī)劃；C.TAM等[7]提出了一種滿足《規(guī)則》的確定性避碰路徑規(guī)劃算法；林曉杰[8]利用改進勢場法，結(jié)合船舶操縱及船舶領(lǐng)域等理論建立了受限水域中船舶的自動避碰模型；張樹凱[9]等基于AIS航跡和Douglas-Peucker 算法實現(xiàn)了航線的自動生成，其能有效避開障礙物。

不難發(fā)現(xiàn)，鮮有學(xué)者對靜態(tài)障礙區(qū)和動態(tài)目標(biāo)船舶同時存在的復(fù)雜水域內(nèi)船舶避碰路徑規(guī)劃問題進行研究。程細得等[10]用遺傳算法對內(nèi)河船舶及障礙區(qū)的避碰問題進行了分析；A.LAZAROWSKA[11]提出了一種基于蟻群算法的動態(tài)環(huán)境下避碰路徑規(guī)劃方法；M.TSOU[12]以ECDIS作為決策支持平臺，結(jié)合PAD理論和《規(guī)則》，用進化算法來進行避碰路徑規(guī)劃。另外，現(xiàn)有研究規(guī)劃出的避碰路徑大部分是折線段路徑，未考慮到船舶回轉(zhuǎn)性能，無法保證船舶一定能按照規(guī)劃出的路徑安全航行。因此，筆者針對礙航障礙區(qū)和目標(biāo)船舶同時存在的復(fù)雜水域避碰路徑規(guī)劃問題，在考慮《規(guī)則》前提下，利用預(yù)測危險區(qū)將目標(biāo)船避碰轉(zhuǎn)化為避讓一個六邊形區(qū)域(PAD)，再利用船舶領(lǐng)域理論對障礙區(qū)進行緩沖區(qū)分析，并用切線圖法對復(fù)雜水域進行環(huán)境建模，然后利用Dijkstra算法和改進的2-turn平滑方法進行了避碰路徑規(guī)劃。最后，通過仿真實驗及對比實驗予以驗證。

1 復(fù)雜水域環(huán)境模型構(gòu)建

1.1 復(fù)雜水域

復(fù)雜水域到目前為止仍沒有一個明確的定義，通常是指自然條件差、船舶交通流復(fù)雜、船舶航行難度大的水域，包括海上施工水域、橋區(qū)水域、多航道交匯水域、航道彎曲段、航道狹窄段、淺灘航行區(qū)、壩區(qū)航段、錨泊區(qū)、漁船捕魚水域、島礁水域等。文中的復(fù)雜水域是指多個靜態(tài)礙航障礙區(qū)和動態(tài)目標(biāo)船舶同時存在水域。靜態(tài)礙航區(qū)主要包括淺灘、暗礁、海島、錨泊區(qū)等；動態(tài)船舶是指在海上正常航行且可能會影響我船安全航行的船舶。筆者研究的水域中同時包括了多個固定礙航障礙區(qū)和船舶會遇局面，因此，其復(fù)雜性不言而喻。

1.2 預(yù)測危險區(qū)

在本船保速情況下，通過對我船和目標(biāo)船的航速、航向等進行預(yù)測處理，可得到可能碰撞點(PPC)的位置坐標(biāo)，并作為避碰的決策依據(jù)。雷達測量和ARPA的跟蹤處理往往存在誤差，此外船舶本身的船型和大小對航行安全不可忽視，僅僅用可能碰撞點進行避碰決策是遠遠不夠的。因此，在可能碰撞點基礎(chǔ)上結(jié)合MIN CPA作圖形成了預(yù)測危險區(qū)(PAD)，如圖1。在目標(biāo)船保速、保向情況下，只要我船航跡避開預(yù)測危險區(qū)即可安全避開目標(biāo)船。圖1中：我船某時刻的位置為O點，航速為VO；目標(biāo)船位置為T點，航速為VT；目標(biāo)船相對航速為VR；PAD為圖中的六邊形。圖2為基于MATLAB編程得到的PAD圖，其中：我船航速為12 kn，航向角330°；目標(biāo)船航速12 kn，航向角30°。

圖1 PAD示意Fig. 1 PAD schematic

圖2 預(yù)測危險區(qū)Fig. 2 Prediction of dangerous areas

1.3 緩沖區(qū)分析

由于船舶本身具有一定尺寸，且船舶正常航行需要滿足一定的水深條件，故船舶不可能完全沿著礙航障礙區(qū)邊界航行。此外，即使船舶能沿著礙航障礙區(qū)邊界航行，由于淺水效應(yīng)存在，反而會增大船舶與礙航障礙區(qū)發(fā)生碰撞的可能性。因此，為使船舶能安全地避開礙航障礙區(qū)，需對礙航障礙區(qū)進行一定的緩沖區(qū)分析。由于筆者未考慮風(fēng)、浪、流等影響因素，故以文獻[13]提出的船舶領(lǐng)域模型中的Rstarb長度作為基礎(chǔ)緩沖距離，計算如式(1)、(2)：

Rstarb=(0.2+KDT)×L

(1)

KDT=DT/L=100.544 1logV-0.079 5

(2)

式中：L為船長，m；KDT為旋回初徑對船長的無因次化；DT為船舶回轉(zhuǎn)直徑，m；V為航速，kn。

另外，當(dāng)船舶航行路徑經(jīng)過礙航障礙區(qū)之間水域時，船舶本身尺寸因素不可忽視。因此，筆者在Rstarb基礎(chǔ)上增加0.5倍船長作為緩沖區(qū)，如式(3)：

Rstarb=(0.7+KDT)×L

(3)

通過該處理，當(dāng)船舶在礙航障礙區(qū)之間水域通行時，由于對每個礙航障礙區(qū)進行緩沖區(qū)分析時增加了0.5船長，即相當(dāng)于對該水域增加了1倍船長緩沖區(qū)。因此可將船舶視為一個質(zhì)點，便于后續(xù)路徑規(guī)劃。

1.4 切線圖法構(gòu)建環(huán)境模型

切線圖法主要是通過求解起始點及終止點對所有礙航區(qū)(包括礙航障礙區(qū)及預(yù)測危險區(qū))的切線及礙航區(qū)相互之間的公切線，從而構(gòu)建一個關(guān)于起始點、終止點及需要避讓的礙航區(qū)切線圖網(wǎng)絡(luò)環(huán)境，并通過該網(wǎng)絡(luò)可進行初步局部最短航路的規(guī)劃。文獻[14]證明了平面上移動機器人局部最短路徑由凸多邊形礙航區(qū)域的邊界和礙航區(qū)域之間的公切線組成。雖然船舶在海上航行時遇到礙航區(qū)不一定是凸多邊形，但根據(jù)前面結(jié)論可知：即使是非凸多邊形，其避碰局部最短路徑與該非凸多邊形對應(yīng)凸包圍盒(凸多邊形)局部最短路徑等同，均是從其邊界點或沿邊界線通過，如圖3。

圖3中：船舶從O點到D點過程中需避開一個非凸多邊形。假設(shè)船舶的最短路徑為OHGJD。HGJ構(gòu)成一個三角形，由三角形的幾何定律易知：HG與GJ的長度之和大于HJ長度，因此船舶最短路徑應(yīng)用HJ代替HGJ，即OHJD為船舶最短路徑；即船舶避碰最短路徑從該非凸多邊形邊界點的連線通過，證畢。因此，為便于處理，可用凸包圍盒來代替非凸多邊形，HJKLH即為原非凸多邊形的一個凸包圍盒(圖3)。

圖3 非凸多邊形最短路徑Fig. 3 The shortest path of non-convex polygon

文中切線及公切線求取算法如下：

1)切線算法

Step 1：連接起點與終點生成一條探測線段；

Step 2：用集合M表示與探測線段相交的礙航區(qū)。若M為空，結(jié)束算法。否則，求起點和終點與M中礙航區(qū)的切線段，用集合N表示；

Step 3：若N為空，結(jié)束算法。否則，在N中任取一條切線段N1，判斷其是否與礙航區(qū)相交。否，則將N1從N移入最終切線段集合R中，然后判斷N中的下一條切線段；若與M之外的礙航區(qū)相交，則用M2表示該情況下的相交礙航區(qū)，并求起點、終點與M2中的每個礙航區(qū)的切線段L，再將L放入N中并刪除N1，將M2移入M中，返回Step 3。

2)公切線算法

Step 1：提取求切線段過程的M集合；

Step 2：若M中礙航區(qū)數(shù)小于1，結(jié)束算法。否則，求M中任意兩個礙航區(qū)之間的公切線段，得到公切線段集合N；

Step 3：若N為空，則結(jié)束算法。否則，在N中任取一條切線段N1，判斷其是否與礙航區(qū)相交。否，則將N1從N移入最終切線段集合R中，然后繼續(xù)判斷N中的下一條切線段；若與M之外的礙航區(qū)相交，則用M2表示該情況下的相交礙航區(qū)，對所有M與M2中的礙航區(qū)m和m2，求m與m2間以及M2中任意兩礙航區(qū)間的公切線段L，并求起點、終點對M2的切線段L1，將L及L1移入N并刪除N1，將m2移入M中，返回Step 3。

通過以上切線及公切線的求取算法，可求得如圖4中的礙航區(qū)切線網(wǎng)絡(luò)。

圖4 切線網(wǎng)絡(luò)Fig. 4 Tangent line network

2 路徑規(guī)劃

2.1 初步路徑規(guī)劃

上述切線及公切線求取算法不但可求得切線網(wǎng)絡(luò)，還可求得每條切線段端點坐標(biāo)，并判斷哪些礙航區(qū)是船舶需要避讓的。相對于直接對所有礙航區(qū)求取切線的算法，該方法時間復(fù)雜度更小。起點、終點及需要避讓的礙航區(qū)頂點構(gòu)成了避碰路徑點集合。通過求切線段的長度及需要避讓的礙航區(qū)中各邊界線長度，則可求得路徑點集合構(gòu)成的距離矩陣。對于圖4中的切線圖網(wǎng)絡(luò)，可求得類似式(4)的距離矩陣。由于該距離矩陣只考慮了起止點及航行時需要避碰的礙航區(qū)頂點，未考慮不需要避碰的礙航區(qū)頂點，因此能減少算法時間復(fù)雜度。

(4)

通過式(4)，用Dijkstra算法可求得如圖5的初始路徑。

圖5 初始路徑Fig. 5 Initial route

2.2 路徑平滑

船舶路徑規(guī)劃不同于機器人路徑規(guī)劃，機器人路徑可以為折線，但船舶路徑不行。為使船舶航行更加符合實際及動力學(xué)要求，需對Dijkstra算法求得的折線路徑進行平滑處理。

目前路徑平滑方法主要有：多項式最小二乘擬合、曲線擬合(如貝塞爾曲線、B樣條曲線)、平滑蟻群算法和筆者使用的2-turn平滑法等[15-16]。在進行船舶避碰路徑平滑處理時，需考慮以下幾點：船舶回轉(zhuǎn)直徑、平滑后路徑與初始路徑之間的總長度偏差(偏差要盡可能小)、平滑后路徑不能與礙航區(qū)域相交(只能相切或相離)。2-turn平滑法能很好滿足這些條件，因此筆者采用2-turn法進行平滑處理。

2-turn平滑法的主要思想是：對相鄰兩個折線路徑段，用兩個外切圓來進行平滑處理，這兩個外切圓彼此之間也相切，如圖6。圖6中：O1與O2分別為兩個外切圓的圓心；S1與S3分別為兩個外切圓與原路徑切點；S2為兩個外切圓交點；d為路徑段2的長度；L為線段S1S3長度；θ和δ分別為船舶在兩次轉(zhuǎn)向過程中的航向改變量，稱第一次航向改變量為避碰轉(zhuǎn)彎角度，第二次航向改變量為復(fù)航角度。

圖6 路徑平滑F(xiàn)ig. 6 The smoothness of route

由于利用2-turn方法進行平滑處理時利用的是船舶回轉(zhuǎn)直徑，因此其路徑平滑部分曲線直徑必須大于船舶最小回轉(zhuǎn)直徑。此外，若利用最小回轉(zhuǎn)直徑求得的平滑路徑中S1與S3兩點組成線段長度大于路徑段2長度，則說明船舶不能夠在此處完成轉(zhuǎn)向操縱，則該路徑規(guī)劃不合理，有碰撞危險。此時，需要將路徑段2所在切線段刪除，并重新進行路徑規(guī)劃。筆者選取季美(Thieme)公式[17]作為船舶的最小回轉(zhuǎn)直徑，如式(5)：

D=0.25L5/3

(5)

基于2-turn思想，結(jié)合船舶航行實際，筆者給出以下改進路徑平滑算法：

Step 1：根據(jù)當(dāng)前航速和欲轉(zhuǎn)向舵角來確定回轉(zhuǎn)直徑D，進而確定D對應(yīng)的半徑R；

Step 2：根據(jù)S1坐標(biāo)和半徑R大小可確定第一個外切圓的圓心O1；

Step 3：根據(jù)O1與O2之間的距離為2R，且O2點到路徑段2所在直線的距離為R，確定O2點坐標(biāo)；

Step 4：根據(jù)上述結(jié)果可得出兩個外切圓O1與O2方程，聯(lián)立該方程可得交點S2坐標(biāo)；聯(lián)立O2與路徑段2直線方程可得S3坐標(biāo)；

Step 5：計算L長度(L=Rcosα+2Rsinδ)。若L

Step 6：根據(jù)以上結(jié)果，畫圓弧S1S2和圓弧S2S3；

Step 7：用圓弧S1S2和圓弧S2S3以及半徑R的長度 來計算避碰轉(zhuǎn)彎角度θ及復(fù)航角度δ。

對Dijkstra算法求得的初始路徑進行平滑處理，得到路徑如圖7。

圖7 最終路徑Fig. 7 The final path

3 仿真實驗

為進一步驗證文中方法的正確性及有效性，筆者用仿真案例進行實驗，并用MATLAB進行仿真計算。其中：船舶以及礙航區(qū)位置坐標(biāo)采用平面直角坐標(biāo)系方法表示，路徑圖中的橫軸表示x坐標(biāo)，縱軸表示y坐標(biāo)，坐標(biāo)單位為m。障礙區(qū)頂點坐標(biāo)如表1。

表1 障礙區(qū)位置信息Table 1 Location information of obstacles

我船的基本參數(shù)如下：油輪，總長為122 m，船寬18 m，滿載吃水8.5 m，舵面積比約為1.4%。現(xiàn)有一組我船航速為6 m/s，輕載狀態(tài)下操不同舵角的旋回直徑數(shù)據(jù)，見表2。

表2 不同舵角下的回轉(zhuǎn)直徑Table 2 Turning diameter at different rudder angles

由表2可知：該船在此情形下的回轉(zhuǎn)性能較差。因此，用其進行算例分析可以充分驗證該路徑平滑處理對于操作性能較差的船舶也具有較好的實用性。因為操縱性能優(yōu)良的船舶在克服轉(zhuǎn)彎過程中所產(chǎn)生的誤差要遠小于操縱性能差的船舶，因此采用操縱性能差的船舶進行計算，對于算法的驗證更具備說服力。

我船某時刻的位置坐標(biāo)為(-6 081.2, -614.09)，目的地坐標(biāo)為(1 005, 7 053)，航速6 kn，航向角30°。利用式(3)可求得：Rstarb=355 m。目標(biāo)船的船長為171 m，其某時刻位置坐標(biāo)為(-4 299.2,-497.27)，航速6 m/s，航向角0°。根據(jù)《規(guī)則》，我船為讓路船，需要“早、大、寬、清”地履行避讓目標(biāo)船義務(wù)[18]，由于要結(jié)合PAD來履行我船讓路義務(wù)，而PAD要求我船保速，因此我船采用轉(zhuǎn)向避讓的措施來避碰目標(biāo)船。此情形下PAD區(qū)域與礙航障礙區(qū)4有重疊部分，構(gòu)成一個非凸的多邊形，如圖8。需先求其凸包圍盒，再進行路徑規(guī)劃。

采用文中算法，并以舵角為10°、航速為6 m/s對應(yīng)回轉(zhuǎn)直徑來進行路徑平滑，可規(guī)劃出如圖9的避碰路徑。另外，轉(zhuǎn)向過程中不考慮船舶回轉(zhuǎn)運動中的反橫距，并以階躍操舵方式進行轉(zhuǎn)舵。路徑平滑處理后得到的參數(shù)如表3。由表3可知：第一個和第二個平滑段航向改變量較小，說明前后路徑段近乎平行。所有平滑處理中的L均小于d，說明規(guī)劃的路徑符合船舶航行實際。由于表3中最大回轉(zhuǎn)直徑能滿足路徑平滑要求，因此可得知船舶在轉(zhuǎn)向時，可采取舵角在[10, 35]之間。同樣，基于Maklink圖可求得最優(yōu)避碰路徑，如圖10。文中方法運行時間為0.21 s，最短路徑長度為11 514 m；基于Maklink圖法運行時間為2.13 s，最短路徑長度為11 727 m。

圖8 礙航區(qū)發(fā)生重疊Fig. 8 Overlapping of navigation-obstruction areas

圖9 切線圖法的避碰路徑Fig. 9 Collision avoidance route of tangent line method

表3 平滑路徑段的參數(shù)Table 3 Parameters of smoothing routes

圖10 Maklink_蟻群算法的避碰路徑Fig. 10 Collision avoidance route of Maklink_ACO method

通過實驗可證明筆者提出的避碰路徑規(guī)劃方法正確性。此外，通過與基于Maklink鏈接圖法的路徑規(guī)劃算法進行對比，可以發(fā)現(xiàn)文中方法在時間性能、路徑整體平滑性和最短路徑長度上均更優(yōu)，且由于筆者的路徑規(guī)劃完全基于幾何以及計算幾何等確定性理論和算法，其計算出路徑無需用智能優(yōu)化算法再進行優(yōu)化計算，因此每次計算得到的路徑是相同的且為最優(yōu)路徑，其路徑唯一性是其他方法所不具有的。此外，由于該算法中路徑平滑考慮到船舶不同航速、舵角下的回轉(zhuǎn)直徑因素，其平滑處理之后不僅更加符合船舶航行實際，還能給出避碰轉(zhuǎn)向角度和復(fù)航角度并能檢驗規(guī)劃路徑是否能保證船舶安全、航行。由于該方法決策時間很短，可有效地應(yīng)用到現(xiàn)有的電子海圖顯示中，并與信息系統(tǒng)(ECDIS)等平臺綜合進行避碰輔助決策。

4 結(jié) 語

筆者結(jié)合《規(guī)則》，考慮船舶航行中的不同舵角、航速下的回轉(zhuǎn)直徑、路徑的平滑性等因素，提出了一種能夠解決目標(biāo)船和礙航障礙區(qū)同時存在的復(fù)雜水域避碰路徑規(guī)劃的方法。

相對于其他方法，其優(yōu)點為：時間性能更好、路徑整體平滑性好、路徑優(yōu)化程度更高、路徑具有唯一性、能給出避碰轉(zhuǎn)彎角度及復(fù)航角度、能檢驗規(guī)劃的路徑是否能夠保證船舶安全航行。因此，可將其應(yīng)用到現(xiàn)有的電子海圖顯示及信息系統(tǒng)(ECDIS)等決策平臺中，從而可為該類復(fù)雜水域的船舶避碰決策提供輔助支持。

筆者對目標(biāo)船進行處理時，以目標(biāo)船保速、保向且我船保速為前提。實際中還存在目標(biāo)船速度大小、方向及我船航向發(fā)生改變等情況，此時需要更新原預(yù)測危險區(qū)，再重新計算避碰路徑，從而可實現(xiàn)動態(tài)的避碰路徑規(guī)劃。