An Improved A-Star Algorithm for Global Path Planning of Unmanned Surface Vehicle

Conventional A-Star (A∗) algorithm exists some problems, such as multiple extended nodes, slow convergence and weak real-time performance, in marine path planning of unmanned surface vehicles (USVs). To solve the aforementioned problems, this study proposes an adaptive-direction and variable-step A∗ algorithm. Firstly, a gridded environment model is established based on S57 electronic navigation chart. Considering the marine scenes, the obstacles and water flow constraints are added into the evaluation function. Secondly, an adaptive direction method and a variable step strategy are proposed, and the bi-directional search method is combined with the proposed method to form an improved A∗ algorithm. An evaluation function for assessing redundancy is designed to optimize the path to suppress the influence of redundant and non-smooth paths. Finally, some visualized simulated experiments are set to verify the performance of the proposed method. And three different scenes ranging from simple to complex are selected for path planning experiments. The results show that the improved algorithm outperforms the conventional A∗ algorithm, artificial potential field algorithm and particle swarm optimization algorithm. It can effectively reduce extended nodes, and has good real-time performance. In addition, it has the robustness and faster convergence that can be used in different path-planning scenes.