UAV Path Planning in 3-D Constrained Environments Based on Layered Essential Visibility Graphs

In this article, an optimal path search methodology for unmanned aerial vehicles (UAVs) flying in 3-D environments is presented, taking into account the presence of obstacles and other constraints deriving from flight dynamics. The so-called essential visibility graph (EVG) is extended to the 3-D case by describing the obstacles using a finite number of parallel planar layers at different altitudes. The resulting graph, called the layered EVG (LEVG), is based on an efficient branching algorithm and it is made up of a reduced number of nodes and edges thus assuring a limited computational burden. Once the optimal piece-wise linear path has been identified over the LEVG, aircraft performance-related constraints, formulated in terms of turn and pull-up radii limits, can be taken into account via a smoothing procedure based on a 3-D extension of Dubins' paradigm. This way an optimal flyable 3-D path can be obtained. The implementation of a specific integer programming formulation within the graph search process ensures the full compliance of the optimal smoothed trajectory with the environmental constraints. The effectiveness of the proposed methodology is proved by means of numerical tests in complex operational scenarios over a real terrain morphology and an urban environment.