Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms

A problem of assigning cooperating uninhabited aerial vehicles to perform multiple tasks on multiple targets is posed as a new combinatorial optimization problem. A genetic algorithm for solving such a problem is proposed. The algorithm allows us to efficiently solve this NP-hard problem that has prohibitive computational complexity for classical combinatorial optimization methods. It also allows us to take into account the unique requirements of the scenario such as task precedence and coordination, timing constraints, and trajectory limitations. A matrix representation of the genetic algorithm chromosomes simplifies the encoding process and the application of the genetic operators. The performance of the algorithm is compared to that of deterministic branch and bound search and stochastic random search methods. Monte Carlo simulations demonstrate the viability of the genetic algorithm by showing that it consistently and quickly provides good feasible solutions. This makes the real time implementation for high-dimensional problems feasible. (c) 2005 Elsevier Ltd. All rights reserved.