Design of constrained dynamic path planning algorithms in large-scale 3D point cloud maps for UAVs

The technology of unmanned aerial vehicles (UAVs) has been growing rapidly in recent years. To achieve highly autonomous flight capability, collision-free path generation becomes a key research topic. However, for a large-scale terrain map, an efficient path searching algorithm is always a challenging problem. Based on the Goal-bias Rapidly-exploring Random Tree Star (GB-RRT*) together with the aid of a bidirectional search technique, in this paper, a new constrained path planning algorithm, called Parent Revisited Goal and Parent Bias RRT* (PRGPB-RRT*), is proposed. Three major objectives are considered as the development benchmark: 1). shorter total distance, 2). smoother flight path, and 3). high computational efficiency. To meet different task requirements, a dynamic path planning method is investigated to diminish the high costs due to large-scale environments and keep track of the changing destination by finding local target points. In addition, unknown object avoidance is an essential part of flight path planning. As a consequence, the Fitting-Octree is presented to partition the point clouds into multiple cubes to represent the obstacles precisely. Moreover, the method of grouping point clouds into clusters effectively increases the efficiency of the implementation under a large number of obstacles. Finally, the feasibility of the proposed method is verified by a real-world 3D large-scale point cloud map. Experiments show that the proposed method successfully enhances the path generation efficiency as well as the trajectory smoothness. Moreover, the presented PRGPB-RRT* can be applied to different intelligent UAVs subject to flight kinematics constrain.