Abstract: Aiming at the problems of slow path-finding on large maps, poor route safety, and unsmooth route during route planning of surface ships in complex ocean environments, this paper proposes a route planning method with improved A* algorithm combined with electronic charts. First, an adaptive and improved heuristic function is proposed. When searching for nodes, the location information of the target node is added to speed up the search path of the A* algorithm. Second, the safe distance forcing the route to stay away from obstacles is added to solve the traditional A*. The algorithm finds the route along the edge of obstacles, which leads to the problem of poor air route safety. Finally, the original route is optimized twice. After the turning point is extracted from the original path, the straight line reachability of any two turning nodes is judged, and the turning nodes are separated. The actual distance is converted into a distance matrix. The Dijkstra algorithm is used to optimize the key turning points with a shorter route length, and finally the second-order Bezier curve is used to smooth the route turning points to meet the requirements of smooth and easy-to-follow routes. Simulation experi-ments show that, compared with the traditional A* algorithm, the path planned by the improved algorithm has the characteristics of faster path finding, shorter route distance, and higher route safety.

Key words: A* algorithm, adaptive heuristic function, Dijkstra algorithm, Bezier curve, electronic chart

摘要： 针对复杂海洋环境下水面舰艇航路规划时出现的大地图寻路速度慢、航路安全性差、航路不平滑等难题，结合电子海图提出了一种改进A*算法的航路规划方法。提出一种自适应的改进启发函数，在搜索节点时加入目标节点的方位信息，加快了A*算法搜索路径的速度；加入迫使航路远离障碍物的安全距离，解决了传统A*算法沿障碍物边缘寻路导致航路安全性差的问题；对原始航路进行二次优化，在对原始路径提取转折点后，通过判断任意两个转折节点的直线可达性，将转折节点之间的实际距离转化为距离矩阵，使用Dijkstra算法优选出航路长度更短的关键转折点，最终使用二阶贝塞尔曲线对航路转折处进行平滑处理，以满足航路平滑且易跟随的要求。仿真实验表明，相对于传统A*算法，改进算法规划的路径具有寻路速度更快、航路距离更短、航路安全性更高的特点。

关键词: A*算法, 自适应启发函数, Dijkstra算法, 贝塞尔曲线, 电子海图