Sage Journals: Discover world-class research

Abstract

Heterogeneous UAVs performing patrol tasks are a new type of border patrol method with high flexibility, high patrol efficiency, and low operating cost In order to improve the ability of heterogeneous UAVs to perform border patrol task, by constructing a three-dimensional complex coordinated planning model, a multi-objective fitness function with the minimum patrol energy consumption and maximum patrol coverage of UAVs in a complex mountain environment is established. Design an improved shuffled frog leaping algorithm (ISFLA) based on spiral search mechanism to solve the problem of task planning in complex mountain environment. The proposed algorithm is verified by simulation experiments. The simulation results show that the ISFLA algorithm for solving the path problem in complex three-dimensional environment has significantly improved the solving efficiency, accuracy and global convergence compared with the particle swarm optimization (PSO), differential evolution (DE) and shuffled frog leaping algorithm (SFLA). The experiments show that the proposed algorithm also has excellent solving ability in solving complex planning problems.

Keywords

heterogeneous UAVs border patrol shuffled frog leaping algorithm patrol task planning track planning

Introduction

In recent years, terrorist activities, smuggling, drug trafficking and other forms of crimes harmful to national public security in border areas have gradually shown a diversified and concealed development trend, and traditional border patrol methods have been unable to adapt to the current requirements of border patrol. At present, the lack of border control facilities is serious, and the problems of difficult manual patrols, low patrol frequency and inadequate patrol supervision are becoming more and more prominent, especially in complex mountainous areas, so the adoption of a new patrol method to replace manual patrols has become a new trend in the development of border patrol. Unmanned aerial vehicles (UAVs) have been widely used in the patrol field due to their flexibility, adaptability and low production costs, and heterogeneous UAVs are more adaptable to the environment and meet the needs of the actual patrol process than a single type of UAV for border patrol. Heterogeneous UAVs have also been widely used in power patrols,¹ combat missions,² etc.

In complex mountainous border areas, the border patrol environment is more complex and the terrain is more variable, while the patrol frequency and accuracy in the border area are also required to be higher due to the global epidemic, so the energy consumption of UAVs in the patrol process and the coverage of UAVs on patrol points also become one of the main factors affecting the quality of the patrol task. Unlike general patrol methods, UAVs have more environmental and physical limitations in patrolling in complex mountainous environments, so the core problem of performing border patrol missions with heterogeneous UAVs can be approximated as the Multiple Travelling Salesman Problem (MTSP) under complex constraints.³

At this stage, the research on UAV trajectory planning at home and abroad is mainly focused on the research of multiple UAVs of the same type,^4–6 and only a few studies have been conducted on the trajectory planning of heterogeneous UAV groups.^2,7 For example, in,^8,9 a multi-objective optimization model for UAVs in a mission context was constructed by considering the range cost, altitude cost, and safety cost of UAVs in combination with the constraints on the physical performance of UAVs. In,¹⁰ an optimization model was developed to optimize the energy consumption of the UAV in the process of delivering goods in the process of UAV delivery, considering the reduction of the weight of the goods with the delivery process. In¹¹ is more specific in analyzing the power output of the power system in each stage of the UAV Logistics distribution process separately to build a mathematical model for the lowest energy consumption of theUAV in the delivery process. In^12–14 analyze the motion process of the UAV and build a kinematic model of the UAV, and further consider the mission requirements of the UAV to build an optimized model of the UAV trajectory.

In terms of algorithm solution, the traditional A^*₁₅ algorithm, Dijkstra algorithm¹⁶ and other path planning algorithms can quickly and accurately solve the two-dimensional path planning problem, but with the increase of the problem-solving dimension and the complexity of the model, the data needed to be solved increases exponentially. Therefore, the traditional algorithm is difficult to meet the planning requirements in solving the UAV path planning whether the solving efficiency or the solving accuracy. At the same time, because the swarm intelligence algorithm has the advantages of simple structure, high solving efficiency and strong robustness, the swarm intelligence algorithm is also widely used in the UAV path planning. At present, the intelligent optimization algorithm for UAV path planning problem is mainly based on heuristic algorithm,¹⁷ because it has better advantages in solving the UAV path planning problem under complex constraints than the accurate algorithm in solving efficiency and accuracy. Therefore, intelligent optimization algorithms such as heuristic algorithm¹⁸ have become one of the key directions of current domestic and foreign scholars. For example, In the literature^19–21 conducted in-depth research on the UAV path planning problem based on genetic algorithm, and literature²² designed a clustering ant colony algorithm to solve the optimal solution of the established model for the UAV path planning requirements in three-dimensional complex urban environment. In addition, particle swarm optimization algorithm,²³ differential evolution algorithm,²⁴ frog leaping algorithm²⁵ and other optimization algorithms are also widely used in the field of UAV path planning.

In summary, the current domestic and foreign scholars in the establishment of UAV planning model mainly consider the energy consumption of UAV in the process of task allocation, and ignore the influence of UAV differences in the process of task execution. At present, only a few literatures have studied the situation of heterogeneous UAVs. At the same time, combined with the task requirements of real border patrols, it is necessary to propose a task planning and track planning method for heterogeneous UAVs for border patrol tasks, so that heterogeneous UAVs are used to perform border patrol tasks more suitable for actual needs. The main innovations of this paper are as follows:

Based on the complex mountainous environment and the dynamic characteristics of UAV, the UAV task planning and track planing model in the quasi-real environment are established;

In view of the fact that the optimization effect of the traditional shuffled frog leaping algorithm is excessively dependent on the initialization parameters, an improved hybrid differential based on adaptive step size factor shuffled frog leaping algorithm was proposed and applied to the task planning and path planning of border patrol of heterogeneous UAVs. Compared with the other three frontier algorithms, the solution accuracy is greatly improved.

Heterogeneous UAVs group patrol model in Complex mountain environment

Problem formulation

There is a police UAV base in a border area, which is equipped with several UAVs of different batches and types, and the area contains a large number of mountains, rivers and other complex terrain environments. The patrolling mode of the heterogeneous UAVs is as follows: the points to be patrolled by each UAV are planned before the UAVs takes off, and then the UAVs takes off to patrol each patrol point in turn according to the planned patrol points, until the patrol of the planned patrol points is completed and then returns to the UAV base.

Model assumptions

To better describe how heterogeneous UAVs perform border patrol tasks, this paper made the following assumptions:

Good flying conditions for the UAVs in the patrol area being flown, with no adverse weather conditions such as high winds, precipitation, fog or lightning.

UAVs are considered to fly at constant speeds on each discrete track segment during patrol task without complex movements, such as drone roll, etc.

This article ignores the energy loss caused by drone pitching and yawing.

The UAV's surroundings’ air density and drag coefficient remain constant during the patrol task.

the locations of the points to be patrolled by the UAV on patrol are known and can be defined according to the patrol task requirements.

Establishment of mathematical models

Construction of border patrol environment model

When drones perform border patrol missions, they are threatened by wind shear, military restricted areas, and magnetic fields. When drones enter such areas, they will be shot down or bombed. Therefore, this article is based on the real environment of a mountainous border area, Comprehensive consideration of threats such as wind shear, through the use of mountain environment functions to complete the establishment of the mountain environment and other threatened areas:

P (x, y) = \sum_{i = 1}^{n} h_{i} \exp [- {(\frac{x - x_{i}}{x_{s i}})}^{2} - {(\frac{y - y_{i}}{y_{s i}})}^{2}]

(1)

where

(x_{i}, y_{i})

is the central coordinate of peak i,

h_{i}

is the height of peak i,

x_{s t}

and

y_{s t}

are the height decay of the peak i in the x and y directions respectively, Control of the danger zone can be achieved directly through the control of the above variables, as shown in the following Figure 2.

Figure 1.

Topographical map of the mountain patrol area.

Figure 2.

Environmental fitting model.

Construction of mathematical model for UAV border patrol

From the literature²³ through the force test analysis of multi-rotor UAV in 3-dimensional space, it can be seen that when the UAV motor output voltage is constant, the power load of the quadrotor UAV can be approximated as a constant through multiple test experimental sampling analysis, and the power load expression is:

q = \frac{\sum F}{P}

(2)

where q A is the power load of the quadcopter UAV,

\sum F

is the total lift of the quadrotor UAV at a constant voltage, P is the power consumed by the quadrotor UAV to generate that lift.

The relationship between the combined force on the UAV and the power consumed by the UAV can therefore be deduced to be proportional:

\sum F = P \cdot q

(3)

Since the speed

v_{i j}^{A}

of the flight of any UAV A is known, the time of flight of UAV A on any path segment can be expressed as

t_{i j}^{A} = \frac{d_{i j}^{A}}{v_{i j}^{A}}

(4)

Where

t_{i j}^{A}

is the flight time of UAV A from waypoint i to j,

d_{i j}^{A}

is the distance from point i to j of A's path.

When UAV A is flying, the air resistance $f_{A}$ experienced by UAV is:

f_{A} = \frac{1}{2} C ρ S v^{2}

(5)

Where

f_{A}

is the air resistance of the drone A during the patrol mission, C is the coefficient of air resistance,

ρ

is the air density, S is the windward area when the drone is flying, v is the flying speed of the UAV during the patrol task.

The process of the UAV's patrol task on any path segment $i - j$ can be decomposed into the z axis in the direction of gravity and the $x o y$ plane perpendicular to the z axis, Since the UAVs fly at a uniform speed during all patrol task, the flight speed of the UAV can be projected in both directions on any path segment $i - j$ . The speed of the UAV in the z axis and $x o y$ plane are:

v_{z_i j}^{A} = {\begin{matrix} v_{u_i j}^{A} = \frac{z_{j}^{A} - z_{i}^{A}}{d_{i j}^{A}} \cdot v_{i j}^{A}, z_{j}^{A} > z_{i}^{A} \\ v_{d_i j}^{A} = \frac{z_{i}^{A} - z_{j}^{A}}{d_{i j}^{A}} \cdot v_{i j}^{A}, z_{j}^{A} < z_{i}^{A} \end{matrix}

(6)

v_{x o y_i j}^{A} = \frac{\sqrt{{(x_{j}^{A} - x_{i}^{A})}^{2} + {(y_{j}^{A} - y_{i}^{A})}^{2}}}{d_{i j}^{A}} \cdot v_{i j}^{A}

(7)

where

v_{z_i j}^{A}

is the speed projection of the UAV in the z axis direction when flying,

v_{u_i j}^{A}

is the speed projection of the UAV climbing in the vertical direction,

v_{d_i j}^{A}

is the projection of the descending speed of the UAV in the vertical direction,

v_{x o y_i j}^{A}

is the speed projection on the

x o y

plane when the drone is flying,

v_{i j}^{A}

is the actual speed of the drone during flight.

In the same way, the force exerted by the UAV during the patrol mission can also be decomposed into the z axis direction and the horizontal $x o y$ plane:

F_{z_i j}^{A} = {\begin{matrix} F_{u z_i j}^{A} = G_{A} + f_{z_A}, z_{j}^{A} > z_{i}^{A} \\ F_{d z_i j}^{A} = G_{A} - f_{z_A}, z_{j}^{A} < z_{i}^{A} \end{matrix}

(8)

F_{x o y_i j}^{A} = \sqrt{G_{A}^{2} + f_{x o y_A}^{2}}

(9)

F_{i j}^{A} = [\begin{matrix} F_{x o y_i j}^{A} \\ F_{z_i j}^{A} \end{matrix}]

(10)

where

F_{z_i j}^{A}

is the force projection in the z axis direction when the UAV is flying,

F_{u z_i j}^{A}

is the force projection when the UAV climbs in the vertical direction,

F_{d z_i j}^{A}

is the force projection when the UAV descends in the vertical direction,

F_{x o y_i j}^{A}

is the force projection on the

x o y

plane when the UAV is flying,

F_{i j}^{A}

is the resultant force experienced during the flight of the UAV,

G_{A}

is the gravity experienced by the UAV during flight,

f_{z_A}

is the air resistance projection in the z direction when the UAV is flying,

f_{x o y_A}

is the air resistance projection on the

x o y

plane when the drone is flying.

Since the total lift of the UAV is proportional to the total power of the drone, the total energy consumption during the flight of the heterogeneous UAVs group can be derived:

J = \frac{1}{q} \cdot \sum_{A = 1}^{} \sum_{i = 1}^{} \sum_{j = 1}^{} F_{i j}^{A} \cdot t_{i j}^{A}

(11)

At the same time, according to the importance of different patrol points, the patrol points of the UAV are optimized by introducing the importance weight of patrol points²⁶:

W_{a l l} = \sum_{i = 1}^{M} (W_{i} \cdot X_{i})

(12)

X_{i} = {\begin{matrix} 0, UAV reaches patrol point i \\ 1, other \end{matrix}

(13)

Where

W_{a l l}

is the total weight of the patrol point weight，

W_{i}

is the weight of the importance of any patrol point i,

X_{i}

is a two-dimensional variable.

In summary, the final optimization goal can be obtained as:

min : f = \frac{J}{W_{a l l}}

(14)

Constraints

Maximum energy constraint for UAV:

J_{U A V}^{A} = \sum_{i = 1}^{} \sum_{j = 1}^{} P_{i j}^{A} \cdot t_{i j}^{A} \leq J_{max}^{A}, \forall : A \in {1, 2, \cdot \cdot \cdot}

(15)

Maximum climb speed of the UAV:

v_{u_i j}^{A} \leq v_{u_max}^{A}, \forall \in {1, 2, \cdot \cdot \cdot}

(16)

Maximum descent speed of the UAV:

v_{d_i j}^{A} \leq v_{d_max}^{A}, \forall \in {1, 2, \cdot \cdot \cdot}

(17)

Return of UAV to UAV base:

\sum_{i = 1}^{} X_{i j}^{A} - \sum_{k = 1}^{} X_{j k}^{A} = 0, \forall : A \in {1, 2, \cdot \cdot \cdot}

(18)

The UAV patrols each patrol point once:

\sum_{A = 1}^{} \sum_{i = 1}^{} X_{i j}^{A} = 1, \forall : j \in {1, 2, \cdot \cdot \cdot}

(19)

Algorithm description

Shuffled frog leaping algorithm

The shuffled frog leading algorithm is a bionic swarm intelligence algorithm proposed in 2000 to solve large-scale continuous optimization problems. In the shuffled frog leading algorithm, the position of each frog represents a feasible solution to the problem. There are small islands in the water area where the frog is located. In the initialization phase of the algorithm, each frog is assigned to on each island, as shown in Figure 3.

Figure 3.

Sketch Map of the population division.

In the update phase of the algorithm, the frog with the worst fitness value on each island will move to the frog with the best fitness value on the island. If the new location has better fitness than the original location, the frog will accept it. This position, otherwise, will approach the optimal global frog. If the new position has better fitness than the original position, the frog will accept this position; otherwise, the frog will move randomly in space.

The basic steps of the shuffled frog leading algorithm are as follows:

Step 1. Initialize the parameters and randomly generate the initial population in the solution space.

Step 2. Parameter setting $n = 1.$

Step 3. Calculate the fitness function value of the individuals in the population, arrange them in ascending order, and assign them to N islands.

Step 4. Update the location $X_{w o r s t}^{i}$ of the worst-fit frog on the n-th island. Assuming that the best-fit frog on the n-th island is $X_{b e s t}^{i}$ , the frog's location update strategy is as follows:

X_{w o r s t}^{i} = X_{w o r s t}^{i} + r a n d ([0, 1], 1, D) \times (X_{b e s t}^{i} - X_{w o r s t}^{i})

(20)

Where,

r a n d ([0, 1], 1, D)

Represents generating a row vector of length D with element values between 0 and 1, D represents the dimension of the problem. Calculate the fitness value of the new location, If the new position is better than the original position, accept the new position and proceed to Step 5, otherwise, follow the global optimal frog

X_{b e s t}^{g l o b a l}

to search:

X_{w o r s t}^{i} = X_{w o r s t}^{i} + r a n d ([0, 1], 1, D) \times (X_{b e s t}^{g l o b a l} - X_{w o r s t}^{i})

(21)

Calculate the fitness value of the new position. If the new position is better than the original position, accept the new position and proceed to Step 5, otherwise, move randomly in the solution space:

X_{w o r s t}^{i} = r a n d ([l b, u b], 1, D)

(22)

l b

and

u b

respectively represent the upper limit of the search space and the lower limit of the search space. After moving, proceed to Step 5.

Step 5. Determine if n is equal to N. If so, proceed to Step 4, otherwise, return to Step 3.

Step 6. Determine whether the maximum number of iterations, is the exit, otherwise Step 2.

Although the shuffled frog leading algorithm is less complex and requires less time to solve the problem, the optimization effect of the algorithm is greatly affected by the initialization. Whether the algorithm can be further optimized depends entirely on the ability of the worst-adapted frog on each island. It is impossible to find a better position than the current position of the frog with the best fitness, so the hybrid leap frog algorithm is not suitable for large-scale applications. On this basis, the differential crossover strategy is introduced for algorithm mixing to solve the problem that the shuffled frog leading algorithm quickly falls into stagnation，the adaptive step factor is introduced to further improve the hybrid algorithm.

improved hybrid differential based on adaptive step size factor shuffled frog leaping algorithm

Difference crossover strategy

In the traditional SFLA algorithm, the algorithm optimization mainly relies on the location update of the worst-adapted frogs on each island, the ability of these frogs to develop the solution space is one of the essential conditions for determining whether the algorithm can find the optimal solution, when the frog is looking for a new position, it does not find a better position than the position of the current optimal frog, so the algorithm will not be optimized, resulting in stagnation. Therefore, in order to ensure that all frogs can participate in the position update, the introduction Differential crossover strategy.

First, the mutant population is generated through the linear combination of different individuals. The generation of the mutant individuals is as follows:

{\begin{matrix} V_{i} = X_{r 1} + F \times (X_{r 2} - X_{r 3}) \\ r 1, r 2, r 3 \in Z \\ r 1, r 2, r 3 \in [1, N P] \\ r 1 \neq r 2 \neq r 3 \end{matrix}

(23)

r 1, r 2, r 3

represent a random integer,

N P

is the population size, F is the difference factor.

After the generation of the variant population, the variant population will be sorted instead of the original population and assigned to each island, updated in position according to equation (20) (21) (22) and crossed with the original population after the variant population has been updated.

{\begin{matrix} {\begin{matrix} U_{i} (j) = V_{i} (j) r n d < C R | j = k \\ U_{i} (j) = X_{i} (j) e l s e \end{matrix} \\ r n d \in [0, 1] \\ j \in Z, j \in [1, D] \\ k \in Z, k \in [1, D] \end{matrix}

(24)

U_{i} (j)

denotes the j-th variable for the i-th individual in the crossover population,

C R

is the crossover probability,

r n d

is a random number, k is the random number generated before the crossover, k is the variable that is used to ensure that there is at least one set of variant populations in the crossover population.

The crossover population is then combined with the original population, fitness values are calculated and the better-adapted individuals are kept, the number of individuals retained should not exceed $N P$ .

Adaptive step factor

In the traditional SFLA algorithm, a random number is used for the step length of the following search; that is, the following search only guarantees the search direction of the individual, and the search step has certain randomness, which may cause the algorithm to converge slowly, so the adaptive step is introduced. The length factor, the step length factor, will be adjusted according to the distance between the two individuals to control the distance that the individual moves. After adopting the adaptive step length factor, the formula (20) (21) becomes:

X_{w o r s t}^{i} = X_{w o r s t}^{i} + \frac{\exp (| X_{b e s t}^{i} - X_{w o r s t}^{i} |) + β - 1}{β \exp (| X_{b e s t}^{i} - X_{w o r s t}^{i} |)} \times (X_{b e s t}^{i} - X_{w o r s t}^{i})

(25)

X_{w o r s t}^{i} = X_{w o r s t}^{i} + \frac{\exp (| X_{b e s t}^{g l o b a l} - X_{w o r s t}^{i} |) + β - 1}{β \exp (| X_{b e s t}^{g l o b a l} - X_{w o r s t}^{i} |)} \times (X_{b e s t}^{g l o b a l} - X_{w o r s t}^{i})

(26)

The changing trend of the adaptive step factor with individual distance is shown in Figure 4.

Figure 4.

Adaptive step factor.

Solution of the model

Data and experimental environment

In the calculation experiment of this paper, we take the environmental data of a plateau mountainous area in southwestern China as the simulation background. In the simulation experiment designed in this paper, there are five available UAVs (which can be divided into three types), and a total of 30 points need to be inspected. The experimental background is a mountainous environment with 3000 m * 3000 m of seven threat areas. In this experiment, the planning of UAV patrol tasks and the track planning of each UAV are mainly studied in a certain period according to the requirements of patrol tasks. The UAV parameters are shown in Table 1 and the mountain threat area parameters are shown in Table 2.

Table 1.

UAVs parameter setting.

UAV parameters	Numerical value
UAV weight	7kg
UAV maximum climb speed	5 m/s
UAV maximum descent speed	4 m/s
Maximum energy of three types of drones	986400 J
	887760 J
	838440J
UAV vertical windward area	0.181m²
UAV horizontal windward area	0.183 m²
UAV power load	0.8598

Table 2.

Parameter setting of mountain peak model.

Coordinates of the center of the mountain /m	Mountain height /m	Attenuation in the x direction of the mountain /m	Attenuation in the y direction of the mountain /m
(300,2300)	70	300	400
(1100,2150)	65	280	453
(1780,2240)	54	383	401
(2700,1985)	38	650	875
(1200,650)	57	600	500
(2800,550)	65	656	556
(200,1200)	47	278	285

In this paper, the experimental environment for the model and algorithm is Interi7 - 9750H CPU (2.60 GHz) with memory of 16 Gb, and the simulation software is Matlab2017b. At the same time, the improved shuffled frog leaping algorithm designed in this paper is simulated and compared with the traditional particle swarm algorithm, differential evolution algorithm and shuffled frog leaping algorithm.

Analysis of simulation results

Table 3 shows the comparison of the solution results of the proposed algorithm and SFLA, DE, PSO algorithms for the established mathematical model of heterogeneous UAVs border patrol. Figures 5, 6, 7 6, 7 and 8 show the simulation diagram of the four algorithms for solving the model. Figures 9, 10, 11 and 12 show the comparison diagram of the improved shuffled frog leaping algorithm designed in this paper with the other three preamble algorithms in four aspects of patrol task planning, patrol revenue, patrol track planning and patrol energy consumption.

Figure 5.

Schematic of ISFLA algorithm optimization.

Figure 6.

Schematic of SFLA algorithm optimization.

Figure 7.

Schematic of DE algorithm optimization.

Figure 8.

Schematic of PSO algorithm optimization.

Figure 9.

Comparison chart of UAVs patrol energy consumption algorithm.

Figure 10.

Comparison chart of UAVs patrol revenue algorithm.

Figure 11.

Comparison chart of UAVs track planning algorithms.

Figure 12.

Comparison chart of UAVs patrol optimization target algorithm.

Table 3.

Comparison of solution results of each algorithm.

Index algorithm	Value of Path	Energy Consumption	Patrol Income	Optimize the Target
ISFLA	15514.14	35926.66	148.3	242.2
SFLA	15540.17	43573.20	138.6	314.4
DE	15536.79	36575.34	139.1	262.9
PSO	15519.52	40834.15	147.6	276.7

Result analysis

The simulation test results show that the ISLFA algorithm proposed in this paper has a more significant improvement in solution accuracy and efficiency than the particle swarm algorithm, differential evolution algorithm, and hybrid frog-jumping algorithm. As shown in Figure 9, the optimization results of the ISLFA, SLFA, PSO, and DE algorithms for the objective function are 242.2, 314.4, 262.9, and 276.7, respectively. The solution accuracy of the ISLFA algorithm is 33.6%, 8.5%, and 12.4% higher than that of the SFLA, PSO, and DE algorithms, respectively. The patrol paths and patrol energy consumption are shown in Figure 5 and Table 3. The patrol gain is 6.99%, 6.75%, and 0.47% higher than the SFLA, PSO, and DE algorithms, respectively.

Conclusion

Compared with the single-type UAVs, the heterogeneous UAVs has better environmental adaptability and is more in line with the actual needs in the process of patrolling. Therefore, the use of heterogeneous UAVs to perform the border patrol task can effectively compensate for the problems existing in the single-type UAVs. In order to optimize the patrol coverage rate and energy consumption of heterogeneous UAVs groups in the implementation of border patrol tasks, this paper establishes a planning model for the border patrol of heterogeneous UAVs groups in complex mountainous environment based on the constraints in complex mountainous environment and the physical properties and kinematic laws of UAVs, and designs an improved shuffled frog leaping algorithm for solving the established UAVs planning model. Finally, the feasibility and effectiveness of the improved shuffled frog leaping algorithm proposed in this paper are effectively illustrated by the horizontal comparison between the simulation experiment and PSO, DE and SFLA algorithms. In the future research, we will focus on the environmental characteristics of plateau mountainous areas to carry out heterogeneous UAVs patrol planning research.

Footnotes

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) declared receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the Infrastructure Construction Project of Yunnan Power Grid Co., Ltd. under Grants 050000WS24140005, and in part by the Yunnan Provincial Science and Technology Project under Grants 202104AP080061.

ORCID iDs

Nan Pan

Shiyun Chen

Haishi Liu

Author biographies

Nan Pan (M'2015) was born in Tonglin, Anhui Province, P.R. China in 1986. He received the B. Sc. Degree in 2008 form Anhui University of Science & Technology and received Ph. D degree in 2012 form Kunming University of Science and Technology. From 2013 to 2017, he was a lecturer with the Faculty of Mechanical & Electrical Engineering, Kunming University of Science & Technology. And from 2017 to now, he was an associate professor with the Faculty of Civil Aviation and Aeronautical of Kunming University of Science & Technology. He is the author of more than 100 articles, and holds more than 100patents. His research interests include Swarm Intelligence and Deep Learning. Dr. Pan was selected to be the Kunming young academic and technical leaders in 2018 and Top young talents in Yunnan in 2019.

Miaohang Zhang was born in JI Xi, Heilongjiang Province. He graduated from Kunming University of Science and Technology, majoring in logistics engineering. He is now a Postgraduate in Faculty of Civil Aviation and Aeronautics, Kunming University of Science & Technology. His main research direction is Swarm Intelligence and Deep Learning.

Yuxuan Sun was born in Shijiazhuang, Heibei Province. He is now an undergraduate student in Faculty of Information Engineering and Automation, Kunming University of Science & Technology. His main research direction are Swarm Intelligence and Deep Learning.

Shiyun Chen was born in Dali, Yunnan Province. He is now an undergraduate student in Faculty of Civil Aviation and Aeronautics, Kunming University of Science & Technology. His main research direction are Swarm Intelligence and Deep Learning.

Haishi Liu was born in Hengshui, Heibei Province. He is now an undergraduate student in Faculty of Civil Aviation and Aeronautics, Kunming University of Science & Technology. His main research direction are Swarm Intelligence and Deep Learning.

Xiaojue Guo was born in Chuxiong City, Yunnan Province, P.R. China in 1991. She received the B. Sc. degree in 2013 from Nanjing University of Finance and Economics and received Master degree in 2017 from East China University of Political Science and Law. From 2020 to now, she was the General manager in Kunming ZhiYuan Measurement & Control Technology Co., Ltd. Her research interests include Intellectual Property and Project Management.

References

Zheng

Yongqiang

Hongxing

, et al. Design and application of UAV intelligent inspection system for transmission lines based on cloud and fog-edge heterogeneous collaborative computing architecture. Electr Power 2020; 53: 161–168. https://dx.doi.org/10.11930/j.issn.1004-9649.201907167

Liu

Chen

Pan

, et al. Three-Dimensional mountain Complex terrain and heterogeneous multi-UAV cooperative combat mission planning. IEEE Access 2020; 8: 197407–197419. https://dx.doi.org/10.1109/ACCESS.2020.3033408

Alaidi

AHM

Mahmood

. Distributed hybrid method to solve multiple traveling salesman problems. 2018 International Conference on Advance of Sustainable Engineering and its Application (ICASEA) 2018: 74–78. https://dx.doi.org/10.1109/ICASEA.2018.8370959

Pan

Yang

. A deep learning trained by genetic algorithm to improve the efficiency of path planning for data collection with multi-UAV. IEEE Access 2021; 9: 7994–8005. https://dx.doi.org/10.1109/ACCESS.2021.3049892

Qie

Shi

Shen

, et al. Joint optimization of multi-UAV target assignment and path planning based on multi-agent reinforcement learning. IEEE Access 2019; 7: 146264–146272. https://dx.doi.org/10.1109/ACCESS.2019.2943253

Qiao

Yang

Zhang

, et al. Multi-UAV cooperative patrol task planning novel method based on improved PFIH algorithm. IEEE Access 2019; 7: 167621–167628. https://dx.doi.org/10.1109/ACCESS.2019.2952877

Chen

Zhang

, et al. A clustering-based coverage path planning method for autonomous heterogeneous UAVs. Transactions on Intelligent Transportation Systems. 2021; 1–11 https://dx.doi.org/10.1109/TITS.2021.3066240

Honghai

ZHANG

Han

Hao

LIU

, et al. Path planning for logistics unmanned aerial vehicle in urban area. Journal of Transportation Systems Engineering and Information Technology 2020; 20: 22–29. https://dx.doi.org/10.16097/j.cnki.1009-6744.2020.06.003

Wenzhao

Naigang

Bei

, et al. Multiple UAV cooperative path planning based on PSO-HJ method. Journal of Chinese Inertial Technology 2020; 28: 122–128. https://dx.doi.org/10.13695/j.cnki.12-1222/o3.2020.01.019

10.

Haosen

Yangli

. Based on UAV delivery track planning algorithm. Information Technology and Informatization 2021; 6: 111–114. https://dx.doi.org/10.3969/j.issn.1672-9528.2021.06.032

11.

Yifei

ZHAO

Yuxin

ZHENG

. Construction and optimization of flight mission profile of urban logistics UAV. Flight Dynamics 2021; 39: 54–59. https://dx.doi.org/10.13645/j.cnki.f.d.20210417.004

12.

Yunfei

Defu

Duo

, et al. Task allocation and trajectory optimization of drones for multi-target time-space synchronization cooperative attack. Acta Armamentarii 2021(07): 1–14[2022-04-08]. https://kns.cnki.net/kcms/detail/11.2176.TJ.20210331.1400.004.html

13.

Jie

Mingfu

. Research on the control system of three degree of freedom picking manipulator based on DSP. Journal of Agricultural Mechanization Research 2022; 2: 28–38. https://dx.doi.org/10.13427/j.cnki.njyi.2022.02.005

14.

Huang

Chen

Pan

. Multiobjective UAV path planning for emergency information collection and transmission. Internet of Things Journal 2020; 7: 6993–7009. https://dx.doi.org/10.1109/JIOT.2020.2979521

15.

Shengyin

Teng

Zhu

, et al. Dynamic path planning using anytime repairing space A* algorithm. Syst Eng Electron 2018; 40: 2714–2721.

16.

Ningyi

Zhiqian

Yuqi

. Path planning algorithm of dijkstra-based intelligent aircraft under multiple constraints. Journal of Northwestern Polytechnical University 2020; 38: 1284–1290.

17.

Rui

Tao

. Review of unmanned aerial vehicle swarm path planning based on intelligent optimization. Control Theory Appl 2020; 37: 2291–2302.

18.

Cho

Kim

. Performance comparison of heuristic algorithms for UAV deployment with low power consumption. 2018 International Conference on Information and Communication Technology Convergence (ICTC) 2018: 1067–1069. 2018: 1067--1069. https://dx.doi.org/10.1109/ICTC.2018.8539485

19.

Dongwu

Hao

, et al. Application of genetic algorithm path planning in UAV power line patrol. Industry Control and Applications 2021; 40: 29–33.

20.

Shuzhao

Committee

, et al. Unmanned aerial vehicle path planning based on improved genetic algorithm. J Comput Applic 2021; 41: 390–397. https://dx.doi.org/10.11772/j.issn.1001-9081.2020060797

21.

Qian

Xiankun

Yujie

. UAV Path planning based on improved genetic algorithm. Journal of Navigation and Positioning 2020; 8: 42–48. https://dx.doi.org/10.16547/j.cnki.10-1096.20200507

22.

Xinting

. Risk-based discrete multi-path planning method for UAVs in urban environments. Acta Aeronautica et Astronautica Sinica 2021; 42: 463–474.

23.

Wang

Bai

Liang

, et al. Reconnaissance mission conducted by UAV swarms based on distributed PSO path planning algorithms. Access 2019; 7: 105086–105099. https://dx.doi.org/10.1109/ACCESS.2019.2932008

24.

Ruilian

Xinzhi

Qian

. Multiple UAV path planning based on improved differential evolution algorithm. Fire Control & Command Control 2020; 45: 169–173 + 179. https://dx.doi.org/10.3969/j.issn.10020640.2020.01.034

25.

Fang

. UAV Path planning based on shuffled frog-leaping algorithm and dubins path. 2020 39th Chinese Control Conference (CCC) 2020: 3990–3995. https://dx.doi.org/10.23919/CCC50068.2020.9188570

26.

Xiong

She

, et al. A path planning method for sweep coverage with multiple UAVs. IEEE Internet Things J 2020; 7: 8967–8978. https://dx.doi.org/10.1109/JIOT.2020.2999083

Study on border patrol task planning of heterogeneous UAVs group based on swarm intelligence

Abstract

Keywords

Introduction

Heterogeneous UAVs group patrol model in Complex mountain environment

Problem formulation

Model assumptions

Establishment of mathematical models

Construction of border patrol environment model

Construction of mathematical model for UAV border patrol

Constraints

Algorithm description

Shuffled frog leaping algorithm

improved hybrid differential based on adaptive step size factor shuffled frog leaping algorithm

Difference crossover strategy

Adaptive step factor

Solution of the model

Data and experimental environment

Analysis of simulation results

Result analysis

Conclusion

Footnotes

Declaration of Conflicting Interests

Funding

ORCID iDs

Author biographies

References