Accession Number:

ADA445154

Title:

UAV Cooperative Multiple Task Assignments using Genetic Algorithms

Descriptive Note:

Corporate Author:

AIR FORCE RESEARCH LAB WRIGHT-PATTERSON AFB OH AIR VEHICLES DIRECTORATE

Report Date:

2005-06-01

Pagination or Media Count:

7.0

Abstract:

A multiple task assignment problem for cooperating uninhabited aerial vehicles is posed as a combinatorial optimization problem. A genetic algorithm for assigning the multiple agents to perform multiple tasks on multiple targets is proposed. The algorithm allows efficiently solving this NP- hard problem that has prohibitive computational complexity for classical combinatorial optimization methods. It also allows taking into account the unique requirements of the scenario such as task precedence and coordination, timing constraints, and flyable trajectories. 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, providing good feasible solutions quickly. Moreover, it converges near to the optimal solution considerably faster than the other methods for some test cases. This makes real time implementation for high dimensional problems feasible.

Subject Categories:

  • Pilotless Aircraft
  • Numerical Mathematics
  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE