A Path Planning Algorithm for Incorporating Improved Oblique Four-neighborhood A* and Cubic B-spline Curve

In order to solve the problem that the traditional A* algorithm has too many eight-neighborhood search path nodes, which leads to slow search and path planning, a new path planning algorithm based on oblique four-neighborhood A* and cubic B-spline curve was proposed. Inspired by the traditional eight-neighborhood search, the original search paths in the the four directions of top, bottom, left, and right were deleted, and the search paths in the upper right, lower right, upper left and lower left directions were retained, so that the algorithm can search faster and the number of search path nodes was less. Cubic B-spline curve was introduced to optimize the sharp inflection points on the path and make the path smoother. Experimental verification was conducted on three maps with different resolutions and obstacle rates using the proposed algorithm and two other algorithms. The results show that compared with the traditional A* algorithm, the search time of the improved oblique four-neighborhood A* algorithm is reduced by 83.4%, and the number of path node is reduced by 89.7%. The cubic B-spline curve introduced makes the path planned by the oblique four-neighborhood A* algorithm smoother, and the proposed algorithm can greatly improve the effectiveness of path search and planning.