融合改进RRT和Dijkstra算法的机器人动态路径规划

Robot Path Planning Based on Improve RRT and Dijkstra Approach

针对传统RRT算法在规划中随机性过大,节点利用率低且得出的路径并非最优等问题,从3个方面进行改进。首先,针对RRT在随机点采样过程中无方向性的问题,设置目标节点采样率,每次采样时目标点有几率成为采样点,使路径可以快速接近目标点;其次,动态设置步长使机器人能根据周围障碍物数量动态调整步长,减少迭代步数;最后,在得到RRT算法规划出的一条可行路径后,向周围扩展可行区域,将可行区域栅格化,通过Dijkstra算法找出可行区域中的最短路线,优化RRT算法得出的路线。最后将所获得的全局路径分段采用动态窗口算法。将RRT-Dijkstra融合算法与RRT算法、Dijkstra算法以及动态窗口算法在路径拐点数量以及路径长度等方面进行对比。实验表明,RRT-Dijkstra融合算法更高效,得到的路径更优。结合动态窗口算法后且能实现动态避障。

Aiming at the problems that the traditional RRT algorithm has too large randomness in planning, low node utilization and non-optimal paths, the following three aspects are improved.First of all, in view of the problem that RRT has no direction in the random point sampling process, the sampling rate of the target node is set, and the target point has a chance to become the sampling point in each sampling, so that the path can quickly approach the target point.Second, dynamically setting the step size enables the robot to dynamically adjust the step size according to the number of surrounding obstacles, reducing the number of iteration steps.Finally, after obtaining a feasible path planned by the RRT algorithm, expand the feasible area to the surrounding area, rasterize the feasible area, find the shortest route in the feasible area through the Dijkstra algorithm, and optimize the route obtained by the RRT algorithm.Finally, the obtained global path is segmented by dynamic window algorithm.The RRT-Dijkstra fusion algorithm is compared with the RRT algorithm, Dijkstra algorithm and dynamic window algorithm in terms of the number of path inflection points and path length.Experiments show that the RRT-Dijkstra fusion algorithm is more efficient and the resulting path is better.Combined with the dynamic window algorithm, it can realize dynamic obstacle avoidance.