顧及惡劣海況的船舶救援路徑規劃

馬凱強, 任利鋒, 曾 喆, 萬劍華

顧及惡劣海況的船舶救援路徑規劃

馬凱強1, 任利鋒2, 曾 喆1, 萬劍華1

(1. 中國石油大學(華東) 海洋與空間信息學院, 山東 青島 266580; 2. 中國石油集團東方地球物理勘探有限責任公司海洋物探分公司, 天津 300457)

為了保障救援船舶在惡劣海況環境下能夠安全、高效地到達救援區域, 本文改進人工魚群算法開展海上救援路徑規劃研究。選取地形、海風和海浪等指標進行風險度量, 采用GIS(geographical infor-mation system)多指標決策方法構建海洋環境威脅場, 通過粒子群算法計算救援路徑規劃的最佳參數, 并實現海上救援路徑搜索。實驗表明, 基于改進的人工魚群算法規劃的船舶救援路徑效果更優, 可為海上應急救援提供輔助決策參考。

惡劣海況; 路徑規劃; 人工魚群算法

近年來, 隨著海上貿易的日益繁榮, 海上安全事故頻頻發生。為了減少船舶人員和財產的損失, 人們對于海上突發事件的應急救援提出了很高的要求。在惡劣海況環境下, 風、浪等自然環境復雜多變, 具有較大的不可預測性, 船舶航行的風險仍然很高[1]。因此, 研究惡劣海況環境下的船舶救援路徑規劃方法對海上應急救援具有重要意義。

路徑規劃研究除了Dijkstra算法、人工勢場法和A*算法等傳統方法[2-3]外, 還包括蟻群算法、粒子群算法、遺傳算法等群智能算法[4-5]。由于群智能算法具有搜索效率高、全局搜索能力強和適用于各種復雜環境等特點, 其已成為了當今研究的熱點。王沛棟等[6]利用蟻群算法實現了機器人在靜態環境下的路徑規劃。向祖權等[7]利用粒子群算法實現了無人船規避障礙物的最優路徑規劃。范云生等[8]利用柵格法對電子海圖建立海洋環境, 提出一種改進遺傳算法的全局路徑規劃算法。人工魚群算法是一種簡單易實現、魯棒性強和全局優化能力強的群智能算法, 已應用于船舶的路徑規劃領域[9]。

目前船舶路徑規劃研究中海洋環境建模大多只考慮了地形靜態環境因素, 較少考慮風、浪等氣象水文環境因素。余夢珺等[10]在西北航道上構建了基于海冰密集度、海表溫度、風強度的海上環境威脅場, 利用蟻群算法進行了海上救援路徑規劃研究, 但其只適應于西北航道區域, 未能解決在惡劣海況等其他情況下的救援路徑規劃。鑒于此, 本文將改進人工魚群算法應用于惡劣海況環境下, 實現了顧及地形、海風和海浪等指標的船舶救援路徑規劃。

1 救援路徑規劃模型的建立

本文研究內容主要包括3部分: 確定規劃目標, 構建海洋環境威脅場, 海上救援路徑規劃。本文以惡劣海況環境下路徑最短、風險最小作為規劃目標, 采用GIS多指標決策方法構建海洋環境威脅場, 利用改進人工魚群算法規劃海上救援路徑, 綜合考慮安全性和高效性。規劃模型流程圖如圖1所示。

1.1 研究區域和規劃目標

1.1.1 研究區域

本文選取遼東半島附近海域為研究區域: 經度為120.5°～123.5°E, 緯度為38.26°～39.66°N。

1.1.2 規劃目標

海上救援路徑規劃實質上指救援船舶從起點出發, 在保證自身安全的情況下, 以最短的時間到達事故區域進行救援。假設船舶全程勻速行駛, 航行時間就可用路徑長度來代替。路徑長度可表示為:

圖1 顧及惡劣海況的船舶救援路徑規劃流程圖

船舶的航行安全可用路徑的風險代價來表示。風險代價可表示為:

因此, 救援路徑規劃的總目標函數可由路徑長度和風險代價加權計算, 表示為:

()=1×() +2×(), (3)

式中,()為總目標值,1、2為比例系數, 其大小由決策者根據情況進行調整, 本文設1=0.4,2=0.6。

1.2 構建海洋環境威脅場

1.2.1 確定海洋環境風險因素

與陸地不同, 海洋環境非常復雜。海洋地理環境常分為兩類: 一類是包含水深、陸地、島礁及淺灘等靜態地形環境; 另一類是包含海風、海浪等動態氣象水文環境。在惡劣海況下, 大風和大浪是影響船舶航行的重要因素。大風可直接影響船舶的航行方向, 可能造成碰撞等事故。大浪可對船舶有縱向、橫向、垂向的影響, 可能會造成螺旋槳、儀器損壞[11]。地形因素也是船舶航行安全的重要危險因素。在水深較淺、海岸和島礁附近海域, 淺灘、礁石等航行障礙物較多, 船舶極易發生碰撞、擱淺等事故。另外, 海流也是影響船舶航行的因素, 但在惡劣海況環境中, 表層海流主要受海風影響, 其對船舶的危險度可通過海風和海浪的作用來表示, 因此可忽略。根據以上原因, 本文選取了地形、海風、海浪3個風險因素, 分別對其進行量化評價。

圖2 研究區域

(1) 風強度

風強度的大小是用風速來表示的, 風速越大, 風強度也越大。風強度1的量化公式為:

式中,為單個柵格單元的實際風速值,min為大風最低危險值, 根據蒲福風力等級表,min定為17.1 m/s。

(2) 浪強度

浪強度的大小是用浪高來表示的, 海浪越高, 浪強度也越大。浪強度2的量化公式為:

式中,為單個柵格單元的實際浪高,min為海浪最低危險值, 根據海況等級表,min定為4.5 m。

(3) 地形危險度

式中,為單個柵格單元的實際水深,min為船舶的最小安全水深, 為了滿足大部分救援船舶的航行安全,min確定為15 m。

離岸距離危險度R的量化公式:

式中,為單個柵格單元距離海岸線的距離,min為船舶的最小離岸距離, 其值定為12 n mile。

地形危險度的量化公式:

式中, 地形危險度3是取單個柵格單元中水深危險度與離岸距離危險度的最大值。

水深地形數據來自美國地球物理中心(national geophysical data center, NGDC), 海風、海浪數據來自歐洲中期天氣預報中心(Europen center for medium- range weather forecasts, ECMWF)。本文選取2019年10月14號14時(UTC)的數據, 此時研究區域最大浪高達4.5 m以上, 符合2萬噸以下船舶惡劣海況的標準[12]。由于各個指標的數據都是網格數據且數據間存在分辨率不一致等問題, 需要對各因素進行空間分析處理, 統一為柵格大小為0.02°× 0.02°的柵格圖。各個指標使用的空間分析方法如表1所示。

表1 各指標的空間分析方法

1.2.2 海洋環境威脅場建立

GIS多指標決策方法是一種綜合評價地理空間的方法。OWA(order weighted average)是根據數據的排序位置進行加權聚合的算子。GIS-OWA方法是GIS多指標決策方法中能根據決策者偏好來評價風險大小的方法, 該方法能從指標補償差異等方面提高決策者對結果的滿意度[13]。基于GIS-OWA的海洋環境威脅場構建主要有3個步驟: 計算指標權重、計算次序權重和OWA算子合并。

指標權重是由層次分析法來確定的。層次分析法用專家的經驗判斷各風險因素之間的相對重要程度, 并合理地給出每個風險因素的指標權重。

次序權重可由指標的重要程度來確定。次序權重v可定義為:

OWA算子合并可由指標權重和次序權重計算得出。OWA算子的表達式為:

經過5名專家打分后, 由層次分析法可計算出浪強度、風強度、地形危險度的指標權重值分別為0.426, 0.412, 0.162。設=0.6, 由公式(9)可計算出浪強度、風強度、地形危險度的次序權重分別為0.659 8, 0.236 6, 0.103 6。最后, 以公式(10)的OWA算子進行空間計算可得到海洋環境威脅場。如圖3, 在海洋環境威脅場中, 西部海域風險低, 東部海域風險高, 東北島礁附近的海域風險最高, 東南海域風險較高。

1.3 海上救援路徑規劃算法

人工魚群算法是由李曉磊等[14]提出的一種群智能優化算法。魚群在水中尋找食物時, 往往會自行或尾隨其他魚找到食物濃度多的位置。通過魚群覓食的這個特點, 人工魚可模擬魚群的覓食、聚群和追尾行為, 找到一條從起點到終點的最佳路徑。

本文針對傳統人工魚群算法易陷入局部最優和路徑冗長的問題。對算法進行了以下的改進。

圖3 海洋環境威脅場

Fig. 3 Marine environment threat field

1.3.1 人工魚游走方式改進

傳統人工魚群算法的人工魚游走方式是隨機搜索, 改進方法是采用混沌搜索。混沌搜索具有隨機性、規律性、遍歷性等特點。因此, 混沌搜索比隨機搜索更優越[15]。混沌搜索可表示為:

式中,x是0到1之間的一個隨機數。

人工魚的游走方式也改為:

式中,X()為人工魚當前的狀態,()為人工魚搜索的狀態,X+1()為人工魚移動一步后的新狀態,為人工魚數目。

1.3.2 視野的改進

傳統人工魚群算法中人工魚的視野范圍是一個定值。視野的大小對算法收斂有較大影響, 視野范圍較小時, 執行覓食和隨機的行為較多。視野較大時, 執行追尾和聚群的行為較多, 但算法復雜度也變大。因此, 在算法初期, 人工魚應在較大的視野中尋優, 在算法的后期, 應相應減少人工魚的視野, 加快算法的收斂速度。視野改進公式為:

1.3.3 路徑冗長的改進

采用以上改進策略, 海上救援路徑規劃的步驟如下:

①初始化各個參數, 包括人工魚數目, 最大迭代次數, 擁擠度因子和重復次數。

②采用公式(1)(2)(3)計算每條人工魚初始的總目標值, 并將其最小值放入公告牌。

③采用公式(13)的結果來作為人工魚的新視野。

④執行人工魚的追尾、聚群和覓食行為, 并采用行為選擇策略選擇最優的前進方向, 同時更新每條人工魚的位置。

⑤每條人工魚執行各種行為后, 計算每條人工魚的總目標值, 取其最小值與公告板的值比較, 若小于時, 更新其值作為公告板的值。

⑥判斷是否滿足終止條件, 若滿足, 執行步驟⑦, 否則, 跳轉到步驟③。

⑦將路徑進行平滑優化, 輸出公告板中的值和對應的路徑, 即為最優路徑。

2 實驗

2.1 海上救援路徑規劃算法參數優化

人工魚群算法的參數選擇不合理會導致算法運行效率變低或易陷入局部最優。因此, 需要對算法的主要參數進行優化。人工魚群算法有5個基本參數: 人工魚數目、視野、步長、擁擠度因子和重復次數。由于柵格網的限制, 人工魚只能以相鄰的柵格作為步長。因此, 本文需要在除步長外的其他4個參數中尋找最優參數。這4個參數對人工魚群算法性能的影響如下[16]:

1) 人工魚數目是算法的重要參數。人工魚數目越多, 跳出局部最優解的能力也越強, 收斂速度也越快。相應地, 數目越多, 效率就會變低。因此, 人工魚數目要在滿足穩定收斂下, 選取較少的人工魚數目。

2) 視野對算法中各種行為的選取有較大的影響。由式(13), 人工魚視野范圍的大小取決于迭代次數的大小。

3) 嘗試次數對人工魚算法的影響表現在其越大, 覓食能力越強, 收斂效率越高。

4) 擁擠度因子對人工魚算法的影響表現在其可避免人工魚由于過度擁擠而陷入局部最優解。

本文采用粒子群算法對人工魚群算法參數進行優化。粒子群算法的適應值評價函數從算法的尋優能力、收斂速度和運算時間3方面考慮[17]。適應值函數如下:

式中,()為粒子群算法的適應值,1,2,3為比例值, 分別為0.5, 0.25, 0.25。()表示人工魚群算法的尋優能力,local表示人工魚群算法得到的最優解,best為理論最優解。()表示人工魚群算法的收斂速度,是魚群找到最優解時的迭代次數,max為魚群算法迭代次數的最大值, 取為500。()表示魚群算法的運行時間,max為魚群數目的最大值, 取為50。

粒子群算法采用基本算法, 其參數粒子個數為10, 學習因子1=2= 0.5, 慣性因子= 0.5(–)/+ 0.4,迭代次數為100,為當前迭代次數。人工魚群算法的參數取值范圍如表2所示。

表2 人工魚群算法參數取值范圍

圖4是粒子群算法迭代過程中適應值的變化曲線。圖4顯示, 適應值總體上一直呈上升趨勢, 表明參數一直在向全局最優的方向趨近。求得的參數可作為海上救援路徑規劃算法的最佳參數, 最佳參數為:=32,=212,=0.628,=8。

圖4 粒子適應值變化曲線

2.2 對比實驗

為了驗證改進人工魚群算法能適用于惡劣海況環境下的海上救援路徑規劃。本文從改進人工魚群算法的性能和路徑上進行分析。設置起點為(120.7°E, 38.52°N), 終點為(122.8°E, 38.46°N)。

根據上述實驗得到的最佳參數, 檢測閾值設為4, 運行改進人工魚群算法20次, 記錄其每次的優化結果。采用與改進人工魚群算法相同的參數, 視野為10, 運行傳統人工魚群算法20次, 也記錄每次的優化結果。表3給出了改進人工魚群算法和傳統人工魚群算法各運行20次后的結果。從表3可知, 改進人工魚群算法在最優總目標值、總目標值均值、總目標值方差和平均迭代次數上均優于傳統人工魚群算法, 表明改進人工魚群算法在尋優能力、穩定性和收斂速度方面均優于傳統人工魚群算法。

表3 改進前與改進后算法性能對比實驗結果

從兩組實驗中挑選出總目標值最優的兩條路徑進行分析。表4為傳統人工魚群和改進人工魚群算法的路徑對比實驗結果。由表4可知, 改進人工魚群算法在總目標值、路徑長度、風險代價上均優于傳統人工魚群算法, 改進人工魚群算法規劃的救援路徑能以更短的路徑長度和更小的風險到達終點。將路徑等距離劃分, 可分為前中后三段。由圖5中可知, 傳統人工魚群算法得到的路徑易陷入局部最優, 路徑迂回曲折, 路徑的中段部分路段未能繞開較高風險區域, 不符合船舶的實際航行要求。而改進人工魚群算法搜索的路徑更加平滑, 路徑的中段一直處于低風險區域, 能很好地避開較高風險區域, 能保障救援船舶安全航行, 更符合船舶的實際航行要求。

表4 改進前與改進后路徑對比實驗結果

圖5 兩條路徑規劃對比圖

為了驗證以上實驗結果的可行性, 選用以上實驗中相同的參數, 更換起點和終點, 設置起點為(122.82°E, 39.26°N), 終點為(123.02°E, 38.46°N), 再次進行一組對比實驗。從表5中可知, 改進人工魚群算法規劃的救援路徑仍能以更短的路程和更小的風險到達終點。從圖6中可知, 起終點位于高風險區域的南北兩側, 兩條路徑均能避開東部島嶼附近風險度接近1的高風險區域。傳統人工魚群算法得到的路徑仍會陷入局部最優, 且路徑的前段靠近島嶼, 未能保障船舶的安全性。而改進人工魚群算法規劃的路徑能從兩個島嶼區域中間相對風險較小的區域穿過, 且路徑平滑, 表明了改進人工魚群算法規劃的路徑的有效性。

表5 改進前與改進后路徑對比實驗結果

3 結論

針對在惡劣海況環境下救援船舶路徑規劃問題, 本文提出了基于改進的人工魚群算法的船舶救援路徑規劃方法。本文的海上救援路徑規劃方法搜索到的路徑在總目標值、路徑長度、風險代價上均優于傳統人工魚群算法, 且路徑更加平滑, 能順利避開海岸、島礁和高風險區域, 能更好地保障救援船舶安全、高效地到達事故區域。

圖6 兩條路徑規劃對比圖

本研究的不足之處是只考慮了在惡劣海況環境下的部分因素, 且未考慮風向、浪向等對船舶航行效率的影響, 未來將開展更深入的研究。

[1] 戴冉, 郝慶龍, 顧祖旭. 惡劣海況中軍用艦船航行決策模型[J]. 中國航海, 2014, 37(3): 68-71, 79.

DAI Ran, HAO Qinglong, GU Zuxu. Sailing Decision Model of Military Vessels on Rough Sea[J]. Navigation of China, 2014, 37(3): 68-71, 79.

[2] CHEN Y B, LUO G C, MEI Y S, et al. UAV path planning using artificial potential field method updated by optimal control theory[J]. International Journal of System Science, 2016, 47(6): 1407-1420.

[3] TOPAJ A G, TAROVIK O V, BAKHAREV A A, et al. Optimal ice routing of a ship with icebreaker assistance[J]. Applied Ocean Research, 2019, 86: 177-187.

[4] TAN Guanzheng, LIU Guanjun. Global optimal path planning for mobile robots based on particle swarm optimization[J]. Application Research of Computers, 2007, 24(11): 210-212.

[5] LI Wei, WANG Gaiyun. Application of improved PSO in mobile robotic path planning[C]//Proceedings 2010 International Conference on Intelligent Computing and Integrated Systems. Guilin: IEEE Network, 2010, 4(4): 45-48.

[6] 王沛棟, 馮祖洪, 孫志長. 一種柵格模型下機器人路徑規劃的改進蟻群算法[J]. 計算機應用, 2008, 28(11): 2877-2880.

WANG Peidong, FENG Zuhong, SUN Zhichang. Improved ant colony algorithm in grid model for mobile robot path planning[J]. Journal of Computer Application, 2008, 28(11): 2877-2880.

[7] 向祖權, 靳超, 杜開君, 等. 基于粒子群優化算法的水面無人艇分層局部路徑規劃[J]. 武漢理工大學學報, 2015, 37(7): 38-45.

XIANG Zuquan, JIN Chao, DU Kaijun, et al. Local obstacle avoidance for unmanned surface vehicle using a hierarchical strategy based on particle swarm optimization[J]. Journal of Wuhan University of Technology, 2015, 37(7): 38-45.

[8] 范云生, 趙永生, 石林龍, 等. 基于電子海圖柵格化的無人水面艇全局路徑規劃[J]. 中國航海, 2017, 40(1): 47-52.

FAN Yunsheng, ZHAO Yongsheng, SHI Linlong, et al. Global path planning for unmanned surface vehicle based on grid model of electronic chart[J]. Navigation of China, 2017, 40(1): 47-52.

[9] 馬文耀, 吳兆麟, 楊家軒, 等. 人工魚群算法的避碰路徑規劃決策支持[J]. 中國航海, 2014, 37(3): 63-67.

MA Wenyao, WU Zhaolin, YANG Jiaxuan, et al. Decision support from artificial fish swarm algorithm for ship collision avoidance route planning[J]. Navigation of China, 2014, 37(3): 63-67.

[10] 余夢珺, 張韌, 高頂, 等. 基于蟻群算法的西北航道海上救援路徑規劃[J]. 海洋預報, 2019, 36(6): 62-72.

YU Mengjun, ZHANG Ren, GAO Ding, et al. Route planning for maritime rescue in Arctic Northwest Passage based on ant colony algorithm[J]. Marine Forecasts, 2019, 36(6): 62-72.

[11] 解以揚, 劉大剛, 吳丹朱, 等. 黃、渤海惡劣天氣影響船舶安全的風險預估技術初探[J]. 災害學, 2014(1): 136-143.

XIE Yiyang, LIU Dagang, WU Danzhu, et al. Risk prediction technology of ship safety in the Yellow Sea and Bohai Sea during severe weathers[J]. Journal of Catastrophology, 2014, (1): 136-143.

[12] 劉冰, 傅敏輝, 薛國虎, 等. 航天測量船海上測控任務分析與設計方法[M]. 北京: 國防工業出版社, 2015: 194-195.

LIU Bing, FU Minhui, XUE Guohu, et al. Analysis and design method of TT & C mission for space survey ship at sea[M]. Beijing: National Defense Industry Press, 2015: 194-195.

[13] WANG Jiasheng, LI Manchun, LIU Yongxue, et al. Safety assessment of shipping routes in the South China Sea based on the fuzzy analytic hierarchy process[J]. Safety Science, 2014, 62: 46-57.

[14] 李曉磊, 薛云燦, 路飛, 等. 基于人工魚群算法的參數估計方法[J]. 山東大學學報(工學版), 2004, 34(3): 84-87.

LI Xiaolei, XUE Yuncan, LU Fei, et al. Parameter estimation method based-on artificial fish school algorithm[J]. Journal of Shandong University(Engineering Science), 2004, 34(3): 84-87.

[15] 黃長強, 趙克新. 基于改進蟻獅算法的無人機三維航跡規劃[J]. 電子與信息學報, 2018, 40(7): 1532-1538.

HUANG Changqiang, ZHAO Kexin. Three dimensional path planning of UAV with improved ant lion optimizer[J]. Journal of Electronics & Information Technology, 2018, 40(7): 1532-1538.

[16] 王聯國, 施秋紅. 人工魚群算法的參數分析[J]. 計算機工程, 2010, 36(24): 169-171.

WANG Lianguo, SHI Qiuhong. Parameters analysis of artificial fish swarm algorithm[J]. Computer Engineering, 2010, 36(24): 169-171.

[17] 劉利強, 戴運桃, 王麗華. 蟻群算法參數優化[J]. 計算機工程, 2008, 34(11): 208-210.

LIU Liqiang, DAI Yuntao, WANG Lihua. Ant colony algorithm parameters optimization[J]. Computer Engineering, 2008, 34(11): 208-210.

Ship rescue path planning considering adverse sea conditions

MA Kai-qiang1, REN Li-feng2, ZENG Zhe1, WAN Jian-hua1

(1. College of Oceanography and Space Informatics, China University of Petroleum, Qingdao 266580, China; 2. BGP INC, China National Petroleum Corporation, Tianjin 300457, China)

To ensure that the rescue ships can reach the rescue area safely and efficiently under adverse sea conditions, this study aims to improve the artificial fish swarm algorithm for maritime rescue path planning. The terrain, sea breeze, and sea wave are selected to measure the risk. The multi-index decision-making method of the geographic information system is used to construct the marine environment threat field. The optimal parameters of rescue path planning are calculated using the particle swarm optimization algorithm, and maritime rescue path planning is realized. The experimental results show that ship rescue path planning based on the improved artificial fish swarm algorithm is effective and can provide auxiliary decision-making reference for maritime emergency rescue.

bad sea; path planning; artificial fish swarm algorithm

Nov. 8, 2020

K928.44; U676.8

A

1000-3096(2021)05-0039-08

10.11759/hykx20201108007

2020-11-08;

2020-12-24

國家重點研發計劃項目(2017YFC1405600); 國家自然科學基金項目(41976184)

[National Key Research and Development Program of China, No. 2017YFC1405600; National Natural Science Foundation of China, No. 41976184]

馬凱強(1996－), 男, 山西呂梁人, 碩士研究生, 研究方向: 船舶路徑規劃, E-mail: 1045783321@qq.com; 萬劍華(1966－),通信作者, 教授, 主要從事海洋遙感和地理信息方面研究, E-mail: wjh66310@163.com

(本文編輯: 叢培秀)