TY - JOUR
T1 - Cooperative Multiple Task Assignment Problem with Target Precedence Constraints Using a Waitable Path Coordination and Modified Genetic Algorithm
AU - Zhao, Yiyang
AU - Zhou, Deyun
AU - Piao, Haiyin
AU - Yang, Zhen
AU - Hou, Rui
AU - Kong, Weiren
AU - Pan, Qian
N1 - Publisher Copyright:
© 2013 IEEE.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
KW - Deadlocks
KW - genetic algorithm
KW - heterogeneous unmanned aerial vehicles
KW - path coordination
KW - task assignment problem
UR - http://www.scopus.com/inward/record.url?scp=85103772972&partnerID=8YFLogxK
U2 - 10.1109/ACCESS.2021.3063263
DO - 10.1109/ACCESS.2021.3063263
M3 - 文章
AN - SCOPUS:85103772972
SN - 2169-3536
VL - 9
SP - 39392
EP - 39410
JO - IEEE Access
JF - IEEE Access
M1 - 9367218
ER -