A Path Planning Algorithm Based on Improved RRT* for Unmanned Aerial Vehicle
Jie Dong, Haiqin Xu, Ranfei Li, Xujian Yu · 2021
Rapidly-exploring Random Tree star (RRT*) is an extension of Rapidly-exploring Random Tree (RRT) algorithm which uses random sampling to discover a collision-free path in a given environment. Although it can guarantee the global search's completeness and asymptotic optimality, there are some problems such as a slow convergence rate, a huge dense sampling space and unsmooth search paths in a complex environment. This paper proposes an improved RRT* algorithm, CG-RRT*(Changeable Bounds based Gaussian Distribution Sampling RRT*) to solve these problems. This algorithm generates more promising nodes by sampling in a flexible and variable connectivity region to find the initial path faster. Then the path is smoothed by eliminating unnecessary nodes through path optimization. Finally, Gaussian distribution sampling is used to accelerate the algorithm's convergence. Simulation and experimental results under various obstacle environments show that the CG-RRT* algorithm can find the initial path faster, converge to a shorter path with a shorter number of iterations and be smoother. The proposed approach can improve search efficiency, accelerate convergence, and reduce memory and processing time.