# A Novel Three-Dimensional Path Planning Method for Fixed-Wing UAV Using Improved Particle Swarm Optimization Algorithm

Authors: Chen Huang
Journal: International Journal of Aerospace Engineering
 (2021)

---

## Abstract

This paper proposed an improved particle swarm optimization (PSO) algorithm to solve the three-dimensional problem of path planning for the fixed-wing unmanned aerial vehicle (UAV) in the complex environment. The improved PSO algorithm (called DCA∗PSO) based dynamic divide-and-conquer (DC) strategy and modified A∗ algorithm is designed to reach higher precision for the optimal flight path. In the proposed method, the entire path is divided into multiple segments, and these segments are evolved in parallel by using DC strategy, which can convert the complex high-dimensional problem into several parallel low-dimensional problems. In addition, A∗ algorithm is adopted to generated an optimal path from the particle swarm, which can avoid premature convergence and enhance global search ability. When DCA∗PSO is used to solve the large-scale path planning problem, an adaptive dynamic strategy of the segment selection is further developed to complete an effective variable grouping according to the cost. To verify the optimization performance of DCA∗PSO algorithm, the real terrain data is utilized to test the performance for the route planning. The experiment results show that the proposed DCA∗PSO algorithm can effectively obtain better optimization results in solving the path planning problem of UAV, and it takes on better optimization ability and stability. In addition, DCA∗PSO algorithm is proved to search a feasible route in the complex environment with a large number of the waypoints by the experiment.


---

## Body

## 1. Introduction

### 1.1. Background and Motivation

In recent years, with the development of sensor technology and intelligent control technology, unmanned aerial vehicle (UAV) has been widely used in military and civil fields, such as reconnaissance [1, 2], surveillance [3], target prosecution [4], wireless communications [5, 6], and oilfield inspection [7]. As a basic technology for autonomous navigation of the UAV system [8], the path planner is an important component to ensure the successful completion of the complex missions. The objective of path planning is to seek an optimal or near-optimal flight route from the starting position to the destination in the mission space under the required constraint conditions [9].The core of the path planning system is route planning algorithm, which has been actively researched for decades. Over the last few decades, a variety of approaches have been proposed to deal with path planning problem for UAV or autonomous robot. Most traditional path planning methods based on the graph are adaptive to 2-dimensional planning problems, such as Voronoi diagram algorithm [10], A∗ algorithm [11], and probabilistic roadmap algorithm. These methods are relatively easy to implement, but UAV kinematic and dynamic constraints are seldom considered by these algorithms. Meanwhile, these methods need more time and huge storage memory in a large space. Potential field-based methods, such as artificial potential field algorithm [12], can obtain a smooth path and has little calculation time. Its disadvantage lies that it is easy to trap into local minimum and even cannot find a feasible path when the distance between the target and the obstacles is near. Hence, potential field-based methods can seldom be used for the practical situations. Compared with the traditional methods, evolutionary computation (EC) algorithms have a strong ability to obtain high-quality solutions in path planning and are easier to implement [13]. The problem of trajectory planning is often treated as a nonlinear NP-hard optimal problem to be solved by evolutionary algorithms. It is well known that the ECs have made much progress and have been deeply and extensively studied in recent years [14–16]. EC algorithms, including evolutionary algorithms (EAs) and swarm intelligence algorithms (SIs), such as genetic algorithm (GA) [17], differential evolution (DE) [18, 19], particle swam optimization (PSO) [20–25], and ant colony optimization (ACO) [26], have been widely used in handling global optimization problems.In the application of route planning of the three-dimensional (3D) environment, it is necessary to require a higher ability to avoid collisions with terrain and much more complicated calculation than two-dimensional path planning. Therefore, how to further enhance convergence speed and solution quality of the planner will be a main motivation in a 3D complex environment. Moreover, as the environment and the planning task become increasingly complex, intelligent optimization algorithms have difficulty in dealing with the high dimension problems.


### 1.2. Related Work

ECs have been applied to find global or approximate global optimum path. Yang et al. [27] discovered the drawback that the high-quality waypoints in previous search can hardly be further exploited in evolutionary algorithm-based due to all the waypoints of a path as an integrated individual. Hence, a new idea of separately evaluating and evolving waypoints is proposed for two-dimensional UAV path planning. On the basis of Ref. [14], Huang [28] proposed an improved PSO algorithm based on the competition of global best solution and applied the path planner to a three-dimensional UAV to demonstrate. Zhang et al. [29] formulated an improved fruit fly optimization (MAFOA) based on the phase angle-encoded connected with mutation adaptation mechanisms to solve the unmanned aerial vehicle (UAV) path planning problem. Du et al. [30] proposed a hybrid evolutionary algorithm included the main algorithm and a subalgorithm. The main algorithm was to evolve a population of main solutions, and the subalgorithm was used to optimize each UAV path. Yang and Yoo [31] proposed a joint genetic algorithm and ant colony optimization to find an optimal flight path in accordance with sensing, energy, time, and risk utilities.Inspired by the foraging behavior of birds, PSO was proposed by Eberhart and Kennedy in 1995 [32]. PSO is a swarm intelligent optimization algorithm, which has many advantages, such as strong robustness, low sensitivity to population size, less adjustment parameters, and better optimization effects. In fact, the path planner is aimed at searching a group of waypoints, which is a NP optimization problem. In this case, PSO and its variants are used to solve the complex optimization problems. In the preliminary study, the PSO-based approach has been used to solve the path planning for fix-wing UAV, which showed that PSO can provide good guidance for the search of path planning owing to the globally best particle of the entire population. Therefore, this paper studies the PSO-based approach with dynamic divide-and-conquer (DC) strategy and modified A∗ algorithm for solving the path planning problem.However, the traditional PSO algorithm has some shortcomings, such as premature convergence, slow convergence speed in the later evolution, and it is easy to fall into local extreme point. Meanwhile, with the increase of problem size or dimension, PSO may be not sufficient in large-scale optimization problem due to large search space and exponential growth of local optimization. Recently, some researches have focused on these challenges. Zhang et al. [21] proposed a cooperative coevolutionary bare-bones particle swarm optimization (CCBBPSO) with function independent decomposition (FID), where binary encoding of the original model is converted to integer encoding to reduce the dimension. Cheng and Jin [33] proposed a novel competitive swarm optimizer (CSO) to solve large-scale optimization problem. Li and Yao [34] proposed a new cooperative coevolving particle swarm optimization (CCPSO2) algorithm, where the coevolving subcomponent sizes of the variables are determined dynamically. Liang and Suganthan [35] developed a modified dynamic multiswarm particle swarm optimizer (DMS-PSO), where the swarms are dynamic. Wang et al. [24] proposed a dynamic group learning distributed particle swarm optimization (DGLDPSO) for large-scale optimization. Cheng and Jin [36] developed a social learning PSO (SL-PSO), where social learning mechanisms are introduced into particle swarm optimization (PSO).


### 1.3. Contribution and Organization

To deal with the challenges of the traditional PSO algorithm, a dynamic DC strategy and modifiedA∗ algorithm are proposed for the path planning problem of UAV. Specifically, three major novel designs and advantages that help DCA∗PSO find the feasible path under minimizing the cost are described as follows.On the basis of analyses of the cost function and constraints for UAVs, a new path planner is formulated to enhance the ability of solving high-dimensional route planning problem in complex 3D environment. The complex route planning problem is decomposed into a serious of small-scale subproblems based on the DC strategy. For each subproblem, only the coordinates of a few waypoints need to be concerned.A new subsegment evaluate function is proposed for estimating the optimal solution. The subsegment evaluate function provides a reference for judging the equality of the whole path according to some waypoints in a path.A∗ algorithm is firstly adopted to optimize the particle composition and enhance the equality of the particles, which is embedded into the evolution process of the PSO algorithm. The A∗PSO algorithm can provide a significant improvement in the convergence speed of the PSO algorithm and avoid the local optimum entrapment.This paper is organized as follows. Section2 introduces the environment and trajectory representation of route planning for UAV. The optimization model of the path planning problem for fixed-wing UAV is established in Section 3. In Section 4, an improved PSO algorithm based on dynamic DC strategy and improved A∗ algorithm is proposed. The improved PSO algorithm is used to solve the path planning problem in Section 5. In Section 6, the data simulation and analysis are introduced in detail. Finally, the conclusion is offered, and the future research direction is discussed in Section 7.


## 1.1. Background and Motivation

In recent years, with the development of sensor technology and intelligent control technology, unmanned aerial vehicle (UAV) has been widely used in military and civil fields, such as reconnaissance [1, 2], surveillance [3], target prosecution [4], wireless communications [5, 6], and oilfield inspection [7]. As a basic technology for autonomous navigation of the UAV system [8], the path planner is an important component to ensure the successful completion of the complex missions. The objective of path planning is to seek an optimal or near-optimal flight route from the starting position to the destination in the mission space under the required constraint conditions [9].The core of the path planning system is route planning algorithm, which has been actively researched for decades. Over the last few decades, a variety of approaches have been proposed to deal with path planning problem for UAV or autonomous robot. Most traditional path planning methods based on the graph are adaptive to 2-dimensional planning problems, such as Voronoi diagram algorithm [10], A∗ algorithm [11], and probabilistic roadmap algorithm. These methods are relatively easy to implement, but UAV kinematic and dynamic constraints are seldom considered by these algorithms. Meanwhile, these methods need more time and huge storage memory in a large space. Potential field-based methods, such as artificial potential field algorithm [12], can obtain a smooth path and has little calculation time. Its disadvantage lies that it is easy to trap into local minimum and even cannot find a feasible path when the distance between the target and the obstacles is near. Hence, potential field-based methods can seldom be used for the practical situations. Compared with the traditional methods, evolutionary computation (EC) algorithms have a strong ability to obtain high-quality solutions in path planning and are easier to implement [13]. The problem of trajectory planning is often treated as a nonlinear NP-hard optimal problem to be solved by evolutionary algorithms. It is well known that the ECs have made much progress and have been deeply and extensively studied in recent years [14–16]. EC algorithms, including evolutionary algorithms (EAs) and swarm intelligence algorithms (SIs), such as genetic algorithm (GA) [17], differential evolution (DE) [18, 19], particle swam optimization (PSO) [20–25], and ant colony optimization (ACO) [26], have been widely used in handling global optimization problems.In the application of route planning of the three-dimensional (3D) environment, it is necessary to require a higher ability to avoid collisions with terrain and much more complicated calculation than two-dimensional path planning. Therefore, how to further enhance convergence speed and solution quality of the planner will be a main motivation in a 3D complex environment. Moreover, as the environment and the planning task become increasingly complex, intelligent optimization algorithms have difficulty in dealing with the high dimension problems.


## 1.2. Related Work

ECs have been applied to find global or approximate global optimum path. Yang et al. [27] discovered the drawback that the high-quality waypoints in previous search can hardly be further exploited in evolutionary algorithm-based due to all the waypoints of a path as an integrated individual. Hence, a new idea of separately evaluating and evolving waypoints is proposed for two-dimensional UAV path planning. On the basis of Ref. [14], Huang [28] proposed an improved PSO algorithm based on the competition of global best solution and applied the path planner to a three-dimensional UAV to demonstrate. Zhang et al. [29] formulated an improved fruit fly optimization (MAFOA) based on the phase angle-encoded connected with mutation adaptation mechanisms to solve the unmanned aerial vehicle (UAV) path planning problem. Du et al. [30] proposed a hybrid evolutionary algorithm included the main algorithm and a subalgorithm. The main algorithm was to evolve a population of main solutions, and the subalgorithm was used to optimize each UAV path. Yang and Yoo [31] proposed a joint genetic algorithm and ant colony optimization to find an optimal flight path in accordance with sensing, energy, time, and risk utilities.Inspired by the foraging behavior of birds, PSO was proposed by Eberhart and Kennedy in 1995 [32]. PSO is a swarm intelligent optimization algorithm, which has many advantages, such as strong robustness, low sensitivity to population size, less adjustment parameters, and better optimization effects. In fact, the path planner is aimed at searching a group of waypoints, which is a NP optimization problem. In this case, PSO and its variants are used to solve the complex optimization problems. In the preliminary study, the PSO-based approach has been used to solve the path planning for fix-wing UAV, which showed that PSO can provide good guidance for the search of path planning owing to the globally best particle of the entire population. Therefore, this paper studies the PSO-based approach with dynamic divide-and-conquer (DC) strategy and modified A∗ algorithm for solving the path planning problem.However, the traditional PSO algorithm has some shortcomings, such as premature convergence, slow convergence speed in the later evolution, and it is easy to fall into local extreme point. Meanwhile, with the increase of problem size or dimension, PSO may be not sufficient in large-scale optimization problem due to large search space and exponential growth of local optimization. Recently, some researches have focused on these challenges. Zhang et al. [21] proposed a cooperative coevolutionary bare-bones particle swarm optimization (CCBBPSO) with function independent decomposition (FID), where binary encoding of the original model is converted to integer encoding to reduce the dimension. Cheng and Jin [33] proposed a novel competitive swarm optimizer (CSO) to solve large-scale optimization problem. Li and Yao [34] proposed a new cooperative coevolving particle swarm optimization (CCPSO2) algorithm, where the coevolving subcomponent sizes of the variables are determined dynamically. Liang and Suganthan [35] developed a modified dynamic multiswarm particle swarm optimizer (DMS-PSO), where the swarms are dynamic. Wang et al. [24] proposed a dynamic group learning distributed particle swarm optimization (DGLDPSO) for large-scale optimization. Cheng and Jin [36] developed a social learning PSO (SL-PSO), where social learning mechanisms are introduced into particle swarm optimization (PSO).


## 1.3. Contribution and Organization

To deal with the challenges of the traditional PSO algorithm, a dynamic DC strategy and modifiedA∗ algorithm are proposed for the path planning problem of UAV. Specifically, three major novel designs and advantages that help DCA∗PSO find the feasible path under minimizing the cost are described as follows.On the basis of analyses of the cost function and constraints for UAVs, a new path planner is formulated to enhance the ability of solving high-dimensional route planning problem in complex 3D environment. The complex route planning problem is decomposed into a serious of small-scale subproblems based on the DC strategy. For each subproblem, only the coordinates of a few waypoints need to be concerned.A new subsegment evaluate function is proposed for estimating the optimal solution. The subsegment evaluate function provides a reference for judging the equality of the whole path according to some waypoints in a path.A∗ algorithm is firstly adopted to optimize the particle composition and enhance the equality of the particles, which is embedded into the evolution process of the PSO algorithm. The A∗PSO algorithm can provide a significant improvement in the convergence speed of the PSO algorithm and avoid the local optimum entrapment.This paper is organized as follows. Section2 introduces the environment and trajectory representation of route planning for UAV. The optimization model of the path planning problem for fixed-wing UAV is established in Section 3. In Section 4, an improved PSO algorithm based on dynamic DC strategy and improved A∗ algorithm is proposed. The improved PSO algorithm is used to solve the path planning problem in Section 5. In Section 6, the data simulation and analysis are introduced in detail. Finally, the conclusion is offered, and the future research direction is discussed in Section 7.


## 2. Environment and Trajectory Representation

### 2.1. Environment Representation

The representation of the environment space, e.g., the terrain and the danger zones, directly affects the efficiency of the planning algorithm and the quality of planning result. The terrain map of the mission space is described by a 2D matrix. The rows and columns of this matrix represent thex-coordinate and y-coordinate in a 3D space, respectively. The elevation data of the map is represented by the corresponding element of the matrix as follows:
(1)terrain=e11e12⋯e1ne21e22⋯e2n⋯⋯⋯⋯em1em2⋯emn,where eij is the altitude of the environment terrain.If the coordinate of a waypoint is defined asx,y,z, hence, the flying space for UAV can be given as
(2)xmin≤x≤xmax,ymin≤y≤ymax,zmin≤z≤zmax,where xmin,xmax,ymin,ymax,zmin,zmax represent the boundaries of the 3D coordinate, respectively.When a UAV flies into the high-risk threat of the radar, the defense scope of the radar may be considered as omnidirectional. The mathematical model of the threat source is denoted as a geometric sphere, as seen from Figure1, which is described by the following matrix:
(3)dangerzones=x1y1z1r1x2y2z2r2⋯⋯⋯⋯xdydzdrd,where xk,yk,zk is the center of the k-th radar threat, and rk is the radius of the k-th threat source.Figure 1
The environment with the terrain and the danger zones.


### 2.2. Trajectory Representation

There are two common representations to describe the trajectory: the first one is a continuous smooth trajectory, which is based on the description of UAV kinematic and dynamic characteristics. The smoothness of the trajectory may be omitted by this representation method. The other is represented by the waypoints, which are connected by straight line segments between the adjacent waypoints. The advantage of the second trajectory representation is that the desired accuracy can be achieved by adjusting the number of waypoints. Subsequently, the path planning problem can be taken as the optimization of the waypoint coordinate.DefineP=S,W1,W2,⋯,Wi,Wi+1,⋯,WNw,T as a trajectory in the flying space, where S is the starting point, T is the target point, and W1,W2,⋯,Wi,Wi+1,⋯,Wn are the waypoints between the start point and the target point. The segment composed by two adjacent waypoints Wi,Wi+1 is divided into Nd parts equally, as shown in Figure 2. Suppose the set of the dividing points is D=D11,D12,⋯,D1Nd,D21,D22,⋯,D2Nd,⋯,DNw1,DNw2,⋯,DNwNd.Figure 2
The flight trajectory in 3D space.The coordinates of dividing points are calculated as:(4)xik=xi−1+k⋅xi−xi−1/Nd,yik=yi−1+k⋅yi−yi−1/Nd,zik=zi−1+k⋅zi−zi−1/Nd,where xik,yik,zik is the coordinate of the k-th division point corresponding to the i-th waypoint. xi−1,yi−1,zi−1 and xi,yi,zi are the i−1-th waypoint and the i-th waypoint, respectively.


## 2.1. Environment Representation

The representation of the environment space, e.g., the terrain and the danger zones, directly affects the efficiency of the planning algorithm and the quality of planning result. The terrain map of the mission space is described by a 2D matrix. The rows and columns of this matrix represent thex-coordinate and y-coordinate in a 3D space, respectively. The elevation data of the map is represented by the corresponding element of the matrix as follows:
(1)terrain=e11e12⋯e1ne21e22⋯e2n⋯⋯⋯⋯em1em2⋯emn,where eij is the altitude of the environment terrain.If the coordinate of a waypoint is defined asx,y,z, hence, the flying space for UAV can be given as
(2)xmin≤x≤xmax,ymin≤y≤ymax,zmin≤z≤zmax,where xmin,xmax,ymin,ymax,zmin,zmax represent the boundaries of the 3D coordinate, respectively.When a UAV flies into the high-risk threat of the radar, the defense scope of the radar may be considered as omnidirectional. The mathematical model of the threat source is denoted as a geometric sphere, as seen from Figure1, which is described by the following matrix:
(3)dangerzones=x1y1z1r1x2y2z2r2⋯⋯⋯⋯xdydzdrd,where xk,yk,zk is the center of the k-th radar threat, and rk is the radius of the k-th threat source.Figure 1
The environment with the terrain and the danger zones.


## 2.2. Trajectory Representation

There are two common representations to describe the trajectory: the first one is a continuous smooth trajectory, which is based on the description of UAV kinematic and dynamic characteristics. The smoothness of the trajectory may be omitted by this representation method. The other is represented by the waypoints, which are connected by straight line segments between the adjacent waypoints. The advantage of the second trajectory representation is that the desired accuracy can be achieved by adjusting the number of waypoints. Subsequently, the path planning problem can be taken as the optimization of the waypoint coordinate.DefineP=S,W1,W2,⋯,Wi,Wi+1,⋯,WNw,T as a trajectory in the flying space, where S is the starting point, T is the target point, and W1,W2,⋯,Wi,Wi+1,⋯,Wn are the waypoints between the start point and the target point. The segment composed by two adjacent waypoints Wi,Wi+1 is divided into Nd parts equally, as shown in Figure 2. Suppose the set of the dividing points is D=D11,D12,⋯,D1Nd,D21,D22,⋯,D2Nd,⋯,DNw1,DNw2,⋯,DNwNd.Figure 2
The flight trajectory in 3D space.The coordinates of dividing points are calculated as:(4)xik=xi−1+k⋅xi−xi−1/Nd,yik=yi−1+k⋅yi−yi−1/Nd,zik=zi−1+k⋅zi−zi−1/Nd,where xik,yik,zik is the coordinate of the k-th division point corresponding to the i-th waypoint. xi−1,yi−1,zi−1 and xi,yi,zi are the i−1-th waypoint and the i-th waypoint, respectively.


## 3. Cost Function of Path Planning for Fixed-Wing

For the UAV path planning problem, the cost function is a series of optimization criteria and constraints to evaluate the quality of the flight path. The smaller the cost function fitness value is, the better the quality of the flight path is. To determine the cost function, it is necessary to consider that all the factors can affect the route performance, such as path length, flight safety altitude, threat probability, UAV dynamic constraint, and environment constraints. In general, the cost function mainly includes two parts: the objective function and the constraint function. The cost functionF of path planning for fixed-wing UAV is the sum of the objective function and the constraint function, which is given as
(5)F=∑k=13Jk+∑n=13Cn,where ∑k=13Jk is the sum of objective function, ∑k=13Cn is the sum of the constraint function.


### 3.1. Objective Function

The objective function enables the UAV to obtain the maximum profit under the premise of satisfying the constraints. Taking the route length, the radar threat, and flight height into account, the objective cost is calculated as follows(6)∑k=13Jk=Jlength+Jaltitude+Jthreat,where Jlength, Jaltitude, and Jthreat represent the costs of path length, the threat, and the height, respectively.
(1)
Route length costIn general, shorter routes can save more fuel consumption. To describe the length cost more accurately, path length ratio (PLR) is utilized to measure the route length costJlength, which is given as follows
(7)Jlength=LtrajLST=∑i=1Nw+1Wi−1Wi⟶LST=∑i=1Nw+1xi−xi−12+yi−xi−12+zi−zi−12xT−xS2+yT−xS2+zT−zS2,where LST is the length of the straight line connecting the starting point S and the destination T. Ltraj is the length of the actual route. ⋅ denotes the Euclidean distance of a vector. When the actual route length is approximately closer to the length of the straight line, a shorter route will be obtained. The range of Jlength is given as follows
(8)Jlength∈1,1.5.The length of the path with good performance is considered within the scope of 1.5 times the distance between start and destination according to [15]. Hence, the value of 1.5 is the preference of feasible PLR.
(2)
Flight height costA lower-height path can reduce the risk of being detected by radar and strengthen the threat to the enemy on the ground for flying missions. The termJaltitude is calculated as follows
(9)Jaltitude=∑i=1Nw+1Aroute.i−ZminZmax−Zmin,where Aroute.i represents the average flight altitude of i-th route segment, Zmin and Zmax are the lower and higher bounds of the flight height in mission space, respectively.Therefore,(10)Jaltitude∈0,1.(3)
Threat costDuring the process of UAV flying, it is essential to avoid into the detection range of the radar, where it may encounter the risk of being discovered or being attacked. The threat cost is computed according to the route length which goes into the threat sphere, which is calculated by(11)Jthreat=∑i=1Nw+1Linside.i∑k=1NDk,where Linside is the length of i-th segment that goes inside the threat circle, Dk indicates the diameter of k-th threat, and N is the number of threat sources. It is noted that Jthreat is limited to 0,1.


### 3.2. Constraint Function

The constraint function to evaluate the candidate route should take the environment constraint and UAV dynamic constraints into account. The environment constraint focuses on the terrain of the flight altitude constraint. UAV dynamic constraints mainly refer to the turning-angle constraint and the climb/dive angle constraint. The constraint function∑n=13Cn is descripted as
(12)∑n=13Cn=Ccollision+Cturn+Cslope,where Ccollision is introduced to penalize the candidate routes colliding with the terrain, Cturn is introduced to penalize the route with a turning angle beyond the maximum, and Cslope is introduced to penalize the route with the climbing/diving angle beyond the constraint. The constraint function can be depicted as follows in detail.
(1)
Terrain constraintIf the flight height is lower than the terrain, then, UAV will collide with the terrain. So the termCcollision associated with the terrain collision is described as follows
(13)Ccollision=0,if∑i=1Nw+1Lunder.i=0,Pe+∑i=1Nw+1Lunder.iLtraj.i,if∑i=1Nw+1Lunder.i>0,where Lunder.i is the length of the i-th segment in a route which located below the altitude of the terrain, Ltraj.i is the length of the i-th actual route segment. Considering the above objective optimization value, the penalty constant Pe is selected to 3.5.
(2)
Turning angle constraintIn view of the physical characteristics of UAV, the turning angle for UAV is required to be less than or equal to the maximum turning angle. The turning angle constraint functionCturning can be expressed by
(14)Cturning=0,if∑i=1Nwai=0e+∑i=1NwaiNwif∑i=1Nwai>0withai=0,ifθi<θmax,1,ifθi>θmax,where θmax is the maximum turning angle, θi is the corresponding turning angle of the i-th waypoint. The turning angle θi is calculated according to
(15)θi=arccosxi+1−xi,yi+1−yi⋅xi−xi−1,yi−yi−1Txi+1−xi,yi+1−yi⋅xi−xi−1,yi−yi−1.(3)
Slope angle constraintThe slope angle for UAV at each waypoint is limited into the range between the maximum slope angle and the minimum slope angle. The slope angle constraint referring to the vertical direction is calculated as(16)Cslope=0,if∑i=1Nw+1bi=0e+∑i=1Nw+1biNw+1if∑i=1Nw+1bi>0withbi=0,ifφmin<φi<φmax,1,else,where φmin and φmax are, respectively, the minimum and maximum slope angle, φi is the corresponding slope angle of the i-th waypoint, which can be calculated as
(17)θi=arctanzi−zi−1xi−xi−1,yi−yi−1.


## 3.1. Objective Function

The objective function enables the UAV to obtain the maximum profit under the premise of satisfying the constraints. Taking the route length, the radar threat, and flight height into account, the objective cost is calculated as follows(6)∑k=13Jk=Jlength+Jaltitude+Jthreat,where Jlength, Jaltitude, and Jthreat represent the costs of path length, the threat, and the height, respectively.
(1)
Route length costIn general, shorter routes can save more fuel consumption. To describe the length cost more accurately, path length ratio (PLR) is utilized to measure the route length costJlength, which is given as follows
(7)Jlength=LtrajLST=∑i=1Nw+1Wi−1Wi⟶LST=∑i=1Nw+1xi−xi−12+yi−xi−12+zi−zi−12xT−xS2+yT−xS2+zT−zS2,where LST is the length of the straight line connecting the starting point S and the destination T. Ltraj is the length of the actual route. ⋅ denotes the Euclidean distance of a vector. When the actual route length is approximately closer to the length of the straight line, a shorter route will be obtained. The range of Jlength is given as follows
(8)Jlength∈1,1.5.The length of the path with good performance is considered within the scope of 1.5 times the distance between start and destination according to [15]. Hence, the value of 1.5 is the preference of feasible PLR.
(2)
Flight height costA lower-height path can reduce the risk of being detected by radar and strengthen the threat to the enemy on the ground for flying missions. The termJaltitude is calculated as follows
(9)Jaltitude=∑i=1Nw+1Aroute.i−ZminZmax−Zmin,where Aroute.i represents the average flight altitude of i-th route segment, Zmin and Zmax are the lower and higher bounds of the flight height in mission space, respectively.Therefore,(10)Jaltitude∈0,1.(3)
Threat costDuring the process of UAV flying, it is essential to avoid into the detection range of the radar, where it may encounter the risk of being discovered or being attacked. The threat cost is computed according to the route length which goes into the threat sphere, which is calculated by(11)Jthreat=∑i=1Nw+1Linside.i∑k=1NDk,where Linside is the length of i-th segment that goes inside the threat circle, Dk indicates the diameter of k-th threat, and N is the number of threat sources. It is noted that Jthreat is limited to 0,1.


## 3.2. Constraint Function

The constraint function to evaluate the candidate route should take the environment constraint and UAV dynamic constraints into account. The environment constraint focuses on the terrain of the flight altitude constraint. UAV dynamic constraints mainly refer to the turning-angle constraint and the climb/dive angle constraint. The constraint function∑n=13Cn is descripted as
(12)∑n=13Cn=Ccollision+Cturn+Cslope,where Ccollision is introduced to penalize the candidate routes colliding with the terrain, Cturn is introduced to penalize the route with a turning angle beyond the maximum, and Cslope is introduced to penalize the route with the climbing/diving angle beyond the constraint. The constraint function can be depicted as follows in detail.
(1)
Terrain constraintIf the flight height is lower than the terrain, then, UAV will collide with the terrain. So the termCcollision associated with the terrain collision is described as follows
(13)Ccollision=0,if∑i=1Nw+1Lunder.i=0,Pe+∑i=1Nw+1Lunder.iLtraj.i,if∑i=1Nw+1Lunder.i>0,where Lunder.i is the length of the i-th segment in a route which located below the altitude of the terrain, Ltraj.i is the length of the i-th actual route segment. Considering the above objective optimization value, the penalty constant Pe is selected to 3.5.
(2)
Turning angle constraintIn view of the physical characteristics of UAV, the turning angle for UAV is required to be less than or equal to the maximum turning angle. The turning angle constraint functionCturning can be expressed by
(14)Cturning=0,if∑i=1Nwai=0e+∑i=1NwaiNwif∑i=1Nwai>0withai=0,ifθi<θmax,1,ifθi>θmax,where θmax is the maximum turning angle, θi is the corresponding turning angle of the i-th waypoint. The turning angle θi is calculated according to
(15)θi=arccosxi+1−xi,yi+1−yi⋅xi−xi−1,yi−yi−1Txi+1−xi,yi+1−yi⋅xi−xi−1,yi−yi−1.(3)
Slope angle constraintThe slope angle for UAV at each waypoint is limited into the range between the maximum slope angle and the minimum slope angle. The slope angle constraint referring to the vertical direction is calculated as(16)Cslope=0,if∑i=1Nw+1bi=0e+∑i=1Nw+1biNw+1if∑i=1Nw+1bi>0withbi=0,ifφmin<φi<φmax,1,else,where φmin and φmax are, respectively, the minimum and maximum slope angle, φi is the corresponding slope angle of the i-th waypoint, which can be calculated as
(17)θi=arctanzi−zi−1xi−xi−1,yi−yi−1.


## 4. Improved PSO Algorithm

### 4.1. PSO Algorithm

PSO is a typical search algorithm based on group cooperation, which comes from the basic concept of the study on simulating the foraging behavior of birds. In the particle swarm optimization algorithm, each bird in the swarm is regarded as a particle. The basic idea of PSO is to find the optimal solution through cooperation and information sharing among the individuals in the group. The process is simplified as follows. First, a group of random particles are generated at the initialization stage, and then to search the optimal solution through iteration. Each particle updates its position and velocity by tracking two extreme values (pbest and gbest) at one iteration. In n-dimensional search space, a population of m particles is X=x1,x2,⋯,xi,⋯,xm, the position of the i-th particle is xi=xi1,xi2,⋯,xinT, and its velocity is vi=vi1,vi2,⋯,vinT. The individual best solution of the population is pbesti=pbesti1,pbesti2,⋯,pbestinT, and the global best solution is gbesti=gbesti1,gbesti2,⋯,gbestinT. The velocity and position of each particle is updated according to the following formula
(18)vidt+1=w⋅vidt+c1r1pbestidt−xidt+c2r2gbestidt−xidt,xidt+1=xidt+vidt+1,where m is the population size, t is the current iteration, r1 and r2 are random numbers in [0,1]. c1 and c2 are, respectively, the personal influence parameter and the social influence parameter, and w is the inertia coefficient.


### 4.2. Improved PSO Algorithm Based on Dynamic DC Strategy

When the number of obstacles, the threat sources increase, or the environment becomes complex, the number of waypoints should increase accordingly. However, the larger the dimension of the particle, and the worse the search ability of the intelligent algorithms becomes. Therefore, a large amount of waypoints will result in failure of planning. The planners based on intelligent optimization algorithms may be difficult to explore a feasible route in a mission space. An efficient way to solve this problem is to simplify the original problem into lower dimensions, where existing intelligent optimization algorithms can well suit. In consideration of computational accuracy and efficiency, dynamic DC strategy is introduced in PSO to find an optimal route when the number of the waypoints increases. According to this idea, the grouping strategy based on dynamic dimension is adopted to divide multiple waypoints into different groups. The number of the group in DC strategy is adjusted according to the cost function value.A new subcost function is established to evaluate the quality of subpath. The group cost function is defined as(19)Fg=∑k=13∑bg−1−2bg+2Jgk+∑n=13∑bg−1−2bg+2Cgn,ifbg−1>2&bg+2≤Nw,∑k=13∑Sbg+2Jgk+∑n=13∑Sbg+2Cgn,ifbg−1≤2&bg+2≤Nw,∑k=13∑STJgk+∑n=13∑STCgn,ifbg−1≤2&bg+2>Nw,∑k=13∑bg−1−2TJgk+∑n=13∑bg−1−2TCgn,ifbg−1>2&bg+2>Nw,where b is the number of the waypoints in each group, Jgk is the objective function, and Cgn is the constrain function. Jgk and Cgn can be denoted as
(20)∑gsgtJgk=Jlength.g+Jaltitude.g+Jthreat.g=∑i=gsgtWi‐1WiLST+∑i=gsgtAroute.i−ZminZmax−Zmin+∑i=gsgtLinside.i∑k=1nDk,(21)∑gsgtCgn=0,if∑i=gsgtLunder.i=0&∑i=gsgtai=0&∑i=gsgtbi=0,Pe+∑i=gsgtLunder.iLtraj.i+Pe+∑i=gsgtaigt−gs+1+Pe+∑i=gsgtbigt−gs+1,if∑i=gsgtLunder.i>0&∑i=gsgtai>0&∑i=gsgtbi>0,Pe+∑i=gsgtLunder.iLtraj.i+Pe+∑i=gsgtaigt−gs+1,if∑i=gsgtLunder.i>0&∑i=gsgtai>0&∑i=gsgtbi=0,Pe+∑i=gsgtaigt−gs+1+Pe+∑i=gsgtbigt−gs+1,if∑i=gsgtLunder.i=0&∑i=gsgtai>0&∑i=gsgtbi>0,Pe+∑i=gsgtLunder.iLtraj.i+Pe+∑i=gsgtbigt−gs+1,if∑i=gsgtLunder.i>0&∑i=gsgtai=0&∑i=gsgtbi>0,Pe+∑i=gsgtLunder.iLtraj.i,if∑i=gsgtLunder.i>0&∑i=gsgtai=0&∑i=gsgtbi=0,Pe+∑i=gsgtaigt−gs+1,if∑i=gsgtLunder.i=0&∑i=gsgtai>0&∑i=gsgtbi=0,Pe+∑i=gsgtbigt−gs+1,if∑i=gsgtLunder.i=0&∑i=gsgtai=0&∑i=gsgtbi>0.The individual best solution of each group is selected by comparing the group cost functionFg of previous parent and offspring. The global best solution based on dynamic DC strategy is generated by choosing the best group of all the groups according to Fg value. In order to explain the strategy, the flow chart of PSO with DC strategy is given in Figure 3. At the starting phase, the positions and speeds of m particles are initialized, and then each particle is divided into g groups based on DC strategy, so each group contains D/g dimensions. D/g dimensions of each particle form a group, which can be evaluated by the group cost function Fg. According to the result of the group cost function value, the groups with minimum group function fitness will be found and compose the global best particle. The parallel search based on DC strategy is developed to find the whole particle swarm and complete an iteration of search. During the iteration of path search, the group number g is adjusted dynamically by
(22)gt+1=Ngt,σ2,ifFg−bestt<Fg−bestt−1,gt+1=randinta,b,ifelse,where Ngt,σ2 is the normal distribution with mean gt and standard deviation σ2. randinta,b represents an integer chosen within the range of a,b,a≥1,b≤D.Figure 3
The flow chart of PSO with divide-and-conquer (DC) strategy.Thus, the individual best solution of each particle is selected to participate in the next iteration operation.


### 4.3. An Improved PSO Algorithm Based onA∗ Algorithm

In order to improve the convergence accuracy and convergence speed,A∗ algorithm is introduced into PSO. The route obtained by A∗ search is regarded as a particle to optimize the performance of the DCPSO algorithm.A∗ algorithm is an effective and direct search algorithm in static environment, which determines search direction from the starting point to the surrounding through the heuristic function. In A∗ algorithm, the open list and close list are used to realize the node expansion and the best choice in the process of path planning. The function of open list is to save the extended nodes which needed to be checked in the search process. The node with the smallest value is selected as the current node and put into close list, then all the neighboring nodes of the current node is added to the open list according to the neighbor node rule. The process is repeated until a path is found from the start point to the end point. During the search process, because each node on the path has the minimum cost, the cost of the path is the least.The heuristic function ofA∗ algorithm is aimed at evaluating the equality of the expandable nodes. The heuristic function is defined as follows
(23)fn=gn+hn,where nis the node to be expanded; gn is the actual cost from the initial node to the node n in the space; hn is the cost from node n to the target node.For fix-wing UAV path planning problem, the heuristic function is denoted as(24)fn=∑k=13fkn+∑v=13fCVn,where ∑k=13fkn is cost function of node n, ∑v=13fCvn is the constraints of node n.The cost function of noden is given by
(25)∑k=13fkn=flengthn+faltituden+fthreatn,where flengthn, faltituden, and fthreatn are the objective functions of the length, the altitude, and the risk of radar detection for node n, respectively.
(1)
Length cost of nodenFor noden, flengthn can be given as
(26)flengthn=n−1n⟶+nT⟶n−1T⇀=xn−xn−1,yn−yn−1,zn−zn−1+xT−xn,yT−yn,zT−znxT−xn−1,yT−yn−1,zT−zn−1,where T is the goal.Therefore,(27)flengthn∈1,1.5.(2)
Flight altitude cost of nodenFor noden, faltituden is described as
(28)faltituden=An−ZminZmax−Zmin,where An is the average flight of the segment between node n−1 and node n.Therefore,(29)faltituden∈0,1.(3)
Threat cost of nodenFor noden, fthreatn can be calculated as
(30)fthreatn=dLinside∑k=1NDk,where dLinside is the length of the segment between node n and node n−1 that go through the threat zones. Therefore,
(31)fthreatn∈0,1.The Constraint Expression of noden(32)∑v=13fCvn=fCterrainn+fCturningn+fCslopen.(1)
Terrain constraint for nodenFor noden, fCcollisionn can be given as
(33)fCterrainn=∑k=1Nds1nNd,withs1n=1,ifzn−1,k≤terrainxn−1,k,yn−1,k,0,else,where xn−1,k,yn−1,k,zn−1,k is the k-th division point coordinate of the node n−1, zterrainxn−1,k,yn−1,k is the terrain altitude of the corresponding coordinate xn−1,k,yn−1,k on the map.
(1)
Turning angle constraint for nodenFor noden, fCturningn is calculated by
(34)fCturningn=C,ifθn>θmax,0,else,where the constant C is used to penalize the segment with the turning angle more than the maximum turning angle.
(2)
Slope constraintFor noden, fCslopen can be given by
(35)fCslopen=0,ifφmin≤φn≤φmax,C,else.


### 4.4. Improved PSO Algorithm Based onA∗ Algorithm

The process of improved PSO algorithm based onA∗ algorithm is described in Figure 4.Figure 4
The flow chart of PSO withA∗ algorithm.From the starting pointS, put S into the open list. The first waypoints of m−1 particles are considered as the adjacent nodes of the starting point S. The adjacent nodes with S are checked to join the open list. Set the starting point as parent node and remove S from the open list to the close list. The first waypoint of m−1 particles with minimum fitness will be searched and add it into the close list. Then, this waypoint in close list is seen as the parent of the next node, and the adjacent nodes with the first waypoint are the second waypoints of m−1 particles. These nodes are put into the open list, repeat the selection process based on the A∗ heuristic function value. Until the last waypoint, a whole route is generated by A∗ algorithm at one iteration in PSO. The waypoints in the close list generate m-th particle. The path found by A∗ algorithm is seen as a particle in the particle swarm. The m−1 particles in PSO will be updated according to the evolution equation. The A∗ algorithm of the new generated particles will be continued. The new route obtained by A∗ algorithm from all the particles can optimize the equality of the particles, enrich the diversity of particle swarm, and enhance the convergence speed.


### 4.5. The Steps of DCA∗PSO Algorithm

The steps of the DCA∗PSO algorithm based on DC strategy and A∗ algorithm are described as follows.Step 1.
Set the parameters and initialize each particle.Set population sizem, the maximum number of iterations, particle dimension, the upper and lower bounds of velocity and position, and learning factor c1 and c2. Randomly generate the initial position and the initial velocity of each particle.Step 2.
Evaluate the particle based on group cost function.Generate the group numberg of DC strategy according to (22). It means that the dimensions are divided into g groups. Calculate the group cost function value of each group. If the value is better than that of the current value, this value is regarded as the new best value of the individual. The global best solution based on dynamic DC strategy is obtained by combining the groups with the best group cost function value.Step 3.
Find the global best solution.A path is searched byA∗PSO algorithm. Calculate the fitness of this path and compare with that of the global best solution based on DC strategy. Select the path with the less fitness value as the global best path.Step 4.
Update speed and position.Update the velocity and position in each group according to (18).Step 5.
Determine the end condition.Determine whether the end conditions are met. If the end condition is met, the global optimum value and position of the particle are saved. Otherwise, turn to Step 2.


## 4.1. PSO Algorithm

PSO is a typical search algorithm based on group cooperation, which comes from the basic concept of the study on simulating the foraging behavior of birds. In the particle swarm optimization algorithm, each bird in the swarm is regarded as a particle. The basic idea of PSO is to find the optimal solution through cooperation and information sharing among the individuals in the group. The process is simplified as follows. First, a group of random particles are generated at the initialization stage, and then to search the optimal solution through iteration. Each particle updates its position and velocity by tracking two extreme values (pbest and gbest) at one iteration. In n-dimensional search space, a population of m particles is X=x1,x2,⋯,xi,⋯,xm, the position of the i-th particle is xi=xi1,xi2,⋯,xinT, and its velocity is vi=vi1,vi2,⋯,vinT. The individual best solution of the population is pbesti=pbesti1,pbesti2,⋯,pbestinT, and the global best solution is gbesti=gbesti1,gbesti2,⋯,gbestinT. The velocity and position of each particle is updated according to the following formula
(18)vidt+1=w⋅vidt+c1r1pbestidt−xidt+c2r2gbestidt−xidt,xidt+1=xidt+vidt+1,where m is the population size, t is the current iteration, r1 and r2 are random numbers in [0,1]. c1 and c2 are, respectively, the personal influence parameter and the social influence parameter, and w is the inertia coefficient.


## 4.2. Improved PSO Algorithm Based on Dynamic DC Strategy

When the number of obstacles, the threat sources increase, or the environment becomes complex, the number of waypoints should increase accordingly. However, the larger the dimension of the particle, and the worse the search ability of the intelligent algorithms becomes. Therefore, a large amount of waypoints will result in failure of planning. The planners based on intelligent optimization algorithms may be difficult to explore a feasible route in a mission space. An efficient way to solve this problem is to simplify the original problem into lower dimensions, where existing intelligent optimization algorithms can well suit. In consideration of computational accuracy and efficiency, dynamic DC strategy is introduced in PSO to find an optimal route when the number of the waypoints increases. According to this idea, the grouping strategy based on dynamic dimension is adopted to divide multiple waypoints into different groups. The number of the group in DC strategy is adjusted according to the cost function value.A new subcost function is established to evaluate the quality of subpath. The group cost function is defined as(19)Fg=∑k=13∑bg−1−2bg+2Jgk+∑n=13∑bg−1−2bg+2Cgn,ifbg−1>2&bg+2≤Nw,∑k=13∑Sbg+2Jgk+∑n=13∑Sbg+2Cgn,ifbg−1≤2&bg+2≤Nw,∑k=13∑STJgk+∑n=13∑STCgn,ifbg−1≤2&bg+2>Nw,∑k=13∑bg−1−2TJgk+∑n=13∑bg−1−2TCgn,ifbg−1>2&bg+2>Nw,where b is the number of the waypoints in each group, Jgk is the objective function, and Cgn is the constrain function. Jgk and Cgn can be denoted as
(20)∑gsgtJgk=Jlength.g+Jaltitude.g+Jthreat.g=∑i=gsgtWi‐1WiLST+∑i=gsgtAroute.i−ZminZmax−Zmin+∑i=gsgtLinside.i∑k=1nDk,(21)∑gsgtCgn=0,if∑i=gsgtLunder.i=0&∑i=gsgtai=0&∑i=gsgtbi=0,Pe+∑i=gsgtLunder.iLtraj.i+Pe+∑i=gsgtaigt−gs+1+Pe+∑i=gsgtbigt−gs+1,if∑i=gsgtLunder.i>0&∑i=gsgtai>0&∑i=gsgtbi>0,Pe+∑i=gsgtLunder.iLtraj.i+Pe+∑i=gsgtaigt−gs+1,if∑i=gsgtLunder.i>0&∑i=gsgtai>0&∑i=gsgtbi=0,Pe+∑i=gsgtaigt−gs+1+Pe+∑i=gsgtbigt−gs+1,if∑i=gsgtLunder.i=0&∑i=gsgtai>0&∑i=gsgtbi>0,Pe+∑i=gsgtLunder.iLtraj.i+Pe+∑i=gsgtbigt−gs+1,if∑i=gsgtLunder.i>0&∑i=gsgtai=0&∑i=gsgtbi>0,Pe+∑i=gsgtLunder.iLtraj.i,if∑i=gsgtLunder.i>0&∑i=gsgtai=0&∑i=gsgtbi=0,Pe+∑i=gsgtaigt−gs+1,if∑i=gsgtLunder.i=0&∑i=gsgtai>0&∑i=gsgtbi=0,Pe+∑i=gsgtbigt−gs+1,if∑i=gsgtLunder.i=0&∑i=gsgtai=0&∑i=gsgtbi>0.The individual best solution of each group is selected by comparing the group cost functionFg of previous parent and offspring. The global best solution based on dynamic DC strategy is generated by choosing the best group of all the groups according to Fg value. In order to explain the strategy, the flow chart of PSO with DC strategy is given in Figure 3. At the starting phase, the positions and speeds of m particles are initialized, and then each particle is divided into g groups based on DC strategy, so each group contains D/g dimensions. D/g dimensions of each particle form a group, which can be evaluated by the group cost function Fg. According to the result of the group cost function value, the groups with minimum group function fitness will be found and compose the global best particle. The parallel search based on DC strategy is developed to find the whole particle swarm and complete an iteration of search. During the iteration of path search, the group number g is adjusted dynamically by
(22)gt+1=Ngt,σ2,ifFg−bestt<Fg−bestt−1,gt+1=randinta,b,ifelse,where Ngt,σ2 is the normal distribution with mean gt and standard deviation σ2. randinta,b represents an integer chosen within the range of a,b,a≥1,b≤D.Figure 3
The flow chart of PSO with divide-and-conquer (DC) strategy.Thus, the individual best solution of each particle is selected to participate in the next iteration operation.


## 4.3. An Improved PSO Algorithm Based onA∗ Algorithm

In order to improve the convergence accuracy and convergence speed,A∗ algorithm is introduced into PSO. The route obtained by A∗ search is regarded as a particle to optimize the performance of the DCPSO algorithm.A∗ algorithm is an effective and direct search algorithm in static environment, which determines search direction from the starting point to the surrounding through the heuristic function. In A∗ algorithm, the open list and close list are used to realize the node expansion and the best choice in the process of path planning. The function of open list is to save the extended nodes which needed to be checked in the search process. The node with the smallest value is selected as the current node and put into close list, then all the neighboring nodes of the current node is added to the open list according to the neighbor node rule. The process is repeated until a path is found from the start point to the end point. During the search process, because each node on the path has the minimum cost, the cost of the path is the least.The heuristic function ofA∗ algorithm is aimed at evaluating the equality of the expandable nodes. The heuristic function is defined as follows
(23)fn=gn+hn,where nis the node to be expanded; gn is the actual cost from the initial node to the node n in the space; hn is the cost from node n to the target node.For fix-wing UAV path planning problem, the heuristic function is denoted as(24)fn=∑k=13fkn+∑v=13fCVn,where ∑k=13fkn is cost function of node n, ∑v=13fCvn is the constraints of node n.The cost function of noden is given by
(25)∑k=13fkn=flengthn+faltituden+fthreatn,where flengthn, faltituden, and fthreatn are the objective functions of the length, the altitude, and the risk of radar detection for node n, respectively.
(1)
Length cost of nodenFor noden, flengthn can be given as
(26)flengthn=n−1n⟶+nT⟶n−1T⇀=xn−xn−1,yn−yn−1,zn−zn−1+xT−xn,yT−yn,zT−znxT−xn−1,yT−yn−1,zT−zn−1,where T is the goal.Therefore,(27)flengthn∈1,1.5.(2)
Flight altitude cost of nodenFor noden, faltituden is described as
(28)faltituden=An−ZminZmax−Zmin,where An is the average flight of the segment between node n−1 and node n.Therefore,(29)faltituden∈0,1.(3)
Threat cost of nodenFor noden, fthreatn can be calculated as
(30)fthreatn=dLinside∑k=1NDk,where dLinside is the length of the segment between node n and node n−1 that go through the threat zones. Therefore,
(31)fthreatn∈0,1.The Constraint Expression of noden(32)∑v=13fCvn=fCterrainn+fCturningn+fCslopen.(1)
Terrain constraint for nodenFor noden, fCcollisionn can be given as
(33)fCterrainn=∑k=1Nds1nNd,withs1n=1,ifzn−1,k≤terrainxn−1,k,yn−1,k,0,else,where xn−1,k,yn−1,k,zn−1,k is the k-th division point coordinate of the node n−1, zterrainxn−1,k,yn−1,k is the terrain altitude of the corresponding coordinate xn−1,k,yn−1,k on the map.
(1)
Turning angle constraint for nodenFor noden, fCturningn is calculated by
(34)fCturningn=C,ifθn>θmax,0,else,where the constant C is used to penalize the segment with the turning angle more than the maximum turning angle.
(2)
Slope constraintFor noden, fCslopen can be given by
(35)fCslopen=0,ifφmin≤φn≤φmax,C,else.


## 4.4. Improved PSO Algorithm Based onA∗ Algorithm

The process of improved PSO algorithm based onA∗ algorithm is described in Figure 4.Figure 4
The flow chart of PSO withA∗ algorithm.From the starting pointS, put S into the open list. The first waypoints of m−1 particles are considered as the adjacent nodes of the starting point S. The adjacent nodes with S are checked to join the open list. Set the starting point as parent node and remove S from the open list to the close list. The first waypoint of m−1 particles with minimum fitness will be searched and add it into the close list. Then, this waypoint in close list is seen as the parent of the next node, and the adjacent nodes with the first waypoint are the second waypoints of m−1 particles. These nodes are put into the open list, repeat the selection process based on the A∗ heuristic function value. Until the last waypoint, a whole route is generated by A∗ algorithm at one iteration in PSO. The waypoints in the close list generate m-th particle. The path found by A∗ algorithm is seen as a particle in the particle swarm. The m−1 particles in PSO will be updated according to the evolution equation. The A∗ algorithm of the new generated particles will be continued. The new route obtained by A∗ algorithm from all the particles can optimize the equality of the particles, enrich the diversity of particle swarm, and enhance the convergence speed.


## 4.5. The Steps of DCA∗PSO Algorithm

The steps of the DCA∗PSO algorithm based on DC strategy and A∗ algorithm are described as follows.Step 1.
Set the parameters and initialize each particle.Set population sizem, the maximum number of iterations, particle dimension, the upper and lower bounds of velocity and position, and learning factor c1 and c2. Randomly generate the initial position and the initial velocity of each particle.Step 2.
Evaluate the particle based on group cost function.Generate the group numberg of DC strategy according to (22). It means that the dimensions are divided into g groups. Calculate the group cost function value of each group. If the value is better than that of the current value, this value is regarded as the new best value of the individual. The global best solution based on dynamic DC strategy is obtained by combining the groups with the best group cost function value.Step 3.
Find the global best solution.A path is searched byA∗PSO algorithm. Calculate the fitness of this path and compare with that of the global best solution based on DC strategy. Select the path with the less fitness value as the global best path.Step 4.
Update speed and position.Update the velocity and position in each group according to (18).Step 5.
Determine the end condition.Determine whether the end conditions are met. If the end condition is met, the global optimum value and position of the particle are saved. Otherwise, turn to Step 2.


## 5. Optimization Model of Path Planning

The proposed DCA∗PSO algorithm, which has stronger optimization performance, is used to solve the optimization model of path planning for UAV. The detailed process is shown in Figure 5. The steps are described as follows:Step 1.
Establish the environment model.Figure 5
The flow chart of the DCA∗PSO algorithm.The environment information is established, mainly including the planning space, the obstacle information, the center, and the size of the threat sources.Step 2.
Initialize the parameters.Initialize the parameters of the DCA∗PSO algorithm. The parameters include the population size, the maximum number of iteration, the number of waypoints, the maximum number of iterations Imax, the upper and lower bounds of the velocity of the position, and the learning factor and inertial coefficient.Step 3.
Initialize the route.For the first particle,x,y,z coordinates of the waypoints are initialized as
(36)xi=i×xT−xSNw+1,yi=i×yT−ySNw+1,zi=Zterrainxi,yi+Dsafe.From the second particle tom−1-th particle, x coordinates of the waypoints are given by evenly distributed on x-axis of the coordinate from the starting point S to the goal for m−1 particles, and y coordinates of the waypoints are selected randomly within the bounds for m−1 particles. Due to the altitude of the terrain information is known before the planning, take full advantage of the altitude of the terrain to optimize the initial routes. So z-coordinate of i-th waypoint is given as follows
(37)zi=Zterrainxi,yi+Dsafe,where Zterrainxi,yi represents the corresponding terrain altitude of the coordinate xi,yi, and Dsafe denotes a safety reference. The m-th path is obtained by using A∗PSO algorithm according to the cost function of A∗ algorithm.Step 4.
Evaluate the particle.Calculate the group fitness value of each group. If the new fitness value is better than that of the current value, this value is regarded as the new best fitness value of individual. The path based on DC strategy is found by combining the group with the best group fitness value in all groups. Calculate the fitness valueFA∗PSO of the path based on A∗PSO algorithm. Compare FDC and FA∗PSO, then, the route with a smaller fitness value is set as the current global best value Fgbest. This route with global best fitness is taken in regard as the global best route.Step 5.
Update the velocity and position.Update the velocity and the position ofm−1 particles by (18) from the first group to g-th based on DC strategy. A∗PSO algorithm is adopted to obtain m-th optimal path.Step 6.
Determine the end condition.Determine whether the termination condition is met, then output the global optimum value and the corresponding route. Otherwise, turn to Step 4.


## 6. The Data Simulation and Analysis

In order to demonstrate the performances of the DCA∗PSO algorithm for the path planning problem, a series of experiments with the realistic environment maps [37] were implemented on a PC with Intel Core (TM) i7-9700 CPU @3.00GHz running Windows10. Each group of experiments was conducted 30 times independently, and the main data of the results were recorded in table for the further analysis.


### 6.1. The Analysis of Different Waypoint Number

The number of the waypoints is an important parameter that affects the performance of the algorithm, which has a very close relationship with accuracy of the route and algorithm computational efficiency. With the number increase of waypoints, the search difficulty of the algorithm will increase rapidly. The following experiments were implemented for testing the performance of DCA∗PSO algorithm when the number of the waypoints changes. The parameters of DCA∗PSO are set as follows: population size N=100, the maximum iteration tmax=100, the personal influence c1=1.5, and the social influence parameter c2=1.5. The number of the dividing point is Nd=6. Three cases are utilized to test: case I is a simple environment with nine threat sources, case II is a complicated model with 24 threat sources, and case III is a larger map environment with 32 threat sources. The statistical results of the three cases are listed in Table 1, which include the best cost, mean cost, standard deviation of the fitness value, Gc, Gc~, and FR during 30 independent runs. Among these, Gc and Gc~ denote the iteration number when the algorithm finds the feasible flight route, which reflects the convergence speed and the efficiency of the algorithm. The Gc is the smallest iteration number in 30 runs, and Gc~ is the mean iteration number in 30 runs. FR means the percentage of the feasible routes in 30 runs, which is the ratio of the runs satisfying the constraints in the total runs. The best results are marked with boldface for clarity. It is only the feasible routes can be used for the statistics of column 6-7. The typical 3D displays and contour routes with different numbers of the waypoints in case I, case II, and case III during 30 runs are plotted in Figures 6, 7, and 8, respectively. It is noted that the mean cost value is represented as the reciprocal of the mean cost value in Figures 6(a), 7(a), and 8(a). According to Ref. [18], Nw is determined as
(38)PLNw+1⋅Nd<DI,where PL is the route length, DI is the minimal diameter of all the missiles and radars in space, and Nw is the number of the waypoints (not including start point and endpoint). In general, DI=0.5. The minimum value of Nw is determined by (38).Table 1
The statistical results of three cases.
ItemNwMin costMean costStd. dev.GcGc~FR (%)Case I51.48511.69510.54701696.6771.50561.67990.137416100101.53521.64430.083615100151.54321.71300.1322510100201.53151.62430.0739512100251.60222.07250.911292393.33Case II52.24253.33621.28964157071.61012.22010.441331596.67101.62491.82120.110226100151.53711.79240.2645516100201.52551.70330.632541296.67251.59851.98631.062741390Case III501.41521.47850.0877410100601.35221.39130.034349100701.42521.44920.0420512100801.36311.71310.952351390901.38131.86340.9499514901001.39161.76710.937672490Figure 6
The comparison of results with different numbers in case I.
(a)
The convergence curves in case I(b)
The 3D planned routes in case I(c)
The contour of planned routes in case IFigure 7
The comparison of results with different numbers in case II.
(a)
The convergence curves in case II(b)
The 3D planned routes in case II(c)
The contour of planned routes in case IIFigure 8
The comparison of results with different numbers in case III.
(a)
The convergence curves in case III(b)
The 3D planned routes in case III(c)
The contour of planned routes in case IIIFrom Table1, it is easy to know that the best mean fitness value and standard deviation are obtained when Nw=20 in case I. The smallest value of the best cost is obtained when Nw=5, and the best FR is obtained when Nw=7, Nw=10, Nw=15, and Nw=20. When Nw=7 and Nw=10, the indicator Gc~ is superior to when Nw=15, Nw=20, and Nw=25. The convergence speed is faster than that of the larger number of path points. Overall, in case I, Nw=20 is the most appropriate value. The FR and the mean fitness value are superior to the other Nw. In case II, as the number of the threat resources increases, the standard deviation and the mean fitness value get worse than those of case I. The best mean fitness cost is obtained when Nw=20, and the standard deviation is obtained when Nw=10. The best FR is obtained when Nw=10 and Nw=15.In case III, the best results are obtained whenNw=60. The preference of Nw=50, Nw=60, and Nw=70 is better than that of Nw=80, Nw=90, and Nw=100. When the number of the waypoints gets larger, the search of the path becomes more difficult and the FR will get low. On the other hand, when the number of the waypoint is too small, the dangerous zone has no way to be avoided efficiently. It is more obvious for the environment where a large number of threat sources exist. If the number of the waypoint is too small or too large, the standard deviation and the FR will get worse. Meanwhile, due to the number of threat sources increases, the security area will get narrow. The planned paths with different numbers of path points will be clustered in a narrow region. The greater the number of waypoints is, the slower convergence speed is, and more complicate the problem becomes. Figure 7 shows the experimental results in case II.


### 6.2. The Performance Comparison of Different Algorithms

In this section, to evaluate the performance of DCA∗PSO, some population-based optimization algorithms, such as DE [38], PSO [17], QPSO [39], AIWPSO [40], and PSOPC [41], are utilized to make several comparisons based on different indicators. Three cases are designed to test the performance of six algorithms.In case IV and case V, the population size and maximum number of iterations for six algorithms are the same, which are equal to 100 and 200, respectively. The number of the waypoints is set to 7 and 10 for cases IV and V, respectively. The specified parameters for the different algorithms are shown in Table2. The simulation results for six different algorithms are given in Figure 9, Figure 10, and Table 3.Table 2
The parameter values of different methods.
AlgorithmParametersDEF=0.4,Cr=0.9DCA∗PSOw=0.73,c1=c2=1.5PSOw=0.7298,c1=c2=1.4960QPSOb∈0.3,0.7AIWPSOw∈0,1PSOPCw∈0.7,0.9,c1=c2=0.5,c3∈0.4,0.6Figure 9
The comparison results of various methods in case IV.
(a)
The average cost in case IV(b)
The 3D UAV route in case IV(c)
The 2D UAV route in case IVFigure 10
The comparison results of various methods in case V.
(a)
The average cost in case V(b)
The 3D UAV route in case V(c)
The 2D contour route in case VTable 3
The statistical results of two cases.
ItemMethodMin costMean costStd. dev.G~cFR (%)Case IVDE1.99143.04801.441910483.33DCA∗PSO1.72371.88790.61251196.67PSO1.85115.33843.933511523.33QPSO1.85933.46391.588010763.33AIWPSO1.82755.30142.09006720PSOPC1.83085.38402.379112623.33Case VDE2.75754.39761.202517026.67DCA∗PSO1.69281.94000.10227100PSO2.28374.68351.390113830QPSO1.89284.96181.15918710AIWPSO1.87493.96071.81405553.33PSOPC1.85323.39241.688710963.33Figure9(a) shows the convergence curves of the average fitness value during the process of 200 generations in case IV, which is a crucial indicator of algorithm performance. As can be seen from Figure 9(a), because the convergence curve of the DCA∗PSO algorithm is always above that of the other five algorithms, it is concluded that the convergence speed of the DCA∗PSO algorithm is faster than the DE, PSO, QPSO, AIWPSO, and PSOPC. The indicator Gc in Table 3 also reflects that the convergence speed of DCA∗PSO is superior to other algorithms. Moreover, the global search ability of the DCA∗PSO algorithm is better than the other five algorithms. From Table 3, it is easy to see that the DCA∗PSO algorithm has the minimum standard deviation, which indicates that the DCA∗PSO algorithm has stronger robustness. The FR, the average cost value, and standard deviation of DE and QPSO are better than PSO, AIWPSO, and PSOPC.The typical 3D stereo displays and contour profiles corresponding to six route planners are shown in Figures9(b) and 9(c) in case V. It can be seen that the flight route generated by DCA∗PSO is shorter and smoother than those based on the DE, PSO, QPSO, AIWPSO, and PSOPC. Among these, the routes by the AIWPSO, PSO, PSOPC, and AIWPSO can avoid threat safely in case V. Due to the routes by DE and QPSO go through the threat, the two algorithms fail to search for a safe path. Threat-avoidance route can increase the effectiveness of performing mission for UAV and enhance the success rate of the mission.The experimental results of case V are shown in Figure10. The average convergence curves express that DCA∗PSO still is superior to DE, PSO, QPSO, AIWPSO, and PSOPC algorithms in Figure 10(a). From the statistical data in Table 3, it is not hard to find that the average fitness cost value, the standard deviation, Gc~, and the successful rate FR of DCA∗PSO are better than those of the other five algorithms. So DCA∗PSO can obtain more excellent performance of the search ability, robustness, and convergence speed in two cases. In case V, the performance of DE and QPSO is worse than case IV. The mean fitness cost of DE and QPSO is larger than AIWPSO and PSOPC algorithms. Figures 10(b) and 10(c) show the 3D stereo displays and contour profiles in case V, and only DE and DCA∗PSO can find the safe route to avoid the detection from the radars.Intelligent method is sensitive to the number of waypoint for the UAV route planning application. As the number of the waypoints increases, a feasible flight route obtained by the algorithm will become more and more difficult in high-dimensional search space. The large realistic terrain environment is utilized to test the performance of DCA∗PSO when solving the high-dimensional planning problem.In order to further demonstrate the optimization performance of the proposed DCA∗PSO algorithm, SLPSO [33], CCPSO2 [34], DMSPSO [35], and CSO [36] are selected to solve the constructed multi-objective optimization model of route planning. The parameters of these algorithms are set in Table 4.Table 4
The parameters of the algorithms.
AlgorithmParameterCSOm=200,φ=0.15CCPSO2m=200,p=0.5,S=2,5,10,20,50,100DMSPSOm=60,w=0.729,c1=c2=1.49445SLPSOm=100,α=0.5,β=0.01DCA∗PSOm=200,w=0.73,c1=c2=1.5,Nd=5The comparison results are shown in Table5. It is noted that the performance of CSO, CCPSO2, DMSPSO, and SLPSO in case III cannot find the feasible route in 30 runs. As can be seen from Table 5, the minimum cost, mean cost, and FR of DCA∗PSO is best among the five algorithms. But the standard deviation is not the minimum one in five algorithms. Because there were three turns in all 30 turns experiments cannot find a feasible solution for the DCA∗PSO algorithm, the standard deviation is increased by the penalty constant.Table 5
The statistical results of different algorithms in case III.
MethodMin costMean costStd. dev.FR (%)CSO13.299013.52310.14220CCPSO214.877420.75423.66290DMSPSO28.212529.20211.45120SLPSO23.975425.63410.72120DCA∗PSO1.39161.76710.937690The path planners based on CSO, CCPSO2, DMSPSO, and SLPSO failed to generate a flight route in case III. The convergence curves are shown in Figure11.Figure 11
The average cost of different algorithms in case III.By comparing the convergence curves shown in Figure11, it is easy to see that as the increase of waypoint number, the initial fitness cost of the DCA∗PSO algorithm is far better than four improved PSO algorithm. The DCA∗PSO still can obtain a more satisfactory performance than the other four PSO-based algorithms and eventually find a flight optimal path with less cost when the number of path points is large. In general, the DCA∗PSO algorithm can effectively improve the performance of route planning in a 3D complex environment. The proposed DCA∗PSO algorithm takes on the ability to escape the local minimum value and improve the global search ability of algorithm.


## 6.1. The Analysis of Different Waypoint Number

The number of the waypoints is an important parameter that affects the performance of the algorithm, which has a very close relationship with accuracy of the route and algorithm computational efficiency. With the number increase of waypoints, the search difficulty of the algorithm will increase rapidly. The following experiments were implemented for testing the performance of DCA∗PSO algorithm when the number of the waypoints changes. The parameters of DCA∗PSO are set as follows: population size N=100, the maximum iteration tmax=100, the personal influence c1=1.5, and the social influence parameter c2=1.5. The number of the dividing point is Nd=6. Three cases are utilized to test: case I is a simple environment with nine threat sources, case II is a complicated model with 24 threat sources, and case III is a larger map environment with 32 threat sources. The statistical results of the three cases are listed in Table 1, which include the best cost, mean cost, standard deviation of the fitness value, Gc, Gc~, and FR during 30 independent runs. Among these, Gc and Gc~ denote the iteration number when the algorithm finds the feasible flight route, which reflects the convergence speed and the efficiency of the algorithm. The Gc is the smallest iteration number in 30 runs, and Gc~ is the mean iteration number in 30 runs. FR means the percentage of the feasible routes in 30 runs, which is the ratio of the runs satisfying the constraints in the total runs. The best results are marked with boldface for clarity. It is only the feasible routes can be used for the statistics of column 6-7. The typical 3D displays and contour routes with different numbers of the waypoints in case I, case II, and case III during 30 runs are plotted in Figures 6, 7, and 8, respectively. It is noted that the mean cost value is represented as the reciprocal of the mean cost value in Figures 6(a), 7(a), and 8(a). According to Ref. [18], Nw is determined as
(38)PLNw+1⋅Nd<DI,where PL is the route length, DI is the minimal diameter of all the missiles and radars in space, and Nw is the number of the waypoints (not including start point and endpoint). In general, DI=0.5. The minimum value of Nw is determined by (38).Table 1
The statistical results of three cases.
ItemNwMin costMean costStd. dev.GcGc~FR (%)Case I51.48511.69510.54701696.6771.50561.67990.137416100101.53521.64430.083615100151.54321.71300.1322510100201.53151.62430.0739512100251.60222.07250.911292393.33Case II52.24253.33621.28964157071.61012.22010.441331596.67101.62491.82120.110226100151.53711.79240.2645516100201.52551.70330.632541296.67251.59851.98631.062741390Case III501.41521.47850.0877410100601.35221.39130.034349100701.42521.44920.0420512100801.36311.71310.952351390901.38131.86340.9499514901001.39161.76710.937672490Figure 6
The comparison of results with different numbers in case I.
(a)
The convergence curves in case I(b)
The 3D planned routes in case I(c)
The contour of planned routes in case IFigure 7
The comparison of results with different numbers in case II.
(a)
The convergence curves in case II(b)
The 3D planned routes in case II(c)
The contour of planned routes in case IIFigure 8
The comparison of results with different numbers in case III.
(a)
The convergence curves in case III(b)
The 3D planned routes in case III(c)
The contour of planned routes in case IIIFrom Table1, it is easy to know that the best mean fitness value and standard deviation are obtained when Nw=20 in case I. The smallest value of the best cost is obtained when Nw=5, and the best FR is obtained when Nw=7, Nw=10, Nw=15, and Nw=20. When Nw=7 and Nw=10, the indicator Gc~ is superior to when Nw=15, Nw=20, and Nw=25. The convergence speed is faster than that of the larger number of path points. Overall, in case I, Nw=20 is the most appropriate value. The FR and the mean fitness value are superior to the other Nw. In case II, as the number of the threat resources increases, the standard deviation and the mean fitness value get worse than those of case I. The best mean fitness cost is obtained when Nw=20, and the standard deviation is obtained when Nw=10. The best FR is obtained when Nw=10 and Nw=15.In case III, the best results are obtained whenNw=60. The preference of Nw=50, Nw=60, and Nw=70 is better than that of Nw=80, Nw=90, and Nw=100. When the number of the waypoints gets larger, the search of the path becomes more difficult and the FR will get low. On the other hand, when the number of the waypoint is too small, the dangerous zone has no way to be avoided efficiently. It is more obvious for the environment where a large number of threat sources exist. If the number of the waypoint is too small or too large, the standard deviation and the FR will get worse. Meanwhile, due to the number of threat sources increases, the security area will get narrow. The planned paths with different numbers of path points will be clustered in a narrow region. The greater the number of waypoints is, the slower convergence speed is, and more complicate the problem becomes. Figure 7 shows the experimental results in case II.


## 6.2. The Performance Comparison of Different Algorithms

In this section, to evaluate the performance of DCA∗PSO, some population-based optimization algorithms, such as DE [38], PSO [17], QPSO [39], AIWPSO [40], and PSOPC [41], are utilized to make several comparisons based on different indicators. Three cases are designed to test the performance of six algorithms.In case IV and case V, the population size and maximum number of iterations for six algorithms are the same, which are equal to 100 and 200, respectively. The number of the waypoints is set to 7 and 10 for cases IV and V, respectively. The specified parameters for the different algorithms are shown in Table2. The simulation results for six different algorithms are given in Figure 9, Figure 10, and Table 3.Table 2
The parameter values of different methods.
AlgorithmParametersDEF=0.4,Cr=0.9DCA∗PSOw=0.73,c1=c2=1.5PSOw=0.7298,c1=c2=1.4960QPSOb∈0.3,0.7AIWPSOw∈0,1PSOPCw∈0.7,0.9,c1=c2=0.5,c3∈0.4,0.6Figure 9
The comparison results of various methods in case IV.
(a)
The average cost in case IV(b)
The 3D UAV route in case IV(c)
The 2D UAV route in case IVFigure 10
The comparison results of various methods in case V.
(a)
The average cost in case V(b)
The 3D UAV route in case V(c)
The 2D contour route in case VTable 3
The statistical results of two cases.
ItemMethodMin costMean costStd. dev.G~cFR (%)Case IVDE1.99143.04801.441910483.33DCA∗PSO1.72371.88790.61251196.67PSO1.85115.33843.933511523.33QPSO1.85933.46391.588010763.33AIWPSO1.82755.30142.09006720PSOPC1.83085.38402.379112623.33Case VDE2.75754.39761.202517026.67DCA∗PSO1.69281.94000.10227100PSO2.28374.68351.390113830QPSO1.89284.96181.15918710AIWPSO1.87493.96071.81405553.33PSOPC1.85323.39241.688710963.33Figure9(a) shows the convergence curves of the average fitness value during the process of 200 generations in case IV, which is a crucial indicator of algorithm performance. As can be seen from Figure 9(a), because the convergence curve of the DCA∗PSO algorithm is always above that of the other five algorithms, it is concluded that the convergence speed of the DCA∗PSO algorithm is faster than the DE, PSO, QPSO, AIWPSO, and PSOPC. The indicator Gc in Table 3 also reflects that the convergence speed of DCA∗PSO is superior to other algorithms. Moreover, the global search ability of the DCA∗PSO algorithm is better than the other five algorithms. From Table 3, it is easy to see that the DCA∗PSO algorithm has the minimum standard deviation, which indicates that the DCA∗PSO algorithm has stronger robustness. The FR, the average cost value, and standard deviation of DE and QPSO are better than PSO, AIWPSO, and PSOPC.The typical 3D stereo displays and contour profiles corresponding to six route planners are shown in Figures9(b) and 9(c) in case V. It can be seen that the flight route generated by DCA∗PSO is shorter and smoother than those based on the DE, PSO, QPSO, AIWPSO, and PSOPC. Among these, the routes by the AIWPSO, PSO, PSOPC, and AIWPSO can avoid threat safely in case V. Due to the routes by DE and QPSO go through the threat, the two algorithms fail to search for a safe path. Threat-avoidance route can increase the effectiveness of performing mission for UAV and enhance the success rate of the mission.The experimental results of case V are shown in Figure10. The average convergence curves express that DCA∗PSO still is superior to DE, PSO, QPSO, AIWPSO, and PSOPC algorithms in Figure 10(a). From the statistical data in Table 3, it is not hard to find that the average fitness cost value, the standard deviation, Gc~, and the successful rate FR of DCA∗PSO are better than those of the other five algorithms. So DCA∗PSO can obtain more excellent performance of the search ability, robustness, and convergence speed in two cases. In case V, the performance of DE and QPSO is worse than case IV. The mean fitness cost of DE and QPSO is larger than AIWPSO and PSOPC algorithms. Figures 10(b) and 10(c) show the 3D stereo displays and contour profiles in case V, and only DE and DCA∗PSO can find the safe route to avoid the detection from the radars.Intelligent method is sensitive to the number of waypoint for the UAV route planning application. As the number of the waypoints increases, a feasible flight route obtained by the algorithm will become more and more difficult in high-dimensional search space. The large realistic terrain environment is utilized to test the performance of DCA∗PSO when solving the high-dimensional planning problem.In order to further demonstrate the optimization performance of the proposed DCA∗PSO algorithm, SLPSO [33], CCPSO2 [34], DMSPSO [35], and CSO [36] are selected to solve the constructed multi-objective optimization model of route planning. The parameters of these algorithms are set in Table 4.Table 4
The parameters of the algorithms.
AlgorithmParameterCSOm=200,φ=0.15CCPSO2m=200,p=0.5,S=2,5,10,20,50,100DMSPSOm=60,w=0.729,c1=c2=1.49445SLPSOm=100,α=0.5,β=0.01DCA∗PSOm=200,w=0.73,c1=c2=1.5,Nd=5The comparison results are shown in Table5. It is noted that the performance of CSO, CCPSO2, DMSPSO, and SLPSO in case III cannot find the feasible route in 30 runs. As can be seen from Table 5, the minimum cost, mean cost, and FR of DCA∗PSO is best among the five algorithms. But the standard deviation is not the minimum one in five algorithms. Because there were three turns in all 30 turns experiments cannot find a feasible solution for the DCA∗PSO algorithm, the standard deviation is increased by the penalty constant.Table 5
The statistical results of different algorithms in case III.
MethodMin costMean costStd. dev.FR (%)CSO13.299013.52310.14220CCPSO214.877420.75423.66290DMSPSO28.212529.20211.45120SLPSO23.975425.63410.72120DCA∗PSO1.39161.76710.937690The path planners based on CSO, CCPSO2, DMSPSO, and SLPSO failed to generate a flight route in case III. The convergence curves are shown in Figure11.Figure 11
The average cost of different algorithms in case III.By comparing the convergence curves shown in Figure11, it is easy to see that as the increase of waypoint number, the initial fitness cost of the DCA∗PSO algorithm is far better than four improved PSO algorithm. The DCA∗PSO still can obtain a more satisfactory performance than the other four PSO-based algorithms and eventually find a flight optimal path with less cost when the number of path points is large. In general, the DCA∗PSO algorithm can effectively improve the performance of route planning in a 3D complex environment. The proposed DCA∗PSO algorithm takes on the ability to escape the local minimum value and improve the global search ability of algorithm.


## 7. Conclusion

In this paper, considering the minimum route length, the minimum flight height, the minimum risk of being detected, the dynamic constraints of fix-wing UAV (e.g., the turning angle and slope angle), and the terrain constraint, a multiobjective optimization model of path planning problem for fix-wing UAV is constructed. A novel improved PSO called DCA∗PSO is proposed to solve the UAV route planning problem. DCA∗PSO is presented by introducing the improved A∗ algorithm and DC strategy. The improved A∗ algorithm can quickly find a high-quality solution from the particles of PSO, which speeds up the optimization of the algorithm. Meantime, the DC strategy enhances the search efficiency by optimizing the structure of particles when the number of path points increases. The experiment results in three typical cases show that DCA∗PSO is better than other methods in terms of convergence speed, robustness, and premature avoidance. The proposed method can effectively provide a valuable reference for route planning in complex 3D terrain. In future work, the cooperative route planning of multiple UAVs will be researched and extended. In future work, more parallel large-scale PSO algorithms and complex terrain environments should be adopted to enhance the performance of the path planner.



---

*Source: 7667173-2021-07-31.xml*