Intelligent ship path planning based on ADR-A* algorithm

[Objectives] In order to improve the autonomous path planning ability of intelligent ships under complex navigation environment, and to improve the traditional A* algorithm's problem of planning paths in complex obstacle environments with many nodes and close distances to obstacles, an Adaptive Direction Restriction-A* (ADR-A*) algorithm is proposed. [Methods]Firstly, a Customizable Double-layer Boundary Expansion Strategy (CDBES) is proposed, which preprocesses the chart environment by extracting the obstacle boundaries, and generates the first-layer expanded chart and the second-layer expanded chart. The algorithm generates initial paths outside the second-layer expanded chart and eliminates redundant nodes outside the first-layer expanded chart. By customizing the buffer zone and warning zone, CDBES enables the planning algorithm to adjust the distance of the path points away from the obstacle boundary on demand while considering the real boundary characteristics of the obstacle, and provides a solution space for optimizing the path to eliminate redundant nodes, which lays a solid foundation for the overall path planning process. Secondly, the node search method of A* algorithm is improved, and the Adaptive Direction Restriction Priority-node Search Strategy (ADRPSS) is innovatively proposed. This strategy defines the neighboring nodes as second- priority nodes and priority nodes, improves the quality of search nodes by traversing the priority nodes, and further improves the search speed by eliminating search nodes with low relevance according to the endpoint position. ADRPSS can adaptively update the position and number of search nodes according to the information of the chart obstacles and the endpoint position, which strengthens the goal-directedness of the algorithm, and significantly enhances the efficiency of the path planning. Finally, a new Path Full Coverage Strategy (PFCS) is proposed to improve the path smoothness. This strategy treats the path as a region with a certain width instead of a single line, and conducts collision detection based on it to eliminate dangerous points and redundant nodes, which results in a more comprehensive algorithmic safety assessment, fewer retained nodes, and smoother paths. [Results] The experimental data show that compared with the A* algorithm, Bi-A* algorithm and RRT* algorithm, in chart I, the ADR-A* algorithm reduces the path length by 3.96%, optimizes the running time by 53.62. % and reduces the number of steering points by 83.33%. In chart II, the ADR-A* algorithm reduces the path length by 3.4%, optimizes the running time by 26.51%, and reduces the number of steering points by 50%. [Conclusions] The experimental results show that the algorithm can plan a navigable path with safety, economy and smoothness under the complex environment, which verifies the autonomous path planning capability of the ADR-A* algorithm, and provides an optimized solution and safety guarantee for the design of autonomous routes for intelligent ships.