An Improved Sparse Hierarchical Lazy Theta Algorithm for UAV Real-Time Path Planning in Unknown Three-Dimensional Environment

• Main Authors: Wu, Chengfang, Huang, Xiaoyan, Luo, Yuanlin, Leng, Supeng, Wu, Fan
• Format: Conference Proceeding
• Language: English
• Subjects: Heuristic algorithms; Kinematics; Path planning; real-time path planning; Real-time systems; Smoothing methods; sparse hierarchical framework; Three-dimensional displays; three-dimensional unknown environment; Unmanned aerial vehicles
• ISSN: 2576-7828
• DOI: 10.1109/ICCT50939.2020.9295690

Real-time path planning in the complex and unknown three-dimensional environments is a very challenging topic for the unmanned aerial vehicle (UAV) systems. In this paper, we propose an improved sparse hierarchical lazy theta* (SHLT*) algorithm to plan a near-optimal path in real-time and efficiently in unknown 3D space. In the proposed SHLT* algorithm, the sparse hierarchical framework is adopted to divide the whole 3D space into different levels, wherein the kinematic constraints of UAV are utilized to filter the unsatisfactory successor nodes, thus ensure the feasibility of the generated path. On this basis, an adaptive lazy theta* algorithm is proposed to find the shortest path in each level, wherein the dynamic heuristic factors are applied in different levels so as to accelerate the path generation and improve the accuracy of the obtained path. Besides, path smoothing procedures are also designed to enhance the smoothness of the generated path. Simulation results demonstrate that the proposed SHLT* algorithm can plan a near-optimal path and significantly outperforms the reference algorithm on the performance in terms of path length and path smoothness.