ε-动态三角采样和过渡递归回溯的RRT算法

RRT algorithm based onε-dynamic triangular region sampling and transition recursive backtracking

针对快速搜索随机树(rapidly exploring random trees,RRT)路径规划算法存在搜索效率低、路径节点多以及路径质量差等问题,提出了ε-动态三角采样区域和过渡递归回溯的RRT路径规划算法(ε-dynamic triangular sampling region and transition recursive backtracking,ε-DT-RRT)。由于RRT算法采样点随机性大,因此通过构建ε-动态三角采样区域,利用树中节点划分采样空间,减少低价值区域搜索次数,增强环境探索能力,提升采样效率。在此基础上,提出了基于障碍物生成过渡节点的方法,当新点与树中最近点之间存在障碍时,将会生成一个过渡节点,增加获取最优节点概率。最后通过递归回溯祖节点方法进一步减少路径中的冗余点,缩短了路径长度。实验结果表明:ε-DT-RRT算法在规划时间、路径质量、迭代次数等方面均优于对比算法。

Aiming at the problems of RRT path planning algorithm,such as low search efficiency,excessive path nodes and poor path quality,a RRT path planning algorithm based onε-dynamic triangular sampling region and transitional recursive backtracking(ε-DT-RRT)is proposed.Due to the strong randomness of the RRT algorithm s sampling points,ε-dynamic triangular sampling area is constructed,and the sampling space is divided by nodes in the tree to reduce the number of low value area searches,enhance environmental exploration ability,and improve sampling efficiency.On this basis,a method of generating transition nodes based on obstacles is proposed.When there is an obstacle between the new point and the nearest point in the tree,a transition node will be generated to increase the probability of obtaining the optimal node.Finally,the redundant points in the path are further reduced by recursively backtracking the parent node method,and the path length is shortened.The experimental results show that the improved algorithm is superior to comparative in terms of planning time,path quality,number of iterations.