融合改进斜四邻域A^(*)与三次B样条曲线的路径规划算法

A Path Planning Algorithm for Incorporating Improved Oblique Fourneighborhood A^(*)and Cubic B-spline Curve

针对传统A^(*)算法八邻域搜索路径节点多导致搜索及规划路径速度慢的问题,提出1种融合改进斜四邻域A^(*)与三次B样条曲线的路径规划算法。在传统八邻域搜索启发下,删除原本上下左右4个方向上的搜索路径,保留右上、右下、左上及左下4个方向的搜索路径,使算法在搜索时速度更快,搜索路径节点数更少;引入三次B样条曲线,优化路径上的尖锐拐点,使路径更平滑。采用提出的算法与其他2种算法在3种不同分辨率及不同障碍率的地图上进行实验验证。结果表明:相比于传统A^(*)算法,改进斜四邻域A^(*)算法的搜索时间缩短83.4%,路径节点数减少89.7%;引入的三次B样条曲线使斜四邻域A^(*)算法规划出的路径更平滑,提出的算法可极大提高路径搜索及规划的有效性。

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.