New method for UAV online path planning

The task of on-line planning paths for unmanned aerial vehicle (UAVs) across a 3D terrain has been paid considerable attention in academia. This paper presents a new tactical path planning algorithm, called List Expanding Algorithm (LEA), which aims at generating a safe path from initial position to destination without any collision with forbidden regions such as threats and obstacles. The input of the task is a digital elevation map and the information of threats. Based on the algorithms in computer graphics, we fuse the two sources of data and then reflect the 3D information into a flight plane which comprises of forbidden regions. In order to generate a collision-free path, the process of region expansion is performed. Finally, the efficient recursive subroutine, the core of LEA, is designed to insert new nodes into a path list to find the path. Experimental results of the proposed algorithm are provided and compared with the Visibility Graph method. The results show that our algorithm has a superior performance in computational time and can plan a path in three-dimensional space effectively and efficiently.