一种双向目标RRT路径规划算法研究

Research on Route Planning Algorithm of Bidirectional Target RRT and Dijkstra

鉴于双向快速搜索随机树算法在复杂环境路径规划中存在目标导向性低、路径冗长且曲折的问题,提出了一种双向目标RRT融合Dijkstra算法,其先采用目标约束采样和偏置扩展策略,提高采样的目标导向性;再融合Dijkstra算法去除双向目标RRT可行路径中的冗余点,获取最短路径;最后对优化路径进行平滑处理,得到一条最优可行路径。在随机障碍物、狭窄障碍物和迷宫障碍物三种情境下对双向目标RRT融合Dijkstra进行数例实验,结果表明融合改进后的B-RRT算法相较于传统的B-RRT算法,节点利用率提高1倍,扩展节点减少49%,搜索时间缩短33%,路径缩短7.9%。

In this paper, a bidirectional RRT fusion Dijkstra algorithm is proposed, because the bidirectional fast search random tree algorithm has the problems of low target orientation, long path and tortuous path planning in a complex environment. In this algorithm, target-constrained sampling and bias expansion strategy are adopted to improve the target orientation of sampling. Then the Dijkstra algorithm removes the redundant points in the feasible path of bidirectional target RRT to obtain the shortest path. Finally, the optimal path is smoothed and an optimal feasible path is obtained. Several experiments were carried out on the bidirectional RRT fusion Dijkstra under three situations of random obstacles, narrow obstacles and maze obstacles. The results show that compared with the traditional B-RRT algorithm, the improved fusion B-RRT algorithm can improve the node utilization by 1 times, reduce the extension nodes by 49%,shorten the search time by 33%,and shorten the path by 7.9%.