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.
UAV Path Planning in 3-D Constrained Environments Based on Layered Essential Visibility Graphs
IEEE Transactions on Aerospace and Electronic Systems ; 59 , 3 ; 2359-2375
2023-06-01
4403472 byte
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
Path Planning Algorithm of Intelligent Vehicle Based on Improved Visibility Graphs
SAE Technical Papers | 2018
|Path Planning Algorithm of Intelligent Vehicle Based on Improved Visibility Graphs
British Library Conference Proceedings | 2018
|Optimal Flight Paths over Essential Visibility Graphs
IEEE | 2018
|Visibility line based methods for UAV path planning
Tema Archiv | 2009
|