Smoothed A* algorithm for practical unmanned surface vehicle path planning

Abstract

Abstract An effective path planning or route planning algorithm is essential for guiding unmanned surface vehicles (USVs) between way points or along a trajectory. The A* algorithm is one of the most efficient algorithms for calculating a safe route with the shortest distance cost. However, the route generated by the conventional A* algorithm is constrained by the resolution of the map and it may not be compatible with the non-holonomic constraint of the USV. In this paper an improved A* algorithm has been proposed and applied to the Springer USV. A new path smoothing process with three path smoothers has been developed to improve the performance of the generated route, reducing unnecessary ‘jags’, having no redundant waypoints and offering a more continuous route. Both simulation and experimental results show that the smoothed A* algorithm outperforms the conventional algorithm in both sparse and cluttered environments that have been uniformly rasterised. It has been demonstrated that the proposed improved A* route planning algorithm can be applied to the Springer USV providing promising results when tracking trajectories.