基于蟻群算法的雙救生艇海上搜救路徑策略研究

羅修波 黃咸康 薛 丹 田祖織 楊建平 謝方偉

（1.泰州市金海運船用設備有限責任公司，泰州 225300；2.中國礦業大學 機電工程學院，徐州 221116；3.中國船舶集團有限公司第七〇四研究所，上海 200031）

0 引 言

海上救援行動是保障海洋生命安全的重要防線，能夠極大降低海上事故發生后的人員傷亡[1-3]，因此建立高效快速的海上搜救路徑策略是對海上人員生命的最佳保障[4]。

對于海上救援策略的研究不僅隨著人類在海上活動的發展而發展，而且隨著通訊技術、人工智能、船舶設計以及路徑規劃等各學科知識的發展而有了更進一步的飛躍[5-6]。目前國內外學者對海上救援策略有了深入的研究。李巖[7]等利用傳統的拍賣規則，建立了多智能體海上搜尋任務分配模型，仿真結果表明該方法能夠實現全局最優的海上搜救任務分配。衣麟卓[8]基于蟻群算法的Dijkstra求解方法，尋找多約束下的海上搜救最短路徑的全局最優解，仿真結果表明算法能夠智能地尋找到一條從出發點與事故點之間最短路徑。劉志晨[9]等通過利用緩沖區分析、疊置分析和網絡分析等關鍵技術，初步完成了海上搜救與撤離模型系統設計。

目前，對于單救生艇救援路徑規劃方面已有眾多學者做了深入的研究，但對于多艇協作救援還處于發展階段。多救生艇同時執行救援行動，一般將行動分為任務劃分與路徑規劃兩個方面。本文首先通過對落水人員進行概率密度分布計算，完成對密集人群和分散人群的劃分。然后基于快速大型艇和雙體船的不同特點，由快速大型艇對密集人群進行救助，同時基于蟻群算法完成對分散人群最短搜救線路的路徑規劃，得出一條依次救出全部落水人員的路徑規劃線路，最后由雙體船依照路徑規劃線路依次前往救助。通過對雙救生艇不同特性布置不同的救援任務，并完成路徑規劃，以期得到一套更加快速高效的海上搜救路徑策略。

1 蟻群算法理論

自然界蟻群的覓食過程中，個體螞蟻會在經過的路徑上留下一種具有隨時間揮發性質的信息素，蟻群通過路徑中信息素的濃度決定所選擇的路徑，路徑中信息素濃度越大，選擇該路徑的概率越大。最終蟻群將會在這種正反饋機制的作用下選擇出巢穴與食物的最優路徑[10-12]。

蟻群算法用于解決TSP問題的模型如下：設蟻群中螞蟻數量為m，城市數量為n，定義單個螞蟻k(k=1，2，…，m)在t時刻從城市i到城市j的轉移概率為P，公式如下：

式中：α為信息啟發因子，反映了螞蟻運動過程中路徑上積累的信息素濃度在對路徑選擇概率的影響力。β為期望啟發因子，β越大，螞蟻受路徑點之間距離信息影響越大，越趨向于選擇目標點近的柵格。τij(t)表示t時刻城市i到j之間的信息素濃度，ηij(t)為啟發函數，為城市i到j之間的距離的倒數。ηij(t)的公式為：

式中，(xi,yi)為螞蟻當前所在城市 的位置。

設ρ為信息素揮發因子，當蟻群完成一次循環覓食運動，每條路徑上的信息素會隨時間揮發，并按以下公式進行調整：

式（3）表示全局信息素濃度更新規則，ρ為信息素濃度揮發系數，(1-ρ)為路徑上信息素濃度殘留系數。式(4)表示路徑(i，j)上的信息素增量由整個蟻群中的螞蟻釋放的信息素增量之和所決定的，其中表示第k只螞蟻在一次循環中釋放在路徑lij上的信息素的量。本文采用蟻周模型來求解信息素增量)，公式為：

式中：Q為信息素強度系數，Lk為螞蟻k走過路徑的長度。

2 搜救策略設計

2.1 智能搜救平臺設計

本文搜救平臺主要包括高速搜救無人艇、雙體搜救無人艇、小型搜救無人艇，如圖1所示。高速搜救無人艇為13 m大容量快艇，具有航行速度快、容量大等特點，事故發生時，能夠快速趕至事故海域，通過遠程遙控釋放救生裝置和救生筏救助集中落水人員，并大范圍的搜尋落水人員；雙體搜救無人艇為8 m中型搜救無人艇，帶有升降框和小型搜救無人艇，救援時低速航行，能夠釋放小型搜救無人艇，能夠對落單人員和失去知覺人員執行精準救助。

圖1 智能搜救艇

2.2 搜救策略設計

根據搜救平臺的特點以及搜救無人艇的特性，確定搜救策略流程圖如圖2所示：

圖2 搜救策略流程圖

Step1：落水人員救生衣內均配備北斗定位器，并與北斗衛星進行數據通信，以獲取落水人員精確的經緯度坐標。

Step2：根據落水人員的位置數據，通過分別計算x軸和y軸的概率密度分布曲線，最終合成二維空間內的概率密度分布圖。

Step3：通過概率密度圖找出最密集點，并根據高速搜救無人艇的搜救范圍進行判定，將落水人員分為密集人群與分散人群，并對點群進行劃分。

Step4：根據蟻群算法對分散人群進行最優路徑規劃，由雙體船前往救助，高速艇前往最密集人群點進行救助。

Step5：若雙體船和高速艇快于對方完成任務，可加入對方任務進行救助，并對救助點重新劃分，并進行路徑規劃擬定。

3 系統測試與結果討論

3.1 落水人員位置信息模擬

本文通過隨機模擬落水人員位置信息，用以測試搜救策略的可行性，生成人員位置信息表如表1所示，本文共設定26個落水人員：

表1 落水人員位置信息表

3.2 二維概率密度分布圖

通過對落水人員位置信息的獲取，根據落水人員位置信息在x軸和y軸的分布信息，基于ksdensity核心平滑密度估計分別對橫縱坐標位置進行概率密度分布計算，再根據落水人員橫縱坐標的概率密度分布，交叉擬合出二維概率密度分布圖，按照密度梯度大小給定不同深淺的顏色圖層，能夠更加直觀的判斷人員密度大小區域。落水人員概率密度分布如圖3所示，根據落水人員位置的橫縱坐標計算出的概率密度分布曲線可以看出，點越密集，概率密度越大。根據概率密度分布圖可知密度梯度圖層與最密集點的位置信息，為后續分散人群和密集人群的劃分提供依據。

圖3 落水人員概率分布圖

3.3 落水人員劃分

將總落水人員人數設置為N（N=26），根據落水人員概率密度分布圖獲取最密集人員位置，并由該位置為圓心，以高速搜救無人艇的搜索范圍為半徑，設定半徑為2.5，做出一個圓。圓內的人員劃定為密集人員Ni，圓外人員劃定為分散人員No，并在分散人員No中選出一些點作為蟻群算法路徑規劃點Na。由于雙體搜救無人艇能夠攜帶小型搜救無人艇，即雙體搜救無人艇具備一定的搜救范圍，因此依據雙體船的搜救范圍對臨近的分散人員進行判定，兩分散人員的距離低于搜救范圍則定為臨近人員，此搜救范圍直徑設定為5，并將臨近人員的中點加入路徑規劃點Na中，并將兩臨近人員從路徑規劃點群中去除。

人員劃分完畢后，最終的點集為：表2為密集人員Ni信息表，表3為蟻群算法路徑規劃點Na信息表，表3中序號為表1的原始序號，無序號點則為臨近人員的中點位置。

表2 密集人員Ni信息表

表3 蟻群算法路徑規劃點Na信息表

3.4 總體路徑規劃

通過對上述點集的劃分，最終確定的總路徑規劃線路圖如圖4所示，以最密集點為圓心所包括的密集人員使用紅色小圓圈標注如圖，由高速搜救無人艇前往圓心進行救助；將表3路徑規劃點代入蟻群算法，其中蟻群算法參數設置為：螞蟻數量: m=1.5*Na=21，信息啟發因子: α=1 ，期望啟發因子:β=4，信息素揮發因子:ρ=0.2，信息素強度系數:Q=20，最大迭代次數：Nmax=200，通過蟻群算法對路徑的優化，獲得最短路徑如圖所示，雙體搜救無人艇沿著路徑規劃線路前往救助，并在臨近人員中點停下，釋放小型搜救無人艇前往救助臨近人員，當救助完成后，回收小船，繼續搜救線路前往救助。

圖4 總體路徑規劃路線圖

4 結 論

提出了一種雙救生艇針對不同人群的搜救策略。根據落水人員的位置信息計算了落水人員概率密度分布，通過密度不同完成了對密集人群和分散人群的劃分，然后基于蟻群算法解決TSP問題的算法流程，完成了對分散人群最短搜救線路的路徑規劃，最后由高速大型艇對密集人群進行救助，雙體船沿著最短路徑線路進行搜救，兩船完成本身任務后可加入對方任務繼續搜救。以上搜救策略能夠對針對救生艇特性布置不同的搜救任務，并依據蟻群算法完成了最短路徑的計算，極大了減少了落水人員的搜救時間，為海上救援行動提出了一條快速可行的搜救策略。