The Dynamic Quickly-RRT* Based on Rapidly-Exploring Random Tree

Abstract

The Rapidly-exploring Random Tree (RRT) is a classic path planning commonly used for navigating high-dimensional spaces. It explores unknown environments by incrementally expanding a tree structure through random sampling. RRT* is the improved RRT version that incorporates the Choose Parent and Rewire to achieve asymptotic optimality. However, RRT* still suffers from slow convergence, low sampling efficiency, and high path costs. To address the issues, this paper proposes a novel path planning algorithm named Dynamic Quickly RRT* (DQ-RRT*). To enhance convergence speed and sampling efficiency, a hybrid sampling strategy combining obstacle-guided sampling and dynamic goal bias and sparse sampling is introduced. A novel dynamic step size is employed to improve obstacle avoidance and accelerate exploration toward the goal. Furthermore, the node generation method based on obstacle density is proposed to smooth the path, along with a multi-segment path optimization by utilizing the triangle inequality and bisection method. The proposed algorithm outperforms the other three compared algorithms across all four simulation maps.