Improved D* Lite Algorithm for Ship Route Planning

Abstract

To address the issue of intelligent ship route planning, a ship planning method based on the improved D* Lite algorithm is proposed. Firstly, a navigation environment grid map is constructed using the acquired meteorological and hydrological datasets. The grids are divided into navigable and non-navigable according to navigation requirements, and a route planning model is built. Secondly, the heuristic function and the path function of the D* Lite algorithm are improved. The heuristic function is optimized and weighted, and a risk factor is introduced into the path function to enhance efficiency of path planning while maintaining a safe distance between the planned route and obstacles. Finally, by dynamically adjusting the search step length and the selectable directions of the D* Lite algorithm, the number of waypoints is reduced, and the voyage of the planned route is shortened, resulting in a smooth and collision-free route of ships. The effectiveness of the proposed algorithm is verified through three sets of simulation experiments. The simulation results show that the proposed method in this paper is more suitable for ship route planning and ship maneuvering in practice and can effectively avoid non-navigable grids while optimizing path length, path smoothness, and computation time, making the routes more aligned with actual navigation tasks.

Keywords

• intelligent route planning
• improved D* lite algorithm
• route optimization
• curve optimization