﻿ 复杂开放水域的无人船避障路线蚁群规划算法
 舰船科学技术  2023, Vol. 45 Issue (20): 101-104    DOI: 10.3404/j.issn.1672-7649.2023.20.019 PDF

Ant colony planning algorithm for ship obstacle avoidance route in complex open waters
CHEN Gai-xia, YE Xiao-ran
Hebi Institute of Engineering and Technology, Henan Polytechnic University, Hebi 458030, China
Abstract: In order to improve the obstacle avoidance effect and obtain the shortest obstacle avoidance route with fewer inflection points, an ant colony programming algorithm for ship obstacle avoidance route in complex open waters is designed. On the basis of the raster processing of obstacles in complex open waters, based on the basic principle of ant colony algorithm, the comprehensive heuristic information combining the potential force and the position information of the target point is obtained, the pheromone concentration increment is optimized, the state transition probability is improved, and the ant colony algorithm is improved to realize the obstacle avoidance route planning of ships. The experimental results show that the algorithm can realize the planning of ship obstacle avoidance route, and the length of the designed obstacle avoidance route is reduced by 40.39% and the number of inflection points is reduced by 60% compared with that before improvement.
Key words: complex open water bodies     obstacle avoidance route planning     ant colony     potential field resultant force     pheromone concentration     state transition probability
0 引　言

1 无人船避障路线蚁群规划算法 1.1 复杂开放水域障碍物栅格化处理

 图 1 障碍物的栅格化处理 Fig. 1 Grid processing of obstacles

1.2 蚁群算法

 $P_{ij}^k = \frac{{{{\left[ {{\tau _{ij}}\left( t \right)} \right]}^\alpha } \times {{\left[ {{\rho _{ij}}\left( t \right)} \right]}^\beta }}}{{{k_{allow}}}} \text{。}$ (1)

 $\tau = \left( {1 - \lambda } \right){\tau _{ij}} + \Delta {\tau _{ij}} \times P_{ij}^k。$ (2)

 $\Delta {\tau }_{ij}^{k}=\left\{\begin{array}{l}\dfrac{Q}{{L}_{k}}\times \tau ,第k只蚂蚁由i节点移动到j节点，\\ 0\text{，}{\rm{other}}。\end{array}\right.$ (3)

1.3 基于改进蚁群算法的无人船避障路线规划 1.3.1 启发信息的改进

 ${\rho _s}\left( t \right) = {C^{{F_{tol}} \times \cos \theta }} \times \Delta \tau _{ij}^k 。$ (4)

${\rho _s}\left( t \right)$ ${\rho _{ij}}\left( t \right)$ 相乘即可确定考虑势场信息与距离信息的启发信息，计算公式为：

 ${\rho '_{ij}}\left( t \right) = {\rho _s}\left( t \right) \times {\rho _{ij}}\left( t \right)。$ (5)

1.3.2 信息素浓度增量优化

 $\Delta \tau _{ij}^k\left( t \right) = \frac{{{Q^*} \times {{\rho '}_{ij}}\left( t \right)}}{{{L_{n,k}} \times f\left( {{\theta _{ij}}} \right)}}\text{。}$ (6)

1.3.3 状态转移概率的改进

 $P_{ij}^k\left(t\right)=\Delta\tau_{ij}^k\left(t\right)\times\left(\frac{T_j-O_j}{S_j}\right)^{\gamma}。$ (7)

2 实验分析

 图 2 复杂开放水域航行环境建模结果 Fig. 2 Modeling results of complex open water navigation environment

 图 3 启发参数 $\alpha$ 对无人船避障路线规划效果影响 Fig. 3 Influence of heuristic parameters on the planning effect of ship obstacle avoidance routes

 图 4 启发参数 $\beta$ 对无人船避障路线规划效果影响 Fig. 4 Influence of heuristic parameters on the planning effect of ship obstacle avoidance routes

 图 5 算法改进前后避障路线规划结果对比分析 Fig. 5 Comparative analysis of obstacle avoidance route planning results before and after algorithm improvement

 图 6 改进前后算法性能对比分析 Fig. 6 Comparative analysis of algorithm performance before and after improvement

3 结　语

1）蚁群规模为80，启发参数 $\alpha$ $\beta$ 分别为1和4时，设计的无人船避障路线最短。

2）本文算法可实现无人船避障路线规划，设计的避障路线长度比改进前降低了40.39%、拐点数减少60%。

 [1] 杨琪森, 王慎执, 桑金楠, 等. 复杂开放水域下智能船舶路径规划与避障方法[J]. 计算机集成制造系统, 2022, 28(7): 2030-2040. Yang Qi-sen, Wang Shen-zhi, Sang Jin-nan, et al. Path planning and real-time obstacle avoidance methods of intelligent ships in complex open water environment[J]. Computer Integrated Manufacturing Systems, 2022, 28(7): 2030-2040. DOI:10.13196/j.cims.2022.07.009 [2] 白响恩, 江明哲, 徐笑锋, 等. 基于双向搜索的改进蚁群算法的船舶路径规划[J]. 中国航海, 2022, 45(3): 13-20. Bai Xiang’en, Jiang Ming-zhe, Xu Xiao-feng, et al. Ship route planning using improved ant colony algorithm with bi-directional search strategy[J]. Navigation of China, 2022, 45(3): 13-20. DOI:10.3969/j.issn.1000-4653.2022.03.003 [3] 殷绍伟, 彭力, 戴菲菲. 融合改进A~*蚁群和滚动窗口法的平滑路径规划[J]. 计算机科学与探索, 2021, 15(10): 1969-1979. Yin Shao-wei, Peng Li, Dai Fei-fei. Smooth path planning by integrating improved A~* ant colony and rolling window method[J]. Computer Science and Exploration, 2021, 15(10): 1969-1979. DOI:10.3778/j.issn.1673-9418.2011061 [4] 张子然, 黄卫华, 陈阳, 等. 基于双向搜索的改进蚁群路径规划算法[J]. 计算机工程与应用, 2021, 57(21): 270-277. Zhang Zi-ran, Huang Wei-hua, Chen Yang, et al. Improved ant colony path planning algorithm based on bidirectional search[J]. Computer Engineering and Applications, 2021, 57(21): 270-277. DOI:10.3778/j.issn.1002-8331.2106-0061 [5] 李清亮, 李彬, 孙国皓, 等. 基于精确罚函数的无人艇航迹规划和自动避障算法[J]. 中国舰船研究, 2021, 16(1): 89-95. Li Qing-liang, Li Bin, Sun Guo-hao, et al. Trajectory planning and automatic obstacle avoidance algorithm for unmanned surface vehicle based on exact penalty function[J]. Chinese Journal of Ship Research, 2021, 16(1): 89-95. DOI:10.19693/j.issn.1673-3185.02209 [6] 吕进锋, 马建伟, 李晓静. 基于改进的随机路径图及和声算法的舰船航线规划[J]. 控制理论与应用, 2020, 37(12): 2551-2559. Lv Jin-feng, Ma Jian-wei, Li Xiao-jing. Route planning based on improved probabilistic roadmap and harmony search[J]. Control Theory & Applications, 2020, 37(12): 2551-2559. [7] 童帮裕, 胡坚堃. 基于改进蚁群算法的船舶冰区航行路径规划[J]. 中国航海, 2020, 43(1): 24-28. Tong Bang-yu, Hu Jian-kun. Improved ant colony optimization for navigation path planning in ice zone[J]. Navigation of China, 2020, 43(1): 24-28. DOI:10.3969/j.issn.1000-4653.2020.01.005 [8] 马庆禄, 黄光浩. 基于改进人工势场法的自动驾驶路径规划方法[J]. 计算机仿真, 2022, 39(8): 160-165. Ma Qing-lu, Huang Guang-hao. Automatic driving path planning based on improved artificial potential field method[J]. Computer Simulation, 2022, 39(8): 160-165. DOI:10.3969/j.issn.1006-9348.2022.08.030