An Efficient RRT*-based Path Planning for Mobile Robot with Fast Convergence Rate

Abstract

In recent decades, sampling-based path planning methods have garnered increasing attention from researchers due to their excellent performance, particularly in nonlinear complex environments and high-dimensional spaces. As a classical sampling-based algorithm, RRT*, claims to achieve an optimal solution, but it has a slow convergence rate or takes an infinite amount of time to do so. To address this limitation, this study proposes a novel algorithm called D-RRT*. D-RRT* employs the concept of dynamic region sampling to enhance the efficiency of path generation by leveraging the tree environment as heuristic information. In contrast to the conventional uniform sampling approach, dynamic region sampling strategy increases the density of sampled points in the forward region near the target point, which significantly improves the search efficiency for feasible paths. Secondly, once the initial path is found, the algorithm extracts the directly accessible nodes of the path as key nodes. The key nodes are positioned to facilitate the discovery of the optimal path. By optimizing these key nodes, not only does the algorithm improve memory utilization, but it also reduces the number of iterations required to converge towards the optimal solution. Finally, the state-of-the art RRT-based algorithm, such as RRT*, Q-RRT* and F-RRT*, are used for comparison in two representative maps including real environments. Statistical analyses are conducted to demonstrate the robustness of the proposed algorithm. Simulation results indicated that the proposed algorithm yields better solutions for solving path planning problems in terms of algorithm convergence speed and path length.