基于改进RRT^(*)算法的移动机器人路径规划

Mobile robot path planning based on improved RRT^(*) algorithm

为解决渐进最优快速扩展随机树(RRT^(*))算法在特殊环境下(如狭窄通道)路径规划存在的内存占用多、规划效率低等问题,提出了一种基于目标约束采样和目标偏置扩展的改进RRT^(*)算法.首先,在采样上引入目标偏置策略,并对每次采样进行位置约束,使采样的目标导向性更强.然后,在新点扩展上摒弃了已有算法单纯朝着采样点扩展的思路,通过给采样点和目标点分配不同权重,使得每一次扩展同时由采样点和目标点共同决定,进而加快搜索速度.接着,采用三次B样条曲线对搜索到的路径进行平滑处理,以保证路径的可行性.最后,分别基于Matlab和V-REP平台对RRT^(*)算法和改进RRT^(*)算法进行了2D和3D的对比实验,实验结果验证了改进RRT^(*)算法的优越性和有效性.

An improved asymptotically optimal rapidly-exploring random tree(RRT^(*)) algorithm was proposed based on goal-biased constrained sampling and goal-biased extending,to address the problems of much memory usage,low planning efficiency of path planning in RRT^(*) algorithm under special environments,such as narrow passages.First,a goal-biased strategy was applied to sampling,and the position constraint was placed in each sample,so as to make sampling more goal-oriented than existing algorithms.Second,discarding the idea that the existing algorithm simply extended towards the sampling point on the new point extension,by assigning different weights to the sampling point and goal point,each extension could be decided by the sampling point and goal point at the same time,thus speeding up the search speed.Then,the cubic B-spline curve was used to smooth the searched path,ensuring the path feasibility.Finally,the 2 D and 3 D comparison experiments were conducted for the RRT^(*)algorithm and the improved RRT^(*) algorithm based on Matlab and V-REP respectively,and experiment results verified the superiority and effectiveness of the improved RRT^(*) algorithm.