The Design And Implementation Of Multi-UAVs Cooperative Task Assignment Algorithm

UAVs are used in various fields due to their strong maneuverability,convenient deployment,and low cost.With the complexity of the task execution environment and the diversification of task types,a single UAV has been unable meet the task requirements,gradually evolves into a multi-UAV coordinated execution mode.When multiple UAVs are coordinated,various constraints of UAVs and tasks must be considered,which makes task assignment a key link in the multi-UAV coordination system.The existing task assignment algorithms lack research on multi-UAV,multi-target,and multi-type task assignment problems,have low efficiency and insufficient ability to deal with large-scale task assignment problems.At the same time,the task assignment is carried out according to the initial constraints of the task,ignoring the task assignment problem in the dynamic environment.Therefore,this paper studies the assignment method of heterogeneous multi-UAV cooperative multi-target multi-type tasks.The specific research work is as follows:First,this paper proposes a "two-stage" task allocation structure(Two-Stage Architecture)in the allocation layer.The first stage is the target clustering stage.Use the k-means algorithm to cluster the targets in the task area according to the principles of "minimum distance" and "balanced quantity";then the heterogeneous UAV swarms are grouped according to the principle of "balanced resources",and the number of groups is the same as the number of clusters.This way they can correspond one-to-one.The experimental results show that the proposed "two-stage" structure can decompose the large-scale task assignment problem into several small-scale sub-problems.Compared with the non-stage structure,the task assignment time is significantly reduced,and it is easier to find the most optimal task allocation plan.Secondly,in the second stage,the task assignment stage,this paper proposes a modified Genetic Algorithm(MGA).It is mainly aimed at the problem that the traditional genetic algorithm is easy to fall into the local optimum,and has been improved from three aspects: the selection method of chromosomes,the crossover method of chromosomes and the calculation method of the crossover and mutation probability.When selecting chromosomes,a combination of "optimal gene retention strategy" and "roulette wheel method" is proposed.When the chromosomes are crossed,the parent chromosomes are first sorted according to the size of the fitness function value,and paired in pairs from high to low,as a pair of parent chromosomes;The part with high fitness value and the part with low fitness value perform single-point crossover and two-point crossover,respectively.The crossover probability and mutation probability are no longer set to a fixed value,but adaptively adjusted according to the performance of the individual fitness value in the population.Individuals with high fitness value have smaller crossover and mutation probability and the individuals with lower fitness value are the opposite.The improvement of the above three aspects can not only increase the diversity of the population,but also enable the inheritance of excellent genes,thereby ensuring that the global optimal solution is found.In the set static task assignment scenario,the improved genetic algorithm(MGA)is combined with the particle swarm optimization algorithm,ant colony optimization algorithm and The traditional genetic algorithm is compared and analyzed,the experimental results prove the effectiveness of the MGA algorithm.Finally,with the execution of the task,the resources carried by the UAV are continuously consumed.The resources of a single UAV are limited and may not be enough to complete a certain type of task about the newly discovered target.In this regard,this paper proposes a consensus based bundle algorithm(Consensus Based Bundle Algorithm with Task Sequence Mechanism,CBBA-TSM)based on the task sequence mechanism,which combines the task sequence mechanism and the consensus based bundle algorithm to achieve Dynamic allocation of tasks and resources by heterogeneous drone swarms.First,the task sequence mechanism is adopted,that is,each UAV establishes a task sequence to strictly separate the necessary task time and waiting time so that when a new target is discovered,its available time period can be quickly determined.Then,according to the available time and task resources,a consensus based bundle algorithm is used to select several UAVs with higher bidding prices to form a task group,under the premise of not affecting the established task allocation sequence,tasks are allocated to new targets,so as to provide drone swarms develop real-time and conflictfree solutions.