Optimal vs. Heuristic Assignment of Cooperative Autonomous Unmanned Air Vehicles

Abstract

This paper describes investigation of algorithms that generate vehicle and task assignments for autonomous UAVs in cooperative missions. In previous work many algorithms have been examined to solve the problem of assignment of autonomous UAVs to tasks based on their ability to perform those tasks. Because of the complexity of this problem, these algorithms have been based on heuristic solutions to the problem. This work presents details of an algorithm that produces the optimal assignment of UAVs for a given scenario. A set of sample scenarios is used to explain the cooperative control assignment problem and how it changes as complexity increases. Three requirements for an optimal to solution to the assignment of UAVs, in a given scenario, are task coordination, task precedence, and flyable trajectories. The requirements and the motivation behind them are explained. An assignment tree generation algorithm is described. This tree generation algorithm produces the optimal assignment of UAVs given a particular scenario. This algorithm is used to produce optimal solutions to the assignment problem which are use to measure the effectiveness of heuristic based cooperative assignment algorithms.