Online Two-Dimensional Route Planning for a Group of Unmanned Aerial Vehicles

Abstract

This paper suggests a novel approach to online two-dimensional route planning for a coordinated flight of a group of unmanned aerial vehicles (UAVs) that complexifies the modified heuristic and integer matrix algorithms using a new nearness criterion of analyzed points to each route. As demonstrated below, this approach guarantees the maximal speed of coordinated flight planning. The modified Dijkstra algorithm that considers the consequences of choosing the nearest point on all future segments of a flight plan is proposed as the heuristic algorithm. For avoiding mistakes in the case of conflict (i.e., assigning a proper route for an analyzed point among the existing options), a modified integer branch-and-bound method is developed that includes the following operations: an alternating analysis of two distance matrices for each UAV; route choice for adding an assigned minimal-length element in each of the matrices. In case of conflict, this method removes short cross connections between paths and their intersections from the flight plan.