Cooperative Multiple Task Assignment Problem With Target Precedence Constraints Using a Waitable Path Coordination and Modified Genetic Algorithm

• Published in: IEEE access 2021, Vol.9, p.39392-39410
• Main Authors: Zhao, Yiyang, Zhou, Deyun, Piao, Haiyin, Yang, Zhen, Hou, Rui, Kong, Weiren, Pan, Qian
• Format: Article
• Language: English
• Subjects: Assignment problem; Constraint modelling; Coordination; Deadlocks; Elongation; Free flight; genetic algorithm; Genetic algorithms; heterogeneous unmanned aerial vehicles; Job shops; Operations research; Optimization; path coordination; Precedence constraints; Sociology; Stochastic processes; System recovery; Task analysis; task assignment problem; Unmanned aerial vehicles
• ISSN: 2169-3536; 2169-3536
• DOI: 10.1109/ACCESS.2021.3063263

Task assignment is a critical technology for heterogeneous unmanned aerial vehicle (UAV) applications. Target precedence has typically been ignored in previous studies, such that it is possible to obtain a task assignment solution with an unreasonable target execution order. For this reason, a cooperative multiple task assignment problem with target precedence constraints (CMTAPTPC) model is proposed in this paper, which considers not only kinematic, resource, and task precedence constraints of the UAV, but also target precedence to achieve more realistic scenarios. In addition, a graph method is improved to detect and eliminate deadlocks in solutions that include target precedence constraints. We also introduced a waitable path coordination (WPC) algorithm to generate conflict-free flight paths. Unlike the traditional path elongation method, this method can reduce the number of path elongation operations and save the energy of UAVs. Based on the characteristics of the CMTAPTPC model, this study proposes a modified genetic algorithm that integrates the graph-based method and WPC algorithm to solve the task assignment problem. In the simulation, three problem-scale scenarios were designed, and the superior performance of the modified genetic algorithm was demonstrated by comparing it with a traditional genetic algorithm. Finally, a time series diagram shows the task assignment solution that meets all time constraints and illustrates the rationality of the WPC algorithm.