Abstract: Aiming at the problems of large randomness, low algorithm efficiency, long search time, and redundant search paths in the path planning process of the traditional RRT-Connect algorithm, a greedy RRT path planning algorithm with bidirectional expansion of the same root is proposed. First of all, the method of expanding from the starting point to the ending point is changed to the middle point of the line connecting the starting point and the ending point to expand to the starting point and the ending point at the same time. At the same time, the gravitational field and the extreme greedy algorithm are superimposed when expanding the node, so that the tree can quickly move to the starting point and the ending point. Diffusion in the direction speeds up the generation of the path. Secondly, the generated path is pruned and optimized, redundant nodes are deleted in the path, and the path length is shortened. The improved algorithm is simulated and compared in three different environments, and the results show that the performance of the proposed algorithm is better than the traditional RRT-Connect algorithm and its related derivatives. Finally, the improved RRT-Connect algorithm is applied to the actual mobile robot, which further proves the practicability and effectiveness of the improved algorithm.

Key words: bidirectional expansion of the same root, gravitational field, greedy algorithm, pruning optimization

摘要： 针对传统RRT-Connect算法路径规划过程中随机性大、算法效率低、搜索时间长、搜索路径冗长等问题，提出一种同根双向扩展的贪心RRT路径规划算法。将由起点开始向终点进行扩展的方式改为由起点与终点连线的中间点同时向起点和终点进行双向扩展，同时在扩展节点时叠加引力场和极度贪心算法，使树快速向起点和终点的方向扩散，加速路径的生成。对生成的路径进行剪枝优化处理，删除路径中冗余的节点，缩短路径长度。在三种不同环境中对改进算法进行仿真对比实验，结果表明所提算法相关性能优于传统RRT-Connect算法及其相关衍生算法。将改进RRT-Connect算法应用在实际移动机器人中，进一步证明改进算法的实用性和有效性。

关键词: 同根双向扩展, 引力场, 贪心算法, 剪枝优化处理