Ship path planning based on improved multi-scale A* algorithm of collision risk function

Abstract

Abstract To improve the safety of ship navigation in complex sea areas and reduce planning time while achieving optimal path planning. The paper proposes an improved A* algorithm that incorporates ship collision risk assessment. The paper utilizes multi-scale raster maps to divide the sea chart in the context of complex sea areas, and combines the Line-of-sight (LOS) algorithm to solve the zigzag paths that may appear in this planning context. Moreover, in order to improve the efficiency of optimal path planning in the context of complex sea areas while ensuring path safety, the paper proposes a collision risk function to optimize the determination of the cost of A* algorithm nodes, thereby enhancing the heuristic function of the A* algorithm. The improved A* algorithm can consider both path length and collision risk to plan the optimal path and to enhance the overall quality of the planning results. To verify the advantages of the improved algorithm proposed in the paper, the Zhoushan Islands sea area with complex environment is selected as the planning background for simulation study. The results show that the improved algorithm with the introduction of the collision risk function reduces the path planning time, the number of expanded nodes, and the path length by 30%, 11%, and 5.8%, respectively, compared with the original algorithm, which can effectively reduce the computational burden of the algorithm. This study provides a relatively complete and scientific route planning strategy for the study of the safe navigation of smart ships in complex sea areas.

Keywords

• Optimal path planning
• Improved A* algorithm
• Collision risk function
• Multi-scale nautical charts
• Safety of navigation in complex sea areas