Path planning for unmanned aerial vehicles using visibility line-based methods

This thesis concerns the development of path planning algorithms for unmanned aerial vehicles (UAVs) to avoid obstacles in two- (2D) and three-dimensional (3D) urban environments based on the visibility graph (VG) method. As VG uses all nodes (vertices) in the environments, it is computationally expensive. The proposed 2D path planning algorithms, on the contrary, select a relatively smaller number of vertices using the so-called base line (BL), thus they are computationally efficient. The computational efficiency of the proposed algorithms is further improved by limiting the BL’s length, which results in an even smaller number of vertices. Simulation results have proven that the proposed 2D path planning algorithms are much faster in comparison with the VG and hence are suitable for real time path planning applications. While vertices can be explicitly defined in 2D environments using VG, it is difficult to determine them in 3D as they are infinite in number at each obstacle’s border edge. This issue is tackled by using the so-called plane rotation approach in the proposed 3D path planning algorithms where the vertices are the intersection points between a plane rotated by certain angles and obstacles edges. In order to ensure that the 3D path planning algorithms are computationally efficient, the proposed 2D path planning algorithms are applied into them. In addition, a software package using Matlab for 2D and 3D path planning has also been developed. The package is designed to be easy to use as well as user-friendly with step-by-step instructions.