为解决传统A*算法搜索效率低、路径拐点多、贴近障碍物等问题，结合无人艇特性，提出一种改进A*算法。首先，引入人工势场法对评价函数进行改进，考虑障碍物斥力场的影响，提高路径安全性；其次，通过改进节点遍历方式和双向搜索机制减少搜索节点，提高路径规划速度；最后，对生成路径进行二次优化，删除冗余节点，提升路径平滑性。仿真结果表明，开阔水域场景下改进A*算法在安全性、路径长度、路径平滑性、规划速度方面均有较大提升；岛礁区场景下改进A*算法虽然在路径长度上有所牺牲，但安全性、路径平滑性、规划速度方面具有明显优势。研究成果可为无人艇全局路径规划问题研究提供一定的参考。
In order to solve the problems of the traditional A* algorithm, such as low search efficiency, many inflection points and close to obstacles, an improved A* algorithm is proposed based on the navigation characteristics of unmanned surface vehicles. Firstly, the artificial potential field method is put in place to improve the evaluation function, and the safety of the path is improved by considering the influence of the obstacles repulsion fields. Secondly, by improving the traversal mode of nodes and bidirectional search mechanism, the search nodes are reduced and the path planning speed is improved. Finally, in order to enhance path smoothness, the redundant nodes are deleted to optimize the path. The simulation results show that the improved A* algorithm in open water has a significant improvement in safety, path length, path smoothness and planning speed. Although the improved A* algorithm in the island regions has some sacrifices in the path length, it has obvious advantages in terms of safety, path smoothness and planning speed. The research results can provide a certain reference for the research of global path planning of unmanned surface vehicles.
2025,47(5): 97-102 收稿日期：2024-2-27
DOI：10.3404/j.issn.1672-7649.2025.05.015
分类号：U675.79
基金项目：国家自然科学基金委员会联合基金项目（U214120082）；武警海警学院院级科研项目（2023YJXM14）
作者简介：梅梦磊（1992 – ），男，硕士，讲师，研究方向为船舶智能化
参考文献：
[1] PU H Y, LIU Y , LUO J, et al. Development of an unmanned surface vehicle for the emergency response mission of the 'sanchi' oil tanker collision and explosion accident[J]. Applied Sciences, 2020, 10 (8): 2704.
[2] 薛双飞, 谢磊, 王树武, 等. 海上风电场区船舶A*避碰寻路算法[J]. 中国航海, 2018, 41(2): 21-25.
XUE X F, XIE L, WANG S W, et al. A* algorithm for ships avoiding offshore wind farm facility[J]. Navigation of China, 2018, 41(2): 21-25.
[3] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1: 269-271.
[4] HART P E , NILSSON N J , RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science & Cybernetics, 1972, 4(2): 28-29.
[5] LAVALLE S M. Rapidly-exploring random trees: a new tool for path planning[R]. 1999.
[6] SONG C H. Global path planning method for USV system based on improved ant colony algorithm[J]. Applie Mechanics and Materials, 2014, 568-570: 785-788.
[7] LAMINI C, BENHLIMA S, ELBEKRI A. Genetic algorithm based approach for autonomous mobile robot path planning[J]. Procedia Computer Science, 2018, 127: 180-189.
[8] MA Y, HU M Q, YAN X P. Multi-objective path planning for unmanned surface vehicle with currents effects[J]. ISA Transactions, 2018, 75(2): 137-156.
[9] 武善平, 黄炎焱, 陈天德. 改进A*算法的水面舰艇静态航路规划[J]. 计算机工程与应用, 2022, 58(23): 307-315.
WU S P, HUANG Y Y, CHEN T D. Static route planning of surface ships based on improved A* algorithm[J]. Computer Engineering and Applications, 2022, 58(23): 307-315.
[10] 任晔, 王俊雄, 张小卿. 基于多因素改进A*算法的AUV路径规划研究[J]. 舰船科学技术, 2022, 44(11): 58-62.
REN Y, WANG J X, ZHANG X Q. Research on AUV path planning based on multi-factor improved A* algorithm[J]. Ship Science and Technology, 2022, 44(11): 58-62.
[11] 张浩, 庞宁林, 胡安康, 等. 基于改进A*算法融合角度信息的船舶路径规划[J]. 上海海事大学学报, 2023, 44(2): 6-10.
ZHANG H, PANG N L, HU A K, et al. Ship path planning based on improved A* algorithm and adding angle information[J]. Journal of Shanghai Maritime University, 2023, 44(2): 6-10.
[12] 冯辉, 杨皓杰, 徐海祥, 等. 基于改进变步长稀疏A*算法的无人艇路径规划方法[J/OL]. 武汉理工大学学报(交通科学与工程版) [2023-07-05].
FENG H, YANG H J, XU H X, et al. Path planning for unmanned surface vessel based on improved variable step sparse A* algorithm[J/OL]. Journal of Wuhan University of Technology (Transportation Science & Engineering)[2023-07-05].
[13] WANG Y, LIANG X, Li B, et al. Research and implementation of global path planning for unmanned surface vehicle based on electronic chart[C]// International Conference on Mechatronics and Intelligent Robotics, 2017.
[14] SONG R, LIU Y, BUCKNALL R. Smoothed A* algorithm for practical unmanned surface vehicle path planning[J]. Applied Ocean Research, 2019, 83: 9-20.
[15] 徐小强, 杨家鼎, 冒燕, 等. 基于速度障碍和改进人工势场算法的无人艇路径规划研究[J]. 武汉理工大学学报, 2022, 44(7): 96-102.
XU X Q, YANG J D, MAO Y, et al. Study on path planning of usv based on velocity obstacle and improved artificial potential field algorithm[J]. Journal of Wuhan University of Technology, 2022, 44(7): 96-102.
[16] DANIEL K, NASH A, KOENIG S, et al. Theta*: any-angle path planning on grids[J]. Journal of Artificial Intelligence Research, 2010, 39(1): 533-579.
