Ship Path Planning Based on Sparse A* Algorithm

Abstract

An improved version of the sparse A* algorithm is proposed to address the common issue of excessive expansion of nodes and failure to consider current ship status and parameters in traditional path planning algorithms. This algorithm considers factors such as initial position and orientation of the ship, safety range, and ship draft to determine the optimal obstacle-avoiding route from the current to the destination point for ship planning. A coordinate transformation algorithm is also applied to convert commonly used latitude and longitude coordinates of ship travel paths to easily utilized and analyzed Cartesian coordinates. The algorithm incorporates a hierarchical chart processing algorithm to handle multilayered chart data. Furthermore, the algorithm considers the impact of ship length on grid size and density when implementing chart gridification, adjusting the grid size and density accordingly based on ship length. Simulation results show that compared to traditional path planning algorithms, the sparse A* algorithm reduces the average number of path points by 25%, decreases the average maximum storage node number by 17%, and raises the average path turning angle by approximately 10°, effectively improving the safety of ship planning paths.

Keywords

Sparse A* algorithm / Path planning / Rasterization / Coordinate transformation / Image preprocessing