Cooperative multiple task assignment considering precedence constraints using multi-chromosome encoded genetic algorithm

In the problem of cooperative multiple task assignment for heterogeneous unmanned aerial vehicles (UAVs), multiple consecutive tasks need to be performed on each target subject to task precedence constraints. An arbitrary task execution order might result in deadlock situations, i.e., one or multiple vehicles fall into an infinite waiting loop. In this paper, a multi-chromosome encoded genetic algorithm (MCE-GA) is proposed for avoiding the deadlock situations and assigning heterogeneous vehicles on multiple targets. The deadlock-free individuals are generated by considering the target identifiers and task precedence constraints in the multi-chromosome encoding process. Moreover, the specific crossover and mutation operators are designed to guarantee the feasibility of offspring individuals during the evolution process. The performance of MCE-GA is tested via comparing with random search method on simulation experiments. The comparison results from Monte Carlo simulations demonstrate that MCE-GA can produce better feasible solutions than random search method.