# Mission Planning for Unmanned Aerial Vehicles Based on Voronoi Diagram-Tabu Genetic Algorithm

Authors: Wei Tan; Yong-jiang Hu; Yue-fei Zhao; Wen-guang Li; Xiao-meng Zhang; Yong-ke Li
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Unmanned aerial vehicles (UAVs) are increasingly used in different military missions. In this paper, we focus on the autonomous mission allocation and planning abilities for the UAV systems. Such abilities enable adaptation to more complex and dynamic mission environments. We first examine the mission planning of a single unmanned aerial vehicle. Based on that, we then investigate the multi-UAV cooperative system under the mission background of cooperative target destruction and show that it is a many-to-one rendezvous problem. A heterogeneous UAV cooperative mission planning model is then proposed where the mission background is generated based on the Voronoi diagram. We then adopt the tabu genetic algorithm (TGA) to obtain multi-UAV mission planning. The simulation results show that the single-UAV and multi-UAV mission planning can be effectively realized by the Voronoi diagram-TGA (V-TGA). It is also shown that the proposed algorithm improves the performance by 3% in comparison with the Voronoi diagram-particle swarm optimization (V-PSO) algorithm.


---

## Body

## 1. Introduction

Unprecedented developments in science and technology have enabled the versatile development of unmanned aerial vehicles (UAV). UAVs are used in a variety of civil and military applications.UAV is referred to as an unmanned aircraft that utilizes airborne avionics devices to execute missions via autonomous are radio-controlled flight control within a certain geographic range. Compared to conventional aircraft, UAVs are often cost-effective and have a smaller size. Since they do not need onboard operators, then UAVs are not prone to casualties.Furthermore, UAVs enable executing “3D (dull, dirty and dangerous)” tasks which are otherwise restricted by the physiological capabilities of the pilots [1, 2].Technological advances have also increased the complexity of the battlefield environment [3]. For instance, perceptibility and beyond visual range (BVR) attack capability have been significantly improved. Therefore, it is extremely difficult to execute missions such as reconnaissance, destruction, and strikes only based on a single UAV. In practice, multi-type UAVs are required to improve the success rate of the target missions based on extensive cooperation between different types of UAVs [4–6].The multi-UAV cooperative mission planning is therefore required for efficient executions of the missions. Mission planning often requires the mission type, geographic region, and time of the mission completion. Accurate analysis of the environment, target, and situation on the battlefield is also required. The objective is to maximize the mission success rate while reducing costs. Therefore, mission planning determines the optimal dispatching scheme and flight path design subject to a set of system and environmental constraints and available data [7–9]. Furthermore, multi-UAV cooperative mission planning often deals with multiple combat targets and missions. Therefore, the mission planning should be able to accommodate the priority principles by prioritizing the high-value and close-range targeted within the shortest possible mission execution time and a minimum number of assigned UAVs [1, 2, 10, 11].For the cooperative execution of a mission, multiple heterogeneous UAVs arrive at the designated region. Therefore, each UAV should dynamically plan its path considering the limiting factors such as the enemy’s radars and antidrone systems, as well as its performance limitations. To complete the mission, all the UAVs are also required to reach the target position as planned, i.e., the rendezvous problem [3, 12, 13]. For multiple targets, the rendezvous problem is usually more complex than that of the single target missions. This is because the mission planning needs to consider the time and spatial constraints of the cooperation, e.g., cooperative strike and cooperative search [14].In [15], a multistage path prediction and cooperative trajectory generation algorithm was proposed which is based on the global A∗ algorithm. They then examined the effectiveness of multitarget planning by spreading the missions in a large geographic area. Furthermore, [16] considers the rendezvous problem where multiple UAVs simultaneously arrive at a target. They then derived a mathematical model and develop a distributed framework to find the optimal solution. In their developed method, the cooperative game-based optimal consensus (CGOC) algorithm minimizes the overall cost for completing the mission by multi-UAV cooperation.An efficient solution to the multi-UAV rendezvous and anticollision problem was proposed in [17]. In the solution proposed by [18], each UAV requires to meet other UAVs at the intersection point. This is enabled using velocity control and adopting proper roaming strategies. Furthermore, [18] proposed a hierarchical framework of multi-UAV mission allocation and path planning in a dynamic environment. In this proposed framework, the multi-UAV rendezvous problem is then solved using a negotiation-based mission allocation algorithm and an intersection-based path generation algorithm.Similarly, a hierarchical mission planning method was proposed in [19] to solve the simultaneous multi-UAV attack problem. This method uses a scheme to decouple and then solve the mission planning problem. In the existing methods, rendezvous maneuver is often planned by a control system or special maneuver planner. Nevertheless, in practice, it is extremely hard to accurately predict the path; hence, the mission allocation algorithm may only obtain suboptimal results.To address the abovementioned problem, here we first investigate the single-UAV mission planning. We then formulate the multi-UAV cooperative pattern to complete the target mission as a many-to-one rendezvous problem. We then build a heterogenous multi-UAV cooperative mission planning model. In our model, the mission background (i.e., mapping the threat and target points from the real three-dimensional space to the two-dimensional plane) is generated based on the Voronoi diagram. We then utilize the tabu genetic algorithm (TGA) quickly obtain the solution to the UAV mission planning. We further evaluate the performance of the proposed method in this paper through simulation.The simulation results confirm that Voronoi diagram-TGA (V-TGA) is efficient in the single- and multi-UAV mission planning. It is also shown that in comparison with the Voronoi diagram-particle swarm optimization (V-PSO) algorithm, the proposed algorithm improves the performance by 3%.In this paper, we first examine the mission planning of a single unmanned aerial vehicle. Based on that, we then investigate the multi-UAV cooperative system under the mission background of cooperative target destruction. We then show that this problem is a many-to-one rendezvous problem. A heterogeneous UAV cooperative mission planning model is then proposed in which the mission background is generated based on the Voronoi diagram. We then adopt the tabu genetic algorithm (TGA) to obtain multi-UAV mission planning.The organization of this paper is as the following. The first chapter presents the UAV mission planning model based on Voronoi graph-taboo genetic algorithm. Then, in Chapter 2, we introduce the principle of the Voronoi graph-taboo genetic algorithm.The third chapter presents the simulation results for a single UAV path optimization mission planning. Chapter four introduces multi-UAV mission planning based on the Voronoi diagram-taboo genetic algorithm. The conclusions are presented at the end of the paper.


## 2. UAV Mission Planning Model Based on Voronoi Diagram-TGA (V-TGA)

### 2.1. The Mission Background

Here, we consider a model, whereNT is the number of important targets, NB is the number of UAV bases, and NC UAVs are set in the target region. For different types of missions, different loaded UAVs were dispatched to the target region. For single-UAV mission allocation and path planning, the objective is to arrive at the target region with the minimum path cost. The main components of our model are defined in the following Figure 1. In Figure 1, the green squares indicate the threat point, the red diamonds are the UAV base, and the black solid lines represent the flight path.Figure 1
The schematic diagram of mission background.Target: the targets are the initially confirmed key enemy missions with certain electronic protection abilities and antiair capability. The number of targets is denoted byNT.Mission: the UAVs must quickly arrive at the designated target region.To facilitate the analysis, we adopt the following hypotheses:(1)
All types of UAVs have favorable load performance, and all are capable of completing their missions(2)
The flight speed of the UAVs are the same


### 2.2. Decision Variable

The decision variable is defined as(1)Xvi,vju,k=1TheUAVperformedthemission0TheUAVdidperformedamission,where k represents the type of UAV and u represents the serial number of UAV.


### 2.3. Constraint Conditions

The Voronoi diagram can provide an effective graphical expression of the objects and regions in the topological structures. The Voronoi diagram has been widely used to solve the related problems in the field of UAV mission planning [20, 21]. In this study, the Voronoi diagram is used to generate the mission environment space and express the possible UAV paths in the graphical form:
(2)T=T1,T2,⋯,TNTP=P1,P2,⋯,PNVV=TUUE=vi,vjvi∈V,vj∈T,where T is the target set, P is the set of threat sources, V is the set of nodes in the directed graph, and E is the set of edges of the directed graph.The constraints considered in the heterogenous multi-UAV collaborative general mission planning are as the following.(1)
Path constraint: for UAVu∈U, Pau is a flyable path, namely,(3)pau=vi,vjXvi,vju,k=1.(2)
All targets are confirmed:(4)∑i=1NVT∑j=1NT∑k=12Xvi,vju,k=NT.(3)
The endurance constraint of the UAV must be met, i.e., the flight range of each UAV must be shorter than their maximum rangeLmaxu which is expressed as(5)∑i=1NVT∑j=1NT∑k=12tvi,vju,kVu=Lmaxu,where tvi,vju,k is the time spent by the UAV u executing the mission along the edge vi,vj, and Vu is the flight velocity of UAV u.Our objective is to obtain the shortest possible mission execution pathJ. Therefore, the objective function is formulated as the following:
(6)J=min∑i=1NVT∑j=1NT∑k=12Xvi,vju,ktvi,vju,kV0.


## 2.1. The Mission Background

Here, we consider a model, whereNT is the number of important targets, NB is the number of UAV bases, and NC UAVs are set in the target region. For different types of missions, different loaded UAVs were dispatched to the target region. For single-UAV mission allocation and path planning, the objective is to arrive at the target region with the minimum path cost. The main components of our model are defined in the following Figure 1. In Figure 1, the green squares indicate the threat point, the red diamonds are the UAV base, and the black solid lines represent the flight path.Figure 1
The schematic diagram of mission background.Target: the targets are the initially confirmed key enemy missions with certain electronic protection abilities and antiair capability. The number of targets is denoted byNT.Mission: the UAVs must quickly arrive at the designated target region.To facilitate the analysis, we adopt the following hypotheses:(1)
All types of UAVs have favorable load performance, and all are capable of completing their missions(2)
The flight speed of the UAVs are the same


## 2.2. Decision Variable

The decision variable is defined as(1)Xvi,vju,k=1TheUAVperformedthemission0TheUAVdidperformedamission,where k represents the type of UAV and u represents the serial number of UAV.


## 2.3. Constraint Conditions

The Voronoi diagram can provide an effective graphical expression of the objects and regions in the topological structures. The Voronoi diagram has been widely used to solve the related problems in the field of UAV mission planning [20, 21]. In this study, the Voronoi diagram is used to generate the mission environment space and express the possible UAV paths in the graphical form:
(2)T=T1,T2,⋯,TNTP=P1,P2,⋯,PNVV=TUUE=vi,vjvi∈V,vj∈T,where T is the target set, P is the set of threat sources, V is the set of nodes in the directed graph, and E is the set of edges of the directed graph.The constraints considered in the heterogenous multi-UAV collaborative general mission planning are as the following.(1)
Path constraint: for UAVu∈U, Pau is a flyable path, namely,(3)pau=vi,vjXvi,vju,k=1.(2)
All targets are confirmed:(4)∑i=1NVT∑j=1NT∑k=12Xvi,vju,k=NT.(3)
The endurance constraint of the UAV must be met, i.e., the flight range of each UAV must be shorter than their maximum rangeLmaxu which is expressed as(5)∑i=1NVT∑j=1NT∑k=12tvi,vju,kVu=Lmaxu,where tvi,vju,k is the time spent by the UAV u executing the mission along the edge vi,vj, and Vu is the flight velocity of UAV u.Our objective is to obtain the shortest possible mission execution pathJ. Therefore, the objective function is formulated as the following:
(6)J=min∑i=1NVT∑j=1NT∑k=12Xvi,vju,ktvi,vju,kV0.


## 3. Principles of the V-TGA Algorithm

### 3.1. Basic Principle of the GA

The GA is an evolutionary algorithm that is based on the “survival of the fittest” principle [22]. The genetic algorithm starts from a population that represents the possible potential solution set. A population is composed of a certain number of individuals coded by genes. Each individual is an entity with several chromosome characteristics. As the main carrier of genetic material, a chromosome is a collection of multiple genes. Its internal performance (i.e., genotype) is a certain combination of genes, which determines the external performance of an individual’s shape. For instance, the characteristics of black hair are controlled by the chromosome, which is determined by a certain combination of the genes for a characteristic. Therefore, it is necessary to realize the mapping from phenotype to genotype which is performed by the coding at the beginning. Since the work of imitating gene coding is complex, it is often simplified as binary coding. After the first generation population is generated, according to the principle of survival of the fittest, the generations evolve to produce better and better approximate solutions. In the first generation, the individuals are selected according to their fitness in the problem domain. The crossovers and mutations are then combined using the genetic operators to generate a representative new population of the solution set. This process results in the offspring population of the population similar to the natural evolution to be more adapted to the environment than the previous generation. The optimal individual in the last generation population can be used as the approximate optimal solution to the problem after decoding [13].Through multiple iterations, the GA then generates the chromosomes conforming to the optimization objective.


### 3.2. Mission/Path Planning Based on V-TGA Algorithm

In this study, the mission environment space is generated through the Voronoi diagram. We use the tabu algorithm to enhance the population diversity of GA. The V-TGA is then designed and applied to the UAV mission planning.The general idea of the proposed algorithm is as the following. The mission environment space is divided using the Voronoi diagram. This is to effectively reduce the space complexity. The tabu criteria and tabu list of the tabu algorithm are then introduced into the GA. This improves the global searching ability of the algorithm and reduces the possibility of getting caught in a local optimum.If the new offsprings produced by the crossover are better individuals (reaching the desired level), they go directly to the next generation. This is regardless of whether they are taboo or not. As for the general chromosome (i.e., not reaching the desired level), if it has been taboo, it cannot enter the next generation. An individual who is not on the taboo list is then randomly generated. The above operations can improve the diversity of the population and avoid premature algorithms.


### 3.3. Chromosome Coding

Coding is essential in the GA. Here, we examine the UAV mission planning for two models including the single-UAV and multi-UAV models described in Chapter 4. The coding mode of the single-UAV mission planning is as the following:(7)X=v1,v2,⋯,vn.The coding mode is the set of nodes in the UAV attack path (i.e., the path of the drone from the starting point to the target point). The final path is, therefore,S,X,E=S,v1,v2,⋯,vn,E, where S is the starting point, and E is the target.


### 3.4. Crossover

Two crossover modes — multi-point crossover and algorithm crossover — are designed to enhance the population diversity. The probability of each crossover mode is set to 50%.As for the multipoint crossover,1×N random numbers between 0 and 1 are randomly generated, where N is the chromosome length. If the random number i is smaller than 0.2, the inheritance is started from parent 1; otherwise, it is started from parent 2.The algorithm crossover is expressed as the following formula:(8)Xnew=RXp1+1−RXp2,where Xp1 and Xp2 are the parent 1 and parent 2, respectively, Xnew represents the new individual, R denotes 1xN random numbers between 0 and 1, and N is the chromosome length.


### 3.5. Mutation

To enhance the population diversity, we use two mutation modes—single-point mutation and Gaussian mutation. The probability of each mutation mode is also set to 50%.For the single-point mutation, a positive integerr between 1 and N is randomly generated, and the gene of the present new individual at the locus r is regenerated.The Gaussian mutation is expressed as the following formula:(9)Xnew=Xnew+λ×Rn,where Rn represents 1xN random numbers following the Gaussian distribution, and λ is a coefficient.


### 3.6. The Fitness Function

Here, the objective is to obtain the shortest mission execution pathJ. Therefore, the objective function is defined as the following:
(10)J=min∑i=1NVT∑j=1NT∑k=12Xvi,vju,ktvi,vju,kV0,where tvi,vju,k is the time spent by the UAV u to execute the mission along the edge vi,vj, V0 is the UAV velocity, and Xvi,vju,k is the decision variable.


### 3.7. The Steps of V-TGA

Step 1.
Generate the mission environment space through the Voronoi diagram and set the algorithm parameters.Step 2.
Initialize the population and calculate the fitness value of each individual.Step 3.
Initialize the tabu list.Step 4.
SetGen=Gen+1.Step 5.
Use the tournament selection method to select the parent individuals.Step 6.
For any parent individual, perform the crossover operation with a probability of p1 (noncrossover operation at a probability of 1-p1). Two crossover methods, including multipoint crossover and algorithm crossover, are used. One of the methods is randomly selected. Also, the probability of using any of these methods is the same.Step 7.
Perform the mutation operation for new individuals with a probability of p2. Two mutation methods including single-point mutation and Gaussian mutation are used. Similar to step 6, one of the methods is randomly selected. Also, the probability of using any of these methods is the same.Step 8.
Check whether the new individuals are included in the tabu list. If yes, regenerate them.Step 9.
Calculate the fitness of new individuals.Step 10.
Update the tabu list.Step 11.
Combine the parent and the offspring populations, select the optimal individuals, and enter the next generation which is based on the survival of the fittest (i.e., elite selection).Step 12.
IfGen<maxgen and the algorithm is not converged, go to step 4; otherwise, end the algorithm and output the calculation results.


### 3.8. Algorithm Conclusion

As mentioned before, the mission environment space is divided using the Voronoi diagram. Therefore, the path search problem in a complex spatial region is transformed into a simple search problem of the weighted diagram. This intuitive approach facilitates the implementation. This addresses the issue with the complexity of the space. The “tabu” criteria of the tabu algorithm are introduced into the GA so that the good chromosomes are directly reserved for the next generation. This further reduces the frequency of individual replacement. If the offspring generated by the crossover operation reaches the aspiration level, the next generation is directly entered. This is irrespective of whether it was tabooed or not. However, for ordinary chromosomes, the next generation is not entered if they do not reach the aspiration level or are already tabooed. Therefore, the parent chromosomes should be chosen. This guarantees that the population diversity and the prematurity of the algorithm are avoided.In the third and fourth chapters of this article, the V-TGA algorithm is mainly compared with V-PSO. In the principle of the PSO algorithm, each particle in the particle swarm has a fitness determined by the optimization function and a speed that determines their flight direction and distance. By continuously updating their position and speed, all particles can follow the current. The optimal particle is searched for in the entire solution space. This algorithm, with few parameters and easy to implement, is favored by many scholars and only suitable for optimization continuity problems and cannot be directly used to solve discrete optimization problems [23, 24].


## 3.1. Basic Principle of the GA

The GA is an evolutionary algorithm that is based on the “survival of the fittest” principle [22]. The genetic algorithm starts from a population that represents the possible potential solution set. A population is composed of a certain number of individuals coded by genes. Each individual is an entity with several chromosome characteristics. As the main carrier of genetic material, a chromosome is a collection of multiple genes. Its internal performance (i.e., genotype) is a certain combination of genes, which determines the external performance of an individual’s shape. For instance, the characteristics of black hair are controlled by the chromosome, which is determined by a certain combination of the genes for a characteristic. Therefore, it is necessary to realize the mapping from phenotype to genotype which is performed by the coding at the beginning. Since the work of imitating gene coding is complex, it is often simplified as binary coding. After the first generation population is generated, according to the principle of survival of the fittest, the generations evolve to produce better and better approximate solutions. In the first generation, the individuals are selected according to their fitness in the problem domain. The crossovers and mutations are then combined using the genetic operators to generate a representative new population of the solution set. This process results in the offspring population of the population similar to the natural evolution to be more adapted to the environment than the previous generation. The optimal individual in the last generation population can be used as the approximate optimal solution to the problem after decoding [13].Through multiple iterations, the GA then generates the chromosomes conforming to the optimization objective.


## 3.2. Mission/Path Planning Based on V-TGA Algorithm

In this study, the mission environment space is generated through the Voronoi diagram. We use the tabu algorithm to enhance the population diversity of GA. The V-TGA is then designed and applied to the UAV mission planning.The general idea of the proposed algorithm is as the following. The mission environment space is divided using the Voronoi diagram. This is to effectively reduce the space complexity. The tabu criteria and tabu list of the tabu algorithm are then introduced into the GA. This improves the global searching ability of the algorithm and reduces the possibility of getting caught in a local optimum.If the new offsprings produced by the crossover are better individuals (reaching the desired level), they go directly to the next generation. This is regardless of whether they are taboo or not. As for the general chromosome (i.e., not reaching the desired level), if it has been taboo, it cannot enter the next generation. An individual who is not on the taboo list is then randomly generated. The above operations can improve the diversity of the population and avoid premature algorithms.


## 3.3. Chromosome Coding

Coding is essential in the GA. Here, we examine the UAV mission planning for two models including the single-UAV and multi-UAV models described in Chapter 4. The coding mode of the single-UAV mission planning is as the following:(7)X=v1,v2,⋯,vn.The coding mode is the set of nodes in the UAV attack path (i.e., the path of the drone from the starting point to the target point). The final path is, therefore,S,X,E=S,v1,v2,⋯,vn,E, where S is the starting point, and E is the target.


## 3.4. Crossover

Two crossover modes — multi-point crossover and algorithm crossover — are designed to enhance the population diversity. The probability of each crossover mode is set to 50%.As for the multipoint crossover,1×N random numbers between 0 and 1 are randomly generated, where N is the chromosome length. If the random number i is smaller than 0.2, the inheritance is started from parent 1; otherwise, it is started from parent 2.The algorithm crossover is expressed as the following formula:(8)Xnew=RXp1+1−RXp2,where Xp1 and Xp2 are the parent 1 and parent 2, respectively, Xnew represents the new individual, R denotes 1xN random numbers between 0 and 1, and N is the chromosome length.


## 3.5. Mutation

To enhance the population diversity, we use two mutation modes—single-point mutation and Gaussian mutation. The probability of each mutation mode is also set to 50%.For the single-point mutation, a positive integerr between 1 and N is randomly generated, and the gene of the present new individual at the locus r is regenerated.The Gaussian mutation is expressed as the following formula:(9)Xnew=Xnew+λ×Rn,where Rn represents 1xN random numbers following the Gaussian distribution, and λ is a coefficient.


## 3.6. The Fitness Function

Here, the objective is to obtain the shortest mission execution pathJ. Therefore, the objective function is defined as the following:
(10)J=min∑i=1NVT∑j=1NT∑k=12Xvi,vju,ktvi,vju,kV0,where tvi,vju,k is the time spent by the UAV u to execute the mission along the edge vi,vj, V0 is the UAV velocity, and Xvi,vju,k is the decision variable.


## 3.7. The Steps of V-TGA

Step 1.
Generate the mission environment space through the Voronoi diagram and set the algorithm parameters.Step 2.
Initialize the population and calculate the fitness value of each individual.Step 3.
Initialize the tabu list.Step 4.
SetGen=Gen+1.Step 5.
Use the tournament selection method to select the parent individuals.Step 6.
For any parent individual, perform the crossover operation with a probability of p1 (noncrossover operation at a probability of 1-p1). Two crossover methods, including multipoint crossover and algorithm crossover, are used. One of the methods is randomly selected. Also, the probability of using any of these methods is the same.Step 7.
Perform the mutation operation for new individuals with a probability of p2. Two mutation methods including single-point mutation and Gaussian mutation are used. Similar to step 6, one of the methods is randomly selected. Also, the probability of using any of these methods is the same.Step 8.
Check whether the new individuals are included in the tabu list. If yes, regenerate them.Step 9.
Calculate the fitness of new individuals.Step 10.
Update the tabu list.Step 11.
Combine the parent and the offspring populations, select the optimal individuals, and enter the next generation which is based on the survival of the fittest (i.e., elite selection).Step 12.
IfGen<maxgen and the algorithm is not converged, go to step 4; otherwise, end the algorithm and output the calculation results.


## 3.8. Algorithm Conclusion

As mentioned before, the mission environment space is divided using the Voronoi diagram. Therefore, the path search problem in a complex spatial region is transformed into a simple search problem of the weighted diagram. This intuitive approach facilitates the implementation. This addresses the issue with the complexity of the space. The “tabu” criteria of the tabu algorithm are introduced into the GA so that the good chromosomes are directly reserved for the next generation. This further reduces the frequency of individual replacement. If the offspring generated by the crossover operation reaches the aspiration level, the next generation is directly entered. This is irrespective of whether it was tabooed or not. However, for ordinary chromosomes, the next generation is not entered if they do not reach the aspiration level or are already tabooed. Therefore, the parent chromosomes should be chosen. This guarantees that the population diversity and the prematurity of the algorithm are avoided.In the third and fourth chapters of this article, the V-TGA algorithm is mainly compared with V-PSO. In the principle of the PSO algorithm, each particle in the particle swarm has a fitness determined by the optimization function and a speed that determines their flight direction and distance. By continuously updating their position and speed, all particles can follow the current. The optimal particle is searched for in the entire solution space. This algorithm, with few parameters and easy to implement, is favored by many scholars and only suitable for optimization continuity problems and cannot be directly used to solve discrete optimization problems [23, 24].


## 4. Single-UAV Path Optimization and Mission Planning

### 4.1. Simulation Platform

We use a Huawei Honor MagicBook2019 laptop with an AMD Ryzen 5 3500 U/8GB/64-bit processor and Win10 operating system. The programming tool is MatlabR2016b (64 bits).


### 4.2. Simulation Process

Here, we simulate the single-UAV path optimization and mission planning based on V-TGA. The battlefield environment is set within a range of100km×100km, including 55 enemy radars with the same spatial density. The V-TGA is used to plan the single-UAV paths for three UAVs. The simulation results are presented in the following Table 1.Table 1
Single UAV trajectory fitness value.
V-TGA algorithmV-PSO algorithmLeft base, left target65.531265.5312Intermediate-based intermediate target89.760196.0699Right base, the right target49.942452.5149In Figure2, (1)–(6) are the path trajectories of a single UAV from different UAV bases to different targets, where (1),(3), and (5) are the V-TGA algorithm, and (2),(4), and (6) are the V-PSO algorithm. The trajectory adaptation value of a single UAV obtained in the experiment is shown in Table 1.Figure 2
Single UAV trajectory diagram.For the left target, the simulation results suggest that the path cost of the V-TGA algorithm is 4% lower than that of the V-PSO algorithm. Moreover, by Figures3–5, the V-TGA requires fewer iterations than that of the PSO. In the selection of launching sites, the V-TGA algorithm outperforms the V-PSO algorithm in increasing the survival rate of the UAVs and reducing their horizontal movement. Furthermore, the algorithms were able to choose a proper launching site and conduct the optimal mission path planning.Figure 3
The fitness function of the left base, left target.Figure 4
The fitness function of the intermediate-based intermediate target.Figure 5
The fitness function of the right base, right target.


## 4.1. Simulation Platform

We use a Huawei Honor MagicBook2019 laptop with an AMD Ryzen 5 3500 U/8GB/64-bit processor and Win10 operating system. The programming tool is MatlabR2016b (64 bits).


## 4.2. Simulation Process

Here, we simulate the single-UAV path optimization and mission planning based on V-TGA. The battlefield environment is set within a range of100km×100km, including 55 enemy radars with the same spatial density. The V-TGA is used to plan the single-UAV paths for three UAVs. The simulation results are presented in the following Table 1.Table 1
Single UAV trajectory fitness value.
V-TGA algorithmV-PSO algorithmLeft base, left target65.531265.5312Intermediate-based intermediate target89.760196.0699Right base, the right target49.942452.5149In Figure2, (1)–(6) are the path trajectories of a single UAV from different UAV bases to different targets, where (1),(3), and (5) are the V-TGA algorithm, and (2),(4), and (6) are the V-PSO algorithm. The trajectory adaptation value of a single UAV obtained in the experiment is shown in Table 1.Figure 2
Single UAV trajectory diagram.For the left target, the simulation results suggest that the path cost of the V-TGA algorithm is 4% lower than that of the V-PSO algorithm. Moreover, by Figures3–5, the V-TGA requires fewer iterations than that of the PSO. In the selection of launching sites, the V-TGA algorithm outperforms the V-PSO algorithm in increasing the survival rate of the UAVs and reducing their horizontal movement. Furthermore, the algorithms were able to choose a proper launching site and conduct the optimal mission path planning.Figure 3
The fitness function of the left base, left target.Figure 4
The fitness function of the intermediate-based intermediate target.Figure 5
The fitness function of the right base, right target.


## 5. Multi-UAV Mission Planning Based on V-TGA

### 5.1. Introduction of Mission Background

As the complexity of the battlefield environment is aggravated and the perceptibility and BVR attack ability of both sides are strengthened, it is very difficult to complete the mission of target destruction just by relying upon a single UAV.Multiple types of UAVs are required to increase the success rate of mission completion. In the modern battlefield, jamming UAVs (JUAVs) are required to perform electronic jamming. This is to ensure that combat UAVs (CUAVs) will not be detected by the enemy’s radars (as shown in Figure6). This process mainly embodies the cooperation to increase the success rate of the attacking UAVs (AUAVs) in completing their missions and their survival rate.Figure 6
Schematic diagram of jamming-combat UAV cooperation.In the early-stage reconnaissance mission region, we considerNT important targets, NC CUAVs, and NJ JUAVs. The strike mission should be completed cooperatively by the JUAVs and AUAVs. The mission allocation and path planning are conducted by the JUAVs and AUAVs in the target region so that they could complete the strike mission efficiently.UAV: according to the different load types, the UAVs are mainly divided into two types: aUAVs and JUAVs, namely, AUAV1 and JUAV2, with the numbers of NA and NS, respectively. The UAV should reach the destination at the same time, and the UAV that arrives near the destination first can hover at the apex of the Voronoi diagram.Target: the targets are the initially confirmed key enemy targets with certain electronic protection abilities and antiair capability. The number of targets is set toNT.Mission: The AUAVs cooperatively jam the UAVs and attack when the jamming effectively disables the enemy. This is to ensure the survival of the UAVs where each target has jamming and attacking missions.


### 5.2. Chromosome Coding

#### 5.2.1. Chromosome Coding

Here, we adopt real number coding which is specifically defined as the priorityprij of each UAV to head for each node.
(11)X=prij∣1≤i≤K,1≤j≤N,0<prij<1,where K is the number of UAVs, and N stands for the number of nodes. This coding mode can transfer the constraint processing from the generation of the initial solution into the decoding process. This is to avoid constraint processing and error correction during the generation of the new solution. This method can effectively reduce the complexity of algorithm design and operation and evade the information loss caused by the error correction.


#### 5.2.2. Chromosome Decoding

As the coding is not equivalent to any decision variable in this study, decoding is also required. Here, the coding is transformed into a decision variable, and the value of the fitness function is calculated. The decoding process is as follows:For the UAVi,Step 1.
The priorities of the UAVsi to M start nodes are extracted from the coding.Step 2.
The highest priority start node that is not occupied by other UAVs is selected.Step 3.
Other nodes connectable to the present node are then obtained. If all these nodes are visited, the UAV path backed off to the node next to the last node. The last node is also deleted in the present path. The priority of each unvisited node is also acquired, and the unvisited node with the highest priority is chosen as the next node to be visited by the UAV.Step 4.
The present node of the UAV is updated, and it is determined whether it arrived at the target. If yes, the path decoding of the present UAV is ended,i=i+1, and the algorithm returns to step. Otherwise, the decoding process is implemented from step 4.


#### 5.2.3. Design of the Fitness Function

Here, our objective is to obtain the shortest mission execution pathJ. Therefore, the fitness function is defined as the following:
(12)J=min∑i=1NVT∑j=1NT∑k=12Xvi,vju,ktvi,vju,kV0,where tvi,vju,k denotes the time spent by the UAV u in executing the mission along the edge vi,vj, V0 stands for the UAV velocity, and Xvi,vju,k represents the decision variable.


#### 5.2.4. Tabu List

The chromosomes generated by the algorithm are saved in the tabu list following the first-in-first-out rule.


#### 5.2.5. V-TGA Algorithm Steps

Step 1.
The mission environment space is generated via the Voronoi diagram, and the algorithm parameters are set accordingly.Step 2.
The population is initialized, and the fitness value of each individual is obtained.Step 3.
The tabu list is initialized.Step 4.
Gen=Gen+1.Step 5.
The parent individuals are selected using the tournament selection method.Step 6.
Any parent individual is crossed over with the probability ofP1 and not crossed over with the probability of 1−P1.Step 7.
New individuals are mutated with the probability ofP2.Step 8.
Check whether the new individuals are already in the tabu list. If yes, the aspiration criterion is not satisfied and the individuals are regenerated.Step 9.
The fitness values of new individuals are obtained.Step 10.
The tabu list is updated.Step 11.
The parent population and offspring population are merged, and the optimal parent and offspring individuals are chosen to enter the next generation.Step 12.
IfGen<maxgen and the convergence are failed, the algorithm is then executed once again from step 4; otherwise, the algorithm is ended, and the calculation results are provided as the outputs.


#### 5.2.6. Pseudocode 1

Input is as follows: coordinates of each node, population size, pop size, the maximum number of iterations, maxIter, crossover and mutation probabilities, and length of tabu list.Pseudocode 1
1. Use Voronoi diagram.2. Initialize the population.3. For iter =1: maxIter.4. Select individuals using the tournament method.5. Perform crossover operation as in Section 2.4.6. Perform mutation operation as in Section 2.5.7. Deleting and regenerate the duplicate individuals according to the tabu list.8. Recalculate the fitness values.9. Update the tabu list.10.End.The coding method consists of two parts. The Sa denotes the starting point of each UAV, Pa is the set of nodes passed by the respective attack paths of two UAVs for each target,Ns is the number of candidate starting points, and S0 is the set of candidate starting points. For the i(th) target, the attack path of the j(th) UAV is Sij,v1ij,v2ij,⋯vnijij,Eij, where Sij is the starting point of the j(th) UAV for the i(th) target, and Eij is the target of the j(th) UAV for the i(th) target. As the two UAVs for any target cannot be overlapped, the following constraints should be also met:
(13)X=Sa,PaSa=SijSij∈S0,1<i<Ns,j=1,2Pa=Pij1<i<Ns,j=1,2Pij=V1ij,V1ij,⋯Vnijijvji1∉Pi2,vji2∉Pi1.


### 5.3. Design of the Fitness Function

The longer the flight time of the UAV during the attack mission, the higher the probability of being threatened by the enemy. Therefore, the total processing time and total path should be as short as possible. The fitness functionJ of multidrone is the same as that of single drone, please refer to Section 2.6.


### 5.4. Simulation Process

The flight velocity of the UAV is set to 100 km/h, a single flight lasts 6 h, and the UAVs of two load types, namely, JUAV and CUAV, are randomly generated 3 targets within 100 km range, respectively. Two UAV types form one group and select the overall shortest path to cooperatively strike and destroy three different mission targets from the base.It could be observed from Figure7 that in the initial plan, the targets 1, 2, and 3 are struck cooperatively by the JUAV and CUAV through selecting the bases (1, 8), (5, 6), and (4, 7) as their respective initial bases. The total value of the objective function is 488.2233 km (Table 2).Figure 7
The initial plan of the cooperative strike path.Table 2
Comparison of the fitness values.
AlgorithmBase coordinatesDistanceInitial plan(1, 8), (5, 6), (4, 7)448.2192V-PSO(1, 3), (4, 7), (6, 8)425.8619V-TAGA(2, 5), (3, 4), (7, 8)404.2302It is seen in Figure8 that the targets 1, 2, and 3 are cooperatively struck by the JUAV and CUAV through selecting the bases (1, 3), (4, 7), and (6, 8) as their respective initial bases. The total value of the objective function is 425.8619 km (Table 2).Figure 8
The cooperative strike path under the V-PSO algorithm.In the cooperative strike path under the V-TGA algorithm presented in Figure9, the targets 1, 2, and 3 are cooperatively struck by the JUAV and CUAV through selecting the bases (2, 5), (3, 4), and (7, 8) as their respective initial bases. The total value of the objective function is also 404.2302 km (Table 2).Figure 9
The cooperative strike path under the V-TGA algorithm.The fitness iteration curves (Figure10) also show that the V-TGA algorithm requires fewer iterations. This algorithm also provides a higher convergence rate and obtains a better objective value than that of the V-PSO algorithm. In general, the algorithm performance is improved by over 3% compared with the V-PSO algorithm.Figure 10
The fitness function curves.The simulations also suggest that both V-TGA and V-PSO algorithms obtain a shorter path than that of the initial plan. The V-PSO algorithm improves the performance by 5% and the V-TGA algorithm by 10%. It is also seen in Figure6 that the number of iterations required for the V-TGA algorithm is smaller than that of the V-PSO algorithm. It is also seen that the obtained path by this algorithm was shorter.The results manifest that given the known enemy’s situation and the targets of different mission types, the V-TGA algorithm can dynamically deploy the launching bases through mobile launching vehicles. It can also select the proper shortest path and reduce the flight at transverse distances.


### 5.5. Compare Algorithms and Parameter Settings

#### 5.5.1. Compare Algorithms and Parameter Settings

In order to verify the effectiveness of the algorithm proposed in this paper, this paper selects some swarm intelligence algorithms for comparative experiments. These algorithms include classic swarm intelligence algorithms: genetic algorithm (GA) [25], particle swarm algorithm (PSO) [26], and recent the latest swarm intelligence algorithms in recent years: whale optimization agorithm (WOA) [27], loin swarm optimization (LSO) [28], and sparrow search algorithm (SSA) [29]. In order to conduct scientific control experiments, all algorithms use the same common parameters, coding methods, and initial populations and are solved based on the task space obtained by the Voronoi diagram. At the same time, each calculation example is repeated 100 times. The parameters of the algorithm are as follows: the population size is 50, the maximum number of iterations is 100, the mutation probability is 0.1, the crossover probability is 0.8, the inertia weight is 0.8, the individual and global learning factors are 1 and 1, the adult lion ratio is 0.5, and the discoverer alert threshold is 0.8. The ratio of discoverers is 0.2, and the ratio of investigators is 0.1.


#### 5.5.2. Example Data

In order to scientifically verify the performance of the algorithm, this paper has designed three different scales of calculation example data, and the specific calculation example data are shown in Table3. In addition, the flying speed of the UAV is 100 km/h, and the single flight time is 6 h. The two types of UAVs are JUAC and CUAV.Table 3
Three types of example data.
ExamplesMap sizeTask quantityUAV launch position numberThreat number1[50, 50]36302[100, 100]510503[150, 150]1020100


#### 5.5.3. Simulation Results

The above three calculation example data use different swarm intelligence algorithms to solve the average optimal target value of 100 times and the average convergence curve as follows in Table4:Table 4
Algorithm convergence curve comparison.
Algorithm\example123GA383.746727.3041493.956PSO384.303726.3831485.488LSO379.819724.1061491.977SSA381.724724.5491471.975WOA381.234727.3761489.955V-TGA379.191721.9251455.108It can be seen from Table2 that the algorithms proposed in this paper have achieved the highest accuracy when solving large, medium, and small-scale calculation examples. With the increase in the scale of the calculation examples, the calculation difficulty and complexity increase, and the calculation accuracy of the V-TGA algorithm is greater than the gap with other algorithms.It can be seen from the convergence curves of the three calculation examples in Figures11–13 that the algorithm proposed in this paper has the fastest convergence rate in the early stage, and it has not fallen into the local optimum due to the excessively fast convergence rate. It can be seen from the final road map (Figures 14–16) obtained by the algorithm in this paper that for all mission targets, two different types of UAVs arrive at the target point from different directions at the same time, successfully achieving the coordinated strike mission.Figure 11
The fitness function curve of algorithms in example 2.Figure 12
The fitness function curve of algorithms in example 2.Figure 13
The fitness function curve of algorithms in example 3.Figure 14
V-TGA coordinated attack path of example 1.Figure 15
V-TGA coordinated attack path of example 2.Figure 16
V-TGA coordinated attack path of example 3.


## 5.1. Introduction of Mission Background

As the complexity of the battlefield environment is aggravated and the perceptibility and BVR attack ability of both sides are strengthened, it is very difficult to complete the mission of target destruction just by relying upon a single UAV.Multiple types of UAVs are required to increase the success rate of mission completion. In the modern battlefield, jamming UAVs (JUAVs) are required to perform electronic jamming. This is to ensure that combat UAVs (CUAVs) will not be detected by the enemy’s radars (as shown in Figure6). This process mainly embodies the cooperation to increase the success rate of the attacking UAVs (AUAVs) in completing their missions and their survival rate.Figure 6
Schematic diagram of jamming-combat UAV cooperation.In the early-stage reconnaissance mission region, we considerNT important targets, NC CUAVs, and NJ JUAVs. The strike mission should be completed cooperatively by the JUAVs and AUAVs. The mission allocation and path planning are conducted by the JUAVs and AUAVs in the target region so that they could complete the strike mission efficiently.UAV: according to the different load types, the UAVs are mainly divided into two types: aUAVs and JUAVs, namely, AUAV1 and JUAV2, with the numbers of NA and NS, respectively. The UAV should reach the destination at the same time, and the UAV that arrives near the destination first can hover at the apex of the Voronoi diagram.Target: the targets are the initially confirmed key enemy targets with certain electronic protection abilities and antiair capability. The number of targets is set toNT.Mission: The AUAVs cooperatively jam the UAVs and attack when the jamming effectively disables the enemy. This is to ensure the survival of the UAVs where each target has jamming and attacking missions.


## 5.2. Chromosome Coding

### 5.2.1. Chromosome Coding

Here, we adopt real number coding which is specifically defined as the priorityprij of each UAV to head for each node.
(11)X=prij∣1≤i≤K,1≤j≤N,0<prij<1,where K is the number of UAVs, and N stands for the number of nodes. This coding mode can transfer the constraint processing from the generation of the initial solution into the decoding process. This is to avoid constraint processing and error correction during the generation of the new solution. This method can effectively reduce the complexity of algorithm design and operation and evade the information loss caused by the error correction.


### 5.2.2. Chromosome Decoding

As the coding is not equivalent to any decision variable in this study, decoding is also required. Here, the coding is transformed into a decision variable, and the value of the fitness function is calculated. The decoding process is as follows:For the UAVi,Step 1.
The priorities of the UAVsi to M start nodes are extracted from the coding.Step 2.
The highest priority start node that is not occupied by other UAVs is selected.Step 3.
Other nodes connectable to the present node are then obtained. If all these nodes are visited, the UAV path backed off to the node next to the last node. The last node is also deleted in the present path. The priority of each unvisited node is also acquired, and the unvisited node with the highest priority is chosen as the next node to be visited by the UAV.Step 4.
The present node of the UAV is updated, and it is determined whether it arrived at the target. If yes, the path decoding of the present UAV is ended,i=i+1, and the algorithm returns to step. Otherwise, the decoding process is implemented from step 4.


### 5.2.3. Design of the Fitness Function

Here, our objective is to obtain the shortest mission execution pathJ. Therefore, the fitness function is defined as the following:
(12)J=min∑i=1NVT∑j=1NT∑k=12Xvi,vju,ktvi,vju,kV0,where tvi,vju,k denotes the time spent by the UAV u in executing the mission along the edge vi,vj, V0 stands for the UAV velocity, and Xvi,vju,k represents the decision variable.


### 5.2.4. Tabu List

The chromosomes generated by the algorithm are saved in the tabu list following the first-in-first-out rule.


### 5.2.5. V-TGA Algorithm Steps

Step 1.
The mission environment space is generated via the Voronoi diagram, and the algorithm parameters are set accordingly.Step 2.
The population is initialized, and the fitness value of each individual is obtained.Step 3.
The tabu list is initialized.Step 4.
Gen=Gen+1.Step 5.
The parent individuals are selected using the tournament selection method.Step 6.
Any parent individual is crossed over with the probability ofP1 and not crossed over with the probability of 1−P1.Step 7.
New individuals are mutated with the probability ofP2.Step 8.
Check whether the new individuals are already in the tabu list. If yes, the aspiration criterion is not satisfied and the individuals are regenerated.Step 9.
The fitness values of new individuals are obtained.Step 10.
The tabu list is updated.Step 11.
The parent population and offspring population are merged, and the optimal parent and offspring individuals are chosen to enter the next generation.Step 12.
IfGen<maxgen and the convergence are failed, the algorithm is then executed once again from step 4; otherwise, the algorithm is ended, and the calculation results are provided as the outputs.


### 5.2.6. Pseudocode 1

Input is as follows: coordinates of each node, population size, pop size, the maximum number of iterations, maxIter, crossover and mutation probabilities, and length of tabu list.Pseudocode 1
1. Use Voronoi diagram.2. Initialize the population.3. For iter =1: maxIter.4. Select individuals using the tournament method.5. Perform crossover operation as in Section 2.4.6. Perform mutation operation as in Section 2.5.7. Deleting and regenerate the duplicate individuals according to the tabu list.8. Recalculate the fitness values.9. Update the tabu list.10.End.The coding method consists of two parts. The Sa denotes the starting point of each UAV, Pa is the set of nodes passed by the respective attack paths of two UAVs for each target,Ns is the number of candidate starting points, and S0 is the set of candidate starting points. For the i(th) target, the attack path of the j(th) UAV is Sij,v1ij,v2ij,⋯vnijij,Eij, where Sij is the starting point of the j(th) UAV for the i(th) target, and Eij is the target of the j(th) UAV for the i(th) target. As the two UAVs for any target cannot be overlapped, the following constraints should be also met:
(13)X=Sa,PaSa=SijSij∈S0,1<i<Ns,j=1,2Pa=Pij1<i<Ns,j=1,2Pij=V1ij,V1ij,⋯Vnijijvji1∉Pi2,vji2∉Pi1.


## 5.2.1. Chromosome Coding

Here, we adopt real number coding which is specifically defined as the priorityprij of each UAV to head for each node.
(11)X=prij∣1≤i≤K,1≤j≤N,0<prij<1,where K is the number of UAVs, and N stands for the number of nodes. This coding mode can transfer the constraint processing from the generation of the initial solution into the decoding process. This is to avoid constraint processing and error correction during the generation of the new solution. This method can effectively reduce the complexity of algorithm design and operation and evade the information loss caused by the error correction.


## 5.2.2. Chromosome Decoding

As the coding is not equivalent to any decision variable in this study, decoding is also required. Here, the coding is transformed into a decision variable, and the value of the fitness function is calculated. The decoding process is as follows:For the UAVi,Step 1.
The priorities of the UAVsi to M start nodes are extracted from the coding.Step 2.
The highest priority start node that is not occupied by other UAVs is selected.Step 3.
Other nodes connectable to the present node are then obtained. If all these nodes are visited, the UAV path backed off to the node next to the last node. The last node is also deleted in the present path. The priority of each unvisited node is also acquired, and the unvisited node with the highest priority is chosen as the next node to be visited by the UAV.Step 4.
The present node of the UAV is updated, and it is determined whether it arrived at the target. If yes, the path decoding of the present UAV is ended,i=i+1, and the algorithm returns to step. Otherwise, the decoding process is implemented from step 4.


## 5.2.3. Design of the Fitness Function

Here, our objective is to obtain the shortest mission execution pathJ. Therefore, the fitness function is defined as the following:
(12)J=min∑i=1NVT∑j=1NT∑k=12Xvi,vju,ktvi,vju,kV0,where tvi,vju,k denotes the time spent by the UAV u in executing the mission along the edge vi,vj, V0 stands for the UAV velocity, and Xvi,vju,k represents the decision variable.


## 5.2.4. Tabu List

The chromosomes generated by the algorithm are saved in the tabu list following the first-in-first-out rule.


## 5.2.5. V-TGA Algorithm Steps

Step 1.
The mission environment space is generated via the Voronoi diagram, and the algorithm parameters are set accordingly.Step 2.
The population is initialized, and the fitness value of each individual is obtained.Step 3.
The tabu list is initialized.Step 4.
Gen=Gen+1.Step 5.
The parent individuals are selected using the tournament selection method.Step 6.
Any parent individual is crossed over with the probability ofP1 and not crossed over with the probability of 1−P1.Step 7.
New individuals are mutated with the probability ofP2.Step 8.
Check whether the new individuals are already in the tabu list. If yes, the aspiration criterion is not satisfied and the individuals are regenerated.Step 9.
The fitness values of new individuals are obtained.Step 10.
The tabu list is updated.Step 11.
The parent population and offspring population are merged, and the optimal parent and offspring individuals are chosen to enter the next generation.Step 12.
IfGen<maxgen and the convergence are failed, the algorithm is then executed once again from step 4; otherwise, the algorithm is ended, and the calculation results are provided as the outputs.


## 5.2.6. Pseudocode 1

Input is as follows: coordinates of each node, population size, pop size, the maximum number of iterations, maxIter, crossover and mutation probabilities, and length of tabu list.Pseudocode 1
1. Use Voronoi diagram.2. Initialize the population.3. For iter =1: maxIter.4. Select individuals using the tournament method.5. Perform crossover operation as in Section 2.4.6. Perform mutation operation as in Section 2.5.7. Deleting and regenerate the duplicate individuals according to the tabu list.8. Recalculate the fitness values.9. Update the tabu list.10.End.The coding method consists of two parts. The Sa denotes the starting point of each UAV, Pa is the set of nodes passed by the respective attack paths of two UAVs for each target,Ns is the number of candidate starting points, and S0 is the set of candidate starting points. For the i(th) target, the attack path of the j(th) UAV is Sij,v1ij,v2ij,⋯vnijij,Eij, where Sij is the starting point of the j(th) UAV for the i(th) target, and Eij is the target of the j(th) UAV for the i(th) target. As the two UAVs for any target cannot be overlapped, the following constraints should be also met:
(13)X=Sa,PaSa=SijSij∈S0,1<i<Ns,j=1,2Pa=Pij1<i<Ns,j=1,2Pij=V1ij,V1ij,⋯Vnijijvji1∉Pi2,vji2∉Pi1.


## 5.3. Design of the Fitness Function

The longer the flight time of the UAV during the attack mission, the higher the probability of being threatened by the enemy. Therefore, the total processing time and total path should be as short as possible. The fitness functionJ of multidrone is the same as that of single drone, please refer to Section 2.6.


## 5.4. Simulation Process

The flight velocity of the UAV is set to 100 km/h, a single flight lasts 6 h, and the UAVs of two load types, namely, JUAV and CUAV, are randomly generated 3 targets within 100 km range, respectively. Two UAV types form one group and select the overall shortest path to cooperatively strike and destroy three different mission targets from the base.It could be observed from Figure7 that in the initial plan, the targets 1, 2, and 3 are struck cooperatively by the JUAV and CUAV through selecting the bases (1, 8), (5, 6), and (4, 7) as their respective initial bases. The total value of the objective function is 488.2233 km (Table 2).Figure 7
The initial plan of the cooperative strike path.Table 2
Comparison of the fitness values.
AlgorithmBase coordinatesDistanceInitial plan(1, 8), (5, 6), (4, 7)448.2192V-PSO(1, 3), (4, 7), (6, 8)425.8619V-TAGA(2, 5), (3, 4), (7, 8)404.2302It is seen in Figure8 that the targets 1, 2, and 3 are cooperatively struck by the JUAV and CUAV through selecting the bases (1, 3), (4, 7), and (6, 8) as their respective initial bases. The total value of the objective function is 425.8619 km (Table 2).Figure 8
The cooperative strike path under the V-PSO algorithm.In the cooperative strike path under the V-TGA algorithm presented in Figure9, the targets 1, 2, and 3 are cooperatively struck by the JUAV and CUAV through selecting the bases (2, 5), (3, 4), and (7, 8) as their respective initial bases. The total value of the objective function is also 404.2302 km (Table 2).Figure 9
The cooperative strike path under the V-TGA algorithm.The fitness iteration curves (Figure10) also show that the V-TGA algorithm requires fewer iterations. This algorithm also provides a higher convergence rate and obtains a better objective value than that of the V-PSO algorithm. In general, the algorithm performance is improved by over 3% compared with the V-PSO algorithm.Figure 10
The fitness function curves.The simulations also suggest that both V-TGA and V-PSO algorithms obtain a shorter path than that of the initial plan. The V-PSO algorithm improves the performance by 5% and the V-TGA algorithm by 10%. It is also seen in Figure6 that the number of iterations required for the V-TGA algorithm is smaller than that of the V-PSO algorithm. It is also seen that the obtained path by this algorithm was shorter.The results manifest that given the known enemy’s situation and the targets of different mission types, the V-TGA algorithm can dynamically deploy the launching bases through mobile launching vehicles. It can also select the proper shortest path and reduce the flight at transverse distances.


## 5.5. Compare Algorithms and Parameter Settings

### 5.5.1. Compare Algorithms and Parameter Settings

In order to verify the effectiveness of the algorithm proposed in this paper, this paper selects some swarm intelligence algorithms for comparative experiments. These algorithms include classic swarm intelligence algorithms: genetic algorithm (GA) [25], particle swarm algorithm (PSO) [26], and recent the latest swarm intelligence algorithms in recent years: whale optimization agorithm (WOA) [27], loin swarm optimization (LSO) [28], and sparrow search algorithm (SSA) [29]. In order to conduct scientific control experiments, all algorithms use the same common parameters, coding methods, and initial populations and are solved based on the task space obtained by the Voronoi diagram. At the same time, each calculation example is repeated 100 times. The parameters of the algorithm are as follows: the population size is 50, the maximum number of iterations is 100, the mutation probability is 0.1, the crossover probability is 0.8, the inertia weight is 0.8, the individual and global learning factors are 1 and 1, the adult lion ratio is 0.5, and the discoverer alert threshold is 0.8. The ratio of discoverers is 0.2, and the ratio of investigators is 0.1.


### 5.5.2. Example Data

In order to scientifically verify the performance of the algorithm, this paper has designed three different scales of calculation example data, and the specific calculation example data are shown in Table3. In addition, the flying speed of the UAV is 100 km/h, and the single flight time is 6 h. The two types of UAVs are JUAC and CUAV.Table 3
Three types of example data.
ExamplesMap sizeTask quantityUAV launch position numberThreat number1[50, 50]36302[100, 100]510503[150, 150]1020100


### 5.5.3. Simulation Results

The above three calculation example data use different swarm intelligence algorithms to solve the average optimal target value of 100 times and the average convergence curve as follows in Table4:Table 4
Algorithm convergence curve comparison.
Algorithm\example123GA383.746727.3041493.956PSO384.303726.3831485.488LSO379.819724.1061491.977SSA381.724724.5491471.975WOA381.234727.3761489.955V-TGA379.191721.9251455.108It can be seen from Table2 that the algorithms proposed in this paper have achieved the highest accuracy when solving large, medium, and small-scale calculation examples. With the increase in the scale of the calculation examples, the calculation difficulty and complexity increase, and the calculation accuracy of the V-TGA algorithm is greater than the gap with other algorithms.It can be seen from the convergence curves of the three calculation examples in Figures11–13 that the algorithm proposed in this paper has the fastest convergence rate in the early stage, and it has not fallen into the local optimum due to the excessively fast convergence rate. It can be seen from the final road map (Figures 14–16) obtained by the algorithm in this paper that for all mission targets, two different types of UAVs arrive at the target point from different directions at the same time, successfully achieving the coordinated strike mission.Figure 11
The fitness function curve of algorithms in example 2.Figure 12
The fitness function curve of algorithms in example 2.Figure 13
The fitness function curve of algorithms in example 3.Figure 14
V-TGA coordinated attack path of example 1.Figure 15
V-TGA coordinated attack path of example 2.Figure 16
V-TGA coordinated attack path of example 3.


## 5.5.1. Compare Algorithms and Parameter Settings

In order to verify the effectiveness of the algorithm proposed in this paper, this paper selects some swarm intelligence algorithms for comparative experiments. These algorithms include classic swarm intelligence algorithms: genetic algorithm (GA) [25], particle swarm algorithm (PSO) [26], and recent the latest swarm intelligence algorithms in recent years: whale optimization agorithm (WOA) [27], loin swarm optimization (LSO) [28], and sparrow search algorithm (SSA) [29]. In order to conduct scientific control experiments, all algorithms use the same common parameters, coding methods, and initial populations and are solved based on the task space obtained by the Voronoi diagram. At the same time, each calculation example is repeated 100 times. The parameters of the algorithm are as follows: the population size is 50, the maximum number of iterations is 100, the mutation probability is 0.1, the crossover probability is 0.8, the inertia weight is 0.8, the individual and global learning factors are 1 and 1, the adult lion ratio is 0.5, and the discoverer alert threshold is 0.8. The ratio of discoverers is 0.2, and the ratio of investigators is 0.1.


## 5.5.2. Example Data

In order to scientifically verify the performance of the algorithm, this paper has designed three different scales of calculation example data, and the specific calculation example data are shown in Table3. In addition, the flying speed of the UAV is 100 km/h, and the single flight time is 6 h. The two types of UAVs are JUAC and CUAV.Table 3
Three types of example data.
ExamplesMap sizeTask quantityUAV launch position numberThreat number1[50, 50]36302[100, 100]510503[150, 150]1020100


## 5.5.3. Simulation Results

The above three calculation example data use different swarm intelligence algorithms to solve the average optimal target value of 100 times and the average convergence curve as follows in Table4:Table 4
Algorithm convergence curve comparison.
Algorithm\example123GA383.746727.3041493.956PSO384.303726.3831485.488LSO379.819724.1061491.977SSA381.724724.5491471.975WOA381.234727.3761489.955V-TGA379.191721.9251455.108It can be seen from Table2 that the algorithms proposed in this paper have achieved the highest accuracy when solving large, medium, and small-scale calculation examples. With the increase in the scale of the calculation examples, the calculation difficulty and complexity increase, and the calculation accuracy of the V-TGA algorithm is greater than the gap with other algorithms.It can be seen from the convergence curves of the three calculation examples in Figures11–13 that the algorithm proposed in this paper has the fastest convergence rate in the early stage, and it has not fallen into the local optimum due to the excessively fast convergence rate. It can be seen from the final road map (Figures 14–16) obtained by the algorithm in this paper that for all mission targets, two different types of UAVs arrive at the target point from different directions at the same time, successfully achieving the coordinated strike mission.Figure 11
The fitness function curve of algorithms in example 2.Figure 12
The fitness function curve of algorithms in example 2.Figure 13
The fitness function curve of algorithms in example 3.Figure 14
V-TGA coordinated attack path of example 1.Figure 15
V-TGA coordinated attack path of example 2.Figure 16
V-TGA coordinated attack path of example 3.


## 6. Conclusion

We examined the single-UAV mission planning. In comparison with the V-PSO algorithm, the proposed V-GA algorithm can effectively improve the system efficiency and complete the single-UAV mission planning by following the principles of threat evasion and the shortest UAV path under the real-time environment. Based on the single-UAV mission planning, the multi-UAV mission planning was further probed, and the multi-UAV cooperative completion of the mission was regarded as a many-to-one rendezvous problem. Compared with the V-PSO algorithm, the proposed V-TGA algorithm is capable of improving the system efficiency by at least 3% and effectively realizing the multi-UAV mission planning. Then, in order to further scientifically verify the performance of the algorithm, some swarm intelligence algorithms were selected for comparative experiments, and three numerical example data of different scales were designed, which effectively verified the effectiveness and superiority of the algorithm in this paper. The problem of trace optimization will be the focus of research.



---

*Source: 4154787-2021-11-09.xml*