Abstract:
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 curves was proposed. Inspired by the traditional eight-neighborhood search, the original search path in the upper, lower, upper and lower left directions was deleted, and the search path in the upper right, lower right, upper left and lower left directions was 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. The proposed algorithm was tested on 3 maps with different resolution and obstacle rate. The results show that compared with the traditional A* algorithm, the search time of the improved oblique quad-neighborhood A* algorithm is reduced by 83.4%, and the number of path nodes is reduced by 89.7%. The cubic B-spline curve introduced makes the path planned by the oblique quadrineighborhood A* algorithm smoother, and the proposed algorithm greatly improves the effectiveness of path search and planning.