Fast Unmanned Vehicles Task Allocation with Moving Targets

This paper presents a fast algorithm for allocation at mission-time of moving targets to a group of unmanned vehicles. A fleet of UAVs must fly through a known environment to reach partially unknown locations, or targets, where three tasks: identification, attack and verification must be performed sequentially. The total mission cost is identified to be the sum of the total times that the UAVs spend completing their tasks, while respecting the task priorities and ensuring the tasks precedence laws. The problem is solved in two steps; the first step is performed off-line and is the most computationally intensive: the environment is subdivided into triangle-shaped areas forming the Tessellation Graph (TG), and the shortest path between each two vertexes couples of the plane is computed using the All-Pairs-Nodes Dijkstra algorithm. The second step, at mission-time, regards management of moving targets and adaptation to the results of the identification phase. Optimal task assignment is performed using the Hungarian algorithm; exact path lengths between vehicles and targets are computed from the off-line computed Dijkstra paths. One parameter is available to tune the optimal task allocation algorithm with respect to desired aggressive/selfish or cooperative behavior.