Hierarchical Task Assignment for Multi-UAV System in Large-Scale Group-to-Group Interception Scenarios

Abstract

The multi-UAV task assignment problem in large-scale group-to-group interception scenarios presents challenges in terms of large computational complexity and the lack of accurate evaluation models. This paper proposes an effective evaluation model and hierarchical task assignment framework to address these challenges. The evaluation model incorporates the dynamics constraints specific to fixed-wing UAVs and improves the Apollonius circle model to accurately describe the cooperative interception effectiveness of multiple UAVs. By evaluating the interception effectiveness during the interception process, the assignment scheme of the multiple UAVs could be given based on the model. To optimize the configuration of UAVs and targets, a hierarchical framework based on the network flow algorithm is employed. This framework utilizes a clustering method based on feature similarity and interception advantage to decompose the large-scale task assignment problem into smaller, complete submodels. Following the assignment, Dubins curves are planned to the optimal interception points, ensuring the effectiveness of the interception task. Simulation results demonstrate the feasibility and effectiveness of the proposed scheme. With the increase in the model scale, the proposed scheme has a greater descending rate of runtime. In a large-scale scenario involving 200 UAVs and 100 targets, the runtime is reduced by $84.86\%$.

1. Introduction

Counter-UAV has become a hot topic, as UAV attacks are increasing and used in conflicts [1]. Traditional counter-UAV approaches include methods such as fire strikes and electromagnetic interference. With the increase in the scale of low-cost UAVs, traditional counter-UAV methods are ineffective. In the face of large-scale UAV attacks, hostile UAV swarms can be constructed to achieve counter-UAV in the form of active interception [2]. This new type of counter-UAV covers advanced technologies including intelligent decision making and control and has certain advantages. For large-scale UAV attacks, interception based on fixed-wing UAV platforms will become one of the most important means of countering [3,4]. Task assignment, as the essential component of the multi-UAV system, plays a vital role in the optimal configuration of targets and UAVs in interception scenarios [5]. Once a target is detected, the UAV needs to provide an intercept solution as soon as possible, based on the situation of both sides. In large-scale interception scenarios, it is crucial for the assignment algorithm to fulfill the prerequisites of a reliable evaluation model and efficient solution speed. Solving the task assignment problem in large-scale group-to-group interception scenarios is still a challenge.

In large-scale group-to-group interception scenarios, multiple UAVs assess the situation by considering relevant information and form an assignment plan based on the evaluation outcomes. The multi-UAV task assignment problem in large-scale interception scenarios has the following characteristics.

• The evaluation model may need to effectively evaluate the offensive and defensive situations of both parties and integrate the task assignment result with the interception technology to ensure the successful execution of the interception task.
• There will be clustering targets in large-scale interception scenarios, and UAVs may need to cooperate to complete the task. In addition, the execution capabilities of UAVs are different.
• The task assignment algorithm should provide feasible solutions in a short time to accommodate the high-speed movements of fixed-wing UAVs.

The establishment of an evaluation model is the basis of task assignment. A reasonable evaluation model is essential to ensure the efficiency of group-to-group interception. Gao et al. conduct an evaluation model that takes into account the azimuth, speed, and distance advantages [6]. Traditional evaluation models typically focus on the individual value of a single UAV and seldom consider the effectiveness of multi-UAV cooperative interception. Sun et al. establish the evaluation model considering not only the relative position and velocity mentioned in traditional functions, but also relative normal velocity, normal acceleration, maneuverability, and cooperation between multiple missiles [7]. Wang et al. and Guo et al. model the cooperative interception effectiveness as a geometric coverage problem [8,9]. The evaluation models in the literature mentioned in this article are mostly aimed at missiles or seldom consider the turning radius constraints of fixed-wing UAVs. When it comes to fixed-wing UAVs, the problem is challenging because all UAVs have different maneuvering capability and are subject to turning radius constraints [10]. Therefore, it is crucial to establish a simple but accurate evaluation model that can describe the interception scenario of the multi-UAV system.

After establishing the evaluation model, the task assignment algorithm is needed to obtain the optimal task scheme. Many scholars have proposed various methods to solve the task assignment problem. The multi-UAV task assignment problem is a non-deterministic polynomial-time hard (NP-hard) problem to find the global optimal solution [11]. The task assignment algorithm can be classified into centralized and distributed algorithms [12]. The centralized algorithm usually has more information available than the distributed algorithm so that the multi-UAV system can find the global optimal solution more efficiently [13]. In interception scenarios, the UAVs can receive all the task information detected by the radar system at the base, so the centralized algorithm has certain advantages in the initial task assignment stage. The centralized task assignment methods include optimization and heuristic algorithms [14,15]. Heuristic algorithms such as ant colony algorithms [16], particle swarm algorithms [17], and genetic algorithms [18] rely on iterations to obtain optimal solutions. However, the efficiency of the algorithms is severely affected by the initial parameters, which are difficult to determine. Classical optimization methods include mixed-integer programming, which can clearly describe the task assignment problem [19]. In addition, graph theory-based approaches such as the network flow model use graph theory methods to formalize the characteristics of tasks and UAVs and to establish the matching relationship between tasks and UAVs to generate an effective task assignment scheme [20]. However, it is generally limited to small-scale models. With the increase in the task assignment model scale, the optimization methods face the risk of exponential computational burden [21]. It is a challenge to give solutions to large-scale task assignment problems in a short time. A significant effort in the research community is the hierarchical task assignment scheme. The idea is to decompose the complex task assignment model into several small-scale submodels. Many scholars have verified the efficiency and scalability of this scheme [22,23,24].

For the task assignment problem in large-scale group-to-group interception scenarios, this paper proposes a hierarchical task assignment scheme to handle the multi-UAV task assignment problem. First, this paper establishes an evaluation model to accurately describe the group-to-group interception scenario for multi-UAV systems. The evaluation model fully considers the dynamic constraints of fixed-wing UAVs and reasonably describes the cooperative interception situation. Moreover, based on a hierarchical task assignment framework, the feasible task assignment scheme will be solved under the optimality and rapidity trade-offs. Compared with the existing works, the main contributions are summarized below.

• A simple but accurate evaluation model is designed to describe complex group-to-group cooperative interception scenarios. Based on the Apollonius circle and the fixed-wing UAV dynamics model, the evaluation model can accurately describe the cooperative interception effectiveness of multiple UAVs and guide the solution of the task assignment problem.
• Under the hierarchical task assignment framework, this paper designs a heuristic model decomposition method for the interception scenarios. In the model decomposition phase, large-scale UAVs and targets are effectively divided based on distribution characteristics and interception advantage. In the task assignment phase, the network flow model (NFO) suitable for multi-UAV systems is established to determine the feasible solutions for each submodel. The simulation results show that the proposed algorithm can give the solution in milliseconds and reduce the runtime even more as the model scale increases.

This article is organized as follows. The scenario description and the hierarchical framework are given in Section 2. Section 3 presents the model decomposition method. Section 4 describes the evaluation model and the network flow algorithm. Section 5 provides the details of the simulation experiment. Section 6 summarizes this paper.

2. Problem Formulation

The typical group-to-group interception scenario in this paper is shown in Figure 1. In this scenario, multiple UAVs attempt to intercept all target clusters, and targets may adopt maneuvering strategies to evade interception after detecting multiple UAVs within the detection range $L_0$. It is assumed that both UAVs and targets are fixed-wing UAV platforms, with more UAVs than targets ($N_U\ge N_T$). Initially, targets can be detected by a radar system. The central control station performs target and UAV grouping based on relevant information to assess the offensive and defensive situations. Then, each UAV is assigned a target suitable for interception, and excess UAVs are assigned to targets with a higher threat level for many-to-one interception to ensure higher interception effectiveness. According to the task assignment scheme, multiple UAVs will intercept multiple targets at optimal interception points.

Therefore, a hierarchical task assignment framework suitable for group-to-group interception scenarios is proposed as shown in Figure 2. First, according to the distribution of targets, feature similarity clustering is applied to decompose the targets into several subclusters. Based on the clustering results, the spatial location and requirements of each task subcluster are determined. Then, the interception advantage-based assignment method is applied to form the UAV teams for these clustered targets. After that, the large-scale task problem can be decomposed into several small-scale submodels to reduce the computational burden. Based on the decomposition results, an Apollonius circle-based evaluation function is proposed to describe the interception effectiveness of each UAV reasonably. In each submodel, the UAV broadcasts its interception effectiveness information to the central UAV. The central UAV assigns specific tasks to the UAVs within the team based on network flow optimization and plans optimal interception points to maximize the probability of successful cooperative interception. After all UAVs are assigned, the path planning algorithm based on the cooperative Dubins curve generates a path to the interception point for the UAV.

3. Model Decomposition

This paper models the task assignment problem as a network flow model $G=(V,E)$ with the min-cost max-flow. In the directed graph G, the number of edges in graph G is denoted by $m=\left|E\right|$, while the number of vertices is $n=\left|V\right|$. Assume that the maximum cost of each edge is C, that is, $C=ma{x}_{(i,j)\in E}c(i,j)$. The capacity of each edge is represented by $U=ma{x}_{(i,j)\in E}u(i,j)$. Due to the limited capacity of the network, the flow value of the graph G will not exceed the maximum flow $MaxFlow=mU$. Accordingly, the maximum cost of the network is $C·MaxFlow$. The cost of the network decreases by at least one in each iteration and reaches its minimum after several iterations. Therefore, the maximum number of iterations of the algorithm is

$$I\le O\left(mCU\right).$$

(1)

Then the Bellman–Ford (BF) algorithm is used to find a path from the source point to the sink point. The BF algorithm takes $O\left(mn\right)$ times to find a feasible flow. Therefore, the maximum computational complexity B of the centralized network flow algorithm to produce a feasible task assignment solution is

$$B=O\left(m^{2}nCU\right).$$

(2)

In this paper, the maximum cost C and capacity U of the network are limited to 1, so the computational complexity in (2) can be simplified as $O\left(m^{2}n\right)$. It can be seen that the computational complexity is closely related to the number of vertices and edges in the graph. At the same time, the number of vertices and edges is directly related to the number of UAVs and targets. In large-scale interception scenarios, solving a feasible task assignment scheme for a large number of UAVs and targets will result in a large amount of computation time. Therefore, it is necessary to design an effective method to reduce the scale of the model.

Assuming that the large-scale task assignment model can be decomposed into $N_S$ submodels, the UAV set and task set in the $q^{th}(q=1,2,...,N_S)$ submodel are separately $U_q=\left\{U_1,...,U_{N_{Uq}}\right\}$ and $T_q=\left\{T_1,...,T_{N_{Tq}}\right\}$. $U_{N_{Uq}}$ and $T_{N_{Tq}}$ represent the number of UAVs and tasks in the $q^{th}$ submodel, respectively. Each submodel is solved by the centralized network flow model. Similar to (2), the maximum computational complexity of the submodel can be expressed as

$$B_q=O\left(m_q^2{n}_q\right).$$

(3)

Then, the maximum computational complexity of the hierarchical task assignment model is

$$\begin{array}{cc}\hfill & B^{\prime }=O(\sum _{q=1}^{N_S}{B}_q)=O(\sum _{q=1}^{N_S}{m}_q^2{n}_q)\le O(\sum _{q=1}^{N_S}{m}_q^{2}n)\hfill \\ \hfill & \le O\left({\left(\sum _{q=1}^{N_S}{m}_q\right)}^{2}n\right)=O\left(m^{2}n\right)=B.\hfill \end{array}$$

(4)

Obviously, the hierarchical task assignment model has less computational complexity than the original task assignment model through effective model decomposition. The required computation time is also reduced. However, the hierarchical scheme may lead to a suboptimal solution of the task assignment problem. Therefore, the core of the problem is to find a model decomposition method suitable for interception scenarios.

3.1. Target Grouping Based on Feature Similarity Clustering

For targets in group-to-group interception scenarios, the individual behavior within the group is consistent, and the individuals are close together to form a relatively dense formation. Therefore, the targets with high similarity can be grouped based on the geometric and motion characteristics. In addition, we hope to limit the number of targets in each group, so the traditional feature similarity clustering algorithm [25] is improved in this section.

According to the sensor detection and fusion results, the state set of targets is assumed to be $S\left(t\right)=\left\{s_1\left(t\right),s_2\left(t\right),...,s_n\left(t\right)\right\}$. Among them, $s_i$ is the state of the $i^{th}$ target. The time of data collection, target position, speed, and heading angle are all taken into account. The similarity matrices $M_d$,$M_v$,$M_{\theta }$ are calculated according to the above information. The similarity matrices’ calculations are carried out in (5) and (6).

(1) The similarity of the target position: According to the Euclidean distance between two targets $d_{mn}$, the target position similarity is defined as

$$M_d\left(d_{mn}\right)=\left\{\begin{array}{cc}1,\hfill & d_{mn}\le \alpha \hfill \\ e^{-k(d_{mn}-\alpha )},\hfill & d_{mn}>\alpha ,\hfill \end{array}\right.$$

(5)

where $\alpha$ is the threshold, representing the allowed Euclidean distance between two targets.

(2) The similarity of target speed and heading angle: The similarity of the target speed is defined as

$$M_v\left(v_{mn}\right)=\frac{{\alpha }_2-v_{mn}}{{\alpha }_2-{\alpha }_1},{\alpha }_1\le v_{mn}\le {\alpha }_2,$$

(6)

Among them, $v_{mn}$ is the absolute value of the velocity difference. We define the parameters ${\alpha }_1$ and ${\alpha }_2$ to measure the influence of the velocity difference. ${\alpha }_2-{\alpha }_1$ represents the maximum allowed velocity difference and (6) is normalized based on it. Considering the cruising speed of the fixed-wing UAV, the values of ${\alpha }_1$ and ${\alpha }_2$ are taken as $5\mathrm{m}/\mathrm{s}$ and $10\mathrm{m}/\mathrm{s}$, respectively. The speed similarity of the two targets is 1 when the speed difference is within $5\mathrm{m}/\mathrm{s}$, and 0 when the speed difference is greater than $10\mathrm{m}/\mathrm{s}$.

The heading angle similarity $M_{\theta }\left({\theta }_{mn}\right)$ calculation method is the same as that of the speed similarity, where the parameter values are 5 and 10.

An undirected graph was constructed to form the target group based on the similarity between the target nodes. Target nodes with high similarity will form connected branches, but there may be isolated target points or subclusters. As shown in Figure 3, target 1 has low similarity with other targets and belongs to isolated nodes. The ideal clustering result is that the number of targets in each subcluster is relatively balanced. Too small or too large subclusters will weaken the clustering effect and further affect the performance of the task assignment algorithm.

Therefore, the upper and lower bounds for the number of targets in the subclusters are defined as $[b_l,b_u]$. For a subcluster whose number of targets is less than the lower bound, iteratively find the target j in other subclusters with the highest similarity with the subcluster, and classify the isolated targets into the cluster where the target j is located. After several iterations, the isolated targets with low similarity are classified into clusters, completing the graph merging process.

At the same time, the algorithm performs graph partitioning for clusters whose number of targets exceeds the upper bounds. Considering interception characteristics, the number of UAVs in the divided subclusters should be balanced as much as possible, and neighboring UAVs should be divided into the same subcluster. Therefore, the linear deterministic greedy (LDG) algorithm is adopted to implement graph partitioning [26]. The algorithm uses a greedy algorithm to ensure a balanced load of nodes in each subgraph. Therefore, the LDG algorithm is suitable for graph partitioning in interception scenarios.

In summary, the feature similarity clustering method with upper and lower bounds is given in Algorithm 1. The parameter $\lambda$ measures the degree of similarity and is set to 0.7 in this paper.

Algorithm 1 Feature Similarity Clustering with upper and lower bounds

Input: $M_d$,$M_v$,$M_{\theta }$,$\lambda$ Output: target clusters: $T_1,T_2\mathrm{\dots }$ 1: $M=M_d\cap M_v\cap M_{\theta }$ 2: for $m_{ij}$ in M do 3:    $m_{ij}=sgn(m_{ij}-\lambda )$ 4:    $i,j=find(m_{ij}=1)$ 5:    $ind=argmin(i,j)$ 6:    $T_{ind}=T_{ind}\cap \left\{j\right\}$ 7: end for 8: for $T_1,T_2,...$ in target clusters do 9:    if size $\left(T_i\right)\le b_l$ then 10:      $j_m=argma{x}_j\left(M_{ij}\right),\forall j$ 11:      if size $\left(T_j\right)\ge b_l$ then 12:         $T_{j_m}=T_{j_m}\cap T_i$ 13:      end if 14:    end if 15:    if size $\left(T_i\right)\ge b_u$ then 16:      $\mathbf{LDG}$(${\mathbf{T}}_{\mathbf{i}}$,${\mathbf{c}}_{\mathbf{num}}$) 17:    end if 18: end for

3.2. UAV Assignment Based on Interception Advantage

UAVs have limited execution capabilities, and the requirements of targets in different subclusters are also different. In order to maximize the execution capability of the UAV and meet the target requirements, an interception advantage-based assignment algorithm is proposed to assign UAV teams to these subclusters.

Assuming that targets have been clustered into $N_S$ target sets $\left\{T_1,T_2,...,T_{N_S}\right\}$, the clustering centers are extracted as representatives of the entire subcluster. The quantity requirements for targets in these subclusters are defined in (7).

$$R_n=\left\{R_1^n,R_2^n,...,R_{N_S}^n\right\},$$

(7)

Among them, $R_j^n$ represents the number of UAVs required by the $j^{th}$ subcluster. The number of UAVs required $R_j^n$ is solved using a proportional approach, where the weights ${\beta }_j$ can be adjusted according to the priority of the target. In the interception scenario, a single UAV can intercept only one target. Therefore, the number of UAVs assigned should be greater than the number of targets. Based on this, the weights are constrained in (8). This paper simply conditions the number of targets in a subcluster to set the assignment weights.

$$\begin{array}{cc}\hfill & R_j^n={\beta }_j·N_U\hfill \\ \hfill & {\beta }_j\ge \frac{N_T^j}{{\sum }_{i=1}^{N_S}{N}_T^i},\forall j=1,2,...,N_S\hfill \\ \hfill & \sum _{i=1}^{N_S}{\beta }_i=1.\hfill \end{array}$$

(8)

Based on the kinematic parameters detected by the radar system, the interception advantage is calculated to guide the assignment of UAVs.

The kinematic characteristics of the UAVs and targets are shown in Figure 4.

The relative velocity advantage is defined in (9).

$$D_{vij}(v_i,v_{Tj})=\left\{\begin{array}{cc}1,\hfill & v_i>v_{Tj}\hfill \\ \frac{v_i}{v_{Tj}},\hfill & 0.5v_{Tj}\le v_i<v_{Tj}\hfill \\ 0.1,\hfill & v_i<0.5v_{Tj}.\hfill \end{array}\right.$$

(9)

The relative distance between the UAV and the target will also affect the interception efficiency due to the cost of the flight. Therefore, the distance between the UAV and the target is considered as a factor in the interception advantage.

$$D_{dij}\left(d_{rij}\right)=\frac{2}{1+e^{d_{rij}-d_0}},$$

(10)

where $d_0$ is the threshold of the relative distance. A smaller weight will be given when the distance between the UAV and the target is greater than $d_0$.

In this paper, the pursuit evasion interception mode is employed, and UAVs have lower speed than targets. When the speeds of the UAV and the target are on the same side as the line of sight, it is considered as the optimal interception angle. The advantage of the heading angle is defined as follows:

$$D_{\theta ij}({\theta }_i,{\theta }_{Tj})=\left\{\begin{array}{cc}1-\frac{|{\theta }_i-{\theta }_{Tj}|}{\pi },\hfill & |{\theta }_i|<\frac{\pi }{2}\left|{\theta }_{Tj}\right|<\frac{\pi }{2}\hfill \\ 0.001,\hfill & others.\hfill \end{array}\right.$$

(11)

If the heading angle advantage is slight, the interception advantage will be small despite the large speed and distance advantage. Therefore, the effect of heading angle on interception advantage is described by multiplication. Thus, the interception advantage is defined as

$$D_{ij}=\left[{\lambda }_1{D}_{vij}(v_i,v_{Tj})+{\lambda }_2{D}_{dij}\left(d_{rij}\right)\right]·D_{\theta ij}({\theta }_i,{\theta }_{Tj}),$$

(12)

Among them, ${\lambda }_1,{\lambda }_2$ are the weights and ${\lambda }_1+{\lambda }_2=1$.

Based on the interception advantage, the auction-based algorithm [22,27] is used to assign UAVs to the cluster. The interception advantage-based assignment of UAVs is given in Algorithm 2.

Algorithm 2 Assignment of UAVs

Input: $R_n$,D Output: $N_S$ UAV teams: $U_1,U_2,...,U_{N_S}$ 1: $U_1=\varnothing ,...,U_{N_S}=\varnothing$ 2: while  $D\ne \varnothing$do 3:    $j_T=argmax{R}_n$ 4:    $i_U=argmax{D}_{i{j}_T}$ 5:    $R_{j_T}^n=R_{j_T}^n-1$ 6:    $D_{i_U}=0$ 7:    $U_{j_T}=U_{j_T}\cap \left\{i_U\right\}$ 8: end while

The large-scale task assignment model can be effectively decomposed into several small-scale and non-overlapping task assignment submodels using the proposed model decomposition method. Then, the network flow model is applied to solve these small-scale task assignment problems.

4. Evaluation Model and Task Assignment Method

4.1. Evaluation Model Based on the Apollonius Circle

In order to describe the spatial location relationship between the UAVs and targets, the local coordinate system is established with zero-point as the origin. The coordinates of UAV i and target j are represented by $(x_u,y_u)$ and $(x_t,y_t)$, respectively. $v_u$ and $v_t$ are the maximum speeds of UAVs and targets, respectively. The velocity rate of the UAV and the target is defined as $\lambda =v_u/v_t<1$. Assuming that both UAVs and the targets start moving at their maximum speeds, they will eventually meet at a point $M=(x_m,y_m)$ in a finite time. The meeting point M satisfies (13).

$$\frac{\sqrt{{(x_u-x_m)}^2+{(y_u-y_m)}^2}}{\sqrt{{(x_t-x_m)}^2+{(y_t-y_m)}^2}}=\frac{v_u·T}{v_t·T}=\lambda .$$

(13)

Then, (13) can be transformed into

$$\begin{array}{cc}\hfill & {(x_m-\frac{x_u-{\lambda }^2{x}_t}{1-{\lambda }^2})}^2+{(y_m-\frac{y_u-{\lambda }^2{y}_t}{1-{\lambda }^2})}^2=\hfill \\ \hfill & \frac{{\lambda }^2({(x_u-x_t)}^2+{(y_u-y_t)}^2)}{{(1-{\lambda }^2)}^2}.\hfill \end{array}$$

(14)

It can be seen that $M=(x_m,y_m)$ is on a circle shown in Figure 5a. The center of this circle can be expressed as (15), with the radius in (16). The circle is known as the Apollonius circle [28].

$$O=(\frac{x_u-{\lambda }^2{x}_t}{1-{\lambda }^2},\frac{y_u-{\lambda }^2{y}_t}{1-{\lambda }^2}).$$

(15)

$$r=\frac{\lambda \sqrt{{(x_u-x_t)}^2+{(y_u-y_t)}^2}}{1-{\lambda }^2}.$$

(16)

In Figure 5a, $l_1$ and $l_2$ are the tangent lines of the Apollonius circle from the target T. If the flight path of the target is between the tangent lines $l_1$ and $l_2$, the UAV can move along the corresponding direction to capture the target. The capture point is on the Apollonius circle. Therefore, we define the angle $\theta$ as the interceptable angle of the UAV, and the arc between the lines $l_1$ and $l_2$ can be defined as the interceptable area.

However, it is impractical for fixed-wing UAVs to reach the interceptable area in Figure 5b due to dynamic constraints. Therefore, the Apollonius circle suitable for fixed-wing UAVs is proposed, and the interceptable area should be redefined. As is shown in Figure 5b, two lines $T{M}_1$ and $T{M}_2$ intersect the circle at $M_1$ and $M_2$, and the interceptable angle of the UAV can be represented by ${\theta }^{\prime }=[{\theta }_1^{\prime },{\theta }_2^{\prime }]$. Compared with Figure 5a, the orange part indicates the reduced interception area for fixed-wing UAVs. According to the sine rule, the interceptable angle for fixed-wing UAVs can be expressed as

$$\begin{array}{c}\hfill \frac{M_{1}T}{sin{\theta }_1^{\prime }}=\frac{M_{1}U}{sin{\theta }_1}\\ \hfill \frac{M_{2}T}{sin{\theta }_2^{\prime }}=\frac{M_{2}U}{sin{\theta }_2}.\end{array}$$

(17)

Then, the interceptable area of the fixed-wing UAV can be defined as

$$\left\{\begin{array}{c}\theta ={\theta }_1+{\theta }_2\hfill \\ {\theta }_1=arcsin\left(\lambda sin{\theta }_1^{\prime }\right)\hfill \\ {\theta }_2=arcsin\left(\lambda sin{\theta }_2^{\prime }\right).\hfill \end{array}\right.$$

(18)

Accordingly, the escapable direction of the target is defined as the maneuverable area ${\theta }_T$. This maneuverable area ${\theta }_T$ can be calculated based on the angular velocity ${\omega }_T$ and the detection range $L_0$ provided by the radar system.

Therefore, the ratio of the interceptable area of the UAV to the maneuverable area of the target can be defined as the the interception probability in (19). In other words, ${\theta }_{ij}/{\theta }_{Tj}$ percent of the escapable directions of the target j are occupied by UAV i.

$$p_{ij}=\frac{{\theta }_{ij}}{{\theta }_{Tj}}.$$

(19)

If the interceptable area of the UAV can cover the maneuverable area of the target, the above interception probability is 1. Therefore, the goal of task assignment is to enable the UAV to cover the maneuverable area of the target as much as possible, i.e., to maximize the interception probability.

In addition, considering that the threat level of the target is different in the practical group-to-group interception scenario, UAVs need to be assigned according to the interception priority of the target. To enable the UAV with better interception performance to intercept the higher-threat target first, the target threat is evaluated to guide the task assignment phase. The position and maneuverability of the target are taken into account to evaluate the threat level.

(1) Target distance: The target distance is defined as the Euclidean distance between the target and the vital area.

As is shown in Figure 6, the threat level of the target increases as the target distance decreases. Based on the effective distance of our defense system, the minimum allowable and maximum defense distances are defined as the thresholds for evaluating the threat level of the target distance. Thus, the evaluation function of target distance is

$$W_1\left(d\right)=\left\{\begin{array}{cc}1,\hfill & d\le d_{min}\hfill \\ \frac{d_{max}-d}{d_{max}-d_{min}},\hfill & d_{min}<d\le d_{max}\hfill \\ 0,\hfill & d>d_{max}.\hfill \end{array}\right.$$

(20)

(2) The maneuverability of the target: The speed of the target is taken into account to evaluate the threat priority of the target. Since the kinetic energy is proportional to the square of the speed, the square of the speed is used as an evaluation factor. The logarithm form of the factor is defined as (21).

$$W_2\left(v_T\right)=ln(1+v_T^2).$$

(21)

The weighted sum of the above factors is used to evaluate the threat level of the target.

$$W_j={\lambda }_3{W}_1\left(d\right)+{\lambda }_4{W}_2\left(v_T\right),$$

(22)

Among them, ${\lambda }_3,{\lambda }_4$ are the weights and ${\lambda }_3+{\lambda }_4=1$.

Note that the higher the threat level, the greater the need to intercept the target. The expected intercept priority also increases accordingly. Therefore, the threat level above is converted into the expected interception priority threshold.

$$P_j^0=\left\{\begin{array}{c}0.5,W_j\le 0.5\hfill \\ W_j,W_j\ge 0.5.\hfill \end{array}\right.$$

(23)

Therefore, in large-scale interception scenarios, the specific modeling methods based on the Apollonius circle and the fixed-wing UAV dynamic model are designed to increase the validity and applicability of the evaluation model and accurately assess the situation. For the $q^{th}$ submodel, the evaluation model is proposed as follows:

$$max{J}_q=\sum _j^{N_{Tq}}\sum _i^{N_{Uq}}{P}_j^0·x_{ij}{p}_{ij},$$

(24)

subject to

$$\sum _{j=1}^{N_{Tq}}{x}_{ij}\le 1$$

(25)

$$1\le \sum _{i=1}^{N_{Uq}}{x}_{ij}\le N_{min}$$

(26)

$$\sum _{i=1}^{N_{Uq}}\sum _{j=1}^{N_{Tq}}{x}_{ij}=N_{Tq}$$

(27)

$$x_{ij}=\left\{0,1\right\},\forall i\in N_{Uq},j\in N_{Tq};$$

(28)

(25) shows that each UAV can intercept only one target. (26) represents that each target can be assigned to multiple UAVs. (27) indicates that all the targets should be assigned.

4.2. Task Assignment Based on Network Flow Model

Based on the above evaluation model, the task assignment phase aims to maximize the effectiveness of interception and satisfy the constraints of UAVs and targets. The task assignment problem for multi-UAV systems in group-to-group interception scenarios can be modeled as a network flow model with upper and lower flow bounds. Therefore, the task assignment minimum-cost maximum-flow algorithm (TAMM) in the previous work is adopted to solve the problem [29].

Since each UAV can only intercept one target, and each target must be executed by at least one UAV, the lower flow bounds of the network are defined. In addition, limited by the flight cost of UAVs, it is assumed that each target requires at most two UAVs to intercept, thus limiting the upper flow bounds of the network. The diagram of the network flow model is shown in Figure 7. UAVs and tasks are considered as vertices to form a two-layer network structure. To ensure the balance of the network flow, a virtual source point $SS$ and a virtual sink point $TT$ are introduced into the network. Among them, the tuples $〈B,C〉$ represent the cost and the capacity of the network. In the interception scenarios, the capacity function is represented by the number of targets that the UAV can intercept. The cost function is directly related to the interception effectiveness of the UAV. The network flow models are described according to the relationship between the number of tasks and UAVs.

(1) $N_U\ge 2N_T$: UAVs can fully satisfy the need for interception, which allows UAVs to have a surplus. Targets are able to satisfy the conditions of interception by two UAVs. Therefore, only the flow bounds of the edges from the target vertices to the sink vertices $E〈V_{Tj},V_t〉$ are limited to $[1,2]$.

(2) $N_T\le N_U<2N_T$: All the UAVs are needed to participate in the intercept mission. Therefore, certain constraints are imposed on the capacity of the target vertices and the UAV vertices. The flow bounds of the edges from the source point to the UAV vertices $E〈V_s,V_{Ui}〉$ are limited to $[1,1]$, while the flow bounds of the edges from the target vertices $E〈V_{Tj},V_t〉$ to the sink vertices are limited to $[1,2]$.

The assignment scheme can be given by solving the minimum-cost maximum-flow problem. The Bellman–Ford algorithm is introduced to find a feasible solution.

4.3. Design of Interception Points for UAVs

When the target detects the UAV, it may take maneuverable strategies to escape. The warring parties will evade or pursue within the detection distance $L_0$. Therefore, the interception points are set on the circle with the target to be intercepted as the center and the detection range $L_0$ as the radius. The superposition of the interceptable area of the UAVs should cover the maneuver able area as much as possible. In addition, the overlap of the interceptable areas should be minimal to improve interception efficiency.

To facilitate the calculation, the polar coordinate system is established with the current position of the target as the origin and the current heading angle as the positive direction. Under the polar coordinate system, the interception scenario is shown in Figure 8.

Thus, the interception points in the polar coordinate system are

$$\left\{\begin{array}{c}{\rho }_i=L_0\hfill \\ {\theta }_i=\sum _{j=1}^{j=i}{\theta }_j+{\theta }_2^i.\hfill \end{array}\right.$$

(29)

Convert the above coordinate to the rectangular coordinate system as $(x_i^{\prime },y_i^{\prime })=({\rho }_{i}cos{\theta }_i,{\rho }_{i}sin{\theta }_i)$. The rotation angle ${\theta }_t$ of the coordinate system is determined as (30) according to the target heading angle ${\theta }_T$ and the maximum maneuvering angle ${\theta }_{\omega }$.

$${\theta }_t={\theta }_{\omega }-{\theta }_T.$$

(30)

Then, the coordinates of the UAV in the world coordinate system are

$$(x_i,y_i)=\left[\begin{array}{cc}cos{\theta }_t& sin{\theta }_t\\ -sin{\theta }_t& cos{\theta }_t\end{array}\right](x_i^{\prime },y_i^{\prime }).$$

(31)

For the path planning of interception scenarios, the planned path should satisfy the dynamic constraints of the fixed-wing UAV. In addition, the time of the UAV arriving at the interception point should be reduced to improve the execution efficiency of the interception task. The multi-UAV cooperative path planning method based on Dubins curves is a relatively simple and common method that can meet real-time requirements. Therefore, this paper uses the Dubins curve as the flight path of the fixed-wing UAVs. The longest path in the UAV team is selected as the reference. Then, the corresponding radius is solved according to the longest path length. For more details on Dubins curve, please see [30]. Moreover, the existing position/attitude controller for UAV maneuvering flight can accurately track the reference path [31,32,33].

5. Results and Analysis

In this paper, model decomposition is the core of the hierarchical task assignment scheme. A centralized network flow algorithm is raised to give a solution to the task assignment. In order to prove the feasibility and superiority of the proposed hierarchical task assignment scheme (HTA-NFO), simulation experiments are conducted in various large-scale group-to-group interception scenarios.

5.1. Feasibility of the Hierarchical Task Assignment Scheme

Assuming that $N_T=30$ targets are randomly clustered at different locations in the 0.7 km × 0.5 km mission area, $N_U=40$ UAVs should perform interception missions on all targets. The randomly distributed targets and UAVs are shown in Figure 9a. The blue star shows the position of the targets, and the orange circle shows the position of the UAVs. The speed is randomly set in the range of [20 m/s, 25 m/s] for UAVs and [25 m/s, 30 m/s] for targets. The speed remains constant throughout the interception. All methods are performed on MATLAB R2017a with Inter(R) Core (TM) i7-10510U CPU @1.80 GHz.

First, the feature similarity clustering algorithm divides the target into different clusters. The upper limit of targets in the subcluster is set to 15. Comparing the clustering results in Figure 9b with the target distribution in Figure 9a, the central control station uses feature similarity clustering to divide the targets into four clusters properly. It is worth noting that Cluster 2 and Cluster 3 have a high similarity. However, they are divided into two subclusters to meet the upper limit of the number of targets in the subclusters. The number of targets in the $N_S=4$ subclusters is separately $\left|T_1\right|=5$, $\left|T_2\right|=11$, $\left|T_3\right|=9$ and $\left|T_3\right|=5$. The targets in subclusters do not overlap. Then, $N_S=4$ UAV sets are formed for each target cluster. The UAV sets for four subclusters are

$$\begin{array}{cc}\hfill & {\mathbf{U}}_1=\left\{U_5,U_6,U_{11},U_{19},U_{21},U_{31}\right\}\hfill \\ \hfill & {\mathbf{U}}_2=\left\{U_1,U_7,U_{10},U_{15},U_{17},U_{20},U_{22},U_{25},\right.\hfill \\ \hfill & \left.U_{28},U_{29},U_{30},U_{32},U_{33},U_{37},U_{38},U_{40}\right\}\hfill \\ \hfill & {\mathbf{U}}_3=\left\{U_4,U_8,U_9,U_{12},U_{13},U_{16},\right.\hfill \\ \hfill & \left.U_{18},U_{23},U_{27},U_{34},U_{36},U_{39}\right\}\hfill \\ \hfill & {\mathbf{U}}_4=\left\{U_2,U_3,U_{14},U_{24},U_{26},U_{35}\right\}\hfill \end{array}$$

(32)

It can be seen that $U_1\cup U_2\cup U_3\cup U_4=U$ and $U_1\cap U_2\cap U_3\cap U_4=\varnothing$. The UAVs in the $N_S=4$ subclusters satisfy the no-overlap requirements. In addition, the algorithm assigns the appropriate number of UAVs according to the number of targets in the clusters. All four subclusters satisfy $N_U>N_T$. In

Table 1. The number of UAVs and targets for $N_S=4$ submodels.

Elements	Cluster 1	Cluster 2	Cluster 3	Cluster 4
Targets	5	11	9	5
UAVs	6	16	12	6

, four submodels with different scales are established. NFO is applied to generate optimal solutions for each submodel.

Figure 10 shows the results of the task assignment. The x-axis and y-axis represent the positions of the targets and the UAVs. All the UAVs are assigned to the target with the same color. Figure 10a–d show the task assignment and planning results of clusters 1, 2, 3, and 4, respectively. It can be seen that each UAV intercepts only one target, and all the targets are intercepted by the corresponding UAV. For targets with higher speed or closer positions, two UAVs will intercept them simultaneously. Furthermore, the black dotted lines show the flight path of UAVs. The blue diamond represents the position of the targets, and the red diamond represents the interception points of the UAVs. The UAVs fly along the planned Dubins path and finally reach the interception point. The two UAVs intercepting the same target rotate and wait to achieve simultaneous assembly at the interception point. The Apollonius circle at the intercept point is also shown in the figure. The orange area represents the interceptable area of the UAV, while the blue area represents the maneuverable area of the target. Note that the interceptable area of the UAV can cover the maneuverable area of the target properly.

The Apollonius circle of targets 1 and 3 in Cluster 4 is shown in Figure 11. It can also be seen that the algorithms can calculate interception points for each UAV. The blue dotted line shows the maneuverable area of the targets, while the red dotted line shows the interceptable area of the UAVs. In the case of single-UAV interception, the UAV is in the center of the maneuverable area to deal with the target, which increases the probability of successful interception, while for the case of multi-UAV interception, the interceptable areas of the two UAVs do not overlap and cover the maneuverable area as much as possible.

To further demonstrate the feasibility of the Apollonius circle-based evaluation function, the interception situation of Cluster 4 at different time steps is shown in Figure 12. The overlap of the gray area and the Apollonius circle represents the interceptable area of the UAVs. Note that the radius of the Apollonius circle decreases as the UAV approaches the target. This is due to the reduction in the remaining interception time, making it more difficult for the UAV to maneuver to intercept the target. In addition, it can be seen that when the speed of the target is faster than that of the UAV, the radius of the Apollonius circle will be smaller, and the target will evade in a more extensive angular range. This is consistent with the actual interception situation. The demonstration can be found in the Supplementary Material.

5.2. Algorithm Runtime Analysis

Comparative experiments with the centralized network flow algorithm (NFO) and Hungarian algorithm (HA) are conducted to verify the performance of the proposed scheme. The experiment was set up with different numbers of UAVs and targets distributed within a 1 km × 1 km mission area. The number of UAVs and targets satisfies the condition $N_U=2N_T$. The relevant experimental parameters are the same as those in Section 5.1. In the experiment, the proposed HTA-NFO method, the centralized NFO method, and the HA algorithm are used to solve the task assignment problem. After the model is decomposed, we record the longest running time of the sub-model. Then, the average runtime of the algorithm is calculated and recorded in

Table 2. Average runtime of three algorithms under different target distributions.

UAVs and Targets Distributions	Algorithm Runtime(s)					Solution Quality
UAVs vs. Targets	HTA-NFO	NFO		HA		HTA-NFO	NFO (HA)
		Time	Ratio	Time	Ratio		Time	Ratio
20 vs. 10	0.1206	0.0776	−	0.1063	−	16.2082	16.9729	95.49%
40 vs. 20	0.1213	0.0928	−	0.1374	11.72%	27.0064	27.8442	96.99%
60 vs. 30	0.1266	0.1317	3.84%	0.1644	22.99%	48.2495	52.1757	92.48%
80 vs. 40	0.1509	0.2403	37.20%	0.2484	39.25%	62.9198	69.3474	90.73%
100 vs. 50	0.1782	0.3626	50.85%	0.3115	42.76%	80.9454	85.1002	95.12%
120 vs. 60	0.2151	0.7345	70.71%	0.4078	47.25%	97.4907	100.0242	97.47%
140 vs. 70	0.2543	1.2147	79.06%	0.5509	53.84%	94.4199	96.9217	97.42%
160 vs. 80	0.3046	1.5251	80.03%	0.7098	55.32%	142.4397	145.8483	97.66%
180 vs. 90	0.4008	2.4752	83.81%	1.0783	62.83%	128.9567	130.4149	98.88%
200 vs. 100	0.4946	3.2658	84.86%	1.3920	64.47%	138.4482	149.4052	92.67%

. Note that the proposed algorithm decomposes the entire task assignment model into $N_S=2$ submodels to avoid the impact of different numbers of submodels on the runtime.

The HTA-NFO model proposed in this paper is heuristic in the model decomposition stage to shorten the computation time. Therefore, the purpose of this paper is not to obtain the optimal solution but to achieve a balance between optimality and rapidity. We use the total probability of interception of the target in the objective function ${\sum }_{i,j}^{N_T,N_U}{x}_{ij}{p}_{ij}$ as a measure of the quality of the solution. The solution quality tests are conducted under different model scales, and the interception probability of the targets is also recorded in Table 2.

We first quantify the interception effectiveness of the UAV on the target. The goal of task assignments is to find a feasible solution to maximize interception effectiveness. The NFO and HA algorithms are used to solve the assignment matrix that can maximize the objective function. For the NFO algorithm, the task assignment problem is modeled as a minimum-cost maximum-flow problem. For the HA algorithm, the interception effectiveness is extended into a cost matrix to find the feasible solution that maximizes the interception effectiveness. For centralized NFO and HA algorithms with no grouping, the obtained feasible solution is the optimal solution; thus, the optimums of them will be presented together.

In Table 2, the runtime of different algorithms increases as the model scale increases, and it can also be seen that the NFO and HA algorithms have a larger increase in runtime than the HTA-NFO method, which is consistent with the analysis in Section 2. When the model scale becomes larger, the centralized NFO and HA algorithms find it challenging to provide a task assignment solution quickly. For example, when $N_U=140,N_T=70$, the average computation time of the NFO algorithm is 1.2147 s. In this case, the centralized NFO does not give a feasible solution in milliseconds. The hierarchical task assignment method proposed in this paper can reduce the computation time in large-scale interception scenarios. In addition, by comparing the optimums of the HTA-NFO with the global optimal solution, it can be seen that the deviation between the proposed HTA-NFO and the optimal solution is less than $10\%$. Taking the $20VS10$ interception scenario as an example, the optimal solutions obtained by the HA algorithm (the NFO algorithm has the same solution as the HA algorithm) and proposed HTA-NFO algorithm are shown in

Table 3. Assignment scheme of different algorithms in $20VS10$ interception scenario.

Target ID		1	2	3	4	5	6	7	8	9	10
UAV ID	HTA-NFO	1, 6	11, 15	5, 17	7, 16	10, 19	1, 18	8, 20	9, 13	4, 14	2, 3
	NFO (HA)	1, 6	10, 11	5, 19	7, 15	12, 17	9, 20	8, 18	13, 16	3, 14	2, 4

.

It can be seen from the table that for each target, the assignment schemes given by different algorithms are quite similar. According to the above task assignment scheme, the total interception efficiency is calculated according to the interception efficiency quantification method proposed in the paper. The total interception efficiency of the HTA-NFO and HA (NFO) algorithm is 12.7281 and 13.3293, respectively. The ratio is $95.49\%$.

Though heuristic methods are used in the model decomposition phase, the proposed algorithm can obtain an approximate optimal solution. This is because the interception probability as an objective function is related to the heading angle. In the model decomposition stage, the modeling of heuristic formulas considers the advantage of the heading angle, resulting in the algorithm being able to obtain an approximate optimal solution. The feasible task assignment scheme will be solved under the optimality and rapidity trade-offs.

To further verify the performance of the HTA-NFO and the NFO algorithm, the runtime diagrams for the two methods are shown in Figure 13a and Figure 13b, respectively.

It can be seen that both HTA-NFO and NFO algorithms show an increase in runtime as the model scale increases. The growth rate of the algorithm runtime increases sharply as the model scale keeps growing. Comparing Figure 13a,b, the runtime growth of the HTA-NFO algorithm is smoother than that of the NFO algorithm. This is due to the decomposition of the large model, which results in a lower growth rate of the algorithm runtime, making the HTA-NFO algorithm more suitable for large-scale interception scenarios. However, for the small-scale interception scenario, the runtime of HTA-NFO is longer than that of the NFO algorithm. To further explore the reasons for this situation, we recorded the runtime of the model decomposition process for the 10 experimental groups mentioned above in Figure 14.

When the task assignment model is divided into two submodels, the runtime of the model decomposition algorithm is stable in the range of $[0.04,0.07]$ seconds, which is not significantly affected by the number of UAVs and targets within the model. For small-scale scenarios, the runtime of the model decomposition (MD) and task assignment (TA) phases is shown in

Table 4. Average runtime of model decomposition and task assignment phase in small-scale scenarios.

UAVs and Targets Distributions	Algorithm Runtime (s)
UAVs vs. Targets	MD Phase	TA Phase
20 vs. 10	0.0544	0.0662
40 vs. 20	0.0545	0.0668

. For the task assignment phase, the runtime of the HTA-NFO algorithm is less than that of the centralized NFO algorithm. However, the model decomposition algorithm requires a certain amount of time, which affects the runtime of the algorithm. Therefore, the small-scale task assignment model does not need to be decomposed. It is better to use the HTA-NFO algorithm when the model scale is more than $60VS30$, and the HTA-NFO algorithm has better performance as the model scale increases.

Since the computation time of the model decomposition algorithm is relatively stable, the runtime of the algorithm may depend on the scale of the model in the task assignment phase. Therefore, we conduct experiments to investigate further the relationship between the number of submodels and the runtime of the HTA-NFO algorithm.

Assuming that $N_T=100$ targets and $N_U=200$ UAVs randomly gather in the mission area, the relevant experimental parameters are the same as those in Section 5.1. The upper and lower bounds $[b_l,b_u]$ in Section 2 are adjusted to divide the target into $N_S=2,3,4,5,10,20,35,50,100$ subclusters, respectively. The average runtime of the HTA-NFO algorithm under different target distributions is recorded in

Table 5. Average runtime of HTA-NFO under different target distributions.

Models Scales	${\mathit{N}}_{\mathit{S}}=2$	${\mathit{N}}_{\mathit{S}}=3$	${\mathit{N}}_{\mathit{S}}=4$	${\mathit{N}}_{\mathit{S}}=5$	${\mathit{N}}_{\mathit{S}}=10$	${\mathit{N}}_{\mathit{S}}=15$	${\mathit{N}}_{\mathit{S}}=20$	${\mathit{N}}_{\mathit{S}}=35$	${\mathit{N}}_{\mathit{S}}=50$
Average runtime (s)	0.4837	0.2561	0.2026	0.1733	0.2188	0.2194	0.2195	0.2443	0.2841

.

As the number of submodels increases, the number of targets and UAVs in a submodel will continue to decrease. The model decomposition algorithm requires a certain amount of runtime. Although the number of targets in the cluster can continue to decrease, the runtime of HTA-NFO may not decrease again. Therefore, from the experimental results in Table 5, it can be seen that with the increase in the model scale, the descending rate of the runtime is continuously decreasing. As the model scale increases ($N_S$ greater than 10), it can be seen that the average runtime of the algorithm starts to increase. The average runtime of the algorithm decreases first and then increases with the increase in the model scale. In other words, the average runtime of the algorithm will reach a minimum value at a specific model scale. In order to avoid the complete failure of the model decomposition, the proposed algorithm in this paper will adjust the model scale and the number of targets in a cluster according to the experimental results. Figure 15 shows the runtime of the model decomposition phase and the task assignment phase. The total runtime of the proposed algorithm is recorded with a black line. In addition, it can be found that the network flow model has a faster running speed and a lower growth rate of runtime when dealing with models of scale smaller than $60VS30$. Correspondingly, the runtime of the clustering algorithm increases with the number of submodels. This leads to the fact that the proposed algorithm will have a minimum at a certain scale. Therefore, the above results can provide a reference for the number of model decompositions when dealing with large-scale task assignment problems.

In addition, it can be found that the network flow model has a faster running speed and a smaller growth rate of runtime when dealing with models of scale smaller than $60VS30$. Therefore, the above results can provide a reference for the number of model decompositions when dealing with large-scale task assignment problems.

In conclusion, the algorithm successfully decomposes the large-scale task assignment problem into several small-scale submodels and shows superiority in large-scale interception scenarios. Moreover, the evaluation model based on the Apollonius circle can reasonably and accurately describe the interception scenarios.

6. Conclusions

This paper proposes a hierarchical task assignment scheme to solve the multi-UAV task assignment problem in large-scale group-to-group interception scenarios. First, the model decomposition method based on feature similarity clustering is proposed to decompose the large-scale task assignment model into several complete small-scale submodels. The model decomposition process reduces the required computational load and time cost in large-scale scenarios. Then, the evaluation model is defined based on the Apollonius circle and the fixed-wing UAV dynamic model. According to the quantitative relationship between UAV and task, the network flow model is used to solve the task assignment. Finally, the optimal target interception points of UAVs are determined, and the cooperative Dubins path planning is used to realize the rendezvous of multi-UAVs. Simulation results comprehensively show that the proposed hierarchical task assignment scheme can rapidly generate effective and feasible task assignment solutions in large-scale group-to-group interception scenarios.

The purpose of this paper is to explore an effective method of task assignment that enables quick decision making without severely impacting performance. For the task assignment problem in large-scale group-to-group interception scenarios, the proposed HTA-NFO can effectively reduce the dimension of the complex problem and give a feasible solution in a short time. In addition, in practice, if the interception strategies can be modeled, the assignment scheme will be adjusted appropriately. Then the complex problem can be decomposed to reduce the searching domain, and the total time of assignment can be reduced. We hope that this work provides insight for designing reasonable assignment strategies based on the model and solving optimization problems in large-scale interception scenarios.