基于蚁群算法的双救生艇海上搜救路径策略研究

罗修波 黄咸康 薛 丹 田祖织 杨建平 谢方伟

（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问题的算法流程，完成了对分散人群最短搜救线路的路径规划，最后由高速大型艇对密集人群进行救助，双体船沿着最短路径线路进行搜救，两船完成本身任务后可加入对方任务继续搜救。以上搜救策略能够对针对救生艇特性布置不同的搜救任务，并依据蚁群算法完成了最短路径的计算，极大了减少了落水人员的搜救时间，为海上救援行动提出了一条快速可行的搜救策略。