Cooperative multiple task assignment problem with stochastic velocities and time windows for heterogeneous unmanned aerial vehicles using a genetic algorithm

• Published in: Aerospace science and technology 2018-05, Vol.76, p.112-125
• Main Authors: Jia, Zhenyue, Yu, Jianqiao, Ai, Xiaolin, Xu, Xuan, Yang, Di
• Format: Article
• Language: English
• Subjects: Genetic algorithm; Heterogeneous unmanned aerial vehicles; Path coordination; Stochastic programming; Task assignment problem
• ISSN: 1270-9638; 1626-3219
• DOI: 10.1016/j.ast.2018.01.025

In this paper, a combinatorial optimization problem, formulated as a cooperative multiple task assignment problem with stochastic velocities and time windows for heterogeneous unmanned aerial vehicles, is studied in the form of a two-stage stochastic programming model. To create a more realistic mission scenario, we involve several types of constraints in this problem, such as kinematic constraints, resource constraints (both boarded weapons and fuels), and time constraints (both task sequences and time windows). Due to the prohibitive computational complexity of the problem, a novel meta-heuristic based on a modified genetic algorithm is proposed to improve the solution of this stochastic task assignment problem. After a feasible solution is obtained, a set of actual flight paths will be created by a path coordination process according to the requirements of the task precedence. In the simulation part, the effect of the proposed algorithm, both on searching capability and convergence speed, is demonstrated by comparison with the random search algorithm. Moreover, the stochastic nature of this problem caused by the stochastic flight velocities is also illustrated by comparison with a deterministic model. Additionally, actual flight trajectories meeting all time constraints are displayed for this stochastic task assignment problem.