Bi-level Flight Path Planning of UAV Formations with Collision Avoidance

This paper deals with the problem of generating 3D flight paths for a swarm of cooperating Unmanned Aerial Vechicles (UAVs) flying in a formation having a prespecified shape, in the presence of polygonal obstacles, no-fly zones and other non cooperative aircraft. UAVs are modeled as Dubins flying vehicles with bounds on the turning radius and flight path climb/descent angle. A Reduced Visibility Graph (RVG) based method, connecting selected nodes by means of circular arcs and segments, is adopted to minimize the length of each path. Then, to keep as much as possible the formation shape while flying between obstacles, the RVG is refined with the addition of so called Rendez-Vous Waypoints (RVWs). These are placed between groups of obstacles where it is impossible to maintain the desired formation. Waypoints locations and UAVs paths are optimized using a bi-level game theoretic approach based on the leader-follower Stackelberg model, where the lower level and upper level problems are the search of the shortest paths and the optimal locations of waypoints respectively. Such an approach allows to fly between obstacles, dispersing the formation and forcing UAVs to recompose it at given waypoints (RVWs) beyond groups of obstacles. Collision avoidance among UAVs and possible non-cooperative aircrafts, called intruders, is then achieved solving a set of linear quadratic optimization problems based on an original geometric based formulation. The effectiveness of the proposed approach is shown by means of numerical simulations where RVWs positions are optimized via a genetic algorithm