A modified genetic algorithm for task assignment of heterogeneous unmanned aerial vehicle system

Abstract

This study deals with the task assignment problem of heterogeneous unmanned aerial vehicle (UAV) system with the limited resources and task priority constraints. The optimization model which comprehensively considers the resource consumption, task completion effect, and workload balance is formulated. Then, a concept of fuzzy elite degree is proposed to optimize and balance the transmission of good genes and the variation strength of population during the operations of algorithm. Based on the concept, we propose the fuzzy elite strategy genetic algorithm (FESGA) to efficiently solve the complex task assignment problem. In the proposed algorithm, two unlock methods are presented to solve the deadlock problem in the random optimization process; a sudden threat countermeasure (STC) mechanism is presented to help the algorithm quickly respond to the change of task environment caused by sudden threats. The simulation results demonstrate the superiority of the proposed algorithm. Meanwhile, the effectiveness and feasibility of the algorithm in workload balance and task priority constraints are verified.

Introduction

Unmanned aerial vehicle (UAV) has made outstanding contributions in military, agriculture, and commercial applications with its unique low cost and strong maneuverability over the previous decades. ¹ However, it is difficult for a single UAV to satisfy the increasingly complex task requirements in many cases due to its limited airborne resources. Therefore, UAV applications are gradually developing toward clusteringLiu et al., and Zhou et al.,.^2,3 tackled the multi-UAV collaborative data collection problem Motlagh et al. ⁴ studied the application of multi-UAV system in the Internet of Things (IOT) and realized the effective transmission of airborne information. Most of the above studies focus on the homogeneous UAV system. However, the diversity of tasks sets higher demands on the UAV system. The heterogeneity will be the main development direction of UAV system in the future. In the large-scale task scenario, the optimization effect of task assignment directly affects the work effectiveness of UAV system.^5,6 The task assignment problem of heterogeneous UAV system has become a hot issue in the field of multiple UAVs control. ⁷

The multiple heterogeneous UAVs task assignment problem is a complex combinatorial optimization problem. In Deng et al., ⁸ the total task execution time was taken as the objective function of the UAV task assignment problem. In Motlagh et al., ⁴ the authors jointly optimized the energy consumption and operational time of UAV system. Most of current studies focus on reducing the resource consumption of UAV system. The task completion effect of UAVs is ignored, which may lead to unnecessary resource consumption. Therefore, it is necessary to evaluate the task completion quality rationally, and jointly optimize the resource consumption and task completion effect of UAV system. In addition, many researchers have studied the workload balance in the UAV task assignment optimization problem.^9,10 The algorithms considering the workload balance can effectively prevent the situation that some vehicles run out of their resources, thereby decreasing the task completion time of UAV system. ¹¹ However, the workload balance problem is difficult to solve due to the coordinated control of multiple UAVs. In Zhu and Yang, ⁹ the workload balance coefficient related to the average traveled distance of UAV system was introduced in objective function to alleviate the imbalance of task assignment effectively. However, the coefficient overlooks the great influence of the real-time resource information of UAV system to the task assignment optimization process. In Chen and Zhu, ¹² a workload balance coefficient considering the real-time traveled distance of UAVs was proposed to achieve a fairer task assignment scheme. However, the proposed coefficient only focuses on the real-time change of traveled distance, the assignment scheme may not satisfy the equalization requirement of other types of resources. For instance, a UAV cannot continue working if a resource carried by the UAV is consumed excessively, then the stability of UAV system will be adversely affected. Therefore, it is of great practical significance to propose a workload balance method that comprehensively considers multiple real-time changing resources to ensure the efficient operation of UAV system.

The task assignment of UAV system is a complex nondeterministic polynomial hard (NP-hard) problem with multiple constraints. It is difficult to solve by traditional convex optimization theory. ⁸ In current studies, the deterministic algorithms such as mixed integer linear program (MILP),^13–15 branch and bound (BAB) algorithm, ¹⁶ and tree search algorithm (TSA)^17,18 have been widely adopted to solve the UAV system task assignment problem. In the process of solving large-scale complex task assignment problem, matrix operations involved in MILP and BAB are numerous and complex, search scope of TSA is large. Thus, they are only suitable for solving small and medium-sized task assignment problems with fewer constraints. As experience-based algorithms, heuristic algorithms can avoid the high computational complexity of the NP-hard problems. Therefore, they have been more extensively studied than deterministic algorithms in the field of task assignment. In Chen et al., ¹⁹ the authors developed a modified two-part wolf pack search (MTWPS) algorithm to solve the UAV system task assignment problem with task priority constraint effectively. In Xi et al., ²⁰ a guiding mechanism based on particle swarm optimization (PSO) algorithm was presented to rapidly provide feasible task assignment scheme for homogeneous strike UAV cooperative operation. In Kalayci and Gupta, ²¹ the modified artificial bee colony (ABC) algorithm was proposed to effectively solve the decentralized task assignment problem. However, in the optimization process of algorithms,^19–21 a solution can only be updated with the guidance of other solutions. Searching ability of the algorithms is insufficient due to the single updating way. Thus, they may fail to provide satisfactory solutions in more complex task scenarios. Compared with the above heuristic algorithms, genetic algorithm (GA) can update solutions in more diversified ways through mutation.^22,23 GA shows stronger exploration ability and more advantages in solving the complex large-scale task assignment problem. In Deng et al., ⁸ a GA-based mirror representation method was proposed to cope with the limited resource constraint in the multi-UAV task assignment. In Schwarzrock et al., ²⁴ the task assignment problem was transformed into a directed graph to simplify the problem complexity, and two different encoding methods were proposed for homogeneous UAVs and heterogeneous UAVs, respectively. In Jia et al., ²⁵ the authors proposed a concept of penalty items to enable GA to solve the multi-UAV task assignment problem with task priority constraint effectively. More diversified constraints must be considered due to the complexity of task scenarios. The introduction of multiple complex constraints directly affects the solving efficiency of traditional GA. In Wu et al., ²⁶ the authors proposed a distributed genetic algorithm (DGA) which treats each UAV as an independent processor to enhance the population diversity. In Bai et al., ²² multiple sub-populations were created to macroscopically increase the intensity of genetic operations, thereby enhancing search ability of the algorithm. In Zhou et al., ²³ good individuals were achieved by adopting the greedy strategy to synthetically adjust the resource allocation of UAV system. These individuals can accelerate the population evolution and convergence speed. The above GAs focus on the convergence speed or search ability. They lack the comprehensive consideration of the two performances. However, it is difficult for GAs to improve these performances simultaneously. The increasing complexity of task scenarios requires higher performance of algorithms. Thus, it is significant to propose an improved GA with fast convergence speed and strong searching ability to solve the complex large-scale UAV system task assignment problem.

Given that GA is an opportunistic optimization algorithm, some infeasible solutions may be generated in the optimization process. Wherein, deadlock problem is the main reason of generating infeasible solutions. Especially in the large-scale task scenarios, deadlock solution appears with more possibility ¹⁹ , Lemaire et al., ²⁷ proposed a swapping method to resolve deadlocks by exchanging the order of any two tasks which violate the task priority constraint. However, the method may fail when multiple UAVs are involved in deadlocks. In Deng et al., ²⁸ an unlock method based on graph theory was presented to detect and solve the deadlock problem. Nevertheless, too many matrix manipulations and loop operations are involved in the method. The tedious and large calculation greatly reduce the unlock efficiency. Therefore, it is meaningful to design a low complexity and high reliability unlocking method to adapt to the ever-expanding task background.

Based on the given analysis, some main challenges in the field of task assignment of heterogeneous UAV system are given as follows: (1) The solving difficulty of task assignment problem increases with the multiplicity of constraints. (2) The current heuristic algorithms show insufficient precision and slow convergence speed in solving the large-scale complex task assignment problem. (3) The existing unlocking methods are inefficient for the deadlock problem caused by the heterogeneity of UAVs and task priority constraint. In this study, we aim to propose an improved GA to solve the task assignment problem of heterogeneous UAV system with multiple constraints. First, we construct a combinatorial optimization model about the resource consumption, task completion effect, workload balance, task priority, and limited resource constraints. Different from the existing studies,^8,24,25 constraints contained in the proposed model are more comprehensive, which are conducive to improving the effectiveness of solutions. The joint optimization of multiple constraints may reduce the solution efficiency of traditional GA. To address the issue, a concept of fuzzy elite degree considering the preservation of good genes and the change intensity of individuals is presented. Based on the concept, we propose the fuzzy elite strategy genetic algorithm (FESGA) with high computational efficiency. Specifically, a novel initialization method and a parent selection method are presented to enhance the convergence speed of algorithm. An avoiding inbreeding (AI) mechanism and a hierarchical mutation (HM) rule are proposed to solve the local extremum problem. Then, a no zero mechanism and two unlock methods are presented to deal with the infeasible solutions which violate the limited resources constraint, and the deadlock infeasible solutions, respectively. Moreover, we presented the sudden threat countermeasure (STC) mechanism to enhance the ability of algorithm to converge quickly after detecting the sudden threats.

The main contributions of this study are further concluded as follows:

• 1) Aiming at the optimization of resource consumption, task completion effect, and workload balance of UAV system, we propose the resource consumption function, detection revenue function, and execution capability, respectively. Further, an optimization model with multiple constraints is formulated by jointly considering the task priority and limited resource constraints.

• 2) We propose a concept of fuzzy elite degree to evaluate the participation of individuals in the optimization process. In the proposed FESGA, the proposed concept can rationally optimize the retention and change intensity of genes. Therefore, the convergence performance and search ability of FESGA can be improved synthetically.

• 3) Multiple low computational complexity and effective unlock methods are presented to solve the deadlock problem in the genetic operations. The proposed diversified unlocking ways can help the algorithm avoid being affected by local extremes.

• 4) The STC mechanism is presented to improve the ability of algorithm to deal with sudden threats in the changing task scenario quickly. Thus, robustness of algorithm in the various complex environments is enhanced.

The rest of this paper is organized as follows. In Section 2, the task scenario and corresponding optimization model are formulated. In Section 3, details of FESGA are introduced. Section 4 describes the methods to deal with the deadlock problem and sudden threats, respectively. Numerical simulations and analyses are provided in Section 5. Finally, Section 6 summarizes this paper.

System model and problem formulation

In this section, we describe a scenario where a heterogeneous UAV system performs multiple tasks on a set of targets. Then, the complex task assignment optimization model with multiple constraints is formulated.

System model

In this study, we consider a task scenario which consists of several targets and a group of heterogeneous UAVs. Three tasks of reconnaissance, attack, and verification should be performed successively on each target. Denote the target set as $T=\{t_1,t_2,...,t_N\}$ , the UAV set as $U=\{u_1,u_2,...,u_M\}$ . Where $N$ and $M$ denote the number of targets and UAVs, respectively. The task set of each target is $I=\{\mathrm{tas}{k}_R,\mathrm{tas}{k}_A,\mathrm{tas}{k}_V\}$ . Where $\mathrm{tas}{k}_R$ , $\mathrm{tas}{k}_A$ , and $\mathrm{tas}{k}_V$ represent reconnaissance task, attack task, and verification task, respectively. Define $\mathrm{tas}{k}_i\succ \mathrm{tas}{k}_k$ to indicate that $\mathrm{tas}{k}_i$ has higher priority than $\mathrm{tas}{k}_k$ , the task priority on each target is expressed as: $\mathrm{tas}{k}_R\succ \mathrm{tas}{k}_A\succ \mathrm{tas}{k}_V$ . The UAV system is classified into two categories depending on the type of tasks that UAVs can perform, that is, $U=\{U_{\mathrm{Su}},U_{\mathrm{St}}\}$ . Thereinto, $U_{\mathrm{Su}}$ includes $M_{\mathrm{Su}}$ surveillance UAVs that can execute the $\mathrm{tas}{k}_R$ and $\mathrm{tas}{k}_V$ ; $U_{\mathrm{St}}$ includes $M_{\mathrm{St}}$ strike UAVs that only can execute the $\mathrm{tas}{k}_A$ . Each UAV belongs to only one collection. All of the UAVs should return to base after completing the assigned tasks. Moreover, a state set $S=\{E,W,F\}$ is defined to describe three different states of the UAV. Elements in the state set denote the task execution state, waiting state, and flight state, respectively. State $E$ represents that the UAV is performing the specific task. State $W$ means that the UAV is being forced to wait for the reason that the higher priority task of the target has not been completed. State $F$ indicates that the UAV is flying to the next destination after completing a task.

Considering that the resource of UAV is limited, each UAV should complete the assigned tasks in a limited time, the fuel consumption and traveled distance of each UAV are not allowed to exceed its maximum limit.

Total range of $u_i$ can be achieved by

$$d_{\mathrm{total}}^i=\sum _{i=1}^{N+1}{d}_{j,j^{*}}(i)$$

(1)

where $d_{j,j^{*}}(i)$ denotes the distance of $u_i$ from $t_j$ to the next target ( $t_{j^{*}}$ ).

Noting that the fuel consumption varies in different states of UAV, the total fuel consumption of $u_i$ is achieved by

$$\begin{array}{c}{\mathrm{fuel}}_{\mathrm{total}}^i=\hfill \\ \sum _{j=1}^{N+1}\sum _{k=1}^3({\mathrm{fuel}}_{\mathrm{ijk}}^{\mathrm{flight}}{x}_{\mathrm{ijk}}+{\mathrm{fuel}}_{\mathrm{ijk}}^{\mathrm{wait}}{x}_{\mathrm{ijk}}+{\mathrm{fuel}}_{\mathrm{ijk}}^{\mathrm{execute}}{x}_{\mathrm{ijk}})\hfill \end{array}$$

(2)

where ${\mathrm{fuel}}_{\mathrm{ijk}}^{\mathrm{flight}}$ , ${\mathrm{fuel}}_{\mathrm{ijk}}^{\mathrm{wait}}$ , and ${\mathrm{fuel}}_{\mathrm{ijk}}^{\mathrm{execute}}$ denote the fuel consumption of $u_i$ when flying to execute the next task from $t_j$ , waiting to execute $\mathrm{tas}{k}_k$ on $t_j$ , and performing $\mathrm{tas}{k}_k$ on $t_j$ , respectively. $x_{\mathrm{ijk}}$ is calculated as follows:

$$x_{\mathrm{ijk}}=\{\begin{array}{c}1,\mathrm{if}\mathrm{tas}{k}_k\mathrm{on}{t}_j\mathrm{is}\mathrm{assigned}\mathrm{to}{u}_i\hfill \\ \multicolumn{1}{c}{0,\mathrm{others}}\end{array}$$

(3)

Similar to fuel consumption, the total time of $u_i$ to complete all assigned tasks can be achieved as follows:

$${\wp }_{\mathrm{total}}^i=\sum _{j=1}^{N+1}\sum _{k=1}^3({\wp }_{\mathrm{ijk}}^{\mathrm{flight}}{x}_{\mathrm{ijk}}+{\wp }_{\mathrm{ijk}}^{\mathrm{wait}}{x}_{\mathrm{ijk}}+{\wp }_{\mathrm{ijk}}^{\mathrm{execute}}{x}_{\mathrm{ijk}})$$

(4)

where ${\wp }_{\mathrm{ijk}}^{\mathrm{flight}}$ , ${\wp }_{\mathrm{ijk}}^{\mathrm{wait}}$ , and ${\wp }_{\mathrm{ijk}}^{\mathrm{execute}}$ denote the time consumed by $u_i$ in the state $F$ , state $W$ , and state $E$ , respectively. ${\wp }_{\mathrm{ijk}}^{\mathrm{execute}}$ is predetermined by the system, ${\wp }_{\mathrm{ijk}}^{\mathrm{flight}}$ and ${\wp }_{\mathrm{ijk}}^{\mathrm{wait}}$ can be achieved by the following formulas:

$${\wp }_{\mathrm{ijk}}^{\mathrm{flight}}=\frac{d_{\mathrm{jk},j^{*}}(i)}{v_i}$$

(5)

$${\wp }_{\mathrm{ijk}}^{\mathrm{wait}}={\wp }_k^s(i,j)-{\wp }_k^w(i,j)$$

(6)

In equation (5), $v_i$ denotes the flight speed of $u_i$ , $d_{\mathrm{jk},j^{*}}(i)$ denotes the distance $u_i$ needs to fly to the next target $t_{j^{*}}$ after completing $\mathrm{tas}{k}_k$ on $t_j$ . In equation (6), ${\wp }_k^s(i,j)$ and ${\wp }_k^w(i,j)$ denote the time that $u_i$ starts to execute $\mathrm{tas}{k}_k$ (the completion time of the task with higher priority than $\mathrm{tas}{k}_k$ ) and the time of $u_i$ to start to get stuck into waiting after reaching $t_j$ , respectively.

In the multiple UAVs task assignment problem, we propose the concept of execution capability to better address the issue of workload unbalance. Execution capability is defined as the ability of UAV to continue executing tasks based on remaining resources, which is an important means to prevent UAVs from running out of resources. The more resources remain, the greater the execution capability is. When the remaining resources of UAV are sufficient, the ability of the UAV to continue executing tasks is relatively strong. In this condition, the execution capability decreases slowly. On the contrary, when the remaining resources of UAV are exhausted, the UAV is most likely to consume all resources and cannot continue executing tasks. To avoid this situation, the execution capacity should decrease sharply in this condition. Since the resource of UAV changes over time, execution capability is a time-varying concept. In this study, traveled range is considered as one of the criteria for the evaluation of execution capacity. Thus, the range-impact execution capability $C_{\mathrm{range}}(\wp )$ is defined. Since range is inversely proportional to remaining resources, it is inversely proportional to execution capability. Thus, $C_{\mathrm{range}}(\wp )$ of $u_i$ is defined as follows:

$$C_{\mathrm{range}}^i(\wp )=e^{\frac{{\kappa }_r}{\frac{d_i(\wp )}{d_{max}^i}-1}}/e^{-{\kappa }_r},i=1,2,...,M$$

(7)

where $d_i(\wp )$ and $d_{max}^i$ represent the traveled distance at time $\wp$ and the allowed maximum range of $u_i$ , respectively. ${\kappa }_r$ denotes the rate at which $C_{\mathrm{range}}^i(\wp )$ varies with $d_i(\wp )$ . The smaller ${\kappa }_r$ is, the slower the rate changes. The value range of ${\kappa }_r$ is: ${\kappa }_r\in (0,1]$ .

In equation (7), with the increase of time $\wp$ , $d_i(\wp )$ gradually increases, $C_{\mathrm{range}}^i(\wp )$ gradually decreases. As the value of $d_i(\wp )$ approaches $d_{max}^i$ , $C_{\mathrm{range}}^i(\wp )$ drops sharply. Thus, it is reasonable to construct equation (7) based on an exponential function to express the relationship between range and execution capacity.

Naturally, $C_{\mathrm{range}}(\wp )$ of the UAV system is calculated as

$$C_{\mathrm{range}}^{\mathrm{total}}(\wp )=\{\begin{array}{c}\sum _{i=1}^M{C}_{\mathrm{range}}^i(\wp ),\forall i,d_i(\wp )<d_{max}^i\hfill \\ \multicolumn{1}{c}{0,\mathrm{others}}\end{array}$$

(8)

The execution capability of UAV is limited due to its limited resources. The situation that traveled distance of any UAV exceeds its permitted limits, $C_{\mathrm{range}}(\wp )$ should be regarded as invalid. In this situation, $C_{\mathrm{range}}^{\mathrm{total}}(\wp )$ is set to 0.

Note that resources of strike UAV are related to the number of carried weapons besides range. The weapon-impact execution capability $C_{\mathrm{weapon}}(\wp )$ is defined. $C_{\mathrm{weapon}}(\wp )$ of $u_i$ is defined as follows:

$$C_{\mathrm{weapon}}^i(\wp )=e^{\frac{-{\kappa }_w{w}_{max}^i}{w_i(\wp )}}/e^{-{\kappa }_w},i=1,2,...,M_{\mathrm{St}}$$

(9)

where $w_{max}^i$ and $w_i(\wp )$ denote the maximum weapon number that $u_i$ can carry and the number of weapons left in $u_i$ , respectively. ${\kappa }_w$ denotes the rate at which $C_{\mathrm{weapon}}^i(\wp )$ varies with $w_i(\wp )$ . The larger ${\kappa }_w$ is, the slower the rate changes. The value range of ${\kappa }_w$ is: ${\kappa }_w\in (0,1]$ .

In equation (9), with the reduction of $w_i(\wp )$ , $C_{\mathrm{weapon}}^i(\wp )$ decreases. When $w_i(\wp )$ is closed to 0, $C_{\mathrm{weapon}}^i(\wp )$ greatly reduces. Therefore, the exponential function in equation (9) is suitable for describing the relationship between the execution capability and the number of remaining weapons.

Similar to equation (8), $C_{\mathrm{weapon}}(\wp )$ of the UAV system can be achieved by

$$C_{\mathrm{weapon}}^{\mathrm{total}}(\wp )=\{\begin{array}{c}\sum _{i=1}^{M_{\mathrm{St}}}{C}_{\mathrm{weapon}}^i(\wp ),\forall i,w_i(\wp )>0\hfill \\ \multicolumn{1}{c}{0,\mathrm{others}}\end{array}$$

(10)

Based on equations (7) and (9), the more residual resources UAV system has, the stronger its execution capability is. In the ideal task assignment process, UAVs with sufficient residual resources (high execution capability) should be fully utilized; UAVs with little residual resources (low execution capability) should be assigned with few tasks. In this way, the situation that some UAVs run out resources due to executing excessive tasks can be avoided, and the workload balance constraint can be satisfied. Thus, the execution capacity of UAV system is directly proportional to workload balance degree of the allocation result.

For the sake of concentrating on the main issue of this study, we make the following assumptions: (1) UAVs are not destroyed when performing tasks ²⁵ ; (2) the actual flight distances of UAVs are replaced by Euclidean distances^7,24; (3) UAVs fly at different altitudes to prevent collisions between them ¹⁹ ; (4) UAV cannot execute multiple tasks simultaneously; (5) the distance that the UAV moves in the task execution state is negligible.

Problem formulation

Resource consumption function

We adopt the total traveled distance $d_{\mathrm{total}}$ , total fuel consumption ${\mathrm{fuel}}_{\mathrm{total}}$ , and time required to complete all tasks ${\wp }_{\mathrm{total}}$ as the main factors to describe the resource consumption of UAV system. The traveled distance, fuel consumption, and task execution time of a single UAV can be calculated by equations (1), (2), and (4), respectively. Therefore, $d_{\mathrm{total}}$ , ${\mathrm{fuel}}_{\mathrm{total}}$ , and ${\wp }_{\mathrm{total}}$ can be achieved by following formulas:

$$d_{\mathrm{total}}=\sum _{i=1}^M{d}_{\mathrm{total}}^i$$

(11)

$${\mathrm{fuel}}_{\mathrm{total}}=\sum _{i=1}^M{\mathrm{fuel}}_{\mathrm{total}}^i$$

(12)

$${\wp }_{\mathrm{total}}=\underset{i}{max}({\wp }_{\mathrm{total}}^i)$$

(13)

On the premise that the three factors mentioned above are equally important, the resource consumption function can be achieved as follows:

$$f_{\mathrm{consume}}=\frac{d_{\mathrm{total}}}{\sum _{i=1}^M{d}_{max}^i}+\frac{\mathrm{fue}{l}_{\mathrm{total}}}{\sum _{i=1}^M{\mathrm{fuel}}_{max}^i}+\frac{{\wp }_{\mathrm{total}}}{\underset{i}{max}({\wp }_{max}^i)}$$

(14)

where ${\mathrm{fuel}}_{max}^i$ and ${\wp }_{max}^i$ represent the maximum fuel capacity and the endurance time of $u_i$ , respectively.

Detection revenue function

Some existing studies assume that UAVs only can perform tasks at the target points to ensure the effective execution of tasks.^24,29 The detection scope of surveillance UAVs is not considered in these task assignment model, which may lead to unnecessary resource consumption of UAV system. ³⁰ In Jia et al., ²⁵ the detection scope of UAV is represented by detection radius. In the allowed detection scope, the closer UAV gets to target, the higher detection accuracy is. For the sake of quantifying the detection accuracy of UAV, the detection revenue function $f_{\mathrm{revenue}}$ is proposed. Given that $f_{\mathrm{revenue}}$ is proportional to detection accuracy, it is proportional to the distance between the UAV and target. Detection revenue function $f_{\mathrm{revenue}}$ can be achieved by the following formula:

$$f_{\mathrm{revenue}}=\frac{\sum _{i=1}^{M_{\mathrm{Su}}}\sum _{j=1}^N\sum _{q=1}^2(x_{\mathrm{ijq}}\frac{\ln (2-\frac{r_{\mathrm{ijq}}}{r_{det\mathrm{ect}}^i})}{\ln 2})}{\sum _{i=1}^{M_{\mathrm{Su}}}\sum _{j=1}^N\sum _{q=1}^2{x}_{\mathrm{ijq}}}$$

(15)

where $x_{\mathrm{ijq}}$ is a binary variable, which equals 1 when the $\mathrm{tas}{k}_q$ on the $t_j$ is assigned to $u_i$ . Note that $\mathrm{tas}{k}_q$ can only be reconnaissance or verification task. $r_{\mathrm{ijq}}$ denotes the distance between the surveillance UAV $u_i$ and the position where $\mathrm{tas}{k}_q$ on $t_j$ is executed. $r_{det\mathrm{ect}}^i$ is the detection radius of $u_i$ . Given that the task completion effect of UAV becomes better with the increase of detection accuracy, task completion effect is proportional to $f_{\mathrm{revenue}}$ .

Optimization model

The task assignment optimization model of heterogeneous UAV system is described as follows:

$$maxf=\frac{l_{\mathrm{ra}}{l}_{\mathrm{we}}(f_{\mathrm{revenue}}+\frac{C_{\mathrm{range}}^{\mathrm{total}}(\wp )}{M}+\frac{C_{\mathrm{weapon}}^{\mathrm{total}}(\wp )}{M_{\mathrm{St}}})}{f_{\mathrm{consume}}}$$

(16)

s.t.

$$\sum _{i=1}^M\sum _{j=1}^N{x}_{\mathrm{ijk}}=1$$

(17)

$$\sum _{i=1}^M\sum _{k=1}^3{x}_{\mathrm{ijk}}=3$$

(18)

$$({\wp }_{\mathrm{rec}}^{\mathrm{sta}}(j)+{\wp }_{\mathrm{rec}}^{\mathrm{exe}})\le ({\wp }_{\mathrm{att}}^{\mathrm{sta}}(j)+{\wp }_{\mathrm{att}}^{\mathrm{exe}})\le ({\wp }_{\mathrm{ver}}^{\mathrm{sta}}(j)+{\wp }_{\mathrm{ver}}^{\mathrm{exe}})$$

(19)

$$\forall i\in [1,M_{\mathrm{St}}],w_{\mathrm{total}}^i\le w_{max}^i$$

(20)

$$\forall i\in [1,M_{\mathrm{Su}}],r_i\le r_{det\mathrm{ect}}^i$$

(21)

$$\forall i,{\wp }_{\mathrm{total}}^i\le {\wp }_{max}^i,{\mathrm{fuel}}_{\mathrm{total}}^i\le {\mathrm{fuel}}_{max}^i,d_{\mathrm{total}}^i\le d_{max}^i$$

(22)

In the fitness function (equation (16)), $l_{\mathrm{ra}}$ and $l_{\mathrm{we}}$ indicate the range-impact execution capability flag and weapon-impact execution capability flag, respectively. They can be achieved by

$$l_{\mathrm{ra}}=\{\begin{array}{c}0,\mathrm{if}{C}_{\mathrm{range}}^{\mathrm{total}}(\wp )=0\hfill \\ \multicolumn{1}{c}{1,\mathrm{others}}\end{array}$$

(23)

$$l_{\mathrm{we}}=\{\begin{array}{c}0,\mathrm{if}{C}_{\mathrm{weapon}}^{\mathrm{total}}(\wp )=0\hfill \\ \multicolumn{1}{c}{1,\mathrm{others}}\end{array}$$

(24)

The denominator of fitness function is resource consumption function, and the molecule consists of detection revenue function and execution capability of the UAV system.

Equations (17) and (18) ensure that each task only can be completed by one UAV, and all tasks must be completely performed. Equation (19) is the task priority constraint, where ${\wp }_{\mathrm{rec}}^{\mathrm{sta}}(j)$ , ${\wp }_{\mathrm{att}}^{\mathrm{sta}}(j)$ , and ${\wp }_{\mathrm{ver}}^{\mathrm{sta}}(j)$ represent the time when $\mathrm{tas}{k}_R$ , $\mathrm{tas}{k}_A$ , and $\mathrm{tas}{k}_V$ begin to be performed on $t_j$ , respectively. ${\wp }_{\mathrm{rec}}^{\mathrm{exe}}$ , ${\wp }_{\mathrm{att}}^{\mathrm{exe}}$ , and ${\wp }_{\mathrm{ver}}^{\mathrm{exe}}$ represent the time required to complete $\mathrm{tas}{k}_R$ , $\mathrm{tas}{k}_A$ , and $\mathrm{tas}{k}_V$ , respectively. In equation (20), $w_{\mathrm{total}}^i$ and $w_{max}^i$ denote the consumed weapon number of UAV and the maximum weapon number it can carry. Thus, equation (20) indicates the constraint on weapon resource of strike UAVs. In equation (21), $r_i$ denotes the distance between the UAV $u_i$ and the target during the mission. Equation (21) indicates the constraint on detection scope of surveillance UAVs. Equation (22) ensures that the task execution time, fuel consumption, and range of any UAV are limited.

Fitness $f$ (equation (16)) represents the satisfaction of UAV system with current task assignment solution. $f$ should decrease with the increase of resource consumption ( $f_{\mathrm{consume}}$ ), and increase with the improvement of task completion effect ( $f_{\mathrm{revenue}}$ ) and workload balance degree ( $C_{\mathrm{range}}^{\mathrm{total}}(\wp )$ , $C_{\mathrm{weapon}}^{\mathrm{total}}(\wp )$ ). The proposed fitness function is capable of describing these properties.

In the proposed task assignment optimization model, we jointly consider the task completion effect, workload unbalance, and other factors. Although the proposed model makes the solutions more efficient, it makes the task assignment optimization problem more complicated. Especially in the large-scale task assignment, the proposed optimization problem is more difficult to be solved.

Fuzzy elite strategy genetic algorithm

GA, a heuristic algorithm with fast random search ability, can provide good approximated solutions for the complex task assignment problem.^21,22,31 However, the traditional GA converges slowly and easily converges to the local extreme when the search space is large. Therefore, the FESGA is proposed. A simple flow chart of the proposed FESGA is illustrated in Figure 1.

Figure 1.

Flow chart of FESGA.

Encoding

Encoding of chromosome is the most critical part of GA. ²⁴ However, traditional encoding method cannot be directly applied to the proposed problem due to the heterogeneity of UAVs and the particularity of tasks. ⁸ Therefore, we propose a matrix encoding method to accommodate the task assignment background. Each chromosome is encoded by a matrix of five lines and $3N$ columns.

• 1) The encoding method of UAV chromosome: The UAV chromosome is composed of $M$ UAV sub-chromosomes, a complete UAV chromosome is achieved by arranging these UAV sub-chromosomes in the order of UAV number from small to large. An encoding example of UAV chromosome is given in Figure 2. The gene (column) sequence of each UAV sub-chromosome represents the task execution order of corresponding UAV. The first three lines of chromosome represent the target number, task number, and UAV number, respectively. ²⁶ Thereinto, the task number of each target contains 1, 2, and 3, which represent $\mathrm{tas}{k}_R$ , $\mathrm{tas}{k}_A$ , and $\mathrm{tas}{k}_V$ , respectively. Each gene represents a task assignment for a specific UAV. Since all tasks are encoded as the first two lines of UAV chromosome, the encoding method satisfies the constraint that all tasks are completely performed (equation (18)). Moreover, UAVs can be assigned to the appropriate type of tasks by encoding the target, task, and UAV as the separate lines. Thus, the proposed encoding method is applicable to the proposed task assignment background.

Figure 2.

Encoding of the UAV chromosome.

In addition, the fourth line of UAV chromosome is the distance $r$ between surveillance UAV and target center, the fifth line of UAV chromosome is the course angle $\theta$ of the UAV. Value ranges of $r$ and $\theta$ are: $r\in [0,r_{det\mathrm{ect}}]$ , $\theta \in [0,2\pi ]$ . Note that the fourth line and fifth line of genes in the strike UAV sub-chromosome are 0. Encoding method of the last two lines can determine the relative position of UAVs and targets, so as to help the algorithm achieve the value of detection revenue function more conveniently.

The proposed encoding method accomplishes the efficient assignment of all tasks, and the task execution order is encoded as the gene sequences of UAV chromosome. Thus, a UAV chromosome achieved by the proposed encoding method can represent a complete task assignment scheme.

• 2) The encoding method of target chromosome: The target chromosome is composed of $N$ target sub-chromosomes, a complete target chromosome is achieved by arranging these target sub-chromosomes in the order of target number from small to large. Each target sub-chromosome is encoded in a matrix of five lines and three columns. An encoding example of $t_1$ sub-chromosome is shown in Figure 3. In Figure 3, the meaning of each line in target chromosome is same as that in UAV chromosome. However, the order of genes in target sub-chromosome is fixed, it cannot represent the task execution order of UAVs. Therefore, different from UAV chromosome, a target chromosome cannot represent a complete task assignment scheme.

Figure 3.

Encoding of the target chromosome.

Initialization

Most of studies generate the initial population by the way of random generation. ³² The way constructs a large search space when solving complex problems, which may lead to a slow convergence speed of the algorithm. Therefore, we propose the novel initialization method for target chromosome and UAV chromosome.

• 1) Target chromosome initialization: Depending on the proposed encoding method, the first two lines of target chromosome can be easily achieved. We assume that matrix formed by the first two lines of target chromosome is $X_t$ . $X_t=\{x_1,x_2,...,x_{3N}\}$ , elements in $X_t$ represent the column of the matrix. Then, a column $x_i$ is randomly selected from $X_t$ , and a complete gene $g_i$ can be achieved based on $x_i$ . For the sake of describing the generation process of $g_i$ more simply and clearly, the j-th line of $g_i$ and $x_i$ are expressed as $g_i(j)$ and $x_i(j)$ , respectively. If $x_i(2)$ is 1 or 3, a surveillance UAV should be selected, and its number is used as $g_i(3)$ . The probability of each surveillance UAV being selected is as follows:

$$P_{\mathrm{Su}}^j=\frac{C_{\mathrm{range}}^j(\wp )}{\sum _{j=1}^{M_{\mathrm{Su}}}{C}_{\mathrm{range}}^j(\wp )},j=1,2,...,M_{\mathrm{Su}}$$

(25)

Afterwards, $g_i(4)$ and $g_i(5)$ are randomly generated within their range of values.

If $x_i(2)$ is 2, a strike UAV should be selected. The probability of each strike UAV being selected is as follows:

$$P_{\mathrm{St}}^j=\frac{C_{\mathrm{range}}^j(\wp )+C_{\mathrm{weapon}}^j(\wp )}{\sum _{j=1}^{M_{\mathrm{St}}}(C_{\mathrm{range}}^j(\wp )+C_{\mathrm{weapon}}^j(\wp ))},j=1,2,...,M_{\mathrm{St}}$$

(26)

Afterwards, both $g_i(4)$ and $g_i(5)$ are set to 0.

The gene generation process should be repeated until all elements of $X_t$ are selected to achieve a complete target chromosome. Note that elements cannot be selected repeatedly.

The proposed target chromosome initialization method should be repeated $n$ times to make the initial population size satisfy the predefined population size $n$ . In the process of the proposed target chromosome initialization, the achieved chromosomes can satisfy the workload balance constraint by generating genes based on the execution capability. These workload balanced chromosomes can constitute a good initial population. Since excellent initial population can speed up the evolution process, ³⁰ the proposed method can accelerate the convergence speed of algorithm. Especially in the complex large-scale task assignment problem, advantages of the method are more prominent.

• 2) UAV chromosome initialization: UAV chromosome is generated during the generation of target chromosome. Once a gene $g_i$ on a target chromosome is generated, which UAV sub-chromosome that $g_i$ belongs to should be determined according to $g_i(3)$ . Suppose that the UAV sub-chromosome is $u_j$ sub-chromosome, $g_i$ should be placed behind genes which have been generated on $u_j$ sub-chromosome. For example, the randomly achieved generation sequence of genes in the target chromosome is: $g_4,g_5,g_1,g_3,...$ , the generation process of UAV chromosome is demonstrated in Figure 4. $N$ UAV sub-chromosomes are achieved when all genes of the target chromosome are generated. Then, a complete UAV chromosome can be easily achieved.

Figure 4.

UAV chromosome initialization process.

In the proposed UAV initialization method, genes on the UAV chromosome correspond one to one with genes on the target chromosome. Therefore, the UAV initialization method ensures that each UAV chromosome has a unique corresponding target chromosome. In addition, the gene generation order of target chromosome is converted into the gene sequence of UAV sub-chromosome. Given that the gene sequence represents the task execution order of UAV, the generated UAV chromosomes can represent a complete assignment scheme and satisfy the encoding requirements.

Fuzzy elite degree

Elitism has a great promotion effect on GA. Convergence speed of the algorithm can be improved by selecting some elite individuals based on the fitness function value. ³³ However, it may reduce the population diversity and finally cause that the algorithm falls into local extremum. Therefore, we propose the concept of fuzzy elite degree $E$ to eliminate this drawback.

Different from elite individuals defined in traditional GA, all individuals in the proposed FESGA are elite to a certain extent. $E$ is adopted to measure the elite degree of an individual. The fitness function value $f$ and the times the individual appears in current iteration $A$ are the major factors of $E$ . Considering that the requirements of elite individuals are different in different genetic operations, we present selection fuzzy elite degree $E_s$ , crossover fuzzy elite degree $E_c$ , and mutation fuzzy elite degree $E_m$ , respectively.

Selection fuzzy elite degree E_s

In the selection process of proposed FESGA, some individuals with high elite degree are selected as elite individuals. Individuals with high $f$ are selected as elite individuals with high probability, so as to retain good genes of the good individuals. Meanwhile, individuals with few $A$ also have the opportunity to be selected, so as to ensure the population diversity. Therefore, $E_s$ is directly proportional to $f$ and inversely proportional to $A$ . $E_s$ of the i-th individual is shown below:

$$\begin{array}{c}\multicolumn{1}{c}{E_s^i={\alpha }_s\left(\frac{{\log }_2(\frac{f_i}{\underset{i}{max}(f_i)}+1)}{\underset{i}{max}({\log }_2(\frac{f_i}{\underset{i}{max}(f_i)}+1))}\right)}\\ +{\beta }_s\left(\frac{\underset{i}{max}(1+e^{\frac{A_i/\underset{i}{max}(A_i)-l_s}{0.1}})}{1+e^{\frac{A_i/\underset{i}{max}(A_i)-l_s}{0.1}}}\right),i=1,2,...,n\hfill \end{array}$$

(27)

where $f_i$ and $A_i$ are the fitness value and occurrence value of the i-th individual. ${\alpha }_s$ and ${\beta }_s$ are constants from 0 to 1. They indicate the influence extent of $f$ and $A$ , respectively. ${\alpha }_s+{\beta }_s=1$ . Considering that $f$ is more important than $A$ , ${\alpha }_s\in [0.5,1]$ , ${\beta }_s\in [0,0.5]$ . $l_s$ is adopted to adjust the range of part $A$ in $E_s$ . For the sake of ensuring that the value range of part $A$ in $E_s$ is closer to [0, 1], $l_s\in [0.4,0.7]$ . And the larger $l_s$ is, the slower $E_s^i$ decreases with the increase of $A_i$ .

Crossover fuzzy elite degree E_c

In the crossover process of proposed FESGA, individuals with higher elite degree are selected as parents with higher possibility. Parents with high $f$ can improve the superiority of offsprings. ³⁴ Meanwhile, the operation that parents with large $A$ are replaced by the newly generated offsprings can increase the population diversity. Therefore, $E_c$ is directly proportional to $f$ and $A$ . $E_c$ of the i-th individual can be achieved in equation (28) by modifying the part of occurrence number in equation (27).

$$\begin{array}{c}\multicolumn{1}{c}{E_c^i={\alpha }_c\left(\frac{{\log }_2(\frac{f_i}{\underset{i}{\max }(f_i)}+1)}{\underset{i}{max}({\log }_2(\frac{f_i}{\underset{i}{\max }(f_i)}+1))}\right)}\\ +{\beta }_c\left(\frac{l_{c2}{e}^{\frac{-l_{c1}}{(A_i/\underset{i}{max}(A_i))+l_{c3}}}}{\underset{i}{max}(l_{c2}{e}^{\frac{-l_{c1}}{(A_i/\underset{i}{max}(A_i))+l_{c3}}})}\right),i=1,2,...,n\hfill \end{array}$$

(28)

where ${\alpha }_c\in [0.5,1]$ , ${\beta }_c\in [0,0.5]$ , and ${\alpha }_c+{\beta }_c=1$ . $l_{c1}$ is used to regulate the rate at which $E_c^i$ varies with $A_i$ . $l_{c1}\in (0,1]$ , and the larger $l_{c1}$ is, the slower the rate changes. $l_{c2}$ and $l_{c3}$ is adopted to ensure that the range of part $A$ in $E_c$ is [0, 1], their values depend on the value of $l_{c1}$ .

Mutation fuzzy elite degree E_m

In the mutation process of proposed FESGA, individuals with lower elite degree are mutated with higher possibility and have higher mutation intensity. Similar to the $E_s$ , $E_m$ is directly proportional to $f$ and inversely proportional to $A$ . However, ideally, more solutions with high $E_m$ are expected to be screened out in the mutation process to destroy good genes of the good individuals as little as possible. Therefore, take $f$ as the example, with the increase of $f$ , $E_m$ increases slowly in the early stage and increases greatly when $f$ increases to nearly its maximum value. Thus, we construct new type exponential function in equation (29) to define $E_m$ of the i-th individual.

$$\begin{array}{c}\multicolumn{1}{c}{E_m^i={\alpha }_m\left(\frac{\underset{i}{max}(1+e^{\frac{-f_i\underset{i}{/max}(f_i)+l_{m1}}{0.1}})}{1+e^{\frac{-f_i\underset{i}{/max}(f_i)+l_{m1}}{0.1}}}\right)}\\ +{\beta }_m\left(\frac{1-e^{l_{m2}-\frac{l_{m2}\underset{i}{max}(A_i)}{A_i}}}{\underset{i}{max}(1-e^{l_{m2}-\frac{l_{m2}\underset{i}{max}(A_i)}{A_i}})}\right),i=1,2,...,n\hfill \end{array}$$

(29)

where ${\alpha }_m\in [0.5,1]$ , ${\beta }_m\in [0,0.5]$ , and ${\alpha }_m+{\beta }_m=1$ . $l_{m1}$ is used to adjust the range of part $f$ in $E_m$ . For the sake of ensuring that the value range of part $f$ in $E_m$ is closer to [0, 1], $l_{m1}\in [0.4,0.7]$ . And the larger $l_{m1}$ is, the slower $E_m^i$ changes with the change of $f_i$ . $l_{m2}$ is the rate at which $E_m^i$ varies with $A_i$ . $l_{m2}\in (0,1]$ , the smaller $l_{m2}$ is, the slower the rate changes.

Fuzzy elite degree is the core concept of the proposed FESGA. In the proposed fuzzy elite degree, the part of fitness function value can help the algorithm quickly converge by largely retaining the good genes of individuals which are closed to the optimal solution; the part of the occurrence number can prevent the algorithm from converging to local extreme by changing the genes of the individuals with more occurrences.

Selection process of FESGA

In the selection process of traditional GA, individuals which do not participate in subsequent genetic operations are defined as elite individuals. Fitness function value is the only criteria for selecting elite individuals without considering other information of the optimization process. ³⁵ For the sake of comprehensively utilizing the effective information of optimization process and improving the performance of algorithm, we present a new selection method. Individuals involved in subsequent genetic operations are called as ordinary individuals in this study. The selection process of FESGA is shown in Algorithm 1.

Algorithm 1. Selection process of FESGA

Input: $n$ individuals (chromosomes) Output: $n_{\mathrm{elite}}$ elite individuals; $n-n_{\mathrm{elite}}$ ordinary individuals 1. Calculate $E_s$ of all individuals by equation (27) 2. Achieve the probability of an individual being elite individual $P_{\mathrm{elite}}^i=\frac{E_s^i}{\sum _{i=1}^n{E}_s^i},i=1,2,...,n$ 3. Rank $n$ individuals in the order of $P_{\mathrm{elite}}^i$ from large to small 4. Achieve an individual set $\Gamma =\{G_1,G_2,...,G_n\}$ 5. Select $\{G_1,G_2,...,G_{n_{\mathrm{elite}}}\}$ from $\Gamma$ as elite individuals 6 Calculate the probability of an individual being ordinary individual $P_{\mathrm{ord}}^i=\frac{f_i}{\sum _{i=1}^{n-n_{\mathrm{elite}}}{f}_i}$ 7. $b=1$ 8. While $b\le n-n_{\mathrm{elite}}$ 9.  Adopt the roulette wheel to select an ordinary individual 10.   $b=b+1$ 11. End

As shown in Algorithm 1, the selection process of FESGA consists of two parts: elite individual selection process (the 1st to 5th statements), and ordinary individual selection process (the 6th to 11st statements). In the elite individual selection process, individuals with higher $E_s$ are selected with higher probability. Since $f$ and $A$ are jointly considered in $E_s$ , the abilities of the algorithm to converge fast and achieve the global optimal solution are enhanced.

Crossover process of FESGA

The essence of crossover is that the new individuals are produced through the gene recombination of parents. In Song et al., ³⁴ a direction-based crossover operator (DBX) was presented to enhance the convergence performance and population diversity. However, DBX only can be applied to the numerically continuous system. It is not suitable for discrete system, such as the task assignment problem. Therefore, we present a parent selection method and a one-point crossover method.

Parent selection method is divided into two parts: selection of the first parent and the second parent.

Individuals with high $E_c$ are selected as the first parent $G_{\mathrm{fp}}$ with high probability. The probability that individuals are selected as $G_{\mathrm{fp}}$ is shown below:

$$P_{\mathrm{fp}}^i=\frac{E_c^i}{\sum _{i=1}^{n-n_{\mathrm{elite}}}{E}_c^i},i=1,2,...,n-n_{\mathrm{elite}}$$

(30)

Then, $G_{\mathrm{fp}}$ can be achieved by roulette wheel. Considering the definition of $E_c$ , the way that selecting parent according to $E_c$ can accelerate the convergence speed of the algorithm and avoid the local extremum problem by improving the superiority and diversity of offspring generation, respectively.

For the sake of further improving search ability of the algorithm, we present the AI mechanism to choose the second parent. The details of AI mechanism are as follows.

First, a concept of elite distance $\Psi \mathrm{ij}$ is proposed to describe the difference degree between any two individuals. $\Psi \mathrm{ij}$ is defined as follows:

$$\Psi \mathrm{ij}=|E_c^i-E_c^j|$$

(31)

Then, individuals which have longer elite distance from $G_{\mathrm{fp}}$ are selected as the second parent with higher probability. Meanwhile, the probability increases slowly in the close elite distance to ensure the sufficient difference of parent generation. The selection probability of the j-th individual can be achieved by

$$P_{\mathrm{sp}}^j=\frac{1}{1+e^{\frac{-\Psi \mathrm{ij}/\underset{j}{max}(\Psi \mathrm{ij})+{\kappa }_{\mathrm{sp}}}{0.1}}},j=1,2,...,n-n_{\mathrm{elite}}-1$$

(32)

where ${\kappa }_{\mathrm{sp}}$ is adopted to adjust the range of $P_{\mathrm{sp}}^j$ . For the sake of ensuring that the value range of $P_{\mathrm{sp}}^j$ is [0, 1], ${\kappa }_{\mathrm{sp}}\in [0.4,0.7]$ . The larger ${\kappa }_{\mathrm{sp}}$ is, the slower $P_{\mathrm{sp}}^j$ changes with the change of $\Psi \mathrm{ij}$ .

Finally, the second parent is achieved by roulette wheel.

In the selection process, more diverse offsprings can be achieved by increasing the difference between parent generation. $f$ , the criterion to evaluate individuals, is adopted to measure the difference in solution between individuals in existing study. ³² $A$ is the occurrence number of the individual in current iteration, it can reflect the difference between individuals during the optimization process. In the proposed AI mechanism, both the solution difference ( $f$ ) and individual difference in the iteration process ( $A$ ) are considered. Thus, difference considered in AI mechanism is more abundant. The AI mechanism is more suitable for complex large-scale task assignment problem.

After determining parents involved in the crossover, the proposed one-point crossover method is adopted to achieve offsprings. The crossover process of a pair of individuals is shown in Figure 5.

Figure 5.

A crossover process example.

Part 1 of Figure 5 can be summarized as following steps.

• Step 1: The first two lines of parent 1 are directly passed on to nonstandard offspring 1 to ensure the integrity of the tasks.

• Step 2: A crossover point are randomly set in the code string of parent 1. All genes in front of the crossover point in parent 1 are directly transmitted to nonstandard offspring 1.

• Step 3: Other genes of nonstandard offspring 1 are provided from parent 2. Gene $g_{\mathrm{parent}1}^4$ in Figure 5 is taken as an example. First, the position of gene $g_{\mathrm{parent}1}^4$ in parent 1 ( ${\mathrm{w}}_4$ ) is recorded. Then, the gene which has the same target and task with $g_{\mathrm{parent}1}^4$ ( $g_{\mathrm{parent}2}^4$ ) is found in parent 2. Finally, $g_{\mathrm{parent}2}^4$ is placed at the position ${\mathrm{w}}_4$ in nonstandard offspring 1.

In part 2 of Figure 5, nonstandard offspring 2 is achieved, and the generation process is similar to that of nonstandard offspring 1. Note that nonstandard offspring 2 is composed of genes in front of the crossover point in parent 2 and genes after the crossover point in parent 1.

In part 3 of Figure 5, the achieved nonstandard offsprings are standardized. Genes whose third line (UAV number) are same are put together to achieve the standard form of chromosomes.

In the one-point crossover method, the first two lines of parents are fully inherited to offsprings, which can guarantee that all tasks are assigned and these tasks are not repeatedly executed. Since the achieved offsprings can still represent a complete allocation scheme, the proposed one-point crossover method is suitable for multiple heterogeneous UAVs task assignment background.

The parent selection method and one-point crossover method should be repeated until $n{P}_c$ pairs of offsprings are achieved, where $P_c$ is the crossover probability.

Mutation process of FESGA

Mutation is helpful for the algorithm to avoid falling into local extremum. ³⁶ In the completely random traditional mutation method, the mutation intensity of good individuals and bad individuals are same. It may cause that good individuals get worse, and bad individuals do not have mutation intensity to overstep the local extreme. Therefore, we propose the HM rule in the mutation process. Meanwhile, we present three mutation methods.

Mutation methods

• (1) Change the execution sequence of tasks: randomly exchange the position of genes on any UAV sub-chromosome. ²⁶

• (2) Assign a different UAV to a randomly selected task: randomly select a gene, and update the third line of the gene by randomly selecting a different matching UAV based on the type of task on the gene. ²⁵

• (3) Change the location of a randomly selected surveillance UAV: randomly select a gene g_m whose third line represents the surveillance UAV. Then, change the values of $g_m(4)$ and $g_m(5)$ . Note that the value range of $g_m(4)$ and $g_m(5)$ are: $g_m(4)\in [0,r_{det\mathrm{ect}}]$ , $g_m(5)\in [0,2\pi ]$ .

A variety of different mutation methods can achieve different task allocation strategy from multiple aspects, so as to better avoid the algorithm being trapped in local extremum.

The implementation process of HM rule

• Step 1: $E_m$ of all individuals are calculated by equation (29).

• Step 2: Individuals which are involved in the mutation operation are selected by roulette wheel. We stipulate that individuals with higher $E_m$ participate in the mutation operation with smaller possibility to prevent the destruction of good genes in good individuals. Therefore, the probability that individuals are involved in mutation can be calculated by

$$P_{\mathrm{mu}}^i=\frac{1/E_m^i}{\sum _{i=1}^{n-n_{\mathrm{elite}}}(1/E_m^i)},i=1,2,...,n-n_{\mathrm{elite}}$$

(33)

• Step 3: The elite class of the selected individual is determined based on $E_m$ . The classification criteria is exhibited in Table 1.

• Step 4: In the proposed HM rule, the lower the elite class of an individual is, the greater the mutation intensity of the individual. The different mutation rules are formulated for individuals of different elite classes. The specific content is shown in Table 1.

Table 1.

The classification criteria of individuals.

$E_m$ of individuals	Elite class	Mutation rule
0.85–1.00	High-class	Randomly adopt one of the mutation methods
0.50–0.85	Middle-class	Adopt any two of the mutation methods
0.00–0.50	Low-class	Successively adopt all the three mutation methods

The HM rule should be repeated until $n{P}_m$ individuals are generated, where $P_m$ is the mutation probability.

The proposed HM rule enhances the ability of individuals with smaller $f$ to overstep the local extreme by giving these individuals larger mutation intensity. Thus, search ability of the algorithm is improved. In addition, the HM rule can generate a more diverse population by mutating individuals with high $A$ . Thus, the ability of the algorithm to find the global optimum is further improved.

Note that some infeasible solutions that do not satisfy the limited resource constraint may be generated in the genetic operations, $f$ of these infeasible solutions are 0. The existence of infeasible solutions can destroy the integrity of the population. ³⁷ Therefore, we propose the no zero mechanism to deal with the infeasible solutions. The pseudo-code of the no zero mechanism is shown in Algorithm 2.

Algorithm 2. The process of no zero mechanism

Input: an infeasible solution (chromosome) $G_{inf}=\{g_1,g_1,...,g_{3N}\}$ ; $f_{\mathrm{nz}}(f\mathrm{of}{G}_{inf})$ Output: a feasible solution $G_{\mathrm{feasible}}$ 1. While $f_{\mathrm{nz}}=0$ 2.  Randomly select a gene $g_i$ from $G_{inf}$ 3.  Achieve the task type $\eta$ by $g_i(2)$ 4.  Achieve a set $U_{\eta }$ consists of UAVs which can execute type $\eta$ of task 5.  While $f_{\mathrm{nz}}=0$ 6.   Randomly select a UAV $u_i$ from $U_{\eta }$ 7.   Update $g_i(3)$ to the number of $u_i$ 8.   Achieved a nonstandard chromosome $G_{\mathrm{feasible}}^{\mathrm{non}}$ 9   Convert $G_{\mathrm{feasible}}^{\mathrm{non}}$ to the standard from to achieve $G_{\mathrm{feasible}}$ 10.    $f_{\mathrm{nz}}=f\mathrm{of}{G}_{\mathrm{feasible}}$ 11.   If all UAVs of $U_{\eta }$ have been selected 12.    Break 13.   End 14.  End 15. End

Algorithm 3. The implement process of STC mechanism

Input: population ${\Gamma }_t^{\mathrm{init}}=\{G_t^1,G_t^2,...,G_t^n\}$ ; time ${\wp }_{\mathrm{th}}$ when detecting sudden threat Output: new population ${\Gamma }_t^{\mathrm{new}}=\{G_u^1,G_u^2,...,G_u^n\}$ 1. Achieve the state, resource consumption, and location of each UAV at ${\wp }_{\mathrm{th}}$ 2. $j=1$ 3. While $j\le n$ 4.  Achieve a new chromosome $G_t^{\mathrm{new}}$ by deleting genes which contain the information of completed tasks from $G_t^j$ 5.  Achieve genes $\{g_{\mathrm{per}}^1,g_{\mathrm{per}}^2,...g_{\mathrm{per}}^k\}$ containing information about tasks being performed 6.  Achieve a matrix $X_t^{\mathrm{new}}$ by deleting the last three lines of $G_t^{\mathrm{new}}$ except for $\{g_{\mathrm{per}}^1,g_{\mathrm{per}}^2,...g_{\mathrm{per}}^k\}$ 7.   $g_{\mathrm{threat}}^1(1)=N+1,g_{\mathrm{threat}}^1(2)=2$ 8.  Select a strike UAV $u_{\mathrm{st}}$ according to $P_{\mathrm{threat}}^i,i=1,2,...,M_{\mathrm{St}}$ 9.   $g_{\mathrm{threat}}^1(3)=\mathrm{the}\mathrm{number}\mathrm{of}{u}_{\mathrm{st}},g_{\mathrm{threat}}^1(4)=0,g_{\mathrm{threat}}^1(5)=0$ 10.  Add $g_{\mathrm{threat}}^1$ after the last column of $X_t^{\mathrm{new}}$ 11.   $g_{\mathrm{threat}}^2(1)=N+1,g_{\mathrm{threat}}^2(2)=3$ 12.  Select a surveillance UAV $u_{\mathrm{su}}$ according to $P_{\mathrm{threat}}^i,i=1,2,...,M_{\mathrm{Su}}$ 13.   $g_{\mathrm{threat}}^2(3)=\mathrm{the}\mathrm{number}\mathrm{of}{u}_{\mathrm{su}},\mathrm{randomly}\mathrm{generate}{g}_{\mathrm{threat}}^2(4)\mathrm{and}{g}_{\mathrm{threat}}^2(5)$ 14.  Add $g_{\mathrm{threat}}^2$ after $g_{\mathrm{threat}}^1$ 15.  Achieve a target chromosome ${\tilde{G}}_t^j$ 16.  Achieve $G_u^j$ based on ${\tilde{G}}_t^j$ according to the initialization method in Section 3.2 17.   $j=j+1$ 18. End 19. Achieve ${\Gamma }_u^{\mathrm{new}}$

In Algorithm 2, the no zero mechanism converts the infeasible solutions to be feasible by coordinating the workload between UAVs. Compared with the method of directly generating new feasible solutions,^25,38 the proposed no zero mechanism can retain good genes of the infeasible chromosomes to a large extent. Thus, the feasible solutions achieved by the no zero mechanism are better than the randomly generated solutions. The mechanism can help the algorithm converge fast.

Methods for deadlock and sudden threat

Deadlock

In the task assignment problem with task priority constraint, the UAV system may fall into deadlock. The possibility that UAV system falls into deadlock increases with the increase of task scale. The deadlock status mainly includes self-lock and interlock. ³²

Self-lock problem

Self-lock means that lower-priority task on a target is executed earlier than the higher-priority task on the target. ¹⁹ The self-lock problem is easy to be solved by swapping the execution order of the tasks.

Interlock problem

In most situations, the deadlock that UAV system is stuck in is interlock. In the interlocked status, multiple UAVs fall into endless waiting as they wait for each other to execute tasks. ³⁹ A pair of corresponding UAV chromosome and target chromosome contain the information of task execution order of UAVs and targets, respectively. The state of each UAV during the mission can be determined by decoding this pair of chromosomes. When two or more UAVs are in the permanent waiting state, the UAV system gets into interlock. Since the interlock problem involves the coordinated control of multiple UAVs, it is more complex and difficult to be solved than self-lock problem. We present two unlock methods for the interlock problem.

To describe the unlock process more clearly, we define the deadlock chromosome. Each deadlocked task assignment scheme is corresponding to a unique UAV chromosome. A new chromosome can be achieved by deleting the genes carrying information about the completed tasks from the UAV chromosome. The new chromosome is the deadlock chromosome. Similar to UAV chromosome, the deadlock chromosome can be divided into several deadlock sub-chromosomes according to the UAV number. The first gene in each deadlock sub-chromosome is defined as the deadlock gene.

Unlock Method 1: Firstly, a deadlock gene $g_{\mathrm{deadlock}}^1$ is randomly selected. Suppose $g_{\mathrm{deadlock}}^1(1)$ indicates the target $t_j$ . Then, gene $g_h$ which contains the information of the task with the highest priority of $t_i$ is found from the deadlock chromosome. Meanwhile, the deadlock sub-chromosome where $g_h$ resides is determined. Finally, deadlock gene of the determined deadlock sub-chromosome switches places with $g_h$ .

Unlock Method 2: Firstly, a surveillance UAV $u_i$ that has not completed its tasks is randomly selected. A reconnaissance task $\mathrm{tas}{k}_r$ is randomly chosen from unexecuted tasks. Suppose the gene carrying the information of $\mathrm{tas}{k}_r$ is $g_c$ . Then, $g_c$ is moved to the position in front of the deadlock gene of $u_i$ deadlock sub-chromosome, and $g_c(3)$ is set to the number of $u_i$ .

Each unlock method is conducted with one-half probability. Note that each method is adopted to remove current deadlock status. After each unlocking, the new solution should be determined whether is deadlocked. If the solution is deadlocked, the unlock methods are adopted again. A deadlock-free solution can be achieved by repeating the above process.

Compared with the unlock methods that only exchanging the task execution order,^19,28 our proposed unlock methods can also resolve the deadlock problem by adjusting the matching relationship between UAVs and targets. Therefore, the proposed unlock methods are more diversified, they can increase the search ability of the algorithm. Moreover, compared with digraph-based unlock method, ³² fewer loops are involved in the proposed unlock methods. Thus, the proposed methods have less computation and faster unlock speed. Especially in the complex large-scale task scenario, the proposed unlock methods have more obvious advantages.

Task assignment with sudden threat

During the execution of scheduled tasks, UAV system may discover some unknown threats. ⁴⁰ We call these threats sudden threats in this study. All sudden threats should be immediately destroyed after being detected. There are two tasks on each sudden threat: the attack task ${\mathrm{task}}_{\mathrm{threat}}^A$ and verification task ${\mathrm{task}}_{\mathrm{threat}}^V$ . Note that ${\mathrm{task}}_{\mathrm{threat}}^A\succ {\mathrm{task}}_{\mathrm{threat}}^V$ . The emergence of sudden threat changes the original task environment. For the sake of making the algorithm adapt to new environment quickly, we propose the STC mechanism.

In the proposed STC mechanism, the probability of $u_i$ to execute ${\mathrm{task}}_{\mathrm{threat}}^A$ or ${\mathrm{task}}_{\mathrm{threat}}^V$ when detecting the sudden threat (at time ${\wp }_{\mathrm{th}}$ ) can be achieved as follows:

$$\begin{array}{c}{P}_{\mathrm{threat}}^i({\wp }_{\mathrm{th}})=l_m(l_1{\gamma }_1\frac{e^{\frac{{\kappa }_{\mathrm{th}1}}{-{\wp }_w^i/{\wp }_{max}^i-1}}}{e^{-{\kappa }_{\mathrm{th}1}}}+l_2{\gamma }_2\frac{e^{\frac{{\kappa }_{\mathrm{th}2}}{-{\wp }_e^i/{\wp }_{max}^i-1}}}{e^{-{\kappa }_{\mathrm{th}2}}}\hfill \\ +l_3{\gamma }_3\frac{e^{\frac{{\kappa }_{\mathrm{th}3}}{-d_i({\wp }_{\mathrm{th}})/d_{max}^i-1}}}{e^{-{\kappa }_{\mathrm{th}3}}}+l_4{\gamma }_4\frac{e^{\frac{-{\kappa }_{\mathrm{th}4}}{w_i({\wp }_{\mathrm{th}})/w_{max}^i}}}{e^{-{\kappa }_{\mathrm{th}4}}})+{\gamma }_5\frac{e^{\frac{{\kappa }_{\mathrm{th}5}}{-d_{\mathrm{th}}^i/d_{max}^i-1}}}{e^{-{\kappa }_{\mathrm{th}5}}}\hfill \end{array}$$

(34)

where ${\wp }_w^i$ represents the remaining waiting time of $u_i$ in the waiting state, ${\wp }_e^i$ represents the remaining time of $u_i$ in the task execution state to complete the task, $d_i({\wp }_{\mathrm{th}})$ is the traveled range of $u_i$ at ${\wp }_{\mathrm{th}}$ , $w_i({\wp }_{\mathrm{th}})$ is the remained weapon number on $u_i$ at ${\wp }_{\mathrm{th}}$ , $d_{\mathrm{th}}^i$ represents the Euclidean distance between the location of $u_i$ and sudden threat. ${\gamma }_1$ , ${\gamma }_2$ , ${\gamma }_3$ , ${\gamma }_4$ , and ${\gamma }_5$ represent the proportion of ${\wp }_w^i$ , ${\wp }_e^i$ , $d_i({\wp }_{\mathrm{th}})$ , $w_i({\wp }_{\mathrm{th}})$ , and $d_{\mathrm{th}}^i$ in equation (34), respectively. $l_m$ is a binary variable, which equals 1 when $u_i$ has executed tasks before ${\wp }_{\mathrm{th}}$ . Moreover, $l_1$ , $l_2$ , $l_3$ , and $l_4$ are binary variables. $l_1$ , $l_2$ , and $l_3$ are set as 1 when $u_i$ is in the waiting state, task execution state, and flight state, respectively. $l_4$ equals 1 only when $u_i$ is strike UAV. ${\kappa }_{\mathrm{th}1}$ , ${\kappa }_{\mathrm{th}2}$ , ${\kappa }_{\mathrm{th}3}$ , ${\kappa }_{\mathrm{th}4}$ , and ${\kappa }_{\mathrm{th}5}$ denote the rate at which $P_{\mathrm{threat}}^i({\wp }_{\mathrm{th}})$ varies with ${\wp }_w^i$ , ${\wp }_e^i$ , $d_i({\wp }_{\mathrm{th}})$ , $w_i({\wp }_{\mathrm{th}})$ , and $d_{\mathrm{th}}^i$ , respectively. Their value ranges are: $(0,1]$ . For ${\kappa }_{\mathrm{th}1}$ , ${\kappa }_{\mathrm{th}2}$ , ${\kappa }_{\mathrm{th}3}$ , and ${\kappa }_{\mathrm{th}5}$ , the smaller the values of these parameters are, the slower the rate changes. But for ${\kappa }_{\mathrm{th}4}$ , the larger the value is, the slower the rate changes.

Simulation results

In this section, we evaluate the search ability and convergence speed of algorithms via extensive numerical simulations. Specifically, we consider a small-scale task assignment scenario (three targets and three UAVs) and a large-scale task assignment scenario (seven targets and four UAVs) in the simulations. The superiority of proposed algorithms is validated through the simulation in comparison with the variants of GA (modified genetic algorithm (GA), ²⁵ DGA, ²⁶ co-evolutionary multi-population genetic algorithm (CMGA), ²² modified genetic algorithm combined with greedy strategy (MGGS) ²³ ) and other optimization algorithms (particle swarm optimization algorithm based on guidance mechanism (GMPSO), ²⁰ artificial bee colony (ABC) algorithm, ²¹ and enumeration method). The effectiveness of proposed algorithm is confirmed by analyzing the typical solutions. All numerical simulations were conducted under the MATLAB environment (i.e. MATLAB 2014, Intel Core i5-8400 CUP@2.80 GHz).

In the simulations, parameters of UAV system and targets are shown in Tables 2 and 3, respectively. The resource consumption of UAVs under different states are shown in Table 4. Moreover, parameters of the proposed FESGA are summarized in Table 5.

Table 2.

Parameters of UAV system.

$u_i$	Type	Initial location (m)	Detection range (m)	Weapon resources	Maximum range (m)	Endurance time (min)	Ideal flight speed (m/min)	Maximum fuel capacity (L)
$u_1$	$U_{\mathrm{Su}}$	[0, 0]	30	0	4400	23	200	20
$u_2$	$U_{\mathrm{Su}}$	[0, 0]	30	0	4400	23	200	25
$u_3$	$U_{\mathrm{St}}$	[0, 0]	0	11	2600	23	150	8
$u_4$	$U_{\mathrm{St}}$	[0, 0]	0	11	2600	23	150	13

Table 3.

Parameters of targets.

Parameters	Targets
	$t_1$	$t_2$	$t_3$	$t_4$	$t_5$	$t_6$	$t_7$
Location (m)	[525, 335]	[347, 387]	[243, 615]	[163, 450]	[578, 513]	[114, 193]	[347, 150]
Required tasks	$R,A,V$	$R,A,V$	$R,A,V$	$R,A,V$	$R,A,V$	$R,A,V$	$R,A,V$
Required weapon number	2	2	3	2	3	2	2

Table 4.

Parameters involved in task scenario.

$u_i$	Fuel consumption per unit of time (L/min)			Time to perform tasks (min)
	UAV state			Task type
	E	W	F	TaskR	TaskA	TaskV
$u_1$	0.80	0.30	1.10	0.30	/	0.30
$u_2$	1.00	0.40	1.20	0.30	/	0.30
$u_3$	0.90	0.30	1.10	/	0.15	/
$u_4$	1.00	0.35	1.15	/	0.15	/

Table 5.

Parameters of the proposed FESGA.

Parameters	Description	Setting	Parameters	Description	Setting
${\mu }_{max}$	Maximum iteration number in small scale	700	$l_{c1}$		0.3
	Maximum iteration number in large scale	3000	$l_{c2}$		$e^{0.25}$
$n$	Population size	50	$l_{c3}$		0.1
$n_{\mathrm{elite}}$	Elite individual number	3	${\alpha }_m$	Calculating $E_m$	0.7
$P_c$	Crossover probability	0.7	${\beta }_m$		0.3
$P_m$	Mutation probability	0.3	$l_{m1}$		0.6
${\kappa }_r$	Adjusting the value of Execution capability	0.1	$l_{m2}$		0.2
${\kappa }_w$		0.3	${\kappa }_{\mathrm{sp}}$	Calculating $P_{\mathrm{sp}}^j$	0.6
${\alpha }_s$	Calculating $E_s$	0.7	${\kappa }_{\mathrm{th}1}$	Calculating $P_{\mathrm{threat}}^j$	0.1
${\beta }_s$		0.3	${\kappa }_{\mathrm{th}2}$		0.1
$l_s$		0.6	${\kappa }_{\mathrm{th}3}$		0.1
${\alpha }_c$	Calculating $E_c$	0.8	${\kappa }_{\mathrm{th}4}$		0.3
${\beta }_c$		0.2	${\kappa }_{\mathrm{th}5}$		0.1

To indicate the computational efficiency of the proposed FESGA intuitively, we analyze the complexity of the proposed algorithm as follows. The key factors affecting the running speed of proposed FESGA are the calculation of fuzzy elite degree, genetic operations of crossover and mutation, and unlocking of deadlock solutions. The complexity of these operations depends on the population size $n$ and maximum iteration number ${\mu }_{max}$ . In the worst case, all individuals need to unlock. Therefore, the complexity of the proposed FESGA can be bound by $O(n{\mu }_{max})$ . Further, the calculation time comparisons are given to show the complexity. The specific comparison results are presented in Table 6 below.

Table 6.

Performance comparison of algorithms.

Task scenario	Algorithm	$\mathrm{ave}(f_{\mathrm{best}})$	$\mathrm{err}$ (%)	$\Gamma$ (s)	${\mu }_{\mathrm{stable}}$
Small-scale task scenario	FESGA	3.5545	0	128.08	286
	MGGS	3.5279	0.75	148.83	568
	CMGA	3.4792	2.12	98.82	598
	DGA	3.2475	8.64	139.78	594
	GA	3.5241	0.86	111.67	601
	GMPSO	3.3392	6.06	133.62	27
	ABC	3.5024	1.47	135.49	313
	Enumeration	3.5545	0	1863.24	/
Large-scale task scenario	FESGA	1.7049	3.17	1653.03	1833
	MGGS	1.5896	9.92	1805.52	2019
	CMGA	1.4791	16.00	1082.69	2517
	DGA	1.4660	16.74	2966.43	2721
	GA	1.4298	18.79	1253.02	2197
	GMPSO	1.4124	19.78	2148.53	49
	E	1.5019	14.70	1821.52	2920
	enumeration	1.7607	0	4,4268.96	/

To verify the universal validity of FESGA, we perform 50 Monte Carlo comparison experiments under two different task-scale scenarios. Given that strong search ability can help the algorithm overstep the local extremum and find good solution, the average of the optimal fitness value achieved by algorithms in the Monte Carlo comparison experiments $\mathrm{ave}(f_{\mathrm{best}})$ and the error between the obtained result and the optimal solution $\mathrm{err}=|\mathrm{ave}(f_{\mathrm{best}})-f_{\mathrm{best}}^{\mathrm{enu}}|/f_{\mathrm{best}}^{\mathrm{enu}}$ are taken as the criteria to judge the search ability of algorithms. Where $f_{\mathrm{best}}^{\mathrm{enu}}$ is the optimal solution obtained by the enumeration method. In addition, the number of iterations required to converge to a stable level ${\mu }_{\mathrm{stable}}$ and the calculation time $\Gamma$ are adopted to measure the rapidity of algorithms. The comparison results are illustrated in Table 6.

As shown in Table 6, in the small-scale task scenario, $\mathrm{err}$ of the presented FESGA is 0. It means that FESGA can converge to the global optimal quickly. In the large-scale task scenario, only $\mathrm{err}$ of the enumeration method equals 0. As a brute force method, the enumeration method can find the global optimal solution at all costs, but it is not suitable for practical applications due to the large amount of calculation time and cost. In addition to the enumeration method, FESGA has the smallest $\mathrm{err}$ compared with other heuristic algorithms. Therefore, the proposed FESGA can find high-quality suboptimal solutions in limited running time. It shows strong searching ability. In addition, only CMGA and GA are slightly better than the proposed FESGA as for the calculation time ( $\Gamma$ ). But the small reduction in running time comes at the expense of algorithm accuracy. Meanwhile, GMPSO converges to the stable level in the fastest way by comparing ${\mu }_{\mathrm{stable}}$ of all algorithms. Nevertheless, $\mathrm{err}$ of GMPSO is too large to provide satisfactory task assignment schemes. The presented FESGA has the smallest ${\mu }_{\mathrm{stable}}$ except GMPSO, it can provide good enough solutions while exhibiting the characteristic of fast convergence.

Generally, the convergence speed of algorithms is judged by ${\mu }_{\mathrm{stable}}$ . As shown in Figures 6 and 7, in any task scales, the four algorithms with the fastest convergence speed are arranged in order: GMPSO, FESGA, ABC, and MGGS. The differences in convergence performance of other algorithms are not obvious. Although the convergence speed of GMPSO is faster than that of the proposed FESGA, the results obtained by GMPSO are inferior to those obtained by FESGA. In addition, Figures 6 and 7 show that FESGA can quickly obtain the global optimal solution in small-scale task scenario, and the result obtained in large-scale task scenario is similar to the global optimal solution, which is obtained by enumeration method. Therefore, the optimization effect of FESGA is verified.

Figure 6.

Comparison of the optimization process in the small-scale task scenario.

Figure 7.

Comparison of the optimization process in the large-scale task scenario.

Figures 6 and 7 indicate that the comprehensive performance of proposed FESGA is superior to other algorithms in any task scales. First, FESGA is slightly inferior to GMPSO in terms of convergence speed. This is because that GMPSO effectively uses the global information to search the current optimal solution space. However, GMPSO is easy to fall into the local extremum due to the over-dependence of current optimal solution. Compared with other algorithms, the proposed FESGA shows the fastest convergence speed. It benefits from the high-quality population obtained by the proposed initialization method. In addition, as shown in Figures 6 and 7, FESGA shows obvious advantages in searching ability than other algorithms. Unlike GMPSO and ABC, the variants of GA can better explore the solution space by the mutation operation. However, the inflexible genetic operation intensity may lead to the insufficient searching strength in the later stage of algorithms. Compared with other algorithms, the great advantage of FESGA lies in the proposed concept of fuzzy elite degree ( $E_s$ , $E_c$ , $E_m$ ). The fuzzy elite degree balances the contradiction between fast converge speed and strong search ability by optimizing the retention of excellent genes and the change of individuals. Meanwhile, the presented HM rule set sufficient mutation intensity for poor individuals to further increase the probability of overstepping the local extremum. The superiority of the proposed FESGA in terms of convergence speed and searching ability are verified in Figures 6 and 7.

In one case of the large-scale task scenario, a solution achieved by FESGA is taken as an example to verify the effectiveness of FESGA. The approximate trajectory of each UAV under the achieved solution is demonstrated in Figure 8. Then, we analyze the feasibility of the solution from two aspects of task priority constraint and workload balance constraint.

Figure 8.

The approximate trajectory of UAV system: (a) approximate trajectories of $u_1$ and $u_2$ and (b) approximate trajectories of $u_3$ and $u_4$ .

The satisfied task priority constraint

The information of task execution order is extracted from Figure 8. Then, the task sequence of UAV system is given in Figure 9. The timeline in Figure 9 starts with the beginning of task execution and ends with the completion of all tasks. The dotted orange line corresponds to the time when all tasks on each target are completed. For each UAV, the flight time required to reach the next target, task execution time and synchronous waiting time are represented by blue, red, and green, respectively. The number of target that UAV reaches and the task to be executed are shown at the end of the blue rectangle. In Figure 9, task execution order of all targets are: $\mathrm{tas}{k}_R$ , $\mathrm{tas}{k}_A$ , and $\mathrm{tas}{k}_V$ . That is, tasks on all targets are performed in order of priority from high to low. Thus, the effectiveness of FESGA in task priority constraint is verified. The proposed algorithm can reasonably plan the task order based on the task priority.

Figure 9.

Task sequence of UAV system.

The satisfied workload balance constraint

Define an equalization coefficient $\zeta$ to evaluate the workload balance degree of the task assignment scheme. The equalization coefficient of $u_i$ is expressed as follows:

$${\zeta }_i={\rho }_1\frac{d_{\mathrm{total}}^i}{d_{max}^i}+{\rho }_2\frac{{\mathrm{fuel}}_{\mathrm{total}}^i}{{\mathrm{fuel}}_{max}^i}+\lambda {\rho }_3\frac{w_{\mathrm{total}}^i}{w_{max}^i},i=1,2,...,M$$

(35)

$$\mathrm{Where}\lambda =\{\begin{array}{c}1,u_i\mathrm{is}\mathrm{a}\mathrm{strike}\mathrm{UAV}\hfill \\ \multicolumn{1}{c}{0,\mathrm{others}}\end{array}$$

(36)

$${\rho }_1+{\rho }_2+\lambda {\rho }_3=1$$

(37)

In equation (35), ${\zeta }_i$ reflects the proportion of consumed resources in the maximum consumable resources. If there are no significant difference found among $\zeta$ of different UAVs, we can consider that this scheme satisfies the workload balance constraint. Nevertheless, given that the value of $\lambda$ corresponding to different types of UAVs is different, only $\zeta$ of the same type of UAVs can be compared. The evaluation results of the workload balance degree of UAV system is shown in Table 7.

Table 7.

Evaluation of the workload balance degree of UAV system.

$u_i$		Sailed distance (m)	Consumed fuel (L)	Consumed weapon number	$\zeta$ (%)	$a_{\zeta }$ (%)	$v_{\zeta }$ (%)
Surveillance UAV	$u_1$	1266.7	7.89	/	34.11	34.77	0.0087
	$u_2$	1443.7	9.51	/	35.43
Strike UAV	$u_3$	1441.7	5.58	8	65.98	60.90	0.5171
	$u_4$	1264.3	5.99	8	55.81

In Table 7, $a_{\zeta }$ and $v_{\zeta }$ are the average and variance of $\zeta$ of the same type of UAVs, respectively. Since $v_{\zeta }$ of surveillance UAV and strike UAV are both less than 1%, we can draw the conclusion that the solution satisfies the workload balance constraint. Therefore, the proposed FESGA can reasonably allocate tasks and plan the proportion of resources according to the airborne resources of UAVs.

The above experiments mainly compare the performance of algorithms in the static task scenario. To verify the wide adaptability of proposed FESGA and the superiority of proposed STC mechanism in dealing with sudden threat, we introduce sudden threat in the original task scenarios. Then, the comparison study on the optimization process of ABC, GMPSO, GA, DGA, CMGA, MGGS, FESGA, and FESGA with STC mechanism are demonstrated. The comparison results are indicated in Figures 10 and 11.

Figure 10.

Comparison result in the small-scale task scenario with sudden threat.

Figure 11.

Comparison result in the large-scale task scenario with sudden threat.

The focus of our study is the optimization process of the algorithm after detecting the sudden threat. Therefore, in the optimization process without sudden threat, we only show the last 50 iterations in Figures 10 and 11. In the simulation of small-scale and large-scale task scenarios, the sudden threat is detected at $\mu =700$ and $\mu =3000$ , respectively. Changes in the resources, state and location of UAVs caused by the sudden threat will decrease the fitness function value, and the value decreases more obviously in large-scale task scenario. This is because that targets are more widely distributed in large-scale task scenario, more resources are consumed when dispatching UAVs to destroy the sudden threat. Task scenario with sudden threats has higher requirement on rapidity. Thus, we focus on the comparison of the rapidity performance of algorithms. Indicators $\Gamma$ and ${\mu }_{\mathrm{stable}}$ can measure the rapidity of algorithms in two aspects of calculation time and convergence speed, respectively. Where ${\mu }_{\mathrm{stable}}$ can be obtained from Figures 10 and 11. The comparison results are indicated in Table 8.

Table 8.

Rapidity performance comparison in the task scenario with sudden threats.

Task scenario	Algorithm	$\Gamma$ (s)	${\mu }_{\mathrm{stable}}$
Small-scale task scenario	FESGA with STC	31.29	36
	FESGA	31.87	48
	MGGS	53.89	79
	CMGA	38.82	138
	DGA	38.02	139
	GA	37.47	130
	GMPSO	91.17	82
	ABC	64.38	38
	Enumeration	992.85	/
Large-scale task scenario	FESGA with STC	42.36	73
	FESGA	62.89	158
	MGGS	76.52	185
	CMGA	50.98	211
	DGA	287.63	213
	GA	62.42	226
	GMPSO	106.68	152
	ABC	100.04	90
	Enumeration	1296.85	/

As shown in Table 8, both $\Gamma$ and ${\mu }_{\mathrm{stable}}$ of FESGA with STC mechanism are the minimum under different task scales. Therefore, the proposed STC mechanism can greatly improve the calculation time and convergence performance of FESGA in both small-scale and large-scale task scenarios. This is because the proposed STC mechanism can make full use of the feedback information of the sudden threat and UAV system, and help the algorithm rapidly adjust the allocation scheme. Thus, many excellent solutions can be achieved in a short time, convergence speed of the algorithm is accelerated.

Conclusion

In this study, we focus on the complex task assignment problem of heterogeneous UAV system with multiple constraints. The optimization model is formulated based on the comprehensive consideration of the UAV resource consumption, task completion effect, workload balance, task priority, and limited resources. The concept of fuzzy elite degree is proposed to optimize the retention and change intensity of genes, so as to improve the efficiency of the algorithm. Based on the concept, the FESGA is presented to assign tasks to heterogeneous UAV system. In addition, two unlock methods are presented to deal with the deadlock solutions appearing in the optimization process. Then, the STC mechanism is proposed to help the algorithm converge quickly in the complex changing task scenario with sudden threats. Finally, the comparative results indicate that the proposed algorithm has significant search ability and convergence performance. Especially in large-scale task scenarios, advantages of the algorithm are more obvious.