This article addresses the cooperative multiunmanned aerial vehicles task assignment problem (CMTAP) with temporally coupled constraints and aims to find a feasible assignment to minimize the equivalent distances of all tasks. We first present a mixed-integer linear programming model of CMTAP. To solve the undesirable deadlocks of CMTAP, a Petri net amender is constructed based on a candidate solution, and a deadlock-free solution is equivalent to a feasible transition sequence that can be fired sequentially in the corresponding amender. With this amender, we present a Petri net-based deadlock amending method (PDAM) with polynomial time complexity to convert a deadlocked solution into a deadlock-free solution. Also, a deadlock-free hybrid estimation of distribution algorithm (DHEDA) is developed for CMTAP by embedding PDAM into the original EDA. To further improve the solution quality, we establish a local exploitation method, and an adaptive operational probability is used to balance the computational burden and local exploitation ability. Then, a match-up-based reassignment method is proposed to cope with time-sensitive targets. Finally, extensive computational experiments demonstrate that PDAM is more effective at solving deadlocks than graph-based methods, particularly for large-scale CMTAP, and DHEDA outperforms existing algorithms when solving CMTAP.
A Deadlock-Free Hybrid Estimation of Distribution Algorithm for Cooperative Multi-UAV Task Assignment With Temporally Coupled Constraints
IEEE Transactions on Aerospace and Electronic Systems ; 59 , 3 ; 3329-3344
2023-06-01
2865091 byte
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
Deadlock-Free Consecutive Task Assignment of Multiple Heterogeneous Unmanned Aerial Vehicles
Online Contents | 2014
|