Emergency flight planning using voronoi diagrams

We present an Emergency Flight Planning functionality for unmanned aerial vehicles that provides a list of waypoints to a safe landing site for a maximum safety against the violation of no-flight zones. These waypoints are the vertices of a shortest-path tree generated from a generalized Voronoi diagram on the flight zone, which is represented by a set of polygons. The software architecture is designed to minimize the computational load on the onboard hardware of the vehicle, securing the capability of frequent updates of the way point list. All task eligible for a-priori execution are implemented in an offline software, which can be run during flight preparation or on the ground control hardware. This software includes a tailored, analytic method for the calculation of the generalized Voronoi diagram, a functionality to generate a graph containing all possible paths along the borders of the Voronoi diagram and a dynamic programming approach to obtain the optimal return tree, which is uploaded to the onboard computer of the Unmanned Aerial Vehicle. Using this return tree and a flexible shortcut algorithm, which can be adopted according to the aircraft degradation state and environmental disturbances, a way point list for a safe return is called periodically to provide a safe path from the current position to the home point. Tests on a representative micro controller showed execution times of approximately 100 ms for reasonably large flight zones, which is well below the required computation time for an execution frequency of 0.1 Hz.