Bi-level flight path optimization for UAV formations

A two-stage optimization model for flight path planning of cooperative UAVs in formation flight in the presence of polygonal obstacles and no-fly zones is proposed. Adopting a Visibility Graph (VG) approach, the virtual formation leader plans its flight path composed of circular arcs and segments connecting obstacles vertices. Then groups of obstacles, being not permeable by the flight formation without UAVs separation or formation shape deformation, are clustered and the VG is revised with the addition of so called rendez-vous waypoints, forcing the formation to be recomposed at a given location beyond groups of obstacles. Such rendez-vous waypoints are optimized at a higher hierarchical level with respect to the flight path optimization leading to a Stackelberg game. The validity of the proposed approach and optimization model is shown by means of numerical simulations where flight paths are obtained calculating shortest path on the revised Visibility Graph and waypoints positions are optimized via a genetic algorithm. Finally, anti-collision among UAVs is achieved via a simple potential based method.