Accelerating RRT* convergence with novel nonuniform and uniform sampling approach

摘要

Path planning plays a crucial role in autonomous mobile robotics. Sampling-based path planners are widely and frequently employed to generate collision-free paths between a start and goal location. Due to its asymptotic optimality, the optimal rapidly-exploring random tree (RRT*) algorithm is the most widely used among these. However, its reliance on uniform sampling often results in slow convergence. To address this issue, this work proposes a novel hybrid sampling method called RRT*-NUS (nonuniform-uniform sampler), which combines both uniform and nonuniform sampling to improve exploration efficiency. The proposed RRT*-NUS method is evaluated against six baseline algorithms: RRT*, Informed RRT*, RRT*-N (normal sampling RRT*), GS-RRT* (goal-oriented sampling RRT*), DR-RRT* (directional random sampling RRT*), and hybrid-RRT* in three different 384*384 2D simulation scenarios. The numerical simulation results indicate that the proposed RRT*-NUS surpasses the baseline RRT* algorithms in terms of planning time and convergence. It outperforms RRT* by 67.5% and Hybrid RRT* by 54% in time performance. Additionally, it achieves a convergence rate of 0.41 units/s, which is 3× faster than RRT* and almost 2× faster than Hybrid RRT*.