WU Husheng, LI Hao, and XIAO Renbin

1.School of Equipment Management and Support, Armed Police Engineering University, Xi’an 710086, China;

2.Department of Intelligence, Air Force Early Warning Academy, Wuhan 430019, China;

3.School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China

Abstract: It is difficult for the double suppression division algorithm of bee colony to solve the spatio-temporal coupling or have higher dimensional attributes and undertake sudden tasks.Using the idea of clustering, after clustering tasks according to spatio-temporal attributes, the clustered groups are linked into task sub-chains according to similarity.Then, based on the correlation between clusters, the child chains are connected to form a task chain.Therefore, the limitation is solved that the task chain in the bee colony algorithm can only be connected according to one dimension.When a sudden task occurs, a method of inserting a small number of tasks into the original task chain and a task chain reconstruction method are designed according to the relative relationship between the number of sudden tasks and the number of remaining tasks.Through the above improvements, the algorithm can be used to process tasks with spatio-temporal coupling and burst tasks.In order to reflect the efficiency and applicability of the algorithm, a task allocation model for the unmanned aerial vehicle (UAV) group is constructed, and a one-to-one correspondence between the improved bee colony double suppression division algorithm and each attribute in the UAV group is proposed.Task assignment has been constructed.The study uses the self-adjusting characteristics of the bee colony to achieve task allocation.Simulation verification and algorithm comparison show that the algorithm has stronger planning advantages and algorithm performance.

Keywords: bee colony double inhibition labor division algorithm, high dimensional attribute, sudden task, reforming the task chain, task allocation model.

1.Introduction

The concept of swarm intelligence stems from the study of the behavior of social insects populations such as ants and bees.These simple individuals can show complex intelligent behaviors through interactions [1−4].With the continuous advancement of sustainable technology, the fields of science and engineering involve more and more real-world problems with non-linear, non-convex, multipeak, discontinuous and even dynamic optimization.The traditional gradient-based method is far from meeting the actual needs.In the past few decades, people have been inspired by swarm intelligence and developed various swarm intelligence optimization techniques to deal with these complex problems [5,6].Algorithms such as the ant colony optimization (ACO) [7], the particle swarm optimization (PSO) [8], the honey bees optimization (MBO)[9], and the artificial fish-swarm algorithm (AFSA) [10]were produced.

Under the effect of the labor division mechanism, ants can adjust the tasks performed according to environmental changes, so that the individual labor division exactly meets the requirements of the ethnic group for various tasks.To social insects, the labor division refers to different individuals performing different tasks.The labor division is a basic characteristic of social insects [11], and it is considered to be the primary reason for the ecological success of social insects [12].At the same time, labor division is also an important swarm intelligence behavior,which is instructive to solve problems in dynamic environments [13].

Therefore, the labor division algorithm based on the population was proposed.Gao et al.[14] started to improve the artificial bee colony algorithm and realized information interaction and learning through labor division and cooperation.It can be seen that the labor division has positive significance for improving the performance of the algorithm.The artificial bee colony algorithm is different from the classic particle optimization algorithm.The artificial bee colony realizes the division of labor by dividing bees into employed bees, on-looker bees and reconnaissance bees.The contradiction between global wide area search and local precise search of the optimization algorithm is solved.This also lays the foundation for the follow-up research on the division of labor in the bee colony.Reference [15] was also inspired by the idea of labor division and cooperation within the bee colony.It optimizes artificial self-organized networking (SON) systems and improves the performance and intelligence of the network.The model of division of labor of ant colonies with adaptive and self-regulating abilities is used to quantify the parameters such as ants, environmental stimulation and traffic characteristics.Through the optimal division of labor between ant colonies, the effective adjustment of signal lamp time can be realized.This also highlights that the division of labor within the population has a positive effect on improving the performance of the algorithm.Jiang et al.[16] used the ant colony labor division model with adaptive and self-adjusting capabilities to quantify the biological characteristics of ants, environmental stimuli, traffic characteristics and other parameters, and optimized the labor division ant colonies to achieve effective adjustment for the signal time.The labor division algorithm realizes the gradual optimization of individuals through the corresponding interaction mode of the environmental stimulus and the individual.This method is different from the process of the intelligent optimization algorithm gradually searching for the optimal solution.This method has good interpretability.Especially for dynamic optimization problems, the optimization solution can be given more quickly and accurately.Wang et al.[17] also built a mapping relationship between ant’s spatial fidelity zones (SFZ) and the cluster supply chain network based on the ant colony division model, thereby improving the recovery performance of the network based on the self-recovery ability of the ant colony.This is also the advantage of the division of the labor model, compared to the optimization algorithm.The division of the labor model has better robustness.Under the condition that part of the population is damaged, compensation can be achieved through division of labor adjustment, which ensures the robustness of the algorithm.Ravary et al.[18] proposed that human experience can be used to enhance the individual attributes of the population and enhance the ability of the ant colony.This gives the ants better learning ability, and further improves the algorithm performance.The labor division algorithm has a better self-learning ability than the intelligent algorithm,and it has a positive effect on quickly optimizing the target solution.Wu et al.[19] improved the ant colony labor division model, and proposed a dynamic ant colony labor division model based on the distributed framework,which realized a highly self-organizing and flexible allocation of unmanned aerial vehicle (UAV) tasks in a dynamic environment.This idea also provides a reference for the algorithm of this paper.Because the bee colony division of the labor algorithm has better interpretability,scholars have a clearer explanation of the mechanism of the bee colony division of the labor algorithm.And compared with the ant colony division of the labor algorithm,the bee colony division of the labor algorithm has a better performance.Therefore, this paper improves the labor division model of the bee colony to optimize task allocation of the UAV swarm.

With the development of drone cluster technology,scholars have also conducted in-depth research on the task allocation of drone clusters.Huang et al.[20] constructed a UAV collaborative task allocation method based on cross entropy, which can effectively and accurately allocate tasks to different types of collaborative UAVs.The performance of this method is related to the random sample extracted.If the randomness of the sample is not strong or the sample size is small, the performance of the method will be affected.Chen et al.[21]combined the directed graph method and the wolf pack algorithm to construct task allocation architecture.Zhu et al.[22] used the simulated annealing method to optimize the particle swarm algorithm and to achieve task allocation.However, intelligent optimization such as the wolf swarm algorithm and the particle swarm algorithm, due to the limited diversity of the population, makes the algorithm easy to fall into the local optimum.Zhou et al.[23] used the iterative Gale-Shapley algorithm to achieve task allocation for UAVs.A fair and efficient solution could be achieved.References [24,25] were based on game theory to optimize the task allocation of UAVs and get the ideal result.However, such an iterative process is difficult to apply to highly changing or unexpected tasks.References [26,27] optimized task sequence through the auction algorithm and the consensus algorithm, which can achieve conflict-free task assignment.The defects of the auctioneer’s identity and the insufficiency of the bid value restrict the effectiveness of the algorithm, and the method has limited compatibility for unexpected new tasks.Cheng et al.[28] constructd an immune cloning algorithm with limited time, and adjusted task allocation according to the priority of time.However, the infeasible elite solution of the algorithm itself should not be retained and the inability to directly learn evolutionary experience restricts the performance of the algorithm.

The organization of this paper is as follows.Section 2 and Section 3 introduce the basic principles of the bee colony double inhibition labor division algorithm, the model’s deficiencies and improvements.Section 4 constructs the task allocation model of the UAV swarm.The model is optimized by using an improved bee colony double inhibition model in Section 5.Through simulation verification and algorithm comparison, the advantages of this method are reflected in Section 6.Finally conclusions are drawn in Section 7.

2.Principle and deficiency of double inhibition labor division algorithm

2.1 Basic principle and model of the bee colony double inhibition labor division algorithm

Amdam et al.proposed the double inhibition hypothesis in order to explain the differentiation of bees from nest bees to foraging bees during the research on bee colony activities [29].The hypothesis (Fig.1) proposes that there are two inhibitors in the bee body—internal repressor(IR) and external repressor (ER), which together produce an inhibitory effect with the allatoregulatory central nervous system (ACNS).

Fig.1 Double inhibition hypothesis model

The hypothesis believes that ACNS can promote the production of juvenile hormone (JH), which in turn depends on juvenile hormone-dependent differentiation pathway (JHDD), and ACNS can directly promote the generation of a kind of juvenile hormone-independent differentiation pathway (JHID).For the concentration of two inhibitors, IR and ER, are produced in the bee body,thereby inhibiting the production of JH for ACNS, and ultimately regulating the growth process of the bee.Among them, because JH has an inhibitory effect on the synthesis of vitellogenin, the content of vitellogenin is positively correlated with the content of IR.External inhibitors are positively related to the foraging bees.

Naug et al.[30] further perfected the theoretical model.This model accomplishes task assignment by individualindividual interaction.The interaction relationship between individuals is shown in Fig.2.

Fig.2 Interaction between individuals in the principle of double inhibition

As shown in Fig.2, each bee in the colony contains a stimulant J and two inhibitors IR and ER.IR is an intrinsic inhibitor of honeybees, which will not hinder its own behavioral development, but it will inhibit the behavioral development of other honeybees during individual interaction.ER is an external inhibitor obtained by bees in the interaction, which will hinder their own behavioral development.Ultimately, the relative levels of stimulator J and inhibitor J/(αIR+ER) determine whether the bee’s behavior develops at a normal rate or is accelerated, delayed,or reversed.

Beshers et al.[31] gave a quantitative form of the excitation-suppression model

wherexis a state variable, describing the individual’s physiological age;yis an auxiliary variable, representing the social inhibitory effect, which is achieved through the interaction between individuals.

Zahadat et al.[32] constructed a correspondence between age and task, as shown in Fig.3.Individualk’s physiological agexk∈[xmin,xmax], tasks are arranged in order along the physiological age from small to large, andthi−1:irepresents the age threshold between taski−1and taski.luandlbrespectively represent the upper and lower limits of the task age threshold.

Fig.3 Age-task correspondence

If an individual executing taskiwants to turn to taski−1,his agexkneeds to be less than the difference betweenthi−1:iandlb.Similarly, for an individual executing taskito turn to taski+1, its agexkneeds to be greater than the sum ofthi:i+1andlu.Assume that the task corresponding to individualkis taski,andrepresent the physiological age of other individuals closest toxk.When individualkinteracts with individualj, according to (2) and (3), updatexkaccording to (4), and adjust tasks according to (5).

2.2 Shortcomings of the bee colony double inhibition labor division

As can be seen from Fig.3, a clear step in the bee colony double inhibition algorithm is to connect the tasks together to form a task chain, that is, task1to tasknin the figure.The bee colony double inhibition algorithm is to arrange the tasks according to the time sequence according to the time sequence of the tasks.And if there is no time sequence between tasks, or multiple new tasks appear in the same time period, it will be difficult for the above-mentioned double inhibition algorithm to solve these two problems.At the same time, the importance of tasks is not the same.Therefore, it is necessary to consider the importance of the tasks and arrange the tasks during the execution process, but the double inhibition algorithm does not involve this aspect.The following three points will be discussed in detail.

2.2.1 Difficulty to handle multi-attribute and high-dimensional tasks

When the task has nothing to do with the timing, that is,there is no timing relationship between the tasks, the bee colony double inhibition algorithm cannot be arranged according to the timing of the tasks.Classical non-sequential optimization problems involve multi-dimensional parameters such as the traveling salesman problem(TSP), the factory location problem, and the clustering problem.The bee colony double inhibition algorithm has limited performance.

From Fig.3 and the corresponding description, the double inhibition algorithm does not consider the task with multiple attributes when it sorts the tasks.Therefore,in order to construct the correspondence between age and tasks in the bee colony algorithm, it is necessary to give a linear ranking method for multi-task, use the bee colony labor division algorithm to optimize the solution, and expand the scope of the algorithm.

The factor restricting the double inhibition model is how to linearly arrange the points in the multi-dimensional space.In a multi-dimensional space, the two task points with the shortest distance can be regarded as related tasks and can be arranged linearly.Then the problem is converted to finding the shortest path of each point in a multi-dimensional space, and the points that appear in sequence on this path are the corresponding task chain.

Then the problem of ordering multi-dimensional parameter tasks is transformed into the classic multi-dimensional TSP.Assume there areNtasks, and the ranking problem is transformed into

whereQis the objective function anddijis the distance between taskiand taskj, that is, to find the shortest path connecting all tasks in the multi-dimensional space.

2.2.2 Sudden tasks

According to the task sequencing method in Fig.3, it is assumed that tasks appear one by one according to the time sequence, so that the task chain in Fig.3 can be constructed.Obviously, in the above process of constructing the task chain, it is assumed that the previous tasks are over, and only one task appears at the new moment.That is, there is only one task to be solved at a time.

However, it is clear that this assumption has certain limitations.First, it is likely that there are multiple tasks to be solved at this time, that is, the tasks that have been planned before but are left unsolved due to limited resources.Secondly, the number of sudden new tasks can be more or less and cannot be generalized.Finally, the proportional relationship between the newly added tasks and the remaining tasks also affects the subsequent processing methods.Therefore, it is necessary to adjust the task chain in Fig.3 according to the proportional relationship between the number of new tasks and the remaining tasks in order to make the bee colony double inhibition labor division algorithm more applicable.

2.2.3 Importance of tasks

The importance of tasks is not the same.Some tasks are more important and urgent and need to be executed as soon as possible, while other tasks have no urgent need for time, as long as they are completed.Formula (6)needs to be improved, namely,

whereωjis the importance of taskj.The method for determining the importance may be obtained according to expert scoring or weight calculation methods, but it will not be repeated here.The more important the task, the larger the value ofωj, the smaller the reciprocal, and the lower the cost to the task point.After considering the importance of the task, the ordering of the task chain is converted to optimize (7).

This is also an improvement point of this paper.We believe that task execution is not good only by considering the spatial attributes, which is similar to the execution of which task point is closer.This strategy is a typical solution to the multiple TSP, but obviously, it does not consider the timeliness of the task.Therefore, this paper weights the path according to the importance of the task.In this way, from the perspective of task space, the relationship between distance and importance is balanced.The more important the task, the shorter the distance from the task being performed in the task space, the more likely it is to perform the corresponding important task.

3.Improved double inhibition labor division algorithm

3.1 Improved algorithm flow

In order to improve the ability of the double inhibition labor division algorithm to solve spatio-temporal coupling tasks and burst tasks, the improved algorithm flow constructed in this paper is shown in Fig.4.

Fig.4 Improved algorithm flow

In the improved algorithm flow, the original tasks are first sorted according to the spatio-temporal characteristics, and then the tasks are executed.The criterion of sorting is to connect tasks with high similarity one by one as much as possible.In order to reduce the amount of calculation, this paper uses a clustering method to initially group tasks.Due to the high similarity within the clustering group, the task sub-chains are formed after connecting within each group, and then the task sub-chains are connected in sequence according to the similarity between the groups, thereby forming the task chain.

When there is a sudden task in the process of execution, the task sequence is adjusted according to the proportional relationship between the sudden task and the remaining tasks.When there are fewer sudden tasks, the tasks are inserted in the remaining task chain.If there are many burst tasks, rearrange the burst tasks together with the remaining tasks.

Through the above process, it is possible to handle spatio-temporal coupling tasks and sudden tasks.Obviously,the task sequencing and handling of unexpected tasks are the core tasks of this improved process.Therefore, this paper introduces these two tasks in detail.

3.2 Linear arrangement method of multi-attribute tasks based on clustering

As mentioned earlier, the double inhibition labor division algorithm cannot handle multiple tasks that occur at the same time.The core reason is that the algorithm does not have the ability to linearly arrange tasks with spatial attributes in a certain order.If a task with spatial attributes or more dimensional attributes is considered as a point in a high-dimensional space, then the problem is transformed to find a line that sequentially connects the specified points in the space.At the same time, as shown in Fig.3, the task chain corresponds to the age of the bees one by one.That is, the age of the bees is arranged in order from small to large.The corresponding task chain also needs to follow certain criteria to maintain a one-toone mapping with the age.To this end, this paper hopes to build a task chain based on the relevance of the task.Correlation is more reflected in the spatial distance in space, therefore, this paper strives to build a shortest line that passes through each task point one by one.

Due to the large amount of tasks, similar to the TSP,greedy search can be used to traverse, which can get a more ideal solution.But the calculation amount is too large, and the problem of explosion of combined dimensions is prone to occur.Therefore, in this paper, all task points are clustered to obtain multiple task groups, and the shortest path within the group is first obtained, meaning that, the task sub-chain is constructed.After that, the shortest path of each cluster center is calculated to determine the link order of task sub-chains.Finally, the order of the shortest path of the clustering center connects each sub-chain to form a task chain.

In this way, a complex whole is integrated into multiple organic parts, and the number of task points in each part is significantly reduced, thereby improving the operational efficiency of the algorithm.At the same time, the number of clusters is the same as the number of agents performing tasks, which also facilitates the coordination of subsequent tasks.

Considering the iterative self-organizing data analysis techniques algorithm (ISODATA) has good grouping accuracy and strong real-time performance, and can also change the grouping parameters according to actual needs, this section uses the ISODATA algorithm to linearly sort the tasks.Since the algorithm is relatively mature, it will not be repeated here.

At this point, we can use the ISODATA algorithm to achieve task grouping and task sequencing.The algorithm can be summarized as quantifying tasks first,making the number of clusters the same as the number of agents performing the tasks, and then performing clustering processing on all tasks to obtain multiple cluster groups and corresponding cluster centers.The shortest path within each group is required to build a task subchain, and to find the shortest connection between clustering centers to determine the connection order of each group, and finally each sub-chain constitutes a complete task chain.It is possible to sort multi-attribute tasks.To this end, this paper briefly discusses it.

Assuming that there areNtasks, quantify them and project them into a two-dimensional space.The corresponding task points areT1−TN.As shown by the red dot in Fig.5.

Fig.5 Task grouping diagram

Suppose that there areUagents performing corresponding tasks.Using the ISODATA algorithm, the aboveNtasks are clustered, and the number of clusters isU.Each cluster groupGuand corresponding grouping centerCuare obtained, as shown in Fig.5.

For each point in each group, solve its shortest path in each group, and get sub-chains as {T2,T1,T3}, ···,{Tn,Tn+1},···, {TN−3,TN−1,TN,TN−2}, as shown by the red line in Fig.5.

Finally, the shortest path of each cluster center is calculated, and the corresponding module chain is {C1, ···,Cu,···,CU}.Then calculate the two points with the shortest distance in each group.It is the connection point of each sub-chain and connected.Thus, the corresponding task chain can be obtained as {T2,T1,T3, ···,Tn,Tn+1,···,TN−3,TN−1,TN,TN−2}.

In this way, the task of spatial attributes and even more dimensional attributes can be realized.

3.3 Reconstruction method of sudden task and executed task chain

3.3.1 A few sudden tasks

Assume that some tasks have been completed during the execution of the task, as shown by the yellow circle in Fig.6.At this time a small number of tasks burst.That is,the ratio of the number of new tasks to the number of remaining tasks is not higher than the threshold of the full group, as shown in Fig.6.

Fig.6 Schematic diagram of a small number of sudden tasks

Assume that tasks are executed synchronously in the order in the previous section.Among them, {T2,T1,···,Tn, ···,TN−3,TN−1} has been completed, indicated by a yellow circle.At this time, {T3, ···,Tn+1, ···,TN,TN−2} has a total ofNrremaining tasks.At this time,NTtasks burst.Suppose its schematic point in two-dimensional space is shown in the blue circle.Calculate the ratio of the new task to the remaining tasks, and set the re-thresholdTh,and determine the relationship between the ratio and the threshold, namely,

Assume no higher than the set threshold, and calculate the distance betweenNTnew tasks and {C1, ···,Cu,···,CU}.Take the group corresponding to the shortest distance and put it into the group.Then recalculate the shortest path in the group, which is the task sequence.Then calculate the point with the shortest distance between the group and other groups.If there is no new task group, the corresponding task chain order remains unchanged, and a new task chain can be obtained.

In this way, a small number of sudden tasks can be processed.

3.3.2 A lot of unexpected tasks

Assume that a large number of tasks burst during the execution of tasks.The ratio of the number of new tasks to the number of remaining tasks is higher than the full group threshold, as shown in the blue circle in Fig.7.The task process and related discussions are the same as in Fig.7.

Fig.7 Schematic diagram of a large number of tasks

At this time, the ratio of the number of newly added tasks to the number of remaining tasks is higher than the thresholdTh.In this case, re-planning is required.

At this time, {T3, ···,Tn+1,···,TN,TN−2,NT1, ···,NTT}exists in the space, and there are (NT+Nr) tasks in total.Re-plan the remaining tasks and burst tasks together.Thus, a large number of sudden tasks can be processed.

3.4 Improved algorithm model of the bee colony double inhabition labor division

The improved algorithm can be discussed as quantifying and clustering the tasks to be processed, and solving the shortest path in each clustering group according to the similarity of task attributes.That is to order the tasks within the group, which can be regarded as a task subchain.Then find the shortest path for each center point,so that all the task fragments can be connected together according to the order of the center points.Thus, the task chain in Fig.3 is formed.When a new task appears, calculate the group corresponding to the task and add it to the group.Finally, the above model is used to allocate the task.The process is shown in Fig.8.

Fig.8 Flow chart of improved bee colony double inhibition labor division algorithm

The above flow chart can be summarized as the following steps.

Step 1Initialize parameters and quantify all tasks.

Step 2Use the ISODATA algorithm to cluster all tasks.At the same time get each cluster center.

Step 3Solve the shortest path of each task point in the group, and connect each task point into a task segment.

Step 4Solve the shortest path between each cluster center, take the shortest two task points between groups as the connection point, and connect each task segment into a task chain.

Step 5After performing a one-step task, determine whether all tasks are completed.If all tasks are completed, the optimization ends.Otherwise, go to Step 6.

Step 6Determine whether there is a new task.If there is no new task, go to Step 5.Otherwise, go to Step 7.

Step 7After new tasks appear, count the number of new tasks and remaining tasks, and quantify the new tasks.

Step 8Calculate the ratiokbetween the new task and the remaining tasks, whenkis greater than the threshold,then consider integrating all tasks as a new whole, perform regrouping, and return to Step 2.Otherwise, go to Step 9.

Step 9kis not greater than the threshold, indicating fewer new tasks.After calculating the distance between the newly added task and each grouping center, the minimum distance is selected, and it is classified into the corresponding group.Perform Step 3.

Through the above process, the connection to the task with spatial characteristics can be determined and the newly added task can be executed.Subsequently, the application of the improved bee colony double inhibition labor division model in the dynamic assignment of UAV swarm tasks will be introduced.

4.Modeling of UAV swarm task dynamic assignment problem

4.1 Drone cluster task dynamic allocation process

A typical task allocation process is shown in Fig.9[33,34].

Fig.9 UAV swarm task allocation process

First define the task requirements of the UAV swarm[35−38], then perform task decomposition, decompose the task set into sub-tasks that can be assigned to the UAV for execution according to the task type, and construct the objective function when performing the task according to the task requirements.At the same time, it collects environmental information, including the current coordinates of the drone, the coordinates of the mission point, and the threat area information, and combines it with the UAV’s own motion and load constraints to build constraints.After the objective function and constraints are obtained, intelligent algorithms are used for optimal scheduling and resource allocation to realize the mission planning of the UAV swarm, and an optimized solution is obtained.Obviously, in actual application, the number of tasks is significantly greater than the number of drones,and the tasks may increase.Therefore, it is necessary to judge whether all tasks have been completed after this task is executed.Thus, task allocation should be a cyclic and progressive process.

In order to achieve this effect, before the task allocation model is established, it is necessary to decompose the issued combat task set and decompose the task set into sub-tasks suitable for a single UAV to complete.The typical combat tasks of UAV swarms include [39−43] reconnaissance, detection, interference, communication relay, and attack.

4.2 Description of UAV swarm dynamic task allocation problem

This paper takes the background of joint execution of multi-UAV operations against the enemy, and performs reconnaissance (R), detection (D), interference (I), attack(A), and communication relay (C) tasks.Suppose the number of tasks to be performed in the battlefield isNT,which areNTR,NTD,NTI,NTA, andNTC, respectively.The number of drones that can perform tasks isNU.The task assignment problem of UAV swarms can be represented by a quadruple {U,T,M,L}, whereUrepresents the set of drones,Trepresents the set of tasks,Mrepresents the set of task types, andLrepresents the set of constraints.

Define the set of combatable drones in the battlefield; the set of tasks isthe type of task is represented by the set,M={R,D,I,A,C}, where each UAV can perform one or more tasks.

The description of the conventional UAV swarm task allocation problem can be summarized as the cost of consumption under the condition of the maximum completion rate.

The number of missions is likely to be greater than the number of UAVs, and the missions may increase, for example, interference or attack missions may be performed after the search process.Therefore, this paper believes that task planning is a problem of dynamic allocation of time series.When planning, we must consider not only the current situation, but also the impact of the current decision on the next step.For example, when a certain UAV performs reconnaissance on target 1, after the task is completed, it can fire on the nearby target 2 or the distant target 3.Obviously, it is very advantageous to perform task 2, because the corresponding transfer cost is small,or the similarity of the just ended task is high.Therefore,this paper believes that in the task planning, the efficiency of executing the task this time should be higher,and it can also have a good effect on the next moment.

In summary, this paper believes that the description of the problem of dynamic task allocation for UAV swarms should be as follows: single planning can maximize the task completion rateJ1, the fuel consumption and mounting resource consumption costsJ2are small, and the terrain and radar threatsJ3are small.The cost of performing subsequent tasksJ4is also small.

According to the task set, a single drone can only perform one task in one plan.Then the task completion rateJ1is

In a single plan, the cost of consumptionJ2and the threats receivedJ3are

wherexijrepresents theith drone to perform thejth task,cijrepresents the corresponding cost, andtijrepresents the threat.

The cost of moving to the next task is small, which means that the next task is closer to the current task.Therefore, after quantifying the tasks and calculating the similarity between tasks,rikis larger, the transfer function is

whererikrepresents the similarity between taskiand taskk, which is the size of the correlation coefficient between the two groups of tasks after quantification.xikrepresents theith drone performing thekth task, andcikrepresents the corresponding cost.

Therefore, the optimization goal can be expressed as:perform as many tasks as possible, the cost of performing the task is relatively small, and it is easier to execute the tasks of the next stage after the execution of the task.That is, makeJ1andJ4as large as possible, andJ2andJ3as small as possible in one planning.

Obviously, this paper is to study a multi-objective optimization problem.There are many methods for solving multi-objective optimization problems at this stage, such as PSO [44], genetic algorithm [45], artificial bee colony[46], ant colony [47] and other intelligent algorithms.The core of this type of algorithm is to convert the multi-objectives in the task assignment problem into linear singleweight optimization or linear optimization methods, and then optimize and solve the objective function through the above-mentioned intelligent algorithm.This design optimization model solution method works well when dealing with static problems, but when dealing with dynamic problems, it is often difficult to make timely and dynamic adjustments according to changes in the environment.The battlefield environment may change at any time, such as in reconnaissance missions and detection missions.As the mission progresses, the opponent’s target may be gradually discovered, and the number of targets will rise.During the electronic interference and fire strike missions, the opponent’s target position changes.After detecting the target, perform new tasks such as interference or strike, and other uncertain factors.Therefore, this paper believes that the problem to be solved is a typical dynamic task assignment problem.

The core of the task allocation research is how to allocate the appropriate tasks to the appropriate drones to achieve the best overall execution effect.Swarm intelligent labor division can effectively and quickly achieve flexible assignment of tasks, has obvious adaptability,and can still efficiently complete tasks in a dynamic environment, showing superiority.

5.Dynamic task assignment of UAV swarm based on improved bee colony double inhabition labor division algorithm

5.1 Algorithm mapping

Based on the previous description, this paper builds a double-inhibition task assignment mapping model based on the improved bee colonization.This model takes bee individuals as modeling objects, and achieves a reasonable labor division for the entire bee colony by superimposing the simple behaviors of bee individuals.

The mapping relationship between the double inhibition model and task assignment is shown in Fig.10.

Fig.10 Mapping relationship between the bee colony double inhibition model and UAV task assignment

The corresponding relationship can be described as follows:

(i) Each UAV is equivalent to a bee.

(ii) The task execution rateJ1is regarded as the physiological age of bees.

(iii) The resourceJ2consumed in the mission planning is regarded as the bee’s ER.

(iv) The threatJ3in the mission planning is regarded as the bee’s IR.

(v) Consider the transfer functionJ4in mission planning as a bee stimulant.

When the system does not perform tasks efficiently,the content of the stimulant increases.Under the action of the double inhibition principle, its task execution rateJ1will increase.At the same time, when the efficiency of the system execution task is not high, the larger the external inhibitor, the task execution rateJ1will increase under the action of double inhibition principle.The tasks corresponding to each UAV are adaptively adjusted through the changes of stimulants and inhibitors, which has the characteristics of concise principles and easy implementation.

In this way, the solution method of swarm labor division is adopted.Over time, the tasks performed by each drone will be adaptively adjusted and the purpose of adaptively improving the task execution rate can be achieved without the need to establish an optimization model.

5.2 Dynamic task allocation process

The double inhibition principle requires a comparison of the stimulator, internal inhibitor, and external inhibitor.However, when the drone is performing a task, the task execution rate, the threat, and the cost are received.These parameters have different dimensions and magnitudes for each performance index, resulting in that the physical meaning of each index weight model is not clear, or due to a certain index.It is difficult to directly compare the dimensionless ambassadorial objective function and overcoming the magnitude difference of the performance index.Since this is a practical problem, the distance magnitude and parameters are difficult to determine directly.For this reason, in the single planning, the maximum valueJ2:maxand the minimum valueJ2:minof all UAVs’ resource consumption are selected.The threatened maximum value and minimum value areJ3:minandJ3:maxrespectively.And the maximum value and minimum value areJ4:maxandJ4:minof the transfer function respectively.

The relative resource consumption indexRJ2(k) of thekth UAV is

The relative resource consumption indexRJ3(k) of thekth UAV is

The relative indexRJ4(k) of the task transfer function of thekth UAV is

The stimulantJ(k) of thekth UAV is

The internal inhibitorIR(k) of thekth drone is

The external inhibitorER(k) of thekth UAV is

The excitation suppression ratioA(k) of thekth UAV is

The principle of double inhibition is to control the physiological age of bees through the ratio of the sum of the stimulator, internal inhibitor and external inhibitor,namely the above formula.Correspondingly, in the algorithm of this paper, the execution rate of the task is determined by the excitation suppression ratio, as follows:

wheredhigheris the upper threshold of the excitation suppression ratio,dloweris the lower threshold of the excitation suppression ratio,zkis the age of the bee corresponding to thekth drone, andσiis the change in age.When the excitation-inhibition ratio is greater than the upper threshold, age increases; when the excitation-inhibition ratio is lower than the lower threshold, age decreases; when the excitation-inhibition ratio is greater than the lower threshold and less than the upper threshold, age does not change.

In (21), when the excitation-inhibition ratio is greater than the upper threshold, the age change is positively correlated; when the excitation-inhibition ratio is lower than the lower threshold, the age change is negatively correlated; when the excitation-inhibition ratio is greater than the lower threshold, and less than the upper threshold, the amount of change in age remains unchanged.

Then the task planning process based on the improved bee colony dual-suppression division of the labor algorithm is shown in Fig.11.

Fig.11 Improved task allocation algorithm

The process in Fig.11 can be described as follows.

Step 1Initialize parameters.Parameters include the number of dronesUU, the number of tasksUT, the age of the bee corresponding to the drone, the coordinates and task types of each task point, the consumption of performing each task, the transfer function between tasks,the upper thresholddhigher, the lower thresholddlower, internal Inhibitor coefficientα, and age changeσ0.

Step 2According to the task parameters and the process in Fig.8, get the task chain.

Step 3Calculate the content of the stimulant, internal inhibitor and external inhibitor corresponding to each UAV, and calculate the excitation inhibition ratioA(k).

Step 4Adjust the age of the bee corresponding to the drone according to (20) and (21).

Step 5According to the adjusted age, combined with Fig.8, perform the tasks corresponding to the task chain.

Step 6Determine whether there is a new task.Step 3 is executed if it does not continue, otherwise Step 2 is executed.

Step 7Repeat Step 2 to Step 6 until all tasks are completed.

Through the above process, it is possible to realize the dynamic allocation of tasks of the UAV swarm.

6.Simulation

6.1 UAVs taking off from the same location

In order to verify the feasibility and advantages of the proposed method, the above algorithm is simulated.This paper assumes that 10 drones will go to 50 points to perform missions and take off from the same point.Assume that there are 50 task points, 10 for each task, the distribution is shown in Fig.12.

Fig.12 Original distribution map of 50 task points in situation A

Assuming that the drone is an integrated surveillance UAV, and it can only perform one task at a time.

In order to reflect the advantages of the method in this paper, it is compared with the classical labor division of hordes, the labor division in ant colonies, and the improved labor division methods in [48−50].The simulation environment is I7-4960, the main frequency is 2.60 GHz,16 G memory, and the simulation experiment is carried out based on Matlab 2014a.Dispatch five drones to perform the corresponding tasks, and the simulation results are shown in Fig.13.

Fig.13 Comparison of task plan and cost of five algorithms in situation A

It can be seen from the cost function of each algorithm that the cost function of the improved algorithm in this paper is smaller than the other four algorithms.Due to the double inhibition model, the performance of the algorithm in this paper is superior to the classical bee colony division labor and ant colony division labor algorithms.The method in [48] designs variable thresholds,but due to the large number of drones set in this paper and the limited parameters for each UAV to perform tasks, the calculated variable threshold cannot be guaranteed to be the optimal threshold.Therefore, the method in this paper is slightly better.The method of [49] needs to design the calculation and evaluation method of suitability and specify the interaction constraints and update rules to have good performance.However, the research in this paper is for both sides of the military confrontation,and the information is not enough to support the corresponding rules and parameters of the design.Therefore,the method in this paper is due to the improvement strategy of [49].At the same time, it also reflects the strong practicability of this method.Among them, [50] is a typical improved ACO algorithm, and its essence is an intelligent optimization algorithm.It can be seen from Fig.13 that the algorithm in this paper has a better effect,because as the search dimension increases, the literature[50] has the risk of falling into a local optimum.

In order to further compare the performance of the method, the performance of the algorithm in this paper and the other four algorithms are subjected to 100 Monte-Carlo experiments to calculate the corresponding optimal cost function, average cost function, corresponding variance, and time-consuming.Results are shown in Table 1.

Table 1 Algorithm performance comparison in situation A

It can be seen from the comparison that the algorithm in this paper has better performance and stability.It is more suitable for solving the problem of task assignment.

The algorithm in this paper has obvious advantages,mainly because of the following four reasons.

(i) Specificity

Conventional intelligent optimization algorithms, such as particle swarms, ant colonies and genetic algorithms,and corresponding improved algorithms, all have a contradiction between algorithm speed and accuracy.That is,the intelligent optimization algorithm always switches between the global broad search and the local precise search, and the corresponding particles also switch between different states.The bee colony division of the labor algorithm is to realize the division of labor for each particle, that is, the particles only perform extensive search or precise search, so that there will be no switching problems, which further improves the performance of the algorithm.

(ii) Robustness

The efficiency of the intelligent optimization algorithm is highly related to the diversity of the population.If the original population can be distributed as evenly as possible in the search space, the possibility of the algorithm converging to the local optimum will be reduced.However, when the population is generated, there is no guarantee that particles can appear in all spaces.Or if the particles in a certain part of the search space disappear,the space here cannot be searched.That is, it is difficult to guarantee the diversity of the population.

The bee colony division of the labor algorithm traverses all possible situations in the optimization process,thus reducing the possibility of falling into a local optimum.Compared with intelligent algorithms, the algorithm in this paper has better robustness.

(iii) Suitable for solving dynamic problems

Intelligent algorithms mainly use particles to optimize the objective function, that is, after the objective function and constraint conditions are determined, the optimal solution is obtained through particle search, meaning that this is a static process.The bee colony division of the labor algorithm is based on an environmental stimuluscolony response mode, and gradually converges to the optimal process through interaction with the environment and loop iterations.This is a method that is more similar to biological characteristics and more interpretable.

(iv) High algorithm efficiency

The fast speed of this algorithm is reflected in the algorithm design level and the bee colony algorithm itself.

In this designed hierarchically algorithm, the task points are classified first, and then the optimization is performed in each classification group.This method has a faster algorithm than the global optimization.

The bee colony algorithm level is because the intelligent optimization algorithm is independent for each optimization, that is, when a new task appears, the intelligent optimization algorithm optimizes it as a brand new problem.The optimization of the bee colony division of the labor model is continuous.When a new task appears,as shown in Section 5.3 of this paper, after 20 new random tasks are added, the previous optimization state continues, and the optimization continues.The algorithm speeds faster than the the intelligent optimization algorithm.

6.2 UAVs taking off from any point

In order to further reflect the applicable scope of the algorithm in this paper, it is assumed that five drones are going to perform tasks at 50 points and can take off from any point.The 50 task points are shown in Fig.14.Also assume that there are 50 task points, each with 10 tasks.The distribution is shown in Fig.14.

Fig.14 Original distribution map of 50 task points in situation B

The simulation parameters and platform parameters remain unchanged, and the above task points are planned.The results and comparison are shown in Fig.15.

Fig.15 Comparison of task plan and cost of five algorithms in situation B

It can be seen from the above comparison that the method in this paper has a better performance than the other four methods in task planning.To further compare the performance of the method, another 100 Monte-Carlo experiments are performed to calculate the corresponding cost function.The results are shown in Table 2.

Table 2 Algorithm performance comparison in situation B

Through the above comparison, it can be seen that the performance of the algorithm in this paper is superior to the other five algorithms.Although from the point of view of variance, the algorithm in this paper is not as stable as the other five algorithms, but it still oscillates around a better value.This shows that the algorithm in this paper is superior to other algorithms.

It can be seen from the above simulations that the algorithm in this paper can be used for multi-objective task allocation in different scenarios and has good efficiency.

6.3 Sudden tasks

As mentioned above, in the process of performing tasks,the UAV swarm may burst new tasks.The simulation parameters and environment are the same as the previous section.Five drones are dispatched to perform 50 tasks,but in the process of execution, 20 new tasks will be generated.That is, on the basis of Fig.14, 20 task points are added at random, of which five are added for each task,as shown in Fig.16.

Fig.16 Original distribution map of 50 task points in situation C

Using the above algorithm for comparison, the results are shown in Fig.17 to Fig.22.By comparison, it can be seen that the algorithm in this paper is superior to other algorithms.This is also because the algorithm in this paper has a better effect on dynamic problems.A total of 100 Monte-Carlo simulation experiments are also conducted, and the results are shown in Table 3.

Table 3 Algorithm performance comparison in situation C

Fig.17 Algorithm of this paper (the cost is 53.806 4)

Fig.22 Algorithm in reference [50] (the cost is 54.422 7)

It can be seen from the comparison that the performance of the algorithm in this paper is not stable compared to the algorithms in [48,49].However, the overall performance parameters are better than the other four algorithms.It is more suitable for solving the situation of newly added tasks.And through the time-consuming algorithm, it can be seen that the algorithm based on the division of labor has better real-time performance than the intelligent optimization algorithm.

Fig.19 Ant colony labor division (the cost is 59.143 0)

Fig.20 Algorithm in [48] (the cost is 54.596 3)

Fig.21 Algorithm in reference [49] (the cost is 54.572 3)

7.Conclusions

Aiming at the bee colony double inhibition labor division algorithm that is difficult to handle tasks with multi-dimensional attributes and sudden tasks, this paper improves the algorithm and applies the improved algorithm to the task allocation of the UAV swarm.The results achieved are as follows.

In order to solve the problem that the labor division algorithm is difficult to construct the task chain with multiattributes, this paper regards it as the problem of finding the strongest point of correlation one by one according to the relevance and similarity of tasks.This paper first clusters the task points, finds the points with the strongest correlation in the cluster group, and forms multiple task sub-chains.Then, according to the relevance of each clustering center, multiple task sub-chains are connected together to form a complete task chain, which can construct a correspondence with the age of the bees in the labor division algorithm.

In order to improve the ability of the labor division algorithm to deal with sudden tasks during the execution of tasks, this paper sets a threshold for the relative proportion between the number of sudden tasks and the number of remaining tasks.When it is lower than the threshold,the sudden task is less than the remaining tasks, the degree of correlation between the sudden task and each cluster center is calculated and grouped.Then, insert the sudden task into the original task sub-chain of the group to form a new task chain.When it is higher than the threshold, all tasks are re-planned according to the method above, and a new task chain is obtained.

In order to reflect the performance advantages of the algorithm and the ability to solve practical problems, this paper uses the improved algorithm to solve the dynamic task planning problem of the UAV swarm.Firstly, a model of dynamic task assignment for the UAV swarm is constructed, and then the task types are refined, and multiple objective functions in the task assignment process are quantified.After that, the mapping relationship between biological characteristics and task planning in the labor division algorithm is constructed, and the dynamic adjustment of the task assignment of the UAV swarm is realized by using the self-adjusting characteristics of the bee colony.Through simulation verification and algorithm comparison, the feasibility and superiority of the algorithm in this paper are reflected.

Although this paper is for UAV research, if the task is replaced by another agent’s executable task, and the constraints are adjusted.The model constructed in this paper can be applied to the task assignment of other agents.And from a theoretical perspective, the model constructed in this paper can also be applied to solve the multi-TSP completely as shown in Section 5.1 and Section 5.2.The research is of great significance for solving such optimization problems.