Sampling space reduction-based UAV online path planning algorithm in complex low altitude environments

The unmanned aerial vehicle (UAV) online path planning in low altitude complex environments is complicated due to the planning spaces of densely distributed obstacles with various shapes, narrow passages for the solution path to pass through, and uncertain information. For solving this problem, a sampling space reduction-based algorithm is proposed to reduce the number of collision detection calls, accelerate the path-search process and decrease the path cost. To deal with the over-reduction problem existing in the dynamic domain rapidly-exploring random tree (DDRRT) method, the algorithm makes the space reduction gradually by employing a cost model. Thus the planning tree can extend rapidly and efficiently under the guidance of the reduction. It also promotes the near neighbors searching speed by a new storage structure for tree nodes and a novel near neighbor searching approach. Indexes are built based on the density of tree nodes to construct the storage structure composed by multiple K-dimensional trees (Kd trees). Simulation results certify that our algorithm can ensure the rationality of the sampling space reduction and improve the efficiency of path planning and the ability of path-searching in passages, as compared to the DDRRT.