An improved RRT* drone three-dimensional path-planning algorithm based on point cloud maps

Abstract

Given the problems of slow convergence and blind sampling of the Rapidly-exploring Random Trees (RRT*) algorithm in 3D path-planning of UAVs, this paper proposes an improved bidirectional probabilistic target bias RRT* algorithm for 3D path-planning of UAVs based on point cloud maps. Initially, 3D point cloud maps and the dynamic step size necessary for the expansion of the RRT* algorithm are derived through the implementation of 3D map reconstruction and point cloud analysis techniques. Subsequently, a double sampling mechanism of random and target sampling is combined with the expansion strategy of the Bi-RRT* and RRT*-Connect algorithms to generate a bidirectional random tree, which improves the search speed and shortens the path. Furthermore, the influence of a gravitational mechanism, generated by the goal, is considered to direct the growth of the random tree toward the target. A collision avoidance strategy based on KD-tree is also introduced to enhance collision detection efficiency and mitigate collision risks. Additionally, cubic spline optimization is employed to achieve a smoother path. Finally, in order to illustrate the viability and efficacy of the proposed algorithm, a comparative analysis is performed between the enhanced algorithm and the RRT*, P-RRT*, and Bi-RRT* algorithms across two distinct environments.