基于改进蚁群的智能船舶全局路径规划方法

赵嵩郢，陈星烨

基于改进蚁群的智能船舶全局路径规划方法

赵嵩郢1，陈星烨2

(1. 武汉船用电力推进装置研究所，武汉 430064；2. 渤海造船厂集团有限公司，葫芦岛 125000)

船舶路径规划是指在特定的海洋环境下，按照一定的寻优策略，给定出发点和目标点，完成船舶航行所需求的航线规划。本文依据改进的蚁群算法进行智能船舶路径规划，基于对障碍物膨化处理后的栅格地图，针对经典蚁群算法局部最优问题，加入了状态自适应调整，信息素自适应更新和拐角处理策略，在提高算法收敛速度的同时保证了所得路径的平滑性及安全性，实现了智能船舶的安全、经济航线规划。

智能船舶 路径规划 蚁群算法

0 引言

船舶是水面交通运输领域最为重要的交通工具，船舶航行安全是世界船舶领域长期的研究课题，其经济性与社会意义十分重大[1]。船舶航行常规方式是操控人员凭借驾驶经验，开展航线规划和船舶操控，其规划和操控效果往往过度依赖操控人员判断能力和经验，出现差错可能性高且存在潜在风险[2]。

智能化是船舶发展的必然方向，而路径规划是船舶智能航行中的重要组成部分[3]。船舶路径规划是指在特定的海洋环境下，按照一定的寻优策略，给定出发点和目标点，完成船舶所需求的安全、经济、可行性高航线规划[4]。一般来说，路径规划主要包括两个方面: 1）一是已知全局地图的全局路径规划；2）已知局部信息，需动态更新的局部路径规划[5]。

本文依据改进的蚁群算法[6-10]进行智能船舶路径规划，该算法不依赖于大量的先验知识，算法结构简单容易理解并易于实现，对于复杂问题的优化求解具有很强的适应性。基于对障碍物进行膨化处理后的栅格地图，本文所改进的蚁群规避了蚁群算法局部最优的缺点，主要加入了状态自适应调整，信息素自适应更新和拐角处理策略，在提高算法收敛速度的同时保证了所得路径的平滑性及安全性，实现了智能船舶的安全、经济全局路径规划。

1 经典蚁群算法

1.1 栅格建模

栅格法是一种基于栅格构建的地图建模方法[11]。考虑到智能船舶在有限区域的移动路径基本服从于二维平面，栅格建模过程中通过将障碍物按照船舶的半径进行适当膨胀，再将未填充满的栅格补充完整（见图1），以确保船舶进行无碰撞运动。即当障碍物未填充整个栅格时，该栅格要作为障碍栅格处理，即障碍物所在的所有栅格均视为障碍栅格，如图1所示。

图1 障碍物膨化过程

1.2 经典蚁群算法基本流程

蚂蚁寻路过程中会在栅格留下信息素,信息素具有累加效果，同时信息素会逐渐消散，所以迭代过程中需要对路径上信息素进行更新：

智能照明系统功能能够在不同的驾驶条件和天气条件下，增加灯光输出并通过促动前大灯中各促动器开启额外灯光源，实现最佳道路照明。尾灯根据相关法规要求，LED灯在白天和夜间具有不同的强度设置，其优势在于照明功能的亮度足以满足后方车辆驾驶员正确判断交通状况的需要。为更好地了解大灯系统，根据其不同的功能借助相应的原理图来进一步说明，如图12所示CAN总线和LIN总线都具有双向性，即能传输又能接收信息。

以智能船舶的全局路径规划问题为例，蚁群算法实现步骤如下:

2 改进蚁群算法

2.1 自适应调整的状态转移概率策略

蚁群算法是一种随机启发式搜索算法[13]，在前期搜索中为提高解得多样性，会产生大量无意义的交叉路径，而且蚂蚁在寻路时由于禁忌表的限制无法走重复的路径[14]，蚂蚁在前期搜索中容易出现还没有走到终点就进入“死路”，无法再继续搜索路径。这种情况在复杂地图和规模较大的地图中表现的更为明显[15]。故为了使其对目标更有趋向性，尽量减少无用路径的出现，对于基本蚁群算法以蚂蚁所在节点到下一节点的距离反比为期望函数选择路径点的概率公式是，本文采用了新的期望函数即以蚂蚁能抵达的下一节点到目标点的距离反比：

式中，为下一路径点到目标点的距离。这样蚂蚁选择路径就更有导向性，搜索路径的有效性也有所提高。并且为了进一步提高初始可行解的构造效率，考虑到蚂蚁移动采用的是八叉树策略，如下图2所示。代表起始点，表示目标点，表示蚂蚁现在所在路径点。可以看出，为了提高蚂蚁的搜索速度，那么希望蚂蚁在该节点尽可能选择右下角的三个方向，其中标红加粗的方向最好。

为此，进一步运用自适应调整的期望函数将节点之间的差值拉大，以保证搜索的针对性，提高算法的运行速度，如下式所示。

2.2 自适应调整的信息素更新策略

2.3 拐点处理策略

在经典蚁群算法的路径搜索中，通常将路径长度作为主要的路径评价标准，为了能更快地找出较优的路径解，不仅仅在最后评价路径时考虑拐角，在算法运行中也加入了拐角处理[17]。而在船舶航行的过程中，路径中多余拐点的产生会影响船舶航行的平滑性和安全性，且对船舶的控制提出了较高的机动性要求[18]。小角度拐角会导致智能船舶的大幅度转向，不利于船舶的安全航行。因此，需要对规划得到的路径进行优化，以减少路径中不必要的拐点，提高路径的平滑度。

图3 多余拐角示意图

2.4 改进蚁群算法步骤

本文对经典蚁群算法予以改进，添加了自适应启发因子提高算法收敛速度，对于所得路径进行小角度拐角处理策略，避免多余拐点的产生，提高了所得路径的平滑性和安全性。所得的改进算法搜索路径流程如图4所示：

图4 改进蚁群算法示意流程图

3 仿真结果验证

3.1 改进蚁群算法验证

为了验证改进算法的普遍性，本文以20*20的栅格地图为例，对改进的蚁群算法与基本的蚁群算法进行对比，其中黑色区域为不可行区域，白色区域为无障碍可行区域。实验仿真结果如图5所示：

图5 对比实验

通过对智能船舶路径规划模块得到的最优路径以及算法收敛曲线可以看出，改进蚁群算法所规划得到的船舶航行路径的拐点数目明显少于由经典蚁群算法规划得到的路径，并且在蚁群搜索的前期，改进算法收敛速度明显高于传统算法，在相同的迭代次数为15时，基本的蚁群算法甚至还未收敛，而改进后的蚁群算法收敛速度已经趋近于结束。结果显示，改进蚁群算法所获得的最优路径长度短且平滑，其收敛速度相比经典蚁群也获得了较大的提升。

3.2 仿真对比与分析

图6 路径规划算法对比

结果显示，虽然三种算法均搜索到起始点及终点间的有效移动路径，但A*算法由于未设置八叉树搜索策略，相比蚁群算法搜索路径较长，耗时较多。而两种蚁群算法都斜向搜索到一条较短的移动路径，但经典的蚁群算法在搜索区域的范围上明显要更大，耗时也更多；本文基于改进的蚁群算法终点趋向性明显，搜索范围较小，并且由于加入拐点处理策略，改进算法在大幅度90°拐点的数量上明显少于传统算法，路径的平滑性能提高了很多，具体对比如表1所示。

表1 仿真计算参数表

表中为同一地图下三种算法经20次运行后的所得结果平均值，拐点平均值取四舍五入结果。由此可得，基于改进蚁群算法搜索得到最优路径长度相比经典蚁群及A*算法更短，且从多次运行的效果来看，本文改进算法的平均运算时间也比其余两种常规算法要低。总而言之，相比经典蚁群算法，改进算法避免了路径中较多拐点的产生，提高了智能船舶路径规划的平滑性和安全性，同时相比改进之前，算法收敛速度也有所提升，改进算法的整体有效性及适用性较佳。

4 结果分析

本文针对智能船舶航行过程中路径规划的特点，充分考虑到船舶航行的经济性、安全性以及航行路径的平滑性。本文所提出面向智能船舶的改进蚁群路径规划方法，相比经典蚁群算法，加入了自适应调整的状态转移概率策略，信息素自适应更新策略和拐角处理策略，提高算法收敛速度的同时保证了所得路径的平滑性及安全性，能够有效完成智能船舶的安全、经济路径规划。本文研究也存在不足之处，即本文的路径规划环境为全局静态，缺乏对动态障碍物及船舶航速等方面的考虑，后续将结合全局地图信息及局部传感器信息进行更为全面的智能船舶航行路径规划。

[1] Jiang J, Zeng X, Guz zet ti D , et al. Path planning for asteroid hopping rovers with pre-trained deep reinforcement learning architectures[J]. ActaAstronautica, 2020, 171:265-279.

[2] 高天航, 吕靖, 赖成寿. 考虑船舶偏好的海上风险规避路径规划研究[J]. 运筹与管理, 2018, 27(11):7.

[3] Jianhua Liu, Jianguo Yang, Huaping Liu, et al. An improved ant colony algorithm for robot path planning[J]. Soft Computing, 2017.

[4] 孟祥杜. 无人船路径规划算法研究[D]. 天津理工大学.

[5] 张玉奎. 水面无人艇路径规划技术研究[D]. 哈尔滨工程大学, 2008.

[6] Dorigo M, Caro G D . The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances. new ideas in optimization, 1999.

[7] 张松灿, 普杰信, 司彦娜,等. 蚁群算法在移动机器人路径规划中的应用综述[J]. 计算机工程与应用, 2020, 56(8): 10.

[8] 童帮裕, 胡坚堃. 基于改进蚁群算法的船舶冰区航行路径规划[J]. 中国航海, 2020, 43(1):5.

[9] Lee S M, Roh M I , Kim K S , et al. Method for a simultaneous determination of the path and the speed for ship route planning problems[J]. Ocean Engineering, 2018, 157: 301-312.

[10] 刘雄, 雷勇, 涂国强. 基于蚁群算法的移动机器人路径规划[J]. 计算机仿真, 2011, 28(11): 4.

[11] 康与涛, 朱大奇, 陈伟炯. 船舶避碰路径规划研究综述[J]. 船海工程, 2013, 42(5): 5.

[12] 吕红光, 尹勇. 基于电子海图矢量数据建模的无人船路径规划[J]. 交通信息与安全, 2019, 37(5):13.

[13] 张海妮. 基于蚁群优化算法的无人船艇航线自动生成及路径规划[J]. 舰船电子工程, 2019, 39(3):5.

[14] Xin J, Zhong J, Yang F, et al. An Improved Genetic Algorithm for Path-Planning of Unmanned Surface Vehicle[J]. Sensors, 2019, 19(11):2640-.

[15] 陈立家, 黄立文, 崔梅. 基于改进蚁群算法的船舶多约束最优航线设计[J]. 上海海事大学学报, 2017, 38(4): 5.

[16] Chen Z, Zhang Y, Zhang Y, et al. A Hybrid Path Planning Algorithm for Unmanned Surface Vehicles in Complex Environment With Dynamic Obstacles[J]. IEEE Access, 2019, PP(99): 1-1.

[17] 赵红. 基于改进势场蚁群算法的波浪动力滑翔器路径规划算法研究[D]. 青岛大学.

[18] 张金水, 何立居, 李启华,等. 蚁群算法和遗传算法结合的航线生成[J]. 中国航海, 2015(2): 5.

Global Path Planning Method for Intelligent Ship Based on Improved Ant Colony Algorithm

Zhao Songying1, Chen Xingye2

(1. Wuhan Institute of Marine Electric Propulsion, Wuhan 430064, China；2. Bohai Shipyard Group Limited Company, Huludao 125000, China)

TP332

A

1003-4862(2022)08-0072-05

2022-02-15

赵嵩郢（1996-），男，助理工程师。研究方向：智能船舶路径规划。E-mail: 15872427429@163.com