Grid-optimized UAV indoor path planning algorithms in a complex environment

Path planning has become a predominant issue for unmanned aerial vehicles (UAVs), especially in complex indoor environments. Existing solutions for UAV indoor path planning are strongly limited due to their high computational complexity, slow convergence speed and poor flight paths. In this study, a set of grid-optimized UAV indoor path planning algorithms targeting complex environments is proposed to solve the abovementioned issues. First, the grid-optimized indoor airspace modeling (GO-IAM) algorithm based on the Geo-graphical coordinates Subdividing grid with One-dimension integral coding on 2n-Tree in 3 Dimensions (GeoSOT-3D) is proposed to reduce the computational complexity of modeling the indoor 3D airspace by means of spatial subdivisions. For regular indoor scenarios and a complex dead zone airspace, the grid-optimized A* path planning (GO-APP) algorithm and the grid-optimized local backtracking path planning (GO-LBPP) algorithm are established to address the efficiency and flyability of path planning. Comparison experiments of multiple UAV indoor path planning algorithms reveal that the GO-APP algorithm has the shortest computation time and planning path. Specifically, with the use of the GO-LBPP algorithm, the indoor local dead zone issue can be solved, and the deadlock of the planning path can be avoided, which cannot be achieved by other algorithms. Hence, the proposed grid-optimized UAV indoor path planning algorithms can realize state-of-the-art path planning through spatial subdivision in complex 3D indoor airspace.

Automated summary

This study proposes a set of grid-optimized UAV indoor path planning algorithms to address the issues of high computational complexity, slow convergence speed, and poor flight paths. Comparison experiments show that these algorithms can achieve state-of-the-art path planning in complex indoor environments.