Generation of Multi-UAV Four-dimensional Cooperative Attack Route Based on T/S-SAS

ZHANG Kun; LIU Zekun; HUA Shuai; ZHANG Zhenchong; LI Ke; YU Jingting

doi:10.12382/bgxb.2022.0211

Acta Armamentarii ›› 2023, Vol. 44 ›› Issue (6) : 1576-1587. DOI: 10.12382/bgxb.2022.0211

Generation of Multi-UAV Four-dimensional Cooperative Attack Route Based on T/S-SAS

Author information +

History +

Abstract

To address the problem of target attack time coordination and route space coordination of multiple UAVs, a multi-UAV four-dimensional cooperative attack route generation algorithm based on the T/S-SAS (Time/Space Dual Cooperative Sparse A^* Search) algorithm is proposed. The flight expansion node model is improved, an algorithm structure based on concurrent expansion is designed, and a cost calculation model for time coordination as well as a multi-UAV anti-collision constraint model are established. Simulations are performed. The results show that the proposed algorithm can enhance the planning efficiency of UAV attack route, shorten the range in coordination time for different drones to reach the target, and solve the anti-collision problem for different UAVs. The multi-UAV cooperative attack route can meet the time/space constraints, allowing the multi-UAV strike performance at cooperative time and the flight route space coordination performance to be improved, and the operational efficiency and capability of multi-UAV cooperative combat to be increased.

Key words

unmanned aerial vehicles / dual constraints / four-dimensional coordination / attack route generation

QR code of this article

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

ZHANG Kun , LIU Zekun , HUA Shuai , ZHANG Zhenchong , LI Ke , YU Jingting. Generation of Multi-UAV Four-dimensional Cooperative Attack Route Based on T/S-SAS. Acta Armamentarii. 2023, 44(6): 1576-1587 https://doi.org/10.12382/bgxb.2022.0211

0 Introduction

Under the background of military intelligence, UAV technology has been developing vigorously, but with the increasingly complex combat environment and the increasingly diverse combat tasks, it is difficult for a single UAV to complete combat tasks alone, so the research of multi-UAV cooperative combat is becoming more and more important^[1]. As a key link of multi-UAV cooperative combat, attack route generation is an important prerequisite to ensure the survival probability of UAVs and enhance the cooperative combat capability of multi-UAVs.

In the actual combat environment, the battlefield situation is complex, and the starting points of multiple UAVs involved in combat are different, but there is often a time requirement to attack the target.As a result, the attack routes of different UAVs in the war are crisscrossed, prone to collision, and the range is uneven, so it is difficult to reach the mission point at a similar time, and then carry out coordinated attacks. Therefore, it is necessary to carry out the research on the generation of attack routes under the time/space coordination of multiple UAVs.

At present, most of the route generation algorithms focus on mathematical programming method, roadmap method, potential field method, stochastic programming method, heuristic search method and so on. In recent years, many reinforcement Learning methods such as Q-Learning have emerged, but reinforcement learning has a high computational cost in the early learning stage^[2]. Mathematical programming methods include dynamic programming, mixed integer linear programming (MILP), model predictive control (MPC)/receding horizon control (RHC), Markov decision process based methods, etc^[3]^[4]^[5]^[6]^[7]. The mathematical programming method is easy to understand, but it is difficult to solve in complex space environment and the amount of calculation is large, so it is difficult to ensure the real-time of the algorithm. The method based on landmark diagram mainly includes visual diagram method, Voronoi diagram method, etc^[8]^[9]. These algorithms usually divide the planning space according to the environment and obstacles, and the planning results are safer, but the planning speed is closely related to the complexity of the planning space, and the route planning results are not dominant, especially for the flight performance constraints of UAV, which need to be further improved. The potential field method guides the UAV to the target assembly point through the action of the resultant force between different force fields. The typical algorithms include the artificial potential field (APF) method and its improved methods, such as the control method combining APF with virtual structure, the stream function (SF) method, and the perturbed fluid dynamic system (IFDS) method^[10]^[11]^[12]^[13]^[14]. This kind of algorithm has small amount of calculation and high practicability, but for complex planning environment, it still needs to consider the problem of avoiding local minimum, and the algorithm is highly dependent on parameters. The stochastic programming method constructs a path set by random sampling and finds the flyable path in it. The main methods include the random landmark graph (PRM) method and the rapidly expanding random tree (RRT) method^[15]^[16]. Different improvements improve the utilization of time and space, and accelerate the convergence speed of the algorithm, but the planning results are difficult to apply to the multi-UAV cooperative route planning process. The path planning algorithm based on heuristic search is represented by A^* and D^* algorithm, which introduces the target information into the heuristic information, makes the search process oriented, and greatly improves the search efficiency. Especially for the A^* algorithm, as the most widely used route planning algorithm, many researchers have proposed improvements in different directions, but for multi-UAV cooperation, especially for the time/space double cooperative planning problem, further consideration and balance are needed^{[17⇓⇓-20]}.

In order to meet the requirements of time cooperation and space anti-collision flight cooperation for multiple UAVs to reach their respective target points, a four-dimensional (time + three-dimensional space) cooperative attack route generation algorithm for multiple UAVs based on time and space double cooperative sparse A^* search (T/S-SAS) algorithm is proposed.In order to improve the cooperative combat capability of multiple UAVs, the flight expansion node model is improved, the multi-UAV anti-collision constraint model is established, the time cooperation cost calculation model is established, the algorithm structure based on concurrent expansion is designed, and the multi-UAV attack route meeting the space safety constraint and the cooperative time arrival constraint is generated.

1 Multi-UAV combat environment model

1.1 Operational environment description

Suppose that the cooperative combat space range of multiple UAVs is l × w × H, and the target T space coordinate position is

P_e=(x,y,z)^T

(1)

The number of UAVs participating in combat is N_U, and the set of UAVs U is defined as

U={U₁,U₂,…,U_i,…,

U_{N_{U}}

}

(2)

Where: the spatial coordinate position of UAV U_i (hereinafter referred to as U_i) is (

x_{i}^{U}

y_{i}^{U}

z_{i}^{U}

), 1≤i≤N_U, a 3-Dof motion model of the UAV is established.

1.2 Operational terrain model

A widely used mathematical equation is used to establish the digital terrain, and the cone is used to simulate the mountain peak and the small fluctuation is added as the original reference terrain. The simulated mountain peak is shown in formula (3):

h_{1} (x, y) = \sum_{j = 1}^{N_{p}} H_{j} \exp [- (\frac{x - A_{j}}{K_{j}}) - {(\frac{y - B_{j}}{K_{j}})}^{2}]

(3)

Where :h₁(x,y) is the peak height of the point calculated by formula (3), and (X, y) is the two-dimensional coordinate of the horizontal projection plane of any point; The N_p is the number of mountain peaks; The H_j is the highest height of the mountain peak; (A_j,B_j) is the coordinate of the two-dimensional center point of the mountain peak; The K_j is the slope steepness of a mountain peak.

The mathematical model of the original reference terrain is shown in Equation (4):

h₂(x,y)=sin(y+a)+b(sin x)+ccos(d

\sqrt{x^{2} + y^{2}}

)+ecos(y)+fsin(f

\sqrt{x^{2} + y^{2}}

)+gcos(y)

(4)

Where :h₂(x,y) is the peak height at point (X, y) calculated using equation (4); A, B, C, d, e, f, are seven different coefficients.

According to the description of formulas (3) and (4), the simulated terrain is established as shown in formula (5):

h(x,y)=max(h₁(x,y),h₂(x,y))

(5)

Where: H (X, y) is the terrain height.

Given the horizontal coordinates (X, y) of any point, the corresponding height H (X, y) of the point in the terrain can be calculated.

1.3 Environmental threat model

The environmental threat model includes adverse climate threat area model, radar threat area model and air defense missile threat area model, which need to be avoided when the multi-UAV coordinated attack route is generated.

1.3.1 Adverse Climate Threat Area Model

The adverse climate threat zone can be approximately modeled as a cylindrical region. The height of the threat zone is much higher than the flight altitude of the UAV, and the horizontal section at different flight altitudes of the UAV is a circular region, as shown in Figure 1. In Fig. 1, d_C represents the Euclidean distance between the horizontal projection point of the current UAV and the horizontal projection center of the adverse climate threat area, O_C is the two-dimensional coordinate of the central horizontal projection plane of the threat area, and d_C_,_min is the radius of the impassable area of the adverse climate threat area respectively.d_C_,_max is the maximum influence radius of the adverse climate threat area, P_C_,_min is the minimum threat cost value of the adverse climate threat area to the UAV, and P_C_,_max is the maximum threat cost value of the adverse weather threat area to the UAV.

Fig.1 Adverse climate threat zone

图1 不利气候威胁区

Full size|PPT slide

The cost of adverse climate threat at different distances is shown in formula (6):

P_C(d_C)=

\{\begin{array}{l} 0, & d_{C} > d_{C, m a x} \\ \frac{d_{C, m a x} - d_{C}}{d_{C, m a x} - d_{C, m i n}}, & d_{C, m i n} \leq d_{C} \leq d_{C, m a x} \\ 1, & d_{C} < d_{C, m i n} \end{array}

(6)

Where :P_C represents the threat cost value of the adverse climate threat zone to the UAV.

1.3.2 Radar Threat Area Model

Radar is a kind of equipment that uses radio electromagnetic waves to detect targets. It can identify, range and even track targets according to the transmitted and recovered electromagnetic waves. Its threat model is shown in Figure 2. In Fig. 2, Δh represents the altitude difference between the current UAV and the radar center coordinate, θ_R is the scanning range angle of the radar threat, d_R_,_min is the unescapeable distance of the radar threat, and d_R_,_max is the maximum radius distance of the Radar threat.

Fig.2 Radar threat zone

图2 雷达威胁区

Full size|PPT slide

Radar threat cost values at different positions are shown in formula (7):

P_R(d_R)=

\{\begin{array}{l} 0, & d_{R} > d_{R, m a x} \lor Δ h < d_{R} c o s θ_{R} \\ 1, & d_{R} < d_{R, m i n} \land Δ h \geq d_{R} c o s θ_{R} \\ \frac{d_{R, m a x}^{4} - d_{R}^{4}}{d_{R, m a x}^{4} - d_{R, m i n}^{4}}, & 其 他 \end{array}

(7)

Where :d_R represents the 3D Euclidean distance between the current position of the UAV and the central position of the radar threat area.

1.3.3 Threat area of air defense missile

The killing zone of an air defense missile has a maximum firing height, so it can be approximated as a frustum of a cone in the vertical section, and its threat model is shown in Figure 3. In Fig. 3, the closed area of

\bar{A B C D E}

is the killing zone, the closed area of

\bar{O D E}

is the non-escape zone, h_M_,_max is the maximum firing height of the air defense missile, and d_M_,_min is the non-escape distance.d_M_,_max is the maximum kill distance, d_M is the three-dimensional Euclidean distance between the current UAV and the central position of the air defense missile threat area, and ξ_M is the pitch angle between the current UAV and the central position of the air defense missile threat area.

Fig.3 Air defense missile threat zone

图3 防空导弹威胁区

Full size|PPT slide

The threat cost of air defense missile at different positions is shown in formula (8):

P_M(d_M)=

\{\begin{array}{l} \frac{d_{M, m a x} - d_{M}}{d_{M, m a x} - d_{M, m i n}}, & 无 人 机 位 于 \bar{A B C D E} 封 闭 区 域 \\ 1, & 无 人 机 位 于 \bar{O D E} 封 闭 区 域 \\ 0, & 其 他 \end{array}

(8)

The two conditions in formula (8) are:

1) If the UAV is located in a

\bar{A B C D E}

enclosed area, then

\{\begin{array}{l} d_{M} \times c o s ξ_{M} \leq h_{M, m a x} \\ d_{M, m i n} < d_{M} \leq d_{M, m a x} \end{array}

(9)

2) If the UAV is located in a

\bar{O D E}

enclosed area, then

d_M≤d_M_,_min

(10)

2 Multi-UAV Cooperative Attack Route Generation

The A^* algorithm is a typical heuristic algorithm, which plans the extended optimal solution of a single node by introducing heuristic information in the search process until the target point is searched^[21-22]. The 3D double collaborative sparse A^* search (SAS) algorithm splits the planning space sparsely and screens the planning directions according to the flight constraints of the UAV, and its node expansion mode is shown in Figure 4 and Figure 5^[23-24]. In Fig. 4, Δψ_max is the maximum angle difference of a single expansion in the horizontal direction of the UAV, P_r is the current position point of the UAV, and P_s_,k is the kth waypoint that can be expanded in the horizontal direction of the UAV at the next moment. In Fig. 5, γ_max_{_}_c is the maximum lift angle difference and γ_max_{_}_d is the maximum dive angle difference of the UAV in the vertical direction.

Fig.4 Horizontal plane node expansion mode of SAS algorithm

图4 SAS算法水平面内节点扩展方式

Full size|PPT slide

Fig.5 Vertical plane node expansion mode of SAS algorithm

图5 SAS算法竖直面内节点扩展方式

Full size|PPT slide

2.1 Multi-UAV Four-dimensional Cooperative Attack Route Generation Algorithm Based on T/S-SAS Algorithm

2.1.1 Improved model of flight expansion node

In the SAS node expansion mode, the nodes are affected by the expansion parameter settings, especially when the number of vertical and horizontal expansion nodes is small, the planning results have insufficient directivity to the mission points, resulting in more broken lines in the attack route, which leads to a larger total range of the UAV. In order to increase the planning efficiency of the algorithm planning results (see the definition of formula (16)) and reduce some unnecessary maneuvering routes of UAVs, the following improvements are made to the flight expansion nodes: additional expandable direction selection of nodes is added to improve the expansion performance of UAV nodes. On the basis of the original node expansion of the traditional SAS algorithm based on flight constraints,Add additional candidate nodes with the current node P_r pointing to the direction of task point P_e, candidate nodes from the starting position of UAV P_s to the direction of task point P_e, and candidate nodes with the same speed direction as the previous track segment P_r_-1P_r, as shown in Fig. 6.

Fig.6 Improved model of flight node expansion

图6 飞行扩展节点改进模型

Full size|PPT slide

2.1.2 Algorithm Architecture Design Based on Concurrent Extension

In order to enhance the relevance of different UAVs in the process of attack route planning, a concurrent expansion algorithm structure is designed. The co-planning process based on concurrent extension is shown in Fig. 7.

Fig.7 Planning process of concurrent expansion algorithm

图7 并发扩展算法规划过程

Full size|PPT slide

In Fig. 7, U_i, U_j, and U_k are three concurrently expanded UAVs respectively, the solid filled points with different colors are the planned route nodes of UAVs, the dotted unfilled points are the planning nodes abandoned in the planning process of UAVs, and the solid unfilled points are the current expandable node selection of UAVS.

In each round of planning process, multiple UAVs are planned at the same time, and the UAVs whose planned node number does not meet the requirement of the number of collaborative planning nodes are extended by the current point route, otherwise, the number of collaborative planning nodes is increased, and the next stage of collaborative expansion process is carried out. As shown in Fig. 7, currently the number of planned nodes of all UAVs is 3 (including the starting point), and the number of cooperative planning nodes is 4. Randomly select the U_i of UAVs to expand the route nodes, that is, the solid line of the U_i in the figure is not filled with points. After the expansion of the U_i is completed,Randomly selecting an unmanned aerial vehicle from the U_j and the U_k which do not meet the requirement of the cooperative planning node number for continuous expansion, and after the planned node number of all unmanned aerial vehicles is consistent with the cooperative planning node number, repeating the process until all unmanned aerial vehicles are expanded to a task point to complete the concurrent expansion planning process.

The concurrent expansion planning process is the basis of the multi-UAV cooperative attack route planning proposed in this paper. In the concurrent expansion planning process, the time cooperation cost calculation model and the multi-UAV anti-collision constraint model are added to realize the multi-UAV time and space cooperative attack route generation.

2.1.3 Time coordination cost calculation model

In the traditional expansion mode, it is difficult for UAVs to achieve the tactical target of reaching the target point at the same time to perform combat tasks. In order to balance the length of different attack routes of multiple UAVs and reduce the time difference between UAVs reaching the target, the following model is added based on the concurrent expansion planning algorithm:

1) a time coordination cost calculation model is added in the route expansion process to increase the node coordination cost value, drive the unmanned aerial vehicle to expand towards the node with low time coordination cost, and reduce the difference of the total flight range of different unmanned aerial vehicles, as shown in formula (11):

R_c,_i(P_s,_k_,_i)=|

{\bar{L}}_{e_t o t_l}

-L_{e_tot_l,}_i|

(11)

Where :R_c,_i is the time synergy cost value of U_i; The P_s,_k_,_i is a current expansion node; The

{\bar{L}}_{e_t o t_l}

is the average value of the estimated remaining route length of multiple UAVs; L_{e_tot_l,}_i is the estimated remaining route of U_i, which satisfies formula (12):

L_{e_tot_l,}_i=‖P_e-P_s,_k_,_i‖

(12)

Where: ‖ · ‖ is the Euclidean distance.

2) In order to further realize the multi-UAV time cooperative attack route planning, after the planning is completed, based on the relevant speed parameters of the UAV, the suggested average flight rate v_r,_i is calculated in combination with the total range of different UAV attack routes, and the time cooperative secondary processing is carried out, as shown in formula (13):

v_r,_i=v_max×

\frac{L_{t o t_l, i}}{\underset{j = 1,2, \dots, N_{U}}{m a x} {L_{t o t_l, j}}}

(13)

Where :v_max is the maximum flight rate of the UAV; L_{tot_l,}_i is the total length of U_i planning results.

If the v_r,_i satisfies Eq. (14), the proposed flight rate is valid:

v_min≤v_r,_i≤v_max

(14)

Where :v_min is the minimum flight rate of UAV.

By balancing the range gap of different UAVs and solving the recommended flight rate after the planning, the cooperative solution of multi-UAV attack route planning time is realized.

2.1.4 Constraint model of multi-aircraft collision avoidance

In order to avoid the cross collision problem of multi-UAV attack route, a multi-UAV anti-collision constraint model is added based on the concurrent expansion planning algorithm.

Let the minimum separation distance between UAVs be ΔL_{min_s}. When node P_s,_k_,_i is expanded at U_i, traverse other UAVs U_j(j≠i,0≤j≤N_U) planned waypoints P_m_,_j(m=1,2,3,4), as shown in Fig. 8.

Fig.8 Realization of anti-collision constraints

图8 防碰撞约束实现

Full size|PPT slide

‖P_s,_k_,_i-P_m_,_j‖>ΔL_{min_s}

(15)

If the formula (15) is not satisfied, it means that the current node P_s,_k_,_i to be selected does not satisfy the minimum distance constraint with the planned waypoints of other UAVs, so the current node P_s,_k_,_i to be selected is eliminated, and the node to be selected is reselected and the above process is repeated. In addition, the anti-collision with the ground is realized through the minimum height constraint of the UAV.

2.2 Multi-UAV Four-dimensional Cooperative Attack Route Generation Algorithm Based on T/S-SAS Algorithm

Combined with the improved model in Section 2.1, a multi-UAV four-dimensional cooperative attack route generation algorithm based on T/S-SAS algorithm is proposed, and the algorithm flow is shown in Figure 9.

Fig.9 Algorithm flow of the generation of multi-UAV four-dimensional cooperative attack route based on T/S-SAS algorithm

图9 基于T/S-SAS算法的多无人机四维协同攻击航线生成算法流程

Full size|PPT slide

The specific flow of the algorithm is as follows:

1) determining the number of unmanned aerial vehicles involved in combat, initial positions, mission point positions, and the like, numbering the unmanned aerial vehicles, and taking the initial positions as initial nodes;

2) compare that planned route of the unmanned aerial vehicle, excluding the unmanned aerial vehicle which has reach the target task point, and taking the maximum number of route segments as the number of cooperative track segments;

And 3) jud whether that numb of the planned route sections of all the unmanned aerial vehicle is equal. If they are equal, jump to step 5;

4) taking the unmanned aerial vehicle with the least number of planned flight path sections as the current extended unmanned aerial vehicle, and if the number of planned flight path sections of a plurality of unmanned aerial vehicles is the same, selecting the unmanned aerial vehicle with the smallest serial number, and skipping to the step 6;

5) take that unmanned aerial vehicle with the minimum serial numb as the current extended unmanned aerial vehicle;

6) generate an item to be selected of that current expand unmanned aerial vehicle node according to the improved algorithm;

7) eliminating the node items to be selected which do not satisfy the constraint conditions according to various constraint conditions;

8) that proces of adding the candidate of the stand-alone SAS algorithm into the OPEN table;

9) excluding the unmanned aerial vehicles arriving at the target task point, judging whether the number of the cooperative track segments of each unmanned aerial vehicle is equal to the number of the cooperative track segments, and if not, jumping to the step 2;

10) Add 1 to the number of cooperative route sections;

11) judging whether each unmanned aerial vehicle reaches a target task point, and if not, jumping to the step 2;

12) All UAV routes have been planned to the mission target point, output the recommended speed and route planning results, and the planning process is over.

3 Simulation verification and analysis

3.1 Initial parameter setting

Experimental simulation platform: CPU is i7-8750H, memory is 8GB. The terrain and threat modeling method in Section 1 is used. It is assumed that the mission is executed in a three-dimensional space of 100km × 100km × 30km. There are four threats in the environment, including mountain, radar, air defense missile and no-fly zone. The planning parameters are set as follows: the planning step is 2km. It is assumed that there are four UAVs in total. The reference maximum flight speed of UAVs is 360km/H, and the minimum flight speed is 180km/H.

The number of threats and parameter information set in the simulation environment are shown in Table 1.

Table 1 Environment threat parameters

表1 环境威胁参数

编号	威胁种类	威胁二维中心坐标/km	最大威胁高度/km	最大威胁半径/km
1	山峰威胁	(45.0, 72.0)	3.0	15.0
2	山峰威胁	(67.0, 40.0)	1.5	10.0
3	山峰威胁	(31.0, 28.0)	2.0	10.0
4	山峰威胁	(88.0, 26.0)	2.5	12.0
5	雷达威胁	(60.0, 52.0)	12.0	12.0
6	雷达威胁	(81.0, 55.0)	8.0	8.0
7	雷达威胁	(57.0, 86.0)	10.0	10.0
8	雷达威胁	(23.0, 68.0)	9.6	9.6
9	雷达威胁	(20.0, 38.0)	10.0	10.0
10	雷达威胁	(44.0, 19.0)	8.0	8.0
11	雷达威胁	(69.0, 24.0)	8.0	8.0
12	防空导弹威胁	(94.0, 27.0)	7.0	10.0
13	防空导弹威胁	(92.0, 46.0)	7.0	10.0
14	防空导弹威胁	(78.0, 75.0)	7.0	8.0
15	防空导弹威胁	(36.0, 80.0)	7.0	9.0
16	防空导弹威胁	(25.0, 16.0)	7.0	9.0
17	防空导弹威胁	(92.0, 85.0)	7.0	7.0
18	气候威胁	(38.0, 38.0)	30.0	6.0
19	气候威胁	(71.0, 38.0)	30.0	8.0
20	气候威胁	(58.0, 69.0)	30.0	6.0
21	气候威胁	(20.0, 85.0)	30.0	6.0
22	气候威胁	(40.0, 66.0)	30.0	6.0
23	气候威胁	(90.0, 68.0)	30.0	6.0

The names of relevant algorithms and the description of algorithm improvements in this section are shown in Table 2, and the description will not be repeated later.

Table 2 Related algorithm name and algorithm improvement description

表2 相关算法名称及算法改进描述

序号	算法	改进
1	传统SAS算法
2	I-SAS算法	添加“飞行扩展节点改进模型”
3	IT-SAS算法	添加“飞行扩展节点改进模型”+“并发扩展结构”+“时间协同代价计算模型”
4	IS-SAS算法	添加“飞行扩展节点改进模型”+“并发扩展结构”+“多机防碰撞约束模型”
5	T/S-SAS算法	添加“飞行扩展节点改进模型”+“并发扩展结构”+“时间协同代价计算模型”+“多机防碰撞约束模型”

3.2 Simulation Verification and Analysis of Planning

In order to fully verify the effectiveness of the improved algorithm model in this paper, the improved model proposed in this paper is simulated and verified respectively, and the following experiments are carried out according to the initial conditions of the simulation.

3.2.1 Verification of efficiency and effectiveness of algorithm planning

Set the parameters of UAV starting point and target point as shown in Table 3.

Table 3 Starting point and target point parameters of algorithm planning efficiency test

表3 算法规划效率测试的起点、目标点参数

无人机编号	起始点坐标/km	设定目标点坐标/km
U₁	(20.0, 0, 1.0)	(20.0, 100.0, 1.0)
U₂	(40.0, 0, 1.0)	(40.0, 100.0, 1.0)
U₃	(60.0, 0, 1.0)	(60.0, 100.0, 1.0)
U₄	(80.0, 0, 1.0)	(80.0, 100.0, 1.0)

Keeping the same planning environment and parameter settings, the traditional SAS algorithm and I-SAS algorithm are used to plan the attack route of UAV.

Due to the addition of additional expansion nodes in the I-SAS algorithm, the calculation time will be increased and the attack route will be shortened in theory. In order to study the relationship between the two and verify the improvement of the improved flight expansion node model proposed in this paper on the performance of the I-SAS algorithm planning results, the planning efficiency of the algorithm is defined as

E_P=

\frac{\overset{N_{U}}{\sum_{i = 1}} T_{F, S A S} - \overset{N_{U}}{\sum_{i = 1}} T_{F, I - S A S}}{T_{p, I - S A S} - T_{p, S A S}}

(16)

In the formula, :T_{F, SAS}, T_{F, I-SAS} are the flight time required for the UAV to use the traditional SAS algorithm, I-SAS algorithm planning results and fly to the target point at the maximum flight speed (s);T_{p, SAS}, and T_{p, I-SAS} are the time (s) used by the traditional SAS algorithm, I-SAS algorithm planning, respectively.

Set a single node to expand the number of nodes M = 4 in the vertical plane and the number of nodes S = 4 in the horizontal plane. The planning results are shown in Figure 10.

Fig.10 Planning result comparison of traditional SAS algorithm and I-SAS algorithm

图10 传统SAS算法与I-SAS算法规划结果对比

Full size|PPT slide

In Figure 10, different hemispheres and cylinders represent different environmental threats, the yellow → brown → white gradient position represents the height fluctuation of the simulated terrain, and the dotted lines of different colors represent the planned attack routes of different UAVs.

As shown in Figure 10, especially in the position circled by the white ellipse, compared with the traditional SAS algorithm, in the planning results of the I-SAS algorithm, in addition to the necessary evasion maneuvers against obstacles, the attack route has a clearer target directivity and a smoother route.

Keep the same planning environment and parameter settings, expand the number of nodes with different vertical and horizontal planes, and carry out multiple experiments. The statistical planning results are shown in Figure 11.

Fig.11 Data comparison between traditional SAS algorithm and I-SAS algorithm under different number of expanded nodes

图11 不同扩展节点数量下传统SAS算法与I-SAS算法规划结果数据对比

Full size|PPT slide

As shown in Figure 11, with the increase of the number of expansion nodes, the number of expansion directions that can be selected increases, and the overall calculation amount of the algorithm increases, so both algorithms generally show a trend that the average planned route length gradually decreases. However, compared with the traditional SAS algorithm, the average route length in the planning results of I-SAS algorithm is reduced by 2. 8%, the maximum 17478 of algorithm planning efficiency is 17478, and the average value is 6377. This shows that for different numbers of expansion nodes (taking the maximum flight speed of 360 km/H set in simulation as an example), when the I-SAS algorithm increases the calculation time by 0. 1 s, the total range of multiple UAVs can be reduced by about 174. 78 km, with an average reduction of 63. 8 km, which greatly improves the planning quality. Especially when the number of vertical and horizontal expansion nodes is small, the planning results of I-SAS algorithm are greatly improved.

3.2.2 Multi-UAV Cooperative Planning-Time Cooperative Validity Verification

In order to make the straight-line distance of UAV route have reference deviation and give the meaning of cooperative time planning, the parameters of UAV starting point and settable target point are set as shown in Table 4. In a single simulation, different target points are set for comparative experiments.

Table 4 Starting point and target point parameters of time coordination test

表4 时间协同测试的起点、目标点参数

无人机编号	起始点坐标/km	目标编号	设定目标点坐标/km
U₁	(20.0, 0, 1.0)	T₁	(20.0, 100.0, 1.0)
U₂	(40.0, 0, 1.0)	T₂	(40.0, 100.0, 1.0)
U₃	(60.0, 0, 1.0)	T₃	(60.0, 100.0, 1.0)
U₄	(80.0, 0, 1.0)	T₄	(80.0, 100.0, 1.0)

Keeping the same planning environment and parameter settings, the I-SAS algorithm and the IT-SAS algorithm are used to plan the attack route of the UAV.

Compared with I-SAS algorithm, IT-SAS algorithm adds concurrent extension structure and time coordination model, which further increases the amount of calculation and planning time in theory. The difference between the maximum and minimum time required for different UAVs to reach the target point, that is, the range of cooperative time, will decrease. In order to study the relationship between the two, and verify the improvement of the planning results of the IT-SAS algorithm on the cooperative time strike performance of multiple UAVs, the cooperative time efficiency E_T: of the algorithm is defined.

E_T=

\frac{Δ T_{F, I - S A S, d} - Δ T_{F, I T - S A S, d}}{T_{p, I T - S A S} - T_{p, I - S A S}}

(17)

In the formula, :ΔT_{F, I-SAS, d} and ΔT_{F, IT-SAS, d} are the cooperative time range (s) obtained when the UAV adopts the planning results of I-SAS and IT-SAS algorithms and flies to the target point at the maximum flight speed, which are calculated as shown in Formula (18) and Formula (19) respectively:

ΔT_{F, I-SAS, d}=T_{F, I-SAS, max}-T_{F, I-SAS, min}

(18)

ΔT_{F, IT-SAS, d}=T_{F, IT-SAS, max}-T_{F, IT-SAS, min}

(19)

Keep the number of nodes M = 4 in the vertical plane and S = 4 in the horizontal plane for a single node in different algorithms. The UAV planning target points are all set as target 2, and the planning results are shown in Figure 12.

Fig.12 Planning result comparison of I-SAS algorithm and IT-SAS algorithm

图12 I-SAS算法与IT-SAS算法规划结果对比

Full size|PPT slide

Reference numerals in fig. 12 have the same meanings as those in fig. 10. In Figure 12, UAVs 1 to 4 and their corresponding planning targets are numbered as 1-2, 2-2, 3-2, and 4-2.

As shown in Figure 12, in the left ellipse of the planning results of the I-SAS algorithm and the IT-SAS algorithm, the directivity to the target is relatively clear and the planning results are similar due to the addition of the flight expansion node improvement model; In the right ellipse of the planning results of I-SAS algorithm and IT-SAS algorithm, the IT-SAS algorithm in this paper can increase the planned range of some UAVs (especially UAV 3), so as to balance the track gap between different UAVs, thus making IT easier to achieve multi-UAV coordinated time attack.

Keep the same planning environment, set different target points for the UAV to carry out multiple experiments, and the statistical planning result data is shown in Figure 13.

Fig.13 Data comparison between I-SAS algorithm and IT-SAS algorithm under different target location settings

图13 不同目标位置设定下I-SAS算法与IT-SAS规划结果数据对比

Full size|PPT slide

As shown in Figure 13, the straight-line distance between the starting point and the end point of multiple UAVs is quite different, and under the influence of environmental threats, the flight distance is even more different; In this case, compared with the I-SAS algorithm, the IT-SAS algorithm proposed in this paper has a shorter range of flight time for different UAVs in its planning results, with an average reduction of about 35. 5% in the experiment, that is, the planning routes of different UAVs are closer, and the maximum value of the algorithm's collaborative time efficiency is 2061.3, with an average of 871.3. Taking the maximum flight speed of 360 km/H set in the simulation as an example, the IT-SAS algorithm can shorten the maximum range of cooperation time of different UAVs by 206. 1 s and the average range of cooperation time of different UAVs by 87. 1 s by increasing the calculation time by 0. 1 s, which makes IT easier to achieve time cooperation by adjusting the flight speed, so that the planning results can be applied to multi-UAV cooperative attack under time cooperation constraints.

3.2.3 Multi-UAV Cooperative Planning-Space Cooperative Effectiveness Verification

In order to increase the possible conflict probability of the UAV route, set the UAV starting point to be close and the target point to be the same, as shown in Table 5.

Table 5 Starting point and target point parameters of space coordination test

表5 空间协同测试的起点、目标点参数

无人机编号	起始点坐标/km	设定目标点坐标/km
U₁	(0.5, 0, 1.0)	(100.0, 100.0, 1.0)
U₂	(1.0, 0, 1.0)	(100.0, 100.0, 1.0)
U₃	(0, 0.5, 1.0)	(100.0, 100.0, 1.0)
U₄	(0, 1.0, 1.0)	(100.0, 100.0, 1.0)

Keeping the same planning environment and parameter settings, the I-SAS algorithm and IS-SAS algorithm are used to plan the attack route of UAV. In order to verify the improvement effect of the planning result of the IS-SAS algorithm proposed in this paper on the spatial coordination performance of the UAV flight route, the E_S of the efficiency of the algorithm coordination space IS defined as shown in formula (20):

E_S=

\frac{\overset{N_{U}}{\sum_{i = 1}} P N_{i} - \overset{N_{U}}{\sum_{i = 1}} I P N_{i}}{\overset{N_{U}}{\sum_{i = 1}} P N_{i}}

(20)

Where:

\overset{N_{U}}{\sum_{i = 1}}

PN_i is the sum of the total number of UAV route planning points for different algorithms;

\overset{N_{U}}{\sum_{i = 1}}

IPN_i is the sum of the total number of UAV route collision points for different algorithms.

Keep the number of nodes M = 4 in the vertical plane and S = 4 in the horizontal plane for a single node in different algorithms. The UAV is set to have a minimum safety distance of 500 m, and the planning results are shown in Figure 14.

Fig.14 Planning result comparison of I-SAS algorithm and IS-SAS algorithm

图14 I-SAS算法与IS-SAS算法规划结果对比

Full size|PPT slide

It can be seen from Fig. 14 that compared with the I-SAS algorithm, the planning results of the IS-SAS algorithm show that the attack routes of different UAVs are more sparse, and the interval between the planned routes of different UAVs IS larger intuitively and visually, so that the cooperative attack routes of multiple UAVs meet the requirements of space cooperative anti-collision flight.

Keep the same planning environment, set different space coordination distances (minimum anti-collision safety distance) for UAVs to carry out multiple experiments, and the statistical planning results are shown in Figure 15.

Fig.15 Data comparison between I-SAS algorithm and IS-SAS algorithm under different safety distances

图15 不同安全距离下I-SAS算法与IS-SAS算法规划结果数据对比

Full size|PPT slide

It can be seen from Fig. 15 that under different safety distances, the IS-SAS algorithm proposed in this paper has no collision point (except the starting point) in the whole route compared with the I-SAS algorithm, that IS, the distance between each node and other UAV planning nodes in the UAV planning results will not be less than the safety distance constraint, and its cooperative space efficiency E_S is stable at more than 99%. There are UAV collision points in the planning results of I-SAS algorithm under partial safety distance constraints, which leads to the non-flyable route and invalid planning results. Therefore, the IS-SAS algorithm proposed in this paper can solve the problem of multi-UAV space cooperative attack route generation.

3.2.4 Effectiveness Verification of Multi-UAV Cooperative Four-dimensional Attack Route Generation

Set the starting point of the UAV to be close and the target point to be the same, as shown in Table 6.

Table 6 Starting point and target point parameters of time/space coordination test

表6 时间/空间协同测试的起点、目标点参数

无人机编号	起始点坐标/km	设定目标点坐标/km
U₁	(1.0, 0, 1.0)	(100.0, 100.0, 1.0)
U₂	(2.0, 0, 1.0)	(100.0, 100.0, 1.0)
U₃	(0, 1.0, 1.0)	(100.0, 100.0, 1.0)
U₄	(0, 2.0, 1.0)	(100.0, 100.0, 1.0)

Keeping the same planning environment and parameter settings, the traditional SAS algorithm, I-SAS algorithm, IT-SAS algorithm, IS-SAS algorithm and T/S-SAS algorithm are used to plan the attack route of UAV. The number of nodes for a single node in the vertical plane is M = 4, and the number of nodes in the horizontal plane is S = 4. The minimum safety distance of UAV is set as 500m, and the statistical planning result data is shown in Fig. 16.

Fig.16 Planning result comparison of different algorithms

图16 不同算法规划结果数据对比

Full size|PPT slide

It can be seen from Figure 16 that under the same conditions, different algorithms are used for planning. With the adjustment and improvement of the improved model, the computational complexity is gradually increased, and the planning results are improved:

In the aspect of planning distance, compared with the average route length of the planning results of the traditional SAS algorithm, other algorithms reduce the average route length in different degrees, the lowest value of the algorithm planning efficiency E_p is 118.23, the maximum value is 2587.93, and the route is shortened between 1.65% and 2.64%, that is to say, the improved model of flight expansion nodes can improve the planning efficiency of different algorithms. In the aspect of time coordination, compared with the traditional SAS algorithm, I-SAS algorithm and IS-SAS algorithm, the IT-SAS algorithm and T/S-SAS algorithm can effectively reduce the time range. Compared with I-SAS algorithm, the time efficiency E_T of IT-SAS algorithm and T/S-SAS algorithm is 80. 9 and 17. 81, respectively, and the time range difference of reducing cooperation is 37. 74% and 26. 46%, respectively.IT is easier to achieve time cooperation of multiple UAVs by adjusting the flight speed. In the aspect of space cooperation, compared with the traditional SAS algorithm, I-SAS algorithm and IT-SAS algorithm, IS-SAS algorithm and T/S-SAS algorithm solve the space collision problem of different UAVs; Compared with I-SAS algorithm, both IS-SAS algorithm and T/S-SAS algorithm have 100% E_s of cooperative space efficiency, which can realize multi-UAV space cooperation.

The above simulation results show that, compared with the traditional SAS algorithm, the proposed T/S-SAS algorithm shortens the average path of UAVs, reduces the range of cooperation time of different UAVs, and solves the space anti-collision problem of different UAVs. It has good balance and applicability in solving time and space coordination.

4 Conclusion

In this paper, a four-dimensional cooperative attack route generation algorithm for multiple UAVs based on T/S-SAS algorithm is proposed to solve the problem of time cooperation and flight route space cooperation of multiple UAVs attacking targets.The flight expansion node model is improved, the algorithm structure based on concurrent expansion is designed, the time coordination cost calculation model and the multi-aircraft anti-collision constraint model are established, and the multi-UAV cooperative attack route generation algorithm is proposed. The main conclusions are as follows:

The algorithm proposed in this paper can enhance the planning efficiency of UAV attack routes, reduce the time difference of coordinated attack between different UAVs to reach the target, and solve the problem of space anti-collision between different UAVs.The multi-UAV attack route can meet the time/space constraint, the multi-UAV cooperative time strike performance and the flight route space cooperative performance are improved, and the UAV cooperative combat efficiency and combat capability are improved.

References

Publishing order | Descend order by publishing year | Descend order by cited within

[1]

尤嵩菀, 王文龙. 美俄军事智能化发展及启示[J]. 海军工程大学学报(综合版), 2020, 17(2): 64-69.

YOU

S Y

, WANG

W L

. Research on military intellectualization of United States and Russia and its enlightenment[J]. Journal of Naval University of Engineering(Comprehensive Edition), 2020, 17(2): 64-69. (in Chinese)

Cited in this article [1]

[2]	XIE R L, MENG Z J, ZHOU Y M, et al. Heuristic Q-learning based on experience replay for three-dimensional path planning of the unmanned aerial vehicle[J]. Science Progress, 2020, 103(1):1-18. Cited in this article [1]

[3]	孙健, 井立, 刘朝君. 突发威胁下的无人机航迹规划算法[J]. 飞行力学, 2018, 36(3): 52-55. SUN J, JING L, LIU Z J. Route planning algorithm of UAV with unexpected threat[J]. Flight Dynamics, 2018, 36(3): 52-55. (in Chinese) Cited in this article [1]

[4]	ALBERT A, LEIRA F S, IMSLAND L. UAV path planning using MILP with experiments[J]. Modeling, Identification and Control, 2017, 38(1): 21-32. https://doi.org/10.4173/mic.2017.1.3 http://www.mic-journal.no/ABS/MIC-2017-1-3.asp Cited in this article [1]

[5]	代进进, 李相民, 薄宁, 等. 基于模型预测控制的无人机避障路径规划方法[J]. 火力与指挥控制, 2020, 45(1): 114-119. DAI J J, LI X M, BO N, et al. Study on UAV obstacle avoidance path planning based on model predictive control[J]. Fire Control & Command Control, 2020, 45(1): 114-119. (in Chinese) Cited in this article [1]

[6]	王文彬, 秦小林, 张力戈, 等. 基于滚动时域的无人机动态航迹规划[J]. 智能系统学报, 2018, 13(4): 524-533. WANG W B, QIN X L, ZHANG L G, et al. Dynamic UAV trajectory planning based on receding horizon[J]. CAAI Transactions on Intelligent Systems, 2018, 13(4): 524-533. (in Chinese) Cited in this article [1]

[7]

LIU

, SHI

, SUN

L L

, et al. Path planning for UAV-mounted mobile edge computing with deep reinforcement learning[J]. IEEE Transactions on Vehicular Technology, 2020, 69(5): 5723-5728.

https://doi.org/10.1109/TVT.25

https://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=25

Cited in this article [1]

[8]

BLASI

, D

AMATO E

, MATTEI

, et al. Path planning and real-time collision avoidance based on the essential visibility graph[J]. Applied Sciences, 2020, 10(16): 5613.

https://doi.org/10.3390/app10165613

https://www.mdpi.com/2076-3417/10/16/5613

Cited in this article [1] Abstract

This paper deals with a novel procedure to generate optimum flight paths for multiple unmanned aircraft in the presence of obstacles and/or no-fly zones. A real-time collision avoidance algorithm solving the optimization problem as a minimum cost piecewise linear path search within the so-called Essential Visibility Graph (EVG) is first developed. Then, a re-planning procedure updating the EVG over a selected prediction time interval is proposed, accounting for the presence of multiple flying vehicles or movable obstacles. The use of Dubins curves allows obtaining smooth paths, compliant with flight mechanics constraints. In view of possible future applications in hybrid scenarios where both manned and unmanned aircraft share the airspace, visual flight rules compliant with International Civil Aviation Organization (ICAO) Annex II Right of Way were implemented. An extensive campaign of numerical simulations was carried out to test the effectiveness of the proposed technique by setting different operational scenarios of increasing complexity. Results show that the algorithm is always able to identify trajectories compliant with ICAO rules for avoiding collisions and assuring a minimum safety distance as well. Furthermore, the low computational burden suggests that the proposed procedure can be considered a promising approach for real-time applications.

[9]

朱杰, 鲁艺, 张辉明. 突发威胁情况下的无人机航迹重规划[J]. 计算机工程与应用, 2018, 54(8): 255-259.

https://doi.org/10.3778/j.issn.1002-8331.1709-0345

Abstract

为了提高Voronoi图在航迹规划方面的实用性，提出了一种改进型的Voronoi图构造模型。该模型通过引入威胁源的不可穿越区域边界，利用折中原理，在Delaunay三角网的基础上构建航迹拓扑空间。改进型的Voronoi图模型拓展了传统模型的航迹段数量，提高了航迹段对威胁的敏感性，使规划的航迹更为合理。其次，在分析突发威胁对于航迹拓扑空间影响的基础上，提出了一种基于改进型Voronoi图的航迹重规划模型，并结合D*算法对突发情况下的航迹重规划进行了研究，规划出了理想航迹。

ZHU

, LU

, ZHANG

H M

. Path replanning for UAV in emergent threats[J]. Computer Engineering and Application, 2018, 54(8): 255-259. (in Chinese)

Cited in this article [1]

[10]	吴云华, 牛康, 李磊, 等. 基于3D-APF和约束动力学的无人机编队飞行控制[J]. 系统工程与电子技术, 2018, 40(5): 1104-1108. WU Y H, NIU K, LI L, et al. Formation flight control of UAV based on 3D-APF and constraint dynamics[J]. Systems Engineering & Electronics, 2018, 40(5):1104-1108. (in Chinese) Cited in this article [1]

[11]

陈天德, 黄炎焱, 沈炜. 基于虚拟障碍物法的无震荡航路规划[J]. 兵工学报, 2019, 40(3): 651-658.

https://doi.org/10.3969/j.issn.1000-1093.2019.03.025

Abstract

人工势场法作为路径规划的一种算法，凭借其解算得到的平滑航路，特别适用于不够灵活的移动机器人、智能体的路径规划。由于人工势场法自身不可避免地存在局部极小值以及算法执行不可避免的离散化，导致航路点解算可能会陷入局部极小值陷阱而进入死循环以及出现航路点震荡问题。针对局部极小值陷阱问题，提出改进型虚拟障碍物法；对虚拟障碍物位置的确定，引入了威胁区的概念，并提出了一个确定标准。针对航路点震荡问题，提出过滤震荡点法。仿真实验证明：改进型虚拟障碍物法能够有效地使陷入局部极小值陷阱的航路点解算，成功逃出陷阱；过滤震荡点法能够有效地消除震荡航路点，得到相对平滑的航路。

CHEN

T D

, HUANG

Y Y

, SHEN

. Non-oscillation path planning based on virtual obstacle method[J]. Acta Armamentarii, 2019, 40(3): 651-658. (in Chinese)

https://doi.org/10.3969/j.issn.1000-1093.2019.03.025

Cited in this article [1] Abstract

The artificial potential field method, as a path planning algorithm, is used for the path planning of clumsy mobile robots, agents and so on because it can provide a smooth route. Due to the inevitable existence of local minimum and discretization of algorithms during algorithm execution, the calculation of the route point may fall into the local minimum trap, which may result in the infinite loop of algorithmic program and the oscillation of path point. For local minimum trap, an improved virtual obstacle method is proposed to overcome this problem. The definition of threat area is introduced to determine the location of virtual obstacle, and a determining standard is put forward. A filtering oscillation point method is proposed to solve the problem of path point oscillation. The simulated results show that the route points which are stuck in local minimum trap can escape from the trap successfully using the improved virtual obstacle method. Additionally, the oscillation route points can be effectively eliminated to obtain a relatively smooth route by the filtering oscillation point method. Key

[12]

潘无为, 姜大鹏, 庞永杰, 等. 人工势场和虚拟结构相结合的多水下机器人编队控制[J]. 兵工学报, 2017, 38(2): 326-334.

https://doi.org/10.3969/j.issn.1000-1093.2017.02.017

Abstract

传统的多水下机器人（AUV）编队算法，例如领航跟随法、虚拟结构法，对编队形成过程中AUV间的避碰问题和编队行进过程中的避障问题，没有进行有效解决。人工势场法可利用势函数进行避碰、避障，但队形组织能力略显不足。针对上述问题，提出了一种人工势场和虚拟结构相结合的多AUV编队控制算法。将系统分为3个部分：编队参考点、虚拟结构质点和AUV. 以编队参考点为中心形成期望的虚拟结构以组织队形；虚拟结构质点以期望的虚拟结构为运动目标，并在运动的过程中，通过人工势场斥函数，实现避碰和避障；AUV对虚拟结构质点进行目标跟踪，从而渐进形成AUV的队形。通过编队路径跟踪、编队队形变换和编队避障等一系列仿真实验，对算法的可靠性和灵活性进行充分验证。实验结果表明：在随机的初始位置条件下，多AUV系统可以快速无碰撞地形成队形；在编队行进过程中进行灵活的队形变换，并对障碍物有效避碰。

PAN

W W

, JIANG

D P

, PANG

Y J

, et al. A multi-AUV formation algorithm combining artificial potential field and virtual structure[J]. Acta Armamentarii, 2017, 38(2): 326-334. (in Chinese)

Cited in this article [1]

[13]

梁宵, 王宏伦, 李大伟, 等. 基于流水避石原理的无人机三维航路规划方法[J]. 航空学报, 2013, 34(7): 1670-1681.

LIANG

, WANG

H L

, LI

D W

, et al. Three dimensional path planning for unmanned aerial vehicles based on principles of stream avoiding obstacles[J]. Acta Aeronautica et Astronautica Sinica, 2013, 34(7): 1670-1681. (in Chinese)

Cited in this article [1]

[14]	王宏伦, 吴健发, 姚鹏. 基于扰动流体动态系统的无人机三维航路规划:方法与应用[J]. 无人系统技术, 2018, 1(1): 72-82. WANG H L, WU J F, YAO P. UAV three-dimensional path planning based on interfered fluid dynamical system: methodology and application[J]. Unmanned Systems Technology, 2018, 1(1): 72-82. (in Chinese) Cited in this article [1]

[15]

FAROOQ

M U

, ZHEN

, EJAZ

, et al. Quadrotor UAVs flying formation reconfiguration with collision avoidance using probabilistic roadmap algorithm[C]//Proceedings of International Conference on Computer Systems, Electronics and Control. Dalian,Liaoning,China:ICCSEC,2017, 2017:866-870.

Cited in this article [1]

[16]

高升, 艾剑良, 王之豪. 混合种群RRT无人机航迹规划方法[J]. 系统工程与电子技术, 2020, 42(1): 101-107.

https://doi.org/10.3969/j.issn.1001-506X.2020.01.14

Abstract

快速扩展随机树（rapidly-exploring random tree，RRT）无人机航迹规划方法能够快速获得满足约束要求的可行航迹，但是无法获得接近最短航迹的较优航迹。针对航迹的最优性问题，提出了混合种群RRT无人机航迹规划方法。在基于环境势场的RRT算法的基础上，设计了一种种群优化方法，通过引入自优化种群和协同优化种群改善航迹段，使算法同时具有局部和全局寻优能力。在得到航迹节点的基础上，采用B样条曲线的平滑方法生成曲率连续的可跟踪航迹。仿真结果表明，所提算法能够综合考虑无人机航程代价和雷达威胁代价，快速地收敛得到接近最优且满足无人机动力学约束的可行航迹，在不同环境下也能有满意的收敛效率。

GAO

, AI

J L

, WANG

Z H

. Mixed population RRT algorithm for UAV path planning[J]. Systems Engineering & Electronics, 2020, 42(1): 101-107. (in Chinese)

Cited in this article [1]

[17]	王生印, 龙腾, 王祝, 等. 基于即时修复式稀疏A^算法的动态航迹规划[J]. 系统工程与电子技术, 2018, 40(12): 2714-2721. WANG S Y, LONG T, WANG Z, et al. Dynamic path planning using anytime repairing sparse A^ algorithm[J]. Systems Engineering & Electronics, 2018, 40(12): 2714-2721. (in Chinese) Cited in this article [1]

[18]

张韬, 项祺, 郑婉文, 等. 基于改进A^*算法的路径规划在海战兵棋推演中的应用[J]. 兵工学报, 2022, 43(4): 960-968.

https://doi.org/10.12382/bgxb.2021.0209

Abstract

为满足海战兵棋推演中多目标路径规划的需求，解决传统A*算法无法在兵棋推演中直接运用的问题，提出一种可供类似兵棋推演环境参考、基于改进A*算法的路径规划方法。建立一种映射机制，实现了A*算法在兵棋推演环境中的初步运用。构建一种既能满足多目标需求又能保证生成最优路径的估价函数。为验证算法有效性，在实际推演平台上进行了相关实验。结果表明，改进A*算法可较好地统筹多个决策目标之间的关系，有效提升路径方案的质量，解决使用A*算法在海战兵棋推演中进行最优路径规划的实际问题。

ZHANG

, XIANG

, ZHENG

W W

, et al. Application of path planning based on improved A^* algorithm in war gaming of naval warfare[J]. Acta Armamentarii, 2022, 43(4): 960-968. (in Chinese)

Cited in this article [1]

[19]

HUANG

, CHEN

J G

, WANG

H L

, et al. A method of 3D path planning for solar-powered UAV with fixed target and solar tracking[J]. Aerospace Science and Technology, 2019, 92(9): 831-838.

https://doi.org/10.1016/j.ast.2019.06.027

https://linkinghub.elsevier.com/retrieve/pii/S127096381930389X

Cited in this article [1]

[20]

李文博, 秦小林, 罗刚. 基于无障碍凸区域的无人机在线航迹规划[J]. 系统科学与数学, 2021, 41(6): 1493-1506.

W B

, QIN

X L

, LUO

. Online trajectory planning of UAV based on convex obstacle-free area[J]. Journal of Systems Science and Mathematical Sciences, 2021, 41(6): 1493-1506. (in Chinese)

https://doi.org/10.12341/jssms20355

Cited in this article [1] Abstract

A method based on obstacle-free convex area is proposed to solve the problem of UAV (Unmanned Aerial Vehicle) online trajectory planning. Firstly, A* algorithm based on probabilistic roadmap (PRM) is used to plan a global path off-line. Then, the path planned above is used for local planning by IRIS-Astar algorithm proposed in this paper. The large convex obstacle-free area of the current position is calculated by IRIS (Iterative Regional Inflation By Semidefinite Programming) algorithm, which is used to find a global path point farthest from the current track point to be taken as the local target point. As the UAV travels towards the local target point, the large convex area of the current position is calculated in real time, at the same time, whether the local target point is in this area is judged. If it is, continue to travel towards the local target point; otherwise, the local target point is recalculated. Experimental results show that compared with traditional algorithms, the proposed method can effectively solve the collision avoidance problem of UAV and greatly reduce the energy consumption of UAV.

[21]	WU Y, WU S, HU X. Multi-constrained cooperative path planning of multiple drones for persistent surveillance in urban environments[J]. Complex & Intelligent Systems, 2021, 7(3): 1633-1647. Cited in this article [1]

[22]

ZHANG

, WU

, DAI

J Y

, et al. Optimal path planning with modified A-Star algorithm for stealth unmanned aerial vehicles in 3D network radar environment[J]. Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, 2022, 236(1): 72-81.

https://doi.org/10.1177/09544100211007381

http://journals.sagepub.com/doi/10.1177/09544100211007381

Cited in this article [1] Abstract

For stealth unmanned aerial vehicles (UAVs), path security and search efficiency of penetration paths are the two most important factors in performing missions. This article investigates an optimal penetration path planning method that simultaneously considers the principles of kinematics, the dynamic radar cross-section of stealth UAVs, and the network radar system. By introducing the radar threat estimation function and a 3D bidirectional sector multilayer variable step search strategy into the conventional A-Star algorithm, a modified A-Star algorithm was proposed which aims to satisfy waypoint accuracy and the algorithm searching efficiency. Next, using the proposed penetration path planning method, new waypoints were selected simultaneously which satisfy the attitude angle constraints and rank-K fusion criterion of the radar system. Furthermore, for comparative analysis of different algorithms, the conventional A-Star algorithm, bidirectional multilayer A-Star algorithm, and modified A-Star algorithm were utilized to settle the penetration path problem that UAVs experience under various threat scenarios. Finally, the simulation results indicate that the paths obtained by employing the modified algorithm have optimal path costs and higher safety in a 3D complex network radar environment, which show the effectiveness of the proposed path planning scheme.

[23]

ZHANG

, WU

, DAI

J Y

, et al. A novel real-time penetration path planning algorithm for stealth UAV in 3D complex dynamic environment[J]. IEEE Access, 2020, 8: 122757-122771.

https://doi.org/10.1109/Access.6287639

https://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=6287639

Cited in this article [1]

[24]	GAO F X, DING J F, LIU Z C, et al. An improved A^* algorithm for UAV path planning[C]//Proceedings of 2021 IEEE International Conference on Electrical Engineering and Mechatronics Technology.Qingdao,Shandong, China:ICEEMT, 2021: 772-776. Cited in this article [1]

Collection(s)

Intelligent Systems and Equipment

Accesses

Citation

Detail

Sections

Recommended

Abstract
Key words
QR code of this article
Cite this article
0 Introduction
1 Multi-UAV combat environment model
1.1 Operational environment description
1.2 Operational terrain model
1.3 Environmental threat model
1.3.1 Adverse Climate Threat Area Model
Fig.1 Adverse climate threat zone
1.3.2 Radar Threat Area Model
Fig.2 Radar threat zone
1.3.3 Threat area of air defense missile
Fig.3 Air defense missile threat zone
2 Multi-UAV Cooperative Attack Route Generation
Fig.4 Horizontal plane node expansion mode of SAS algorithm
Fig.5 Vertical plane node expansion mode of SAS algorithm
2.1 Multi-UAV Four-dimensional Cooperative Attack Route Generation Algorithm Based on T/S-SAS Algorithm
2.1.1 Improved model of flight expansion node
Fig.6 Improved model of flight node expansion
2.1.2 Algorithm Architecture Design Based on Concurrent Extension
Fig.7 Planning process of concurrent expansion algorithm
2.1.3 Time coordination cost calculation model
2.1.4 Constraint model of multi-aircraft collision avoidance
Fig.8 Realization of anti-collision constraints
2.2 Multi-UAV Four-dimensional Cooperative Attack Route Generation Algorithm Based on T/S-SAS Algorithm
Fig.9 Algorithm flow of the generation of multi-UAV four-dimensional cooperative attack route based on T/S-SAS algorithm
3 Simulation verification and analysis
3.1 Initial parameter setting
Table 1 Environment threat parameters
Table 2 Related algorithm name and algorithm improvement description
3.2 Simulation Verification and Analysis of Planning
3.2.1 Verification of efficiency and effectiveness of algorithm planning
Table 3 Starting point and target point parameters of algorithm planning efficiency test
Fig.10 Planning result comparison of traditional SAS algorithm and I-SAS algorithm
Fig.11 Data comparison between traditional SAS algorithm and I-SAS algorithm under different number of expanded nodes
3.2.2 Multi-UAV Cooperative Planning-Time Cooperative Validity Verification
Table 4 Starting point and target point parameters of time coordination test
Fig.12 Planning result comparison of I-SAS algorithm and IT-SAS algorithm
Fig.13 Data comparison between I-SAS algorithm and IT-SAS algorithm under different target location settings
3.2.3 Multi-UAV Cooperative Planning-Space Cooperative Effectiveness Verification
Table 5 Starting point and target point parameters of space coordination test
Fig.14 Planning result comparison of I-SAS algorithm and IS-SAS algorithm
Fig.15 Data comparison between I-SAS algorithm and IS-SAS algorithm under different safety distances
3.2.4 Effectiveness Verification of Multi-UAV Cooperative Four-dimensional Attack Route Generation
Table 6 Starting point and target point parameters of time/space coordination test
Fig.16 Planning result comparison of different algorithms
4 Conclusion
References

Received	Published
2022-03-30	2023-07-19
Just Accepted Date	Issue Date
2022-07-23	2023-06-30

模态框（Modal）标题

Please choose a citation manager

Content to export

Abstract

Key words

QR code of this article

Cite this article

0 Introduction

1 Multi-UAV combat environment model

1.1 Operational environment description

1.2 Operational terrain model

1.3 Environmental threat model

1.3.1 Adverse Climate Threat Area Model

Fig.1 Adverse climate threat zone

1.3.2 Radar Threat Area Model

Fig.2 Radar threat zone

1.3.3 Threat area of air defense missile

Fig.3 Air defense missile threat zone

2 Multi-UAV Cooperative Attack Route Generation

Fig.4 Horizontal plane node expansion mode of SAS algorithm

Fig.5 Vertical plane node expansion mode of SAS algorithm

2.1 Multi-UAV Four-dimensional Cooperative Attack Route Generation Algorithm Based on T/S-SAS Algorithm

2.1.1 Improved model of flight expansion node

Fig.6 Improved model of flight node expansion

2.1.2 Algorithm Architecture Design Based on Concurrent Extension

Fig.7 Planning process of concurrent expansion algorithm

2.1.3 Time coordination cost calculation model

2.1.4 Constraint model of multi-aircraft collision avoidance

Fig.8 Realization of anti-collision constraints

2.2 Multi-UAV Four-dimensional Cooperative Attack Route Generation Algorithm Based on T/S-SAS Algorithm

Fig.9 Algorithm flow of the generation of multi-UAV four-dimensional cooperative attack route based on T/S-SAS algorithm

3 Simulation verification and analysis

3.1 Initial parameter setting

Table 1 Environment threat parameters

Table 2 Related algorithm name and algorithm improvement description

3.2 Simulation Verification and Analysis of Planning

3.2.1 Verification of efficiency and effectiveness of algorithm planning

Table 3 Starting point and target point parameters of algorithm planning efficiency test

Fig.10 Planning result comparison of traditional SAS algorithm and I-SAS algorithm

Fig.11 Data comparison between traditional SAS algorithm and I-SAS algorithm under different number of expanded nodes

3.2.2 Multi-UAV Cooperative Planning-Time Cooperative Validity Verification

Table 4 Starting point and target point parameters of time coordination test

Fig.12 Planning result comparison of I-SAS algorithm and IT-SAS algorithm

Fig.13 Data comparison between I-SAS algorithm and IT-SAS algorithm under different target location settings

3.2.3 Multi-UAV Cooperative Planning-Space Cooperative Effectiveness Verification

Table 5 Starting point and target point parameters of space coordination test

Fig.14 Planning result comparison of I-SAS algorithm and IS-SAS algorithm

Fig.15 Data comparison between I-SAS algorithm and IS-SAS algorithm under different safety distances

3.2.4 Effectiveness Verification of Multi-UAV Cooperative Four-dimensional Attack Route Generation

Table 6 Starting point and target point parameters of time/space coordination test

Fig.16 Planning result comparison of different algorithms

4 Conclusion

{{custom_sec.title}}

{{custom_sec.title}}

References

{{custom_fnGroup.title_en}}

Footnotes