基于ADR-A*算法的智能船舶路径规划

Intelligent ship path planning based on ADR-A* algorithm

  • 摘要: 【目的】为提升复杂航行环境下智能船舶的自主路径规划能力,提出了一种自适应方向限制A*算法(Adaptive Direction Restriction-A*, ADR-A*)。【方法】首先,对海图环境进行预处理,提取障碍物边界并进行双层膨化,使船舶与障碍物保持安全距离。其次,改进A*算法的节点搜索方法,使其在路径规划过程中可根据终点自适应的调整搜索节点的方向与数量,提高算法的运行效率。最后,优化路径的安全检测方式,提取关键路径点,提高路径的安全性与平滑性。【结果】实验数据显示,相比于A*算法、Bi-A*算法和RRT*算法,ADR-A*算法减少了3.4%路径长度,优化了26.51%的运行时间,减少了50%的转向点数。【结论】实验结果表明,算法可以在复杂环境下规划出兼具安全性、经济性与平滑性的可航路经,验证了ADR-A*算法的自主路径规划能力,为智能船舶自主航线设计提供优化的解决方案与安全保障。

     

    Abstract: 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. MethodsFirstly, 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.

     

/

返回文章
返回