Improved RRT-D*: Algorithm Fusion for Optimal Path Planning

The rapidly exploring random tree (RRT) is a widely used algorithm in path planning. However, the algorithm has an excessively large sampling range, overly random sampling, and numerous invalid iterations. Additionally, the algorithm path is not optimal; it cannot avoid obstacles dynamically, and the generated route is not sufficiently smooth, which limits its use. To overcome these problems, we propose the improved RRT* algorithm that enhances the RRT algorithm in terms of two aspects: target sampling in adaptive environments and adaptive dynamic step size strategy. It then integrates the improved RRT and D* algorithms to enhance the quality and efficiency of track generation. After obtaining a feasible path planned using the improved RRT algorithm, the feasible area was expanded to the surrounding area and rasterized. The D* algorithm was used to determine the shortest path in the feasible area, and the fused algorithm was suitable for dynamic obstacle avoidance. Finally, the path length, number of path inflection points, and path planning time were used as evaluation indicators to compare the improved RRT-D* algorithm with the RRT and improved RRT algorithms. The simulation results show that the improved RRTD* algorithm is more efficient and dynamically avoids obstacles. This study provides a new approach to improving sampling algorithms and application effectiveness.