基于改进蚁群算法的长航程无人船路径规划

计算机工程与科学 ›› 2024, Vol. 46 ›› Issue (10): 1835-1842.

基于改进蚁群算法的长航程无人船路径规划

乔珍,尹传忠,仇鑫

(上海海事大学交通运输学院，上海 201306)

收稿日期:2023-09-18 修回日期:2023-10-25 接受日期:2024-10-25 出版日期:2024-10-25 发布日期:2024-10-29
基金资助:
教育部人文社科规划项目(23A10254002)；国家自然科学基金(72074141)

Path planning of long-range unmanned ship based on improved ant colony algorithm

QIAO Zhen,YIN Chuan-zhong,QIU Xin

Addressing the issue of insufficient endurance for unmanned surface vehicles (USVs), an angle-priority ant colony optimization algorithm based on reinforcement learning is proposed to plan long-range paths for USVs. The Canny operator is employed to extract environmental information, and a combination of pixel grayscale weighted averaging and Gaussian filtering smoothing is applied to analyze the gradients in the image and extract edge features. The ginput function is then used to extract the edge coordinates. Based on the MAKLINK graph theory principle, the edge coordinates are defined as nodes, and the link lines and path points between nodes are used to represent the structure and connectivity of the navigation environment, thereby establishing a navigation environment model. By comparing the shortest paths obtained under the influence of different heuristic factors in the navigation environment, the optimal combination of heuristic factors for the algorithm is determined. An angle-priority mechanism is introduced to improve convergence speed, and reinforcement learning reward and penalty coefficients are utilized to adjust pheromone concen-tration, optimizing the algorithm flow and generating the optimal path. Experimental results demonstrate that the improved algorithm yields a USV navigation path with smooth corners, enhances the endurance of the USV by 4.6%, and accelerates the algorithm convergence speed by 68.9%.

Received:2023-09-18 Revised:2023-10-25 Accepted:2024-10-25 Online:2024-10-25 Published:2024-10-29

摘要/Abstract

摘要： 针对无人船续航能力不足问题，提出基于强化学习的角度优先改进蚁群算法，规划长航程无人船路径。采用Canny算子提取环境信息，应用像素的灰度加权平均及高斯滤波平滑处理的方法，分析图像中的梯度并提取边缘特征，采用ginput函数提取边缘坐标；基于MAKLINK图论原理，以边缘坐标为节点，定义节点之间的链接线与路径点表示航行环境的结构和连接关系，建立航行环境模型；对比航行环境中不同启发因子作用下取得的最短路径，确定算法最优启发因子组合；引入角度优先机制提高收敛速度、强化学习奖励与惩罚系数调节信息素浓度对算法流程进行优化，生成最优路径。实验结果显示，该改进算法得到的无人船航行路径拐角平滑，无人船续航能力提升4.6%，算法收敛速度提升68.9%。

关键词: 无人船, 续航能力, 路径规划, 环境建模, 改进蚁群算法

Abstract: unmanned ship；endurance;path planning;environmental modeling;improved ant colony algorithm

Key words: (College of Transport &, Communications,Shanghai Maritime University,Shanghai 201306,China)

乔珍, 尹传忠, 仇鑫. 基于改进蚁群算法的长航程无人船路径规划[J]. 计算机工程与科学, 2024, 46(10): 1835-1842.

QIAO Zhen, YIN Chuan-zhong, QIU Xin. Path planning of long-range unmanned ship based on improved ant colony algorithm[J]. Computer Engineering & Science, 2024, 46(10): 1835-1842.

[1]	安园园, 马晓宁. 改进遗传算法与多目标优化模型的航班路径规划[J]. 计算机工程与科学, 2024, 46(09): 1660-1666.
[2]	吕倩茹, 杨翔瑞, 蔡志平. 基于影响力地图的计算机兵棋推演路径规划[J]. 计算机工程与科学, 2024, 46(06): 1041-1049.
[3]	沈克宇, 游志宇, 刘永鑫. 基于拟合优先搜索的多场景自适应改进A*算法[J]. 计算机工程与科学, 2024, 46(01): 142-149.
[4]	李中华, 袁杰, 郭振宇. 基于信息启发的目标导向Bi-RRT机器人路径规划[J]. 计算机工程与科学, 2023, 45(12): 2237-2245.
[5]	张贝, 闵华松, 张新明. 差分变异和领地搜索的平衡优化算法及其机器人路径规划[J]. 计算机工程与科学, 2023, 45(11): 2078-2090.
[6]	张志远, 陈海进, 章一鸣. 基于局部障碍率预获取和双向父节点变更的A*算法优化[J]. 计算机工程与科学, 2023, 45(09): 1661-1669.
[7]	于家斌, 陈志豪, 邓维, 许继平, 赵峙尧, 王小艺. 一种无人巡航船遍历多目标点的路径规划算法研究[J]. 计算机工程与科学, 2023, 45(05): 840-848.
[8]	杨炳媛, 袁杰, 郭园园. 一种自适应鲸鱼快速优化算法[J]. 计算机工程与科学, 2023, 45(01): 145-153.
[9]	郭园园, 袁杰, 赵克刚. 基于改进A*算法和动态窗口法的机器人路径规划[J]. 计算机工程与科学, 2022, 44(07): 1273-1281.
[10]	赵广元, 赵英. 基于改进蚁群优化算法的养殖场机器人路径规划[J]. 计算机工程与科学, 2022, 44(05): 910-915.
[11]	赵炳巍, 贾峰, 曹岩, 孙瑜, 刘一鸿. 基于模拟退火算法的人工势场法路径规划研究[J]. 计算机工程与科学, 2022, 44(04): 746-752.
[12]	刘雨青, 向军, 曹守启. 基于改进蚁群算法的水下自主航行机器人路径规划[J]. 计算机工程与科学, 2022, 44(03): 536-544.
[13]	张志远, 陈海进. 基于动态矩阵的未知环境地图构建与路径规划[J]. 计算机工程与科学, 2022, 44(03): 563-570.
[14]	王俊喜, 陈桂芬. 能耗均衡的多跳多路径认知分层路由算法[J]. 计算机工程与科学, 2021, 43(03): 442-448.
[15]	王翼虎, 王思明. 基于改进粒子群算法的无人机路径规划[J]. 计算机工程与科学, 2020, 42(09): 1690-1696.