机器人路径规划中快速扩展随机树算法的改进研究

Research on Improvement of Rapidly Exploring Random Tree Algorithm in Robot Path Planning

针对基本快速扩展随机树(RRT)算法在路径规划中具有树的扩展随机性大、冗余节点多、容易在目标点周围发生振荡、规划的路径较长等问题,提出了一种改进的RRT算法。该算法首先采用目标偏向策略,通过引入动态权重系数使树尽可能地在向目标点进行扩展的同时又能够即时地避开障碍物;利用自适应扩展步长减少树在目标点附近的振荡;最后,对路径进行剪枝处理,并用三次B样条曲线对剪枝后的路径进行平滑处理。仿真分析的结果表明,与基本RRT算法相比,改进的RRT算法有效减少了冗余节点数,规划的路径更短,减少了19.56%,同时规划时间大大降低,减少了54.08%,有效地提高了路径规划的效率。

In order to solve the problems of the basic rapidly exploring random tree(RRT)algorithm in path planning,such as large randomness,excessive redundant nodes,oscillation around the target point and long planned paths,an improved RRT algorithm was proposed.Firstly,the algorithm applies the target bias strategy and introduces dynamic weight coefficient to make the tree expand to the target point as much as possible while avoiding obstacles instantly.Next,the oscillation of the tree near the target point is reduced by using the adaptive expansion step.Finally,the path is pruned and smoothed by cubic B-spline curves.Simulation results show that compared with the basic RRT algorithm,the improved RRT algorithm effectively reduces the number of redundant nodes,the planned path is shorter by 19.56%,and the planning time is greatly reduced by 54.08%,which effectively improves the efficiency of path planning.