双约束RRT算法的移动机器人路径规划

Path planning using duple constraints RRT algorithm for mobile robot

针对快速扩展随机树(RRT)算法和目标偏置RRT(GB-RRT)算法存在较多冗余节点、搜索时间较长、路径转角幅度大、不适于移动机器人的实际运行等问题,提出一种双约束RRT(Duple Constraints RRT,DC-RRT)算法。该算法基于目标偏置思想,使用随机函数进行了多次采样,形成概率采样池,通过采样池中的点与规划终点的距离来约束采样点,能有效减少不必要的空间搜索,减少采样点及路径包含的节点个数;考虑移动机器人的前轮转角,提出用包含长度和角度的新节点生成函数来约束新节点,使规划路径转角幅度更小,更符合移动机器人的实际运行。将DC-RRT算法与RRT、GB-RRT算法从路径规划的成功率、有效节点占比、完成时间、转折角度以及路径长度五个方面进行比较,仿真结果表明,在保证规划成功率的同时,DC-RRT算法显著减少了无效搜索,缩短了寻路时间,规划路径更平滑,有效提升了算法的性能。

Aiming at the problems that the Rapidly Expanding Random Tree(RRT) algorithm and the Goal Biased RRT(GB-RRT) algorithm have many redundant nodes, long search time, large path angle, and are not suitable for the actual operation of the mobile robot, a Duple Constraints RRT(DC-RRT) algorithm is proposed.Based on the idea of target bias, the algorithm used random functions to sample multiple times to form a probability sampling pool, and constrained the sampling points by the distance between the points in the sampling pool and the planned end point, effectively reducing unnecessary space searches, reducing the number of sampling points and the number of nodes included in the path.Considering the rotation angle of the front wheel of the mobile robot, a new node generating function including length and angle was proposed to constrain the new node, so that the planned path rotation angle was smaller, and the path angle was more consistent with the actual operation of the mobile robot.The DC-RRT,RRT and Goal-Bias RRT algorithm were compared from the success rate of the path planning, the proportion of effective nodes, the completion time, turning angle and the length of the path.Simulation results show that, while ensuring the success rate of planning, the DC-RRT algorithm significantly reduces the invalid search, shortens the path-finding time, makes the planned path smoother, and effectively improves the performance of the algorithm.