Improved RRT* Algorithm Based on Node Density Diffusion Strategy
Zhongyuan Zhang, Hongqiang Liu, Qibo Deng, Jingwei Jiang, Guangyu Li · 2023
Although the optimal rapidly-exploring random tree (RRT*) algorithm has probability completeness, it cannot guarantee the feasible path solution within the specified time, especially in an obstacle environment with complex geometric characteristics. This paper proposes Density Quick-RRT*(DQ-RRT*), a modified RRT* algorithm in which sampling space is dynamically adjusted according to the node density of the random tree. DQ-RRT* algorithm has a sampling preference for the unexplored region and achieves the initial feasibility path solution faster than RRT*. For the path optimality problem, the proposed algorithm is combined with the Quick-RRT* algorithm to achieve fast path optimization based on the parent node reconnection strategy. The simulation results show that the random sampling strategy proposed in this paper can get a faster initial feasible path solution, and can be combined with other graph pruning algorithms to further improvement