Path planning is one of the important links in the control process of UAVs. However, the standard particle swarm optimization (PSO) algorithm has the shortcomings of slow convergence speed and easy falling into the "premature" phenomenon in UAV path planning. To solve this problem, this paper proposes an IPSO algorithm based on integrated improved PSO. A fitness function considering constraints including path minimization and smoothness is formulated in the configuration space to describe the path planning problem of UAVs. By introducing chaos initialization, the quality of particle distribution is improved; global search and local search power of particles are balanced with the help of dynamic inertia weights and learning factors. And the Cauchy variational operator is introduced for avoiding local optimal solutions and accelerating the convergence of the algorithm. Simulation results show that the IPSO algorithm is stable with fast convergence and a small path cost while avoiding obstacles.
With the development of the mobile robot industry, UAVs are widely used in military or civilian fields such as security inspection[1], emergency rescue[2], logistics distribution[3], agricultural irrigation[4], etc. due to their high flexibility, strong maneuverability, and low cost[5]. The applications of UAVs in the above aspects all involve UAV path planning. The so-called path planning [6] is to find an optimal or approximately optimal path from the starting point to the endpoint in an environment containing obstacles, and satisfy certain constraints, such as the shortest path, the least time-consuming and the highest security.
Due to the traditional algorithms such as A* algorithm [7] and artificial potential field method [8], there are problems such as large amount of calculation, large memory occupation, complex process and poor efficiency in solving 3D paths. With the emergence of intelligent optimization algorithms, more and more researches focus on intelligent algorithms and their improved methods, and they are applied to solve the problem of robot path planning[9]. Particle swarm optimization was first proposed by Kennedy and Eberhart [10] in November 1995. The model was derived from the study of bird predation behavior in nature. Abstract each bird as a particle, each particle is a potential solution to the problem[11]. The particle evaluates the position through the fitness function and shares the information of the best position with the local neighboring particles. At the same time, the information is used to update the velocity and position, and the global optimal solution is obtained through iteration. PSO algorithm has the characteristics of simple operation, clear thinking, easy implementation ,and high efficiency, but it is also easy to have shortcomings such as long running time, unsmooth path, and easy to fall into "premature" phenomenon [12].
In response to these problems in PSO, researchers have made many improvements in initialization, particle position and velocity update rules, adjusting parameters and combining them with other optimization strategies. Hu et al. [13] introduced the weight factor to improve the traditional objective function and introduced the crossover operator of the genetic algorithm into the PSO algorithm, which increased the diversity of the population, but the operation effect was unstable. Zhang et al. [14]used the natural selection mechanism of survival of the fittest to obtain a near-optimal solution for UAV trajectory planning, but because it reduces the diversity of the PSO population, it is not conducive to finding the global optimal solution. Dewang et al. [15] used the distance between the robot and the obstacle to construct a new objective function, so that the robot successfully avoided the obstacle, but there were still problems such as slow convergence speed and so on.
Given the above problems, an improved particle swarm algorithm with faster convergence speed and better path cost is proposed in this study. Firstly, the obstacles are inflated and a 3D environment model of UAV flight is established in the configuration space. The adaptation function is constructed to increase the safety of UAV flight and the smoothness of the path by comprehensively weighing the influencing factors such as path length, obstacle collision, altitude change, and path smoothness. Then, chaos initialization is introduced to improve the quality of particle distribution and increase the stability of the algorithm. Dynamic inertia weights and learning factors are set to balance the global search and local search power of particles and improve the convergence speed. The Cauchy variational operator is introduced to improve the diversity of the population and avoid generating local optimal solutions. Finally, our simulation experiments show that the proposed method has a high success rate of planning results, fast convergence speed, small track cost, and the effectiveness and stability of the algorithm have been improved.
In the path planning of UAV, some influencing factors need to be considered, such as the path length of UAV flight, obstacle threat, flight height and so on. The path planning problem of UAV is expressed through the fitness function, which can calculate the cost of the path, and compare the cost value of different paths to judge the quality of the path[16]. The constraint functions are as follows:
The planned path needs to be optimal under certain criteria according to different application
scenarios and purposes. In this study, we choose to minimize the path length, and let the Euclidean
distance of two path nodes be expressed as = , , and the cost function of the path length
be:
( ) =
,
(
In UAV path planning, it is also necessary to guide the UAV safely through the obstacles caused by the threats. Let K be the collection of all threats, and each threat is represented by a cylinder [17] with the central coordinates of the projection of the obstacle being and the radius being . In order to make the threat cost of the UAV more accurate, the size of the UAV is considered here, and the diameter size of the UAV is set as D. Introduce the configuration space and expand the range of obstacles based on the size of the drone in the environment map to obtain the collision zone. In this environment, the robot can be used directly as a particle for path planning.
Due to the influence of various external factors and unstable positioning accuracy in the actual flight environment, the UAV still has the probability of collision with obstacles, so these factors are taken into account and the secondary expansion is carried out. The distance S from the collision zone is referred to as the danger zone. S can choose the length according to the environmental situation as shown in Figure 1.
UAV flying in an obstacle area will encounter three situations: If the UAV is outside the danger
zone, its cost is 0; when the UAV enters the danger zone, the collision occurs, and its cost is infinite; if
the UAV is between the danger zone and the collision zone, its obstacle threat cost can be calculated as:
( ) =
( + +
) −
+
(
, = ,
, Where, D represents the total number of track nodes, and is the height value at the dth track node.
For UAV, it is not only necessary to shorten the path length as much as possible, but also to reduce the ups and downs of the path in complex environments to make it go to the termination point smoothly. The smoothness of the path is determined by the angle between two imaginary lines connected by two continuous positions of the target point and the UAV in the iterative process. Calculating the smoothing cost requires calculating the turning angle and climbing angle. The turning angle is the angle between the horizontal plane projections of two consecutive path segments, Path segment , = in the horizontal plane projection vector respectively to remember
. Then the turning Angle can be computed as: constraint can be computed as:
The climb angle is the angle at which the current waypoint is pitched vertically to the next waypoint. If the vertical height difference between two adjacent waypoints is , − , , then the climbing angle = arctan = arctan , × ,
, ∙ , ,
− , , + The path smoothing cost associated with turning and climbing angles can be expressed as: ( ) = − , and
are the penalty coefficients for the turning angle and the climb angle.
In this paper, four constraints are weighed in this paper: path length, obstacle threat, flight altitude,
and path smoothing. Define the total fitness function according to equations (
Where , ,
are constants, which represent the weight values of different costs, and their proportions are related to the tasks performed by the UAV. ( ) is the total cost. ( ) is the path length cost; ( ) is the obstacle threat cost; ( ) is the flight altitude cost; ( ) is the path
and value, and the update equation is:
For the three-dimensional space path planning problem discussed in this paper, suppose that in a Ddimensional search space, the total number of particles is N, and the position of the ith particle is represented by a d-dimensional vector: d-dimensional vector, denoted as can save the optimal position , = ( = ( = ( , , ⋯ , , , , ⋯ , , ⋯ ,
), The velocity of the ith particle is also a ). Particles have the ability to remember, which ) during the ith particle iteration, and also have social learning ability, which can share the optimal position = ( , , ⋯ , ) among all particles.
Then for the ith particle of the kth generation, the velocity and position of the particle are updated
according to equations (
−
+
=
+
(
where = {1,2, ⋯ , } is the serial number of the particle, = {1,2, ⋯ , } is the dimension. is an inertial factor that affects the particle's global search ability and local search ability. individual learning factors and social learning factors, respectively, which affect the ability of particles and are to acquire information. and
are random numbers in the range 0,1 and are used to increase search Before each particle flight, determine whether has crossed the set speed range. If crossed, the velocity boundary value is substituted for the current speed. After flying, determine whether exceeds the maximum search space. If it is exceeded, the boundary value is also replaced by the current value.
in the particle swarm according to the corresponding change in fitness , = = , ,
,
,
,
,
,
≤
>
≤
,
>
,
,
,
,
(
The stability and solution of the PSO algorithm are affected by the initial particle distribution. Chaos
initialization can improve the quality of particle distribution, speed up algorithm initialization, and
improve the stability of particle swarm optimization. Considering the good uniform distribution of
Logistic chaos[18], Logistic chaos is used to initialize the position of the particle swarm. The basic
formula is as follows:
=
(1 − )
(
A larger inertia weight is more conducive to global search, while a smaller inertia weight is more
conducive to local search. Moreover, the particle has strong nonlinearity in the search process, and the
nonlinear adjustment control parameter is beneficial to adjust the local and global search ability of the
particle and improve the convergence speed of the algorithm. Therefore, a nonlinear inertia weight is
proposed to dynamically adjust the inertia factor during the search process of the algorithm. As shown
in Equation (
inertia weight, respectively. T is the maximum number of iterations.
The learning factor has a certain influence on the direction of particle search. By adaptive amplitude
modulation design of the learning factors, the particle population can accelerate the approach to the
optimal solution in the iterative learning process, and at the same time avoid the population falling into
the local optimum. As shown in Equations (
When c2 is large, it can guide the search direction of the global optimal solution of the particle, which is suitable for the early iteration and helps to improve the convergence speed. When c1 is large, the searchability of particles can be strengthened, and it is generally set in the late iteration to prevent the algorithm from falling into the local optimum. ,
is the maximum and minimum values is the maximum and minimum values of the social learning
The traditional PSO algorithm lacks the diversity of the particle population, and the Cauchy mutation[19] is introduced into it, which can generate large disturbance near the current individual particle, expand the search space, increase the population diversity, and avoid falling into the local optimal solution.
If ∈ (−∞, +∞) satisfies the condition given by equation (16), it becomes a Cauchy distribution. (; , ) =
(16) , = = ( ( 1 + 1 −
1 density function, and equation (17) is its cumulative distribution function.
In the formula:
is the location of the maximum value of the function, is the half the width of the scale parameter at half with . When and are 1 and 0, satisfy the condition of a probability ( ) = arctan( ) +
(17) 1 2
The inverse function can be derived by inverting equation (17), and then the random numbers generated by the uniform distribution can be generated to obey the random numbers of the Cauchy distribution, as shown in equation (18).
= tan −
(18) 1 2
Where CM is the Cauchy variational operator and rand is any real number uniformly distributed in
the range of (
The dynamic adjustment of the Cauchy variation step can make the particles generate perturbation at a larger step in the early stage of the algorithm operation to make the particles jump out of the current position; and accelerate the convergence at a smaller step in the later stage. The update rule for each particle in each iteration is as follows： = + ∙ ∙ exp ( 1 − ) ∙ is the position of particle i,
is the position of particle i after passing the Corsi variation, is a constant coefficient to control how fast or slow the variation step changes, and k is the current
The pseudo code of the IPSO algorithm is shown below: 4 5 6 7 8 9 10 11 end 13 end
particle; Algorithm 1: Pseudocode of the proposed IPSO algorithm 1 Get search map; 2 The velocity of the particle is randomly initialized, and the position of the particle is initialized with the Logistic map; 3 for ← 1 to T do
Calculate the particle fitness value; foreach ← 1 to N do
Find ,
; ;
; Update the inertia weight and the learning factor; Update the position and velocity of the local best particle; 12 Update the position and velocity of the global best
threats are set up in these scenes.
This experiment simulates UAV path planning in MATLAB R2020b. The environment model for the experiment is a 3D terrain environment built from real digital elevation model maps, and obstacle
In order to evaluate the performance of IPSO algorithm, three typical PSO variants are selected for comparison with IPSO algorithm in this experiment, which is the traditional particle swarm algorithm PSO, particle swarm algorithm
with a linear variation of inertia weights (LDWPSO), and CPSO algorithm with the introduction of linear inertia weights and logistic chaos mapping. The specific parameter settings are shown in Table 1. For the purpose of ensuring the fairness of using different algorithms for experimental comparison, the dimensionality D of the test function is set to 20, the initial population number N is set to 500, the maximum number of iterations T is set to 200, and each algorithm is run 50 times independently.
IPSO has the shortest algorithm running time of 7.32 seconds, 76% shorter compared to the PSO algorithm, and at the same time, the optimal value, variance and average value of the adaptation of IPSO algorithm is also the smallest, showing better the path optimality and stability of IPSO algorithm. IPSO and the other three algorithms, which shows that the IPSO algorithm has the lowest adaptation value and better convergence accuracy than the other three algorithms.
The top view of the paths of the four algorithms is shown in Figure 3. Combining the results in Table 2 and Figure 2 shows that all four algorithms can generate feasible paths that satisfy the requirements of path length, threat, and smoothness. However, the PSO algorithm tends to fall into the phenomenon of "premature maturity", and there is no way to find a high-quality solution. The CPSO algorithm introduces chaos theory, which makes the algorithm more stable. IPSO algorithm uses Cauchy mutation to increase the diversity of particle population, and can accurately obtain the approximate optimal solution.
This paper proposes an IPSO algorithm to improve the traditional particle swarm optimization algorithm in path planning, which has the problems of long initialization time, slow convergence speed and easy to fall into local optimal solution. The cost function with various constraints is designed in the configuration space; chaotic initialization is introduced to increase the stability of the algorithm; dynamic inertia weights and learning factors are set to improve the convergence efficiency, and the Cauchy variational operator is used to increase the population diversity. Through experimental simulation, it can be seen that the improved algorithm has the effect of a stable algorithm, fast convergence, and a better path while avoiding obstacles safely. This paper addresses the single UAV path planning problem in the presence of static obstacles, but in the actual environment there may be dynamic obstacles, and the problem of multi-UAV interaction also needs to be considered, so future research will further consider the multi-UAV collaborative planning problem under the influence of dynamic obstacles and other effects, and propose corresponding solutions.
This research was funded by National Project of Foreign Experts (No.G2022033007L), The Bagui
[16] R.K. Mandava, S. Bondada, P.R. Vundavilli, An optimized path planning for the mobile robot using potential field method and PSO algorithm, Soft Computing for Problem Solving, Springer2019, pp. 139-150. [17] M.D. Phung, Q.P.J.A.S.C. Ha, Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization, Applied Soft Computing, 107 (2021) 107376. [18] D. Tian, Z.J.S. Shi, e. computation, MPSO: Modified particle swarm optimization and its applications, Swarm and evolutionary computation, 41 (2018) 49-68.