Multi-UAV reconnaissance task allocation for heterogeneous targets using an opposition-based genetic algorithm with double-chromosome encoding

This paper presents a novel multiple Unmanned Aerial Vehicles (UAVs) reconnaissance task allocation model for heterogeneous targets and an effective genetic algorithm to optimize UAVs' task sequence. Heterogeneous targets are classified into point targets, line targets and area targets according to features of target geometry and sensor's field of view. Each UAV is regarded as a Dubins vehicle to consider the kinematic constraints. And the objective of task allocation is to minimize the task execution time and UAVs' total consumptions. Then, multi-UAV reconnaissance task allocation is formulated as an extended Multiple Dubins Travelling Salesmen Problem (MDTSP), where visit paths to the heterogeneous targets must meet specific constraints due to the targets' feature. As a complex combinatorial optimization problem, the dimensions of MDTSP are further increased due to the heterogeneity of targets. To efficiently solve this computationally expensive problem, the Opposition-based Genetic Algorithm using Double-chromosomes Encoding and Multiple Mutation Operators (OGA-DEMMO) is developed to improve the population variety for enhancing the global exploration capability. The simulation results demonstrate that OGA-DEMMO outperforms the ordinary genetic algorithm, ant colony optimization and random search in terms of optimality of the allocation results, especially for large scale reconnaissance task allocation problems.