Abstract: The Bidirectional Rapidly-exploring Random Tree(RRT-Connect) algorithm is limited by the long generated paths, the large number of turns and the low convergence speed in the path planning for mobile robots. To address the problem, an improved RRT-Connect algorithm is proposed. For the new nodes, the algorithm introduces a step of re-selecting the parent node that considers the ancestor point. The principle of triangle inequality is used to optimize the partial path length. At the same time, corner constraints are set for each generated new node to reduce path turning, and a dynamic step strategy is designed to accelerate the convergence of the improved algorithm. In the two-tree connection stage, the corner constraint and distance constraint are set at the connection part, and the nodes that share the same parent node are preferred for reconnection, making the two extended trees connect smoothly and rapidly. The experimental results show that the improved algorithm reduces not only the length of the planned path, but also the convergence time, and the quality of the generated path is also significantly improved.

Key words: mobile robot, path planning, RRT-Connect algorithm, path optimization, dynamic step length

摘要： 针对双向快速扩展随机树算法RRT-Connect在移动机器人路径规划中生成路径绕远、转折多、收敛速度慢等问题，提出一种改进RRT-Connect算法。对新节点引入考虑祖代点的重选父节点环节，利用三角不等式原理优化部分路径长度，对每一个新节点的生成设置转角约束以减小路径转折，同时设计一种动态步长策略以加快算法的收敛速度。在两树连接阶段，为使拓展树之间能够平滑且快速连接，在连接处设置转角约束和距离约束，并使用同父节点重连的连接方法。实验结果表明，改进算法能够缩短规划路径长度和收敛时间，生成的路径质量较改进前更优。

关键词: 移动机器人, 路径规划, RRT-Connect算法, 路径优化, 动态步长

CLC Number: 

• TP391.9