Research On Cooperative Task Assignment Of Multiple Unmanned Aerial Vehicles Under Multiple Constraints

As the key premise for collaborative operation of the multiple unmanned aerial vehicles(UAVs),the multi-UAV cooperative task assignment can develop mission plans for multiple UAVs that meet the operational requirements,improve the fault tolerance of multi-UAV systems and ensure the mission coverage in the combat area.Under the background of multi-UAV collaborative operations of Suppression of Enemy Air Defences(SEAD)mission,the cooperative task assignment of multiple UAVs faces multiple constraints including UAVs’ heterogeneous performance,limited resources,tasks’temporal coupling and time sensitivity,etc.Therefore,under the background of multiple UAVs cooperatively performing SEAD mission,this paper focuses on the cooperative task assignment for multiple UAVs under multiple constraints including UAVs’ heterogeneous performance,limited resources,tasks" temporal coupling and time sensitivity,and studies the multi-UAV cooperative task assignment algorithms with centralized,decentralized and distributed control structures in multi-UAV cooperation.The cooperative task assignment for multiple UAVs with centralized control structure is mostly used to make the prearranged and off-line task schedules for multi-UAV systems.The centralized multi-UAV cooperative task assignment under multiple constraints is a kind of NP-hard combinatorial optimization problem.The optimization methods have the potential problem of exponential computation burden because of their exhaustive characteristics,and the optimization process of swarm intelligence optimization methods inevitably yields invalid individuals that violate the multiple constraints.Therefore,this paper proposes a modified genetic algorithm(GA)with multi-type-gene chromosome encoding strategy to achieve the centralized multi-UAV cooperative task assignment.The proposed algorithm firstly designs the multi-type-gene chromosome encoding strategy that conforms to multiple constraints,to generate effective and deadlock-free feasible individuals for GA iterations.Then the Dubins car model is introduced to simulate the cruise trajectory of UAVs and calculate the fitness value of GA individuals.Finally,the improved crossover and mutation operators that accord with multiple constraints are raised to trade-off the global and local search abilities in the optimization process.Accordingly,to avoid the subjective setting of parameters,an adaptive GA with mutation operators based on the state-transition factor is put forward.The proposed algorithm dynamically adjusts the number of crossover and mutation offspring individuals based on the number of current iterations to ensure that GA has a stronger global search ability in the early iteration stage and stronger local search ability in the later iteration stage.Besides,the proposed two mutation operators based on the state-transition factor can help the algorithm jump out of the local optimal solution because of its stronger random mutation ability.The simulation results demonstrate that compared with the optimization methods and the swarm intelligence optimization methods,these two proposed algorithms have better optimization performance and convergence speed within a limited number of iterations.By abandoning the participation of the central control station,the cooperative task assignment for multiple UAVs with decentralized control structure allows the autonomous task assignment and negotiation to make the real-time and on-line task schedules for multi-UAV systems in the dynamic and time-sensitive battlefield environment.Considering the decentralized multi-UAV cooperative task assignment under multiple constraints,the paper proposes a consensus-based bundle algorithm(CBBA)with timing coupling constraints.The proposed algorithm firstly adopts the task performing time list to build the local bundle,which is used to assist in determining whether the time coupling constraint of tasks is satisfied.Then a Can-do list is raised to establish the task list for each UAV that conforms to its heterogeneous capability and tasks’ temporal coupling constraints,which avoids the computational complexity caused by tasks’ exhaustive addition.With the comprehensive score function with time attenuation,a revised greedy task selection method is applied to build the local task assignment result with multiple constraints,and an inner-consensus strategy based on UAV communication is used to solve the potential conflicts of the local task assignment.Finally,an outer-consensus strategy based on insert-position matrix is presented to ensure the completion of tasks.In addition,considering the new tasks in the dynamic environment,this paper proposes a CBBA with local replanning.The proposed algorithm implements a local reset process on the original task schedules according to the comprehensive analyses of the time window and distance correlations between the new task and original task schedules,which is conductive to the on-line and rapid assignment for the new task.Simulation results verify that these two proposed algorithms can quickly deal with the task assignment problem and on-line local task reassignment problem in the dynamic and time-sensitive environment,respectively.In the task allocation problem with dispersed clustering targets,and large combat area,centralized and decentralized task assignment algorithms have the problems of heavy computational load and massive communication burden,which makes it hard to guarantee the effectiveness and convergence speed of their task assignment results.Hence,a hierarchical task assignment algorithm based on density clustering and negotiation mechanism is raised under the multi-UAV collaborative distributed control structure.The proposed algorithm firstly applies density clustering method to effectively cluster the dispersed clustering targets,and utilizes the negotiation mechanism to form heterogeneous UAV teams for these clustered targets according to UAVs’limited resources and different task requirements of multiple clustered targets.Therefore,the large-scale task assignment problem with dispersed clustering targets is decomposed into several non-intersection and complete small-scale task assignment problem,which effectively reduces the required computational amount and communication cost.To achieve the monitoring of central control station about the task assignment information in the combat area,the cluster heads of all UAV teams will transmit their local task assignment scheme back to the central station.Thus,a cluster head selection strategy based on DS fusion decision is raised to select rational cluster head for each UAV team according to the overall analyses of UAVs’ four factors including the mission execution time,the number of its undertaken tasks,the total comprehensive score value and the residual task capacity loads.Besides,under the circumstance of UAVs’ limited and unbalanced resources,a few tasks cannot be effectively allocated through their corresponding UAV team.Therefore,this paper proposes an auction-based task-sharing scheme among UAV teams.In the proposed algorithm,the central control station and cluster heads of all UAV teams will participate in the auction process of unallocated tasks to achieve the effective assignment of all tasks in the mission area,which further guarantees the mission coverage of the multi-UAV system in the entire combat space.Simulation results prove that under the large-scale task assignment model with dispersed clustering targets,the proposed distributed task assignment algorithm can quickly generate effective,reliable and conflict-free task assignment solutions that conform to multiple constraints.