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

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