Threat-Oriented Collaborative Path Planning of Unmanned Reconnaissance Mission for the Target Group

Abstract

Unmanned aerial vehicle (UAV) cluster combat is a typical example of an intelligent cluster application, and it is characterized by its large scale, low cost, retrievability, and intra-cluster autonomous coordination. An unmanned reconnaissance mission for a target group (URMFTG) is a significant pattern in UAV cluster combat. This paper discusses the collaborative path planning problem of unmanned aerial vehicle formations (UAVFs) and refueling tankers in a URMFTG with threat areas and fuel constraints. The purpose of collaborative path planning is to ensure that the UAVFs (with fuel constraints) can complete the reconnaissance mission for the target group with the assistance of refueling tankers, which is one of the most important constraints in the collaborative path planning. In this paper, a collaborative path-planning model is designed to analyze the relationship between the planning path of the UAVFs and the tankers, and a threat avoidance strategy is designed considering the threat area. This paper proposes a two-stage solution algorithm. It creates a UAVFs path-planning algorithm based on the fast search genetic algorithm (FSGA) and a refueling tanker path-planning algorithm based on the improved non-dominated sorting genetic algorithm II (NSGA-II). Based on simulation experiments, the solution method proposed in this paper can provide a better path-planning scheme for a URMFTG. That is, it decreases the rate of the UAVF’s distance growth from 3.1% to 2.2% for the path planning of UAVFs and provides a better Pareto solution set for the path planning of refueling tankers.

1. Introduction

With more efficient resource sharing and cooperation, cluster combat has become one of the main features of future warfare [1]. For example, early warning airplanes (EWAs) usually use the cluster formation during aerial surveillance, and their targets are also marked as target groups [2]. Formation flying is a flying pattern in which multiple aerial vehicles form a formation to complete a specific combat mission.

Unmanned aerial vehicle cluster combat suppresses enemy targets with a numerical advantage and achieves a more robust combat capability at a lower cost [3,4]. Planning and executing missions in terms of trajectory generation are challenging problems in the operational phase of the unmanned aerial vehicles (UAVs) lifecycle [5]. In an unmanned reconnaissance mission for a target group (URMFTG), UAVs with excellent stealth performance, low cost, and easy maintenance are sent out in formation with reconnaissance radar and other equipment, replacing large EWAs to complete the reconnaissance mission [6,7]. In the URMFTG, formation flying represents the flying pattern that multiple UAVs form a formation to complete the unmanned reconnaissance mission for the specific targets in the target group. In the process of carrying out the mission, multiple UAVs are regarded as a whole, starting from the airport at the same time and returning to the airport together at the end of the mission. Multiple UAV formations work together to complete the URMFTG.

When performing URMFTG, the unmanned reconnaissance mission for the target group is one of the most important constraints in the path-planning problem studied in this paper. On the premise of completing the reconnaissance mission of the target group, the planning problem of UAVs and refueling tankers is of great significance for improving combat efficiency and reducing resource consumption.

There are two difficulties in path planning for a URMFTG. The first difficulty is fuel constraint. The low fuel-carrying capacity of a UAV limits the flying distance of the unmanned aerial vehicle formations (UAVFs), which can result in the formation being unable to complete the mission. As a result, during a mission, air tankers are needed to perform timely aerial refueling of the UAVFs [8,9,10]. Therefore, the path planning of a URMFTG is collaborative for both the tankers and the UAVFs, and the purpose of collaborative path planning is to ensure that the UAVFs can complete the reconnaissance mission for the target group under the condition of fuel constraints. The key issue of collaborative path planning is the setting of refueling locations [11,12]. The second difficulty is the threat posed by the enemy. There are many threat factors for a target group in actual combat, such as radar and strike weapons. If the UAVFs and the tanker are spotted, the enemy will take countermeasures, such as missile interception. Thus, the collaborative path planning of the tankers and the UAVFs should reasonably avoid threat areas to ensure their safety.

Researchers have favored path planning in both military and civil fields as a critical technique for ensuring flight safety and improving flight efficiency [13,14,15,16]. The collaborative path planning for a URMFTG involves finding the optimal path for the UAVFs and tankers that meets the specific performance indicators within various constraints [17,18]. Refueling locations can be set along the path of the UAVFs to minimize the route distance of the UAVFs. The refueling locations must meet the accessibility of the UAVFs, ensuring the timeliness of the refueling. The conditions above lead to a strong coupling relationship between the paths of the tankers and the UAVFs, which enhances the complexity of the problem. In addition, to avoid threat areas, the routes of the UAVFs and the tankers need to be appropriately adjusted [19,20,21].

Various studies have been conducted on the fuel constraints in UAV path planning. In some studies, to overcome a UAV’s range limitation by refueling and charging, path planning is conducted in the given situation of refueling locations. Khuller et al. [22] and Kannon et al. [23] have provided a solution for path planning in which a single fuel-constrained aircraft arrives at the destination after passing through a series of given refueling locations. Khuller et al. [22] used dynamic programming (DP) to solve this problem. Based on their work [22], Kannon et al. [23] compare the mixed-integer linear programming (MILP) and DP algorithms, proving the DP algorithm’s superiority. MILP models are widely studied among articles considering path planning in this area [24,25,26]. Coutinho et al. [27] defined the UAV routing and trajectory optimization problem (UAVRTOP) and proposed a Mixed-Integer Non-linear Programming (MINLP) formulation to solve the problem. Chodnicki et al. [28] proposed a UAV path-planning algorithm based on a model from a group of algorithms of MILP optimization, considering obstacles and gusts of Wind. Zuo et al. [29] proposed a two-stage MILP model for surveillance coverage path planning and demonstrated the efficiency and applicability of the proposed method using two scenarios. Adler et al. [30] studied path planning with limited refueling times. Several studies have imposed constraints on the margins of the path, such as finite loads and fuel costs [31,32]. Shao et al. [33] set up maintenance checkpoints and charging stations (similar to refueling stations) based on the above research. A path-planning model in which a single UAV arrives at the destination after visiting these two service points was established, making the remote navigation of the UAV safer and more reliable. Sundar et al. [34] focused on the fuel-constrained, multi-warehouse, multi-vehicle routing problem (FCMVRP). They proposed four MILP formulas and conducted experimental analysis and comparison. The alternative solution algorithms for similar problems have been presented in previous studies [35,36].

Other scholars have studied path planning without given refueling points in order to optimize the refueling locations. Wang et al. [37] analyzed the sensitivity of refueling locations. Their results revealed that a more extensive vehicle range is essential to reducing the number of refueling stations and facility location costs. Considering the spatial and temporal constraints, such as the vehicle mileage and charging time, Tu et al. [38] proposed a refueling location model to enhance the charging service for electric taxis. Maini et al. [39] studied the path planning of a fuel-constrained UAV that is refueled by a tanker on the ground. The joint path between the UAV and the tanker was determined through the constraints imposed by the road network on the refueling locations. Ramasamy et al. [40] extended the work of Maini et al. [39] by considering multiple UAVs with fuel constraints. The road network constraints on refueling locations were canceled, and K-means clustering was applied to determine the refueling points.

Most previous studies have focused on path planning in civil scenarios based on the above analysis. Only a few studied path planning with set refueling points, while others studied collaborative path planning without pre-set refueling locations, neglecting the threatening factors. Other studies considered the threatening factors while ignoring the refueling constraints. Therefore, in this study, the collaborative path planning of UAVFs and refueling tankers was conducted, and the influences of the threat areas on path planning were considered.

In this study, a collaborative path-planning model was developed to solve the problems involved in path planning for a URMFTG. A two-stage solving algorithm was designed by analyzing the relationship between the paths of the UAVFs and the tankers. In the first stage, the shortest flying distance of the UAVFs was taken as the objective. The path planning was adjusted based on the threat-avoidance strategy considering the threat area. The fast search genetic algorithm (FSGA) was applied to obtain the threat-oriented path of the UAVFs. In the second stage, based on the path obtained in the previous step, with fuel and path constraints, the shortest refueling time of the UAVFs and the shortest flight path of the tankers are taken as the objectives. The improved non-dominated sorting genetic algorithm II (NSGA-II) was used to obtain the planned route of the tanker while considering the threat area.

The innovations of this study include the following: (1) In this paper, we establish a collaborative path planning model for URMFTG and design a two-stage solution algorithm to solve the model. A threat-avoidance strategy is also intended to adjust the paths of the UAVFs and the tankers considering the threat area in the target group during the solution process. (2) In the two-stage model-solving algorithm, the FSGA is proposed in the first stage to improve the convergence rate and calculation results compared with GA. An improved NSGA-II is proposed in the second stage to solve the Pareto solution of the path planning of the tanker. The genetic operator and crowding distance calculation formula is improved, which enhances the accuracy of the calculation results.

The remainder of this paper is arranged as follows. Section 2 presents the problem analysis of a threat-oriented URMFTG. In Section 3, the collaborative path-planning model for a URMFTG is constructed. In Section 4, the solving algorithm of the model is described. In Section 5, several computational experiments are conducted, and the results are analyzed. Finally, the conclusions and directions of future studies are presented in Section 6.

2. Problem Analysis

This section provides a detailed description of the URMFTG scenario, aerial refueling process, and threat avoidance strategy.

2.1. URMFTG Scenario

Figure 1 presents a schematic diagram of the URMFTG scenario. The red team needs to scout a target group. In the target group, the number of target points (red points) is m, and the number of threat areas (purple points) is q. Multiple UAVF $d(d=1,2,\dots ,l)$ set out from different airports $a(a=1,2,\dots ,o)$ and go to the target points in the target group for reconnaissance at cruising speed $v_d$, which requires that all of the target points in the target group be scouted. Each UAVF will return to the departure airport after reconnaissance. In the navigation of the UAVFs, due to the fuel constraints, it is necessary to set up a refueling point $c(c=1,2,\dots ,l)$ on each UAVF’s path. The tanker $e(e=1,2,\dots ,p \mathrm{and} p<l)$ and UAVF meet at the refueling point (blue points) to refuel. In addition, when planning the navigation route of the UAVF and tanker, we need to consider the threat area $f(f=1,2,\dots ,q)$ in the target group and adjust the path to prevent it from crossing the threat area.

2.2. Aerial Refueling Process

The specific refueling process of the UAVF is shown in Figure 2. The first pair of drones enters the waiting position. After the first pair of drones arrives at the refueling position, they dock with the tanker to begin refueling, and the second pair of drones enters the waiting position. After refueling, the first pair of drones is separated from the tanker and enters the exit position, and the second pair of drones enters the refueling position to refuel. The subsequent refueling process of the UAV is similar to that mentioned above. After all of the UAVs in the formation have been fueled, the formation quickly returns to the cruising speed and continues to fly along the scheduled path. The tanker goes to the next refueling point or returns to the departure airport at its cruising speed. The total time consumed in the docking and detaching process between the tanker and UAV is a fixed constant. There is a limit to the number of drones that can refuel simultaneously. While the tanker refuels the front pair of UAVs in the formation, the rear pair of UAVs is still waiting for refueling, consuming more fuel during this period. Therefore, the later the UAV starts refueling, the less fuel is left in the UAV’s tank, the more fuel is required, and the longer the corresponding refueling time.

2.3. Threat Avoidance Strategy

In this paper, a threat avoidance strategy, which ensures that the aircraft can effectively avoid the threat area and reduces the distance growth caused by path adjustment, is proposed. In the threat avoidance diagram shown in Figure 3, there is only one threat area in the path. When threat areas overlap with the predetermined path between the two nodes, the aircraft adjusts its course so that the plane’s path takes the center of the threat area as the dot and the tangent of the circle with the threat range as the radius. In the threat avoidance diagram shown in Figure 3, there is only one threat area in the path.

When the threat area overlaps the predetermined path between the two nodes, the aircraft adjusts its course so that the path to the threat area is a circular tangent with the center of the threat area as the dot and the threat range as the radius. The aircraft flies along the circle followed by an arc, leaving the threat area from the tangent point to node j. This enables the aircraft to ideally avoid the threat area and minimizes the aircraft’s path adjustment cost (additional flight distance). The black dotted line in Figure 3 is the predetermined path that does not consider the threat. The red and yellow lines are the routes adjusted based on the avoidance strategy. The black dotted line in Figure 3 is the predetermined path without considering the threat area. There are two situations for the aircraft to select the cut-in point and the cut-out point: (1) the tangent point chosen is close to the predetermined path (yellow line in Figure 3); (2) the selected tangent point is far away from the predetermined direction (red line in Figure 3). Through comparison, it was found that the cost of the path adjustment is lower for the first case. Therefore, we should choose the adjustment path where the tangent point is closer to the predetermined direction. The threat avoidance strategy for when there are multiple threat areas between two nodes is shown in Figure 4.

3. Threat-Oriented Collaborative Path Planning Model for URMFTG

The collaborative path planning process developed in this study is shown in Figure 5. To shorten the residence time of the UAVFs in the target group, the path planning of the UAVFs is carried out with the shortest path of the UAVFs as the objective. A reasonable refueling point is set up on the planning path of the UAVF so that the UAVF does not have to replan the route and increase the flight distance. The refueling points are not predefined and should be calculated through our algorithm. In addition, the position of the refueling point will not only affect the navigation distance of the tanker but will also affect the refueling time of the UAVF. Based on the UAVFs planning path, the path planning of the tankers is carried out with the objective of the shortest flight distance to the tankers and the shortest refueling time for the UAVFs.

3.1. Model Assumptions

To simplify the practical problems, the main assumptions of the model are as follows:

(1)

Taking the formation as a whole, the UAVF refuels at the refueling point, scouts the target group’s mission points, and returns to the departure airport at the end of the mission. The performance parameters of the UAVs in the same formation can be regarded as being the same. During the flight, the cruising speed of the UAVF is constant.

(2)

The single-tube oil receiving speed of the refueling tanker and the docking time between the UAV and the tanker are regarded as constant.

(3)

All of the target points in the target group have no difference in reconnaissance priority, and any UAVF can be responsible for surveillance.

(4)

The effects of real factors such as the wind direction, wind speed, aircraft turning radius, and cruising altitude on the aircraft’s path distance in refueling are ignored.

(5)

All of the UAVFs refuel only once during their flight. The refueling point should be set on the path of each UAVF to ensure that the UAVF can reach the target point to complete the mission as soon as possible.

(6)

To ensure safety, the remaining fuel capacity of the aircraft should be at least 10% of the fuel tank capacity during flight.

3.2. Symbol Descriptions

For ease of description,

Table 1. Symbol descriptions.

Variables	Variable Definition	Description
m	$m\in {\mathbb{Z}}^{+}$	Number of target points
o	$o\in {\mathbb{Z}}^{+}$	Number of airports
l	$l\in {\mathbb{Z}}^{+}$	Number of drones in formation (equal to the number of refueling points)
p	$p\in {\mathbb{Z}}^{+}$	Number of tankers
q	$q\in {\mathbb{Z}}^{+}$	Number of threat areas
n	$n\in {\mathbb{Z}}^{+}$	Total number of nodes
N	$N=\{1,\dots ,i,\dots ,n\}$	Node set
$\delta (i)$	$\delta (i)=(x_i,y_i),i\in N$	Coordinates of the nodes
A	$A=\{1,\dots ,a,\dots ,o\}$	Airport set
B	$B=\{1,\dots ,b,\dots ,m\}$	Target point set
C	$C=\{1,\dots ,c,\dots ,l\}$	Refueling point set
D	$D=\{1,\dots ,d,\dots ,l\}$	UAVF set
E	$E=\{1,\dots ,e,\dots ,p\}$	Tanker set
F	$F=\{1,\dots ,f,\dots ,q\}$	Threat area set
T	$T=\left\{T_d\right|d\in D\}$	Set of refueling time for UAVF
$s(d)$	$s(d)\in {\mathbb{Z}}^{+},d\in D$	UAVF scale
$v_d$	$v_d\in {\mathbb{R}}^{+},d\in D$	Cruising speed of UAVF
$v_e$	$v_e\in {\mathbb{R}}^{+},e\in E$	Single-tube refueling speed of the tanker
$T_{pre}$	$T_{pre}\in {\mathbb{R}}^{+}$	Docking and disengagement time between UAV and tanker during refueling
$v_d^{\ast }$	$v_d^{\ast }\in {\mathbb{R}}^{+},d\in D$	UAV fuel consumption rate of UAVF
ηi-j	ηi-j ∈ {0,1}	Remaining fuel ratio of the jth pair drones in formation i when refueling begins
$T_{i-j}$	$T_{i-j}\in {\mathbb{R}}^{+}$	Refueling time of jth pair of drones in formation i
$r_{ijk}$	$r_{ijk}\in \{0,1\}(i\in D,j\in N,k\in N)$	Binary variable for determining whether the flight from node j to node k is in the planned path of UAVF i
$r_{ijk}^{\ast }$	$r_{ijk}^{\ast }\in \{0,1\}(i\in E,j\in N,k\in N)$	Binary variable for determining whether the flight from node j to node k is in the planned path of tanker i
$U_{jk}$	$U_{jk}\in {\mathbb{R}}^{+}(j\in N,k\in N)$	Flight distance from node j to node k
$V_{dac}$	$V_{dac}\in {\mathbb{R}}^{+}(a\in A,c\in C,d\in D)$	Flight distance of UAVF d from the airport a to the refueling point c along the planned path
$W_{dac}$	$W_{dac}\in {\mathbb{R}}^{+}(a\in A,c\in C,d\in D)$	Flight distance of UAVF d returning to the airport a from the refueling point c along the planned path

shows the relevant variables involved in the model.

3.3. Objective Functions

The decision variables of the objective function are as follows. (1) $r_{ijk}$: a binary variable to determine whether the flight from node j to node k is in the planned path of UAVF i, where the nodes include the airports and target points. (2) $r_{ijk}^{\ast }$: a binary variable to determine whether the flight from node j to node k is in the planned path of tanker i, where the nodes include airports and target points. (3) $C=\{1,\dots ,c,\dots ,l\}$: refueling point set. In the collaborative path-planning process (shown in Figure 5), we try to shorten the flight distance of the UAVFs so that the UAVFs can complete the reconnaissance mission for the target group as soon as possible (assuming the formation speed is constant). Therefore, we first carry on the path planning of the UAVFs, and we set the refueling points on the path of the UAVFs to avoid increasing the flight distance and replanning the route. Using the decision variable $r_{ijk}$ and the threat avoidance strategy, we can obtain the path planning for the UAVFs. We can obtain the path planning of the refueling tankers using the decision variable $r_{ijk}^{\ast }$, $C=\{1,\dots ,c,\dots ,l\}$ and the threat avoidance strategy. We can calculate the refueling time of the UAVFs and flight distance of the tankers using the UAVFs planning path and the set of refueling points.

In the path planning of the UAVFs, the objective is to minimize the total flight distance of the UAVFs.

$$\min F_1=\sum _{i\in D}\sum _{j\in (A\cup B)}\sum _{k\in (A\cup B)}\left[r_{ijk}\times U_{jk}\right]$$

(1)

The objective function ${\displaystyle \sum _{i\in D}}{\displaystyle \sum _{j\in (A\cup B)}}{\displaystyle \sum _{k\in (A\cup B)}}\left[r_{ijk}\times U_{jk}\right]$ represents the total flight distance of all of the UAVFs, which is based on the graph model [41,42]. $U_{jk}$ is the sailing distance from node j to node k. If threat areas need to be avoided, $U_{jk}$ is the flight distance between the two nodes adjusted using the threat strategy; otherwise, it is the shortest Euclidean distance between the two nodes. The constraints are shown in Formulas (2)–(7).

$$\sum _{i\in D}\sum _{j\in B}{r}_{ijk}=1,\forall k\in B$$

(2)

$$\sum _{i\in D}\sum _{k\in B}{r}_{ijk}=1,\forall j\in B$$

(3)

Formulas (2) and (3) are designed to ensure that all of the targets are reconnoitered only once by a UAVF.

$$\sum _{j\in (A\cup B)}\sum _{k\in (A\cup B)}{r}_{ijk}\ge \beta ,\forall i\in D$$

(4)

$$\sum _{j\in A}\sum _{k\in A}{r}_{ijk}=0,\forall i\in D$$

(5)

Formulas (4) and (5) ensure that each UAVF carries out a reconnaissance mission and detects a certain number of target points. $\beta$ represents the minimum number of target points for each UAVF in the reconnaissance.

$$\sum _{j\in Q}\sum _{k\in Q}{r}_{ijk}\le \left|Q\right|-1,\forall Q⊈B,i\in D,2\le \left|Q\right|\le \left|B\right|-1$$

(6)

$$r_{ijk}\in \{0,1\}$$

(7)

Formula (6) ensures that there are no sub-tours in each UAVF’s path. Q represents the nonvoid proper subset of B, || represents the number of elements in a certain set. If there are sub-tours in the path of the UAVF i, ${\displaystyle \sum _{j\in Q}{\displaystyle \sum _{k\in Q}{r}_{ijk}\ge \left|Q\right|},\exists Q⊈B,2\le \left|Q\right|\le \left|B\right|-1}$. We only need to consider nonvoid subsets with more than two elements, because at least two elements are needed to form a sub-tour. Formula (7) represents the range of the binary-type decision variables used.

In the path planning of the refueling tankers, this is a multi-objective optimization problem. The objective is to minimize the entire flight distance of the refueling tankers and the total refueling time of the UAVFs.

$$\min F_2=\sum _{i\in D}\sum _{j\in (A\cup B)}\sum _{k\in (A\cup B)}\left[r_{ijk}^{\ast }\times U_{jk}\right]$$

(8)

$$\min F_3=\sum _{i\in C}{T}_i$$

(9)

${\displaystyle \sum _{i\in D}{\displaystyle \sum _{j\in (A\cup B)}{\displaystyle \sum _{k\in (A\cup B)}\left[r_{ijk}^{\ast }\times U_{jk}\right]}}}$ represents the total flight distance of all of the refueling tankers. ${\displaystyle \sum _{i\in C}{T}_i}$ represents the refueling time of all of the UAVFs. T_i is the refueling time of UAVF i. The main constraint is that the refueling points should be set on the path of the UAVFs. In Formula (1), we use indices of route points from sets A and B. Therefore, the path of UAVF can be defined as a vector of point numbers from these sets, assuming that the starting and ending points belong to A. The other constraints are shown in Formulas (10)–(16).

$$\sum _{i\in E}\sum _{j\in C}{r}_{ijk}^{\ast }=1,\forall k\in C$$

(10)

$$\sum _{i\in E}\sum _{k\in C}{r}_{ijk}^{\ast }=1,\forall j\in C$$

(11)

Formulas (10) and (11) ensure that all of the refueling points are accessed only once by a tanker.

$$\sum _{j\in (A\cup C)}\sum _{k\in (A\cup C)}{r}_{ijk}^{\ast }\ge 1,\forall i\in E$$

(12)

$$\sum _{j\in A}\sum _{k\in A}{r}_{ijk}^{\ast }=0,\forall i\in E$$

(13)

Formulas (12) and (13) ensure that each tanker accesses at least one refueling point.

$$\sum _{j\in Q}\sum _{k\in Q}{r}_{ijk}^{\ast }\le \left|Q\right|-1,\forall Q⊈C,i\in E,|Q|\ge 2$$

(14)

$$0.1\le \eta (i)\le 0.5,\forall i\in C$$

(15)

$$r_{ijk}^{\ast }\in \{0,1\}$$

(16)

Formula (14) ensures that each tanker’s path does not have multiple divided sub-route cycles. Formula (15) ensures that the remaining fuel ratio for each UAVF to the refueling point is between 0.1 and 0.5. Formula (16) represents the range of the binary-type decision variables used.

Next, the specific calculation process of the refueling time of the UAVF, $T_i$ in the objective function, is presented.

The remaining fuel ratio $\eta (i)$ when UAVF i arrives at their refueling point can be calculated as follows:

$$\eta (i)=1-\frac{V_{iac}*v_d^{\ast }}{Y_d*v_d}$$

(17)

In Formula (17), $V_{iac}$ is the flight distance of UAVF i from the airport a to refueling point c along the planned path. $Y_d$ is the fuel tank capacity of the UAV. $v_d$ is the cruising speed of the UAVF, and $v_d^{\ast }$ is the fuel consumption rate of the UAVF.

Formula (18) is used to calculate the refueling times of UAVF i, which is guaranteed by a refueling tanker:

$$Nr(i)=\left[\frac{s(i)}{num}\right]$$

(18)

In Formula (18), [] represents an upward rounding calculation, $s(i)$ is the scale of UAVF i, and num is the number of drones that a refueling tanker can guarantee at once.

The remaining fuel ratio ${\eta }_{i-1}$ and refueling time $T_{i-1}$ of the first pair of drones in the UAVF i can be calculated as follows:

$${\eta }_{i-1}=\eta (i)$$

(19)

$$T_{i-1}=T_{pre}+\frac{Y_d(1-{\eta }_{i-1})}{v_e-v_d^{\ast }}$$

(20)

In Formula (20), $T_{pre}$ is the docking and disengagement time between the UAV and tanker during refueling, and $v_e$ is the single-tube refueling speed of the tanker.

While waiting for refueling, the other drones in the formation are still consuming fuel at speed. Therefore, the later the drones in the formation refuel, the longer their refueling time. The remaining fuel ratio and refueling time of the second pair of drones in the UAVF can be calculated as follows:

$${\eta }_{i-2}={\eta }_{i-1}-\frac{v_d^{\ast }*T_{i-1}}{Y_d}$$

(21)

$$T_{i-2}=T_{pre}+\frac{Y_d(1-{\eta }_{i-2})}{v_e-v_d^{\ast }}$$

(22)

Through recursion, we can obtain the formulas for calculating the remaining fuel ratio and refueling time when the jth pair of drones in UAVF i begins to refuel (Formula (23) and (24)). As a result, we can calculate the refueling time of UAVF i (Formula (25)).

$${\eta }_{i-j}={\eta }_{i-1}-\frac{v_d^{\ast }*{\displaystyle \sum _{k=1}^{j-1}{T}_{i-k}}}{Y_d}$$

(23)

$$T_{i-j}=T_{pre}+\frac{Y_d(1-{\eta }_{i-j})}{v_e-v_d^{\ast }}$$

(24)

$$T_i={\displaystyle \sum _{k=1}^{Nr(i)}{T}_{i-k}}$$

(25)

4. Threat-Oriented Collaborative Path-Planning Model for URMFTG Solution Approach

4.1. Framework of the Two-Stage Solving Algorithm

The algorithm can be divided into two stages (Figure 6). (1) First, there is the path-planning algorithm for the UAVFs based on the FSGA: considering the disadvantages of the genetic algorithm (GA), i.e., that the search direction is not strong and it easily falls into the precocious phenomenon, in this study, the FSGA algorithm was used to quickly search the population by introducing the optimal search operator to improve the search speed and avoid falling into the local optimal solution on the premise of ensuring that the individual adaptive value of the population does not decrease. (2) Second, there is the path-planning algorithm for the refueling tanker based on the improved NSGA-II: although the NSGA-II increases the population diversity through the crowding distance mechanism, it still has some problems, such as a poor distribution and local optimization. The NSGA-II uses the simulated binary crossover (SBX) operator and polynomial mutation operator. To improve the global search ability, prevent falling into the local optimum, and maintain the diversity of the population, in this study, the normal distribution crossover (NDX) operator, adaptive mutation operator, and a new crowded distance calculation method were used to improve the NSGA-II.

4.2. Path-Planning Algorithm for UAVFs Based on the FSGA

The process of the path-planning algorithm for UAVFs is as follows:

Step 1: Determine the coding mode and generate the initial population. The individual gene code is a two-segment chromosome code. The first part is the path genotype, which is the random arrangement of n target points; and the second part is the breakpoint genotype, the length of which is the number of UAVF-1. Figure 7 shows an example of an individual genotype. There are nine target points and three UAVFs. The path genotypes are {2 3 1 5 4 8 7 6 9}, and the breakpoint genotype is [26]. The information presented in Figure 7 is as follows: the planned route of UAVF 1 is airport–target 2–target 3–airport. The planned route of UAVF 2 is airport–target 1–target 5–target 4–target 8–airport. The planned path of UAVF 3 is airport–target 2–target 6–airport.

Step 2: Calculate the individual fitness value. The individual fitness value is the path distance of the UAVFs ($F_1$), which is calculated according to Formula (1). If the threat area does not overlap with the planned path of the individual, the individual adaptation value is calculated directly according to the intended path; otherwise, the adaptation value of the individual is calculated according to the path adjusted using the threat avoidance strategy.

Step 3: Genetic operation. In this study, new individuals were produced through mutation of the path genotype instead of using the cross-exchange between two individuals. Three mutation operators are given: the reversal, exchange, and insertion operators (Figure 8). Reversal operator: select two reversal points in the path genotypes and reverse the sequence between the two points. Exchange operator: in the path genotype, select two exchange points and exchange the positions of the two points. Insertion operator: in the path genotype, select two insertion points and insert the first point in front of the second point.

Step 4: Evolutionary iteration. In the evolution process, individuals with higher fitness values are retained to form new populations, and new offspring are generated through genetic operations such as mutation (Figure 8) and recombination (Figure 9). When the maximum number of evolution cycles is reached, we can obtain the path-planning results for the UAVFs.

4.3. Path-Planning Algorithm for the Refueling Tankers Based on the Improved NSGA-II

The improved NSGA-II is roughly the same as the NSGA-II in terms of the algorithm’s workflow.

Step 1: Determine the coding mode and generate the initial population that meets the constraints. The constraints mainly include the fuel constraint of the UAVFs (as shown in Formula (15)) and the refueling points that must be set on the path of the UAVFs. Some other constraints are shown in Formulas (10)–(14) and (16).

Step 2: Genetic operation. The initial population generates a new population that meets the constraints through crossover and mutation operations.

Step 3: Screen individuals via sorting to generate the next population. The population obtained in step 2 is blended with the initial population, and the population of the next generation is obtained through non-dominant sorting and crowding distance sorting. In the process of non-dominant sorting, the indicators of evaluation are the entire flight distance of the refueling tankers ($F_2$), which is calculated according to Formula (8) and the total refueling time of the UAVFs ($F_3$), which is calculated according to Formulas (9) and (17)–(25).

Step 4: Evolutionary iteration. Determine whether the evolutionary algebra reaches its maximum. If not, take the population obtained in step 3 as the initial population and return to step 2; otherwise, we can obtain the Pareto solution set.

Compared with the NSGA-II, the improved NSGA-II has the following advantages. In the crossover and mutation processes, in this study, the NDX operator and adaptive mutation operator were used, which expands the search range and improves the convergence speed. When calculating the individual crowding degree, a new crowding degree calculation formula was used to enhance the uniformity of the distribution of the individuals in the population.

The crossover process in the NSGA-II uses the SBX operator, and most of the child solutions of the SBX operator are located in the adjacent areas of the parent solution, which leads to a low possibility of finding a non-dominant solution. In contrast, the NDX operator has stronger global searchability. In this study, the NDX operator was introduced to enhance the spatial search ability of the algorithm. Assuming that the parents are $x_1$ and $x_2$ and the offspring are $y_1$ and $y_2$, the cross-process of the variables is as follows:

$$\left\{\begin{array}{c}{y}_{1,i}=\frac{x_{1,i}+x_{2,i}}{2}+\frac{1.481(x_{1,i}-x_{2,i})|N(0,1)|}{2},\\ y_{2,i}=\frac{x_{1,i}+x_{2,i}}{2}-\frac{1.481(x_{1,i}-x_{2,i})|N(0,1)|}{2},\end{array}\right.u\le 0.5$$

(26)

$$\left\{\begin{array}{c}{y}_{1,i}=\frac{x_{1,i}+x_{2,i}}{2}-\frac{1.481(x_{1,i}-x_{2,i})|N(0,1)|}{2},\\ y_{2,i}=\frac{x_{1,i}+x_{2,i}}{2}+\frac{1.481(x_{1,i}-x_{2,i})|N(0,1)|}{2},\end{array}\right.u>0.5$$

(27)

where u is a random number with values ranging from 0 to 1, and N(0,1) is a random variable with a normal distribution.

The NSGA-II uses the polynomial mutation operator, which has limitations in terms of its application in this study. The most commonly used mutation operators are the Gaussian, Cauchy, and uniformly distributed mutation operators. Compared with the polynomial mutation operator, the effects of these three mutation operators are better. The Gaussian mutation operator has an outstanding local search performance, while the uniformly distributed mutation operator has a solid global search advantage, making the individual jump out of the local optimization. The searchability of the Cauchy mutation operator is between those of the above two operators. According to the characteristics of the different evolution stages, in this study, an adaptive mutation operator was set up to give full play to the advantages of the varying mutation operators (Formula (28)). In the early stage of evolution, the uniform distribution mutation operator is used to improve the global search ability of the algorithm. In the middle stage of evolution, the Cauchy mutation operator is used to improve the convergence speed of the algorithm. In the later stage of evolution, the Gaussian mutation operator is used to complete the local search of the algorithm.

$$y_{1,i}=\left\{\begin{array}{c}{x}_{1,i}+U(-{\delta }_1,{\delta }_1),0<t\le 3T/10\\ \begin{array}{l}{x}_{1,i}+C(0,{\delta }_2),3T/10<t\le 7T/10\\ x_{1,i}+N(0,{\delta }_3),7T/10<t\le T\end{array}\end{array}\right.$$

(28)

In Formula (28), $U(-{\delta }_1,{\delta }_1)$ is a uniformly distributed random number with values ranging from $-{\delta }_1$ to ${\delta }_1$. $C(0,{\delta }_2)$ is a random number satisfying the Cauchy distribution.$N(0,{\delta }_3)$ is a random number satisfying a normal distribution with a mean value of 0 and a standard deviation of ${\delta }_3$.

The NSGA-II algorithm only considers the distances between the individuals and neighboring individuals. Still, individuals with significantly different crowding distance values in different objective functions cannot obtain more genetic opportunities, which is not conducive to maintaining the distribution of the population. A new formula for calculating the crowding distance was derived:

$$d_n={\displaystyle \sum _{j=1}^m(|\frac{f_j^{n+1}-f_j^{n-1}}{f_j^{\max }-f_j^{\min }}|)}$$

(29)

In Formula (29), $f_j^{n+1}$ and $f_j^{n-1}$ are the jth objective functions of individuals n + 1 and n − 1. Respectively, $f_j^{\max }$ and $f_j^{\min }$ are the maximum and minimum values of the jth objective function in this level under non-dominant sorting, respectively.

5. Computational Experiments

5.1. Experimental Conditions

This section presents several computational experiments used to verify the model and two-stage solving algorithm. The solving algorithm and experiments were implemented in MatlabR2017b. The test experiment was conducted using a ThinkPad with Intel Core i5-7500, 8GB RAM, running Windows 10. In this paper, a threat-oriented URMFTG scene is generated within the scope of a 2500 km × 2000 km area. The scene contains twenty target points, five departure airports (including two tanker airports and three UAVF airports), and four threat areas (Figure 10).

There are four UAVF and two refueling tankers. The value of $\beta$ is 4, which represents that each UAVF detects at least four targets The parameters of the UAVFs and refueling tankers are presented in

Table 2. UAVF parameters.

Formation	Departure Airport	Cruising Speed (km/h)	Fuel Consumption Rate (kg/min)	Formation Scale	Fuel Tank Capacity of UAV (kg)
UAVF 1	Airport 1	900	24	10	4500
UAVF 2	Airport 2	900	25	12	4700
UAVF 3	Airport 3	800	23	8	5500
UAVF 4	Airport 2	850	22	10	4400

and

Table 3. Refueling tanker parameters.

Refueling Tanker	Departure Airport	Cruising Speed (km/h)	Refueling Speed (kg/min)	Fuel Tank Capacity (kg)	Number of Drones That Can Be Guaranteed at Once
Tanker 1	Airport 4	650	1500	80,000	2
Tanker 2	Airport 5	600	1200	90,000	2

. In the GA, the population size is 160, and the evolution algebra is 1000. In the FSGA, the population size is 160, and the evolution algebra is 1000. In the NSGA-Ⅱ, the population size is 100, and the evolution algebra is 2000. The crossover probability is 0.9, and the mutation probability is 0.25. The binary crossover parameter is 20, and the polynomial variation parameter is 50. In the improved NSGA-II, the population size is 100, and the evolution algebra is 2000. The crossover probability is 0.9, and the mutation probability is 0.25. The parameter settings of the mutation operator are ${\delta }_1=20,{\delta }_2=10,\mathrm{and} {\delta }_3=5$.

5.2. Analysis of Results

Figure 11 shows the optimal path-planning results under different conditions. Without considering the threat area, the total flight distance of the UAVFs is 14189.71 km, and the specific path planning is shown in Figure 11a. When the threat area is considered, the total distance of the UAVFs increases due to the need to avoid the threat area. The total distances of the UAVFs calculated using the FSGA and GA are 14626.85 km and 14505.97 km, respectively. Figure 11b,c show the specific routes. Figure 11d shows the solution history for the FSGA and GA. It can be seen that the FSGA is superior to the GA in terms of the calculation result and convergence speed.

Table 4. Detailed information about the flight distances of the UAVFs for the three situations.

Formation	Flight Distance (km)
	Without Consideration of Threat Areas	GA Algorithm Considering the Threat Areas	FSGA Algorithm Considering the Threat Areas
UAVF 1	2682.54	4798.16	3179.54
UAVF 2	4730.93	3117.63	3117.63
UAVF 3	3648.42	3648.42	3272.06
UAVF 4	3127.82	3062.64	4936.73
Total distance	14,189.71	14,626.85	14,505.97
Increase rate of distance	/	3.1%	2.2%

shows the detailed information about the flight distances of the UAVFs for the three different cases. Compared with the GA, the FSGA decreases the rate of the UAVF distance growth from 3.1% to 2.2%.

Taking the UAVFs planning path calculated using the GA as the constraint, the refueling points were set on the planning path. We used the improved NSGA-II and NSGA-II to conduct the refueling tankers’ path planning. After 2000 generations of evolution, the Pareto level of the Pareto solution obtained by the improved NSGA-II and NSGA-II is 1. We select the first 50 Pareto solutions by using the ranking method of crowding distance, and the results are shown in Figure 12 with the total refueling time of the UAVFs and the total distance of the tankers as the objective functions.

Through calculation, the Pareto solutions of infinite crowding distance in NSGA-II are (7552.20, 61.15) and (7319.52, 67.27). The Pareto solutions of infinite crowding distance in the improved NSGA-II are (7552.20, 61.15) and (7233.83, 74.53), respectively. The two Pareto solutions are the same. Taking the above two Pareto solutions obtained using the improved NSGA-II as examples, the collaborative route planning of the refueling tankers and UAVFs is shown in Figure 13, and the detailed information about the second Pareto solution is presented in

Table 5. Detailed information about the Pareto solution of infinite crowding distance obtained by improved NSGA-II.

The Pareto Solution (7552.20, 61.15)
Refueling point	Coordinates	Refueling time (min)	Total refueling time (min)
Point 1	(1661.4, 987)	13.85	61.15
Point 2	(1618.82, 633.88)	19.92
Point 3	(1710, 1871)	11.96
Point 4	(1594, 979.2)	15.42
Refueling tanker	Flight distance (Km)		Total flight distance (Km)
Tanker 1	4194.63		7552.20
Tanker 2	3357.57
The Pareto Solution (7233.83, 74.53)
Refueling point	Coordinates	Refueling time (min)	Total refueling time (min)
Point 1	(1661.4, 987)	13.85	74.53
Point 2	(1643.26, 759.62)	27.18
Point 3	(1950, 1437)	17.47
Point 4	(1647.2, 911.56)	16.03
Refueling tanker	Flight distance (Km)		Total flight distance (Km)
Tanker 1	3982.52		7233.83
Tanker 2	3251.31

.

We further analyze the performance of the two algorithms. We analyzed the distribution of the Pareto solutions calculated by using the two algorithms under different four evolution algebra (500, 1000, 1500, and 2000), as shown in Figure 14.

By comparison, we can draw the conclusion that the range of Pareto solutions obtained by Improved NSGA-II is obviously larger than that of NSGA-II. With the increase in evolutionary algebra, NSGA-II cannot guarantee the optimization of the Pareto solution. In the solution process, NSGA-II uses a binary crossover operator and polynomial mutation operator, which makes the search range of the Pareto solution small and the search process has great uncertainty, resulting in the appearance of local optimal solutions and unstable Pareto solution results. In Figure 14c, the Pareto results obtained by NSGA-II running for 1500 generations are worse than 1000 generations. In Figure 14d, NSGA still falls into the local optimal solution when it runs for 2000 generations. Improved-NSGA-II uses a normal distribution crossover operator and adaptive mutation operator, which expands the search range of the Pareto solution and is more purposeful in the evolutionary iteration process, thereby improving the stability and convergence speed of the algorithm solution. From Figure 14, the Pareto solution of Improved NSGA-II tends to be stable when running for 500 generations, which is consistent with the results of 1000, 1500 and 2000 generations. However, the result of the Pareto solution obtained by NSGA-II running for 2000 generations is still unstable and falls into the local optimal solution. From the result of the Pareto solution, Improved-NSGA-II is better than NSGA-II, which is mainly reflected in the distribution range of the Pareto solution and the fitness function of the Pareto solution.

We further analyze the solution speed of the two algorithms. We analyzed the time distribution of determining individual solutions calculated by using the two algorithms under different four evolution algebra (500, 1000, 1500, and 2000). In each evolution algebra setting, we repeated the experiment 10 times and calculated the average running time of the algorithms in the experiments to compare the solution speed of the two algorithms, as shown in

Table 6. Comparison of the two algorithms for time of determining individual solutions under different four evolution algebra.

Algorithm	Time of Determining Individual Solutions under Different Evolution Algebra (s)
	500 Generations	1000 Generations	1500 Generations	2000 Generations
NSGA-II	182.7	374.0	565.5	760.9
Improved-NSGA-II	220.6	420.1	644.2	836.5

.

By comparison, we can draw the conclusion that the running time of Improved NSGA-II is relatively longer than that of NSGA-II, which shows that Improved NSGA-II is worse than NSGA-II in terms of running speed. Through the analysis, we think that the main reason is that the adaptive mutation operator and the new crowding distance calculation in Improved NSGA-II are improved on the basis of algorithm NSGA-II to expand the search space of the individual solutions. In addition, the calculation of these two variables becomes more complicated. These factors will increase the computational complexity of the algorithm, which makes the running time of the algorithm longer.

Through the above analysis, we think that Improved NSGA-II is better than NSGA-II in terms of algorithm stability, convergence speed, and Pareto solution results, but it is worse in terms of running speed. While Improved NSGA-II has some defects in running speed, its remarkable advantages in convergence speed, solution search space and stability can make up for this deficiency and can help us to find better Pareto solutions. Therefore, we think that Improved NSGA-II is better than NSGA-II as a whole.

6. Conclusions

In this paper, we establish a collaborative path planning model for a URMFTG and design a two-stage solution algorithm to solve the model. In the first stage, the path planning of the UAVFs is carried out with the shortest path of the UAVFs as the objective. In the second stage, based on the path planning of the UAVFs (the refueling points should be set on the flight of the UAVFs), the path planning of the refueling tankers is carried out with the total refueling time and the total distance of the refueling tankers as the objectives. A threat-avoidance strategy is also used to adjust the paths of the UAVFs and the tankers considering the threat areas in the target group during the solution process.

In the first stage of the model-solving algorithm, we propose the FSGA to improve the search efficiency and calculation result of the algorithm. In the second stage of the model-solving algorithm, an improved NSGA-II is proposed to solve the Pareto solution of the path planning of the refueling tankers. Compared with the NSGA-II, we use the normal distribution crossover operator, design a new adaptive mutation operator, and propose a new formula for calculating the crowding distance., which enhances the accuracy of the calculation results, the searching range of the Pareto solution, and the convergence rate of the algorithm. The conclusion can be drawn as follows:

(1)

Through research, it is concluded that the collaborative path planning for a URMFTG is primarily affected by the locations and sizes of the threat areas. In order to avoid the threat area, the UAVFs and refueling tankers should adjust their routes, resulting in increased flight distances.

(2)

A threat-oriented collaborative path-planning model for a URMFTG was established to analyze the collaborative complexity of the path planning of the UAVFs and the refueling tankers. A threat avoidance strategy was designed to adjust the path in order to avoid the threat area.

(3)

In the first stage of the solving algorithm, the FSGA can reduce the total UAVF’s distance growth rate from 3.1% to 2.2% and improve the convergence speed compared with the GA. FSGA is better than GA in terms of convergence speed and solution results.

(4)

In the second stage of the algorithm, compared with the NSGA-II, the improved NSGA-II uses a normal distribution crossover operator, a new adaptive mutation operator, and a new crowding distance formula, which expands the search range of the Pareto solution and is more purposeful in the evolutionary iteration process. The Improved NSGA-II is better than NSGA-II in terms of algorithm stability, convergence speed and Pareto solution results.

Some limitations should be investigated in further research. The threat avoidance strategy proposed in this paper is useful for the obstacles clustered in clusters. However, it is not applicable in the case of scatter obstacles that may form convex polygons, which is a problem that we need to consider in our future research. The Improved NSGA-II proposed in this paper should have its running speed improved. When selecting the refueling points in the tanker’s path planning, time factors, such as the departure time of the UAVF and the tanker and the constraints of the refueling point arrival time sequence, were not taken into account and should be considered in future research. Based on actual situations, the mission completion time should also be further considered.