Intelligent ship path planning based on ADR-A* algorithm

To enhance the autonomous path planning ability of intelligent ships in complex navigation environment, and address the limitations of the traditional A* algorithm in planning paths for environments with numerous obstacles and tightly spaced nodes, an adaptive direction restriction-A* (ADR-A*) algorithm is proposed.

First, a customizable double-layer boundary expansion strategy (CDBES) is proposed, which preprocesses the chart environment by extracting the obstacle boundaries. This strategy generates a first-layer expanded chart and a 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 path planning algorithm to adjust the distance of the path points away from the obstacle boundary as needed, while considering the real boundary characteristics of the obstacle. It also provides a solution space for optimizing the path and eliminating redundant nodes, thus laying a solid foundation for the overall path planning process. Second, the node search method of the A* algorithm is improved with the innovative introduction of the adaptive direction restriction priority-node search strategy (ADRPSS). This strategy classifies neighboring nodes into second-priority and priority nodes, enhancing the quality of the search by traversing the priority nodes, and further improves the search speed by eliminating nodes with low relevance based on the endpoint position. ADRPSS can adaptively update the position and number of search nodes according to information from the chart's obstacles and the endpoint, strengthening the goal-directed nature of the algorithm and significantly enhancing the efficiency of the path planning. Finally, a new path full coverage strategy (PFCS) is proposed to improve path smoothness. This strategy treats the path as a region with a certain width instead of a single line, and conducts collision detection within this region to eliminate dangerous points and redundant nodes. This results in a more comprehensive algorithmic safety assessment, fewer retained nodes, and smoother paths.

The experimental data show that, compared with the A*, Bi-A*, ERA*, and RRT* algorithms, in nautical chart 1, the proposed ADR-A* algorithm reduces the path length by at least 3.56%, reduces the running time by at least 60.13%, and decreases the number of steering points by at least 76.71%. In nautical chart 2, the proposed ADR-A* algorithm reduces the path length by at least 3.36%, reduces the running time by at least 11.16%, and decreases the number of steering points by at least 53.85%.

The experimental results show that the algorithm can plan a navigable path with safety, efficiency and smoothness in a complex environment. These findings validate the autonomous path planning capability of the ADR-A* algorithm and provide an optimized solution and safety assurance for the design of autonomous routes for intelligent ships.