基于改进渐进最优的双向快速扩展随机树的移动机器人路径规划算法

Path planning of mobile robot based on improved asymptotically-optimal bidirectional rapidly-exploring random tree algorithm

针对带启发式的快速扩展随机树(RRT-Connect)算法路径生成的随机性以及渐进最优的双向快速扩展随机树(B-RRT~*)算法收敛速度的缓慢性,提出了一种基于B-RRT~*改进的高效路径规划算法(EB-RRT~*)。首先引入一种智能采样函数,使随机树的扩展更具方向性,从而减少寻路时间,并提高路径的平滑性;其次在B-RRT~*算法的基础上,在EB-RRT~*算法中加入了一种快速扩展策略,使改进后的算法在自由空间中使用RRT-Connect算法的扩展方式进行快速扩展,而在障碍物空间则使用改进的渐进最优的快速扩展随机树(RRT~*)算法进行扩展,在提高扩展效率的同时避免算法陷入局部最优。将EB-RRT~*算法分别与快速扩展随机树(RRT)、RRT-Connect、RRT~*和B-RRT~*算法进行仿真对比,仿真结果表明,改进后的算法在路径规划效率及路径平滑性方面均明显优于其他算法;且相对于B-RRT~*算法,其在路径规划时间上降低了68.3%,在迭代次数上减少了48.6%。

To overcome the randomness of RRT-Connect and slow convergence of B-RRT~*(asymptotically-optimal Bidirectional Rapidly-exploring Random Tree) in path generation, an efficient path planning algorithm based on B-RRT~*, abbreviated as EB-RRT~*, was proposed. Firstly, an intelligent sampling function was intriduced to achieve more directional expansion of random tree, which could improve the smoothness of path and reduce the seek time. A rapidly-exploring strategy was also added in EB-RRT~* by which RRT-Connect exploration mode was adopted to ensure rapidly expanding in the free space and improved asymptotically-optimal Rapidly-exploring Random Tree(RRT~*) algorithm was adopted to prevent trapped in local optimum in the obstacle space. Finally, EB-RRT~* algorithm was compared with Rapidly-exploring Random Tree(RRT), RRT-Connect, RRT~* and B-RRT~* algorithms. The simulation results show that the improved algorithm is superior to other algorithms in the efficiency and smoothness of path planning. It reduced the path planning time by 68.3% and the number of iterations by 48.6% compared with B-RRT~* algorithm.