# A Novel Sparrow Particle Swarm Algorithm (SPSA) for Unmanned Aerial Vehicle Path Planning

Authors: Wangwang. Yu; Jun. Liu; Jie. Zhou
Journal: Scientific Programming
 (2021)

---

## Abstract

Unmanned aerial vehicle (UAV) has been widely used in various fields, and meeting practical high-quality flight paths is one of the crucial functions of UAV. Many algorithms have the problem of too fast convergence and premature in UAV path planning. This study proposed a sparrow particle swarm algorithm for UAV path planning, the SPSA. The algorithm selects a suitable model for path initialization, changes the discoverer position update, and reinforces the influence of start-end line on path search, which can significantly reduce blind search. The number of target points reached is increased by adaptive variable speed escapes in areas of deadlock. In this case, the planned trajectory will fluctuate, and adaptive oscillation optimization can effectively reduce the fluctuation of the path. Finally, the optimal path is simplified, and the path nodes are interpolated with cubic splines to improve the smoothness of the path, which improves the smoothness of the UAV flight trajectory and makes it more suitable for use as the UAV real flight trajectory. By comparison, it can be concluded that the improved SPSA has good convergence speed and better search results and can avoid local optimality.


---

## Body

## 1. Introduction

Unmanned aerial vehicle (UAV) has been widely used in various fields, such as transportation, rescue, and military, with the continuous progress of technology. Compared with ground robot path planning, the path planning of UAV in 3D environment increases the complexity of trajectory calculation as the spatial dimension rises. UAVs are affected by buildings, weather, and their energy consumption during flight, so how to plan a safer, more efficient, and faster path is an ongoing hot research problem. Traditional algorithms such as the A∗ algorithm [1], artificial potential field method [2, 3], and RRT [4] have been used for path planning, but most of them still suffer from high computational complexity and local convergence.A heuristic algorithm is a new solution algorithm obtained by imitating various natural phenomena and summarizing and refining that natural phenomenon. The heuristic algorithm can solve some problems that ordinary methods cannot solve. The UAV path planning problem is a multivariate problem in the real environment to find the optimal solution. Many scholars have studied this problem with heuristic algorithms [5–11] to find suitable solutions. Duan [12] et al. used the maximum-minimum adaptive ant colony optimization algorithm to replan the UAV collaborative path in dynamic and uncertain environments, determine the time for the UAV to reach the conflict point, and then determine the flight trajectory and speed of the UAV to avoid static threats and popup threats. Shiri et al. [13] proposed a neural network-assisted online control algorithm for remote UAV paths that enable UAV to make control decisions locally in harsh communication environments, thereby reducing travel time. Qu [14] et al. proposed a reinforcement learning algorithm based on the grey wolf algorithm that adaptively switches selection by controlling the performance accumulated by individual four operations of exploration, exploitation, geometric adjustment, and optimal adjustment, which has better results than other improved grey wolf algorithms. Duan [15] et al. proposed a UAV path planning based on an improved water droplet algorithm, which considers the effects of ice accumulation, Richardson number, meteorological changes, and different flight altitudes on UAV path planning. They used the virtual potential field method to adjust the flight direction of the UAV to perform static path planning and dynamic path planning for the UAV. Liu [16] et al. proposed an evolutionary algorithm based on the evolutionary algorithm for UAV path planning, which changes the t distribution algorithm to effectively solve the high computational complexity and low efficiency in UAV dynamic path planning.The sparrow search algorithm [17] is a new heuristic algorithm proposed by Jiankai Xue in 2020, and it is a group intelligence algorithm that imitates sparrow predation. The algorithm has the characteristics of fast convergence and merit-seeking solid ability. The sparrow search algorithm has been widely used in the field of control engineering, for example, tracking the maximum power point [18], network configuration [19], and path planning field [20]. Liu [21] proposed a modified sparrow search algorithm (CASSA) to balance the convergence speed and searchability. The algorithm improved the efficiency of path planning by the Corsi–Gaussian variation strategy and adaptive inertia weights. Ouyang [22] proposed the learning sparrow search algorithm (LSSA) to improve stability and security. This algorithm solves the shortcomings of strong randomness and easy to fall into local optimum. Abdulhammed [23] applied the sparrow search algorithm to the load balancing problem of cloud computing by separately provisioning different tasks to shorten the server response time and reduce power consumption. The algorithm shows that the advantages of fast convergence and good searchability of the sparrow search algorithm are highly applicable in solving engineering problems.Particle swarm algorithm [24] is an algorithm proposed by James Kennedy and Russell Eberhart, which has the characteristics of fast convergence and simple structure. Many scholars have applied it to various optimization scenarios [25–30] and achieved good results. Li [31] proposed an SLPSO algorithm for solving collision hazards, insufficiently smooth paths, and long planning paths of mobile robots in path planning, and the experimental results showed that the algorithm is effective and feasible. Phung [32] proposed an improved discrete particle swarm algorithm (DPSO) to be used in UAV path planning to improve the algorithm's performance through qualitative initialization, random variation, and edge swapping by taking advantage of parallel computing. Foo [33] proposed a particle swarm algorithm-based 3D UAV path planning that considers the fuel consumption of the UAV, flies over specified obstacles, and leaps over specified reconnaissance targets. Thabit [34] proposed a multi-robot particle swarm optimization algorithm for multi-UAV path planning in unknown situations. The robot decides the direction of movement based on the information collected by sensors and combines probabilistic windows to obtain current information and previous robot experience to select the path with better fitness.In the field of human-machine path planning, the current UAV still suffers from the problem of locally optimal solutions, making it difficult to search for globally optimal paths. A novel SPSA is proposed for this problem, which guides the subsequent path search through path initialization. The discoverer position update rule is improved to enhance the search near the start-end line. Adaptive variable speed escape search is used to improve the search efficiency of paths when obstacles are encountered. Adopting adaptive oscillation optimization reduces path fluctuations and improves path smoothing. Finally, the path smoothness is improved by simplifying the nodes and smoothing process, which is more suitable for path planning in the real environment. It is also verified that the SPSA has a shorter convergence path and lower energy consumption than other algorithms.The structure of this study is as follows: Section2 establishes the environment model that matches the actual situation. Section 3 describes the specific implementation of the sparrow search algorithm and the particle swarm algorithm. Section 4 describes the specific implementation of the SPSA. Section 5 draws the corresponding structure and flow chart for the structure of the SPSA. Section 6 analyzes the experimental results for the algorithm complexity analysis and experimental results. Section 7 concludes the SPSA.


## 2. Environment Modelling

In the actual complex environment, the UAV will encounter multiple threats such as obstacles and trees in reaching the target set from the start point, and sometimes, it also needs to consider the climate, the energy of the UAV, and other factors. The main problem of UAV path planning is the path optimization problem considering multiple disturbance factors. By building a mathematical model, the optimal flight path is calculated.


### 2.1. Environmental Model Building

The movement of the UAV is less restricted by the terrain and can reach the target point quickly in a complex environment, but the trajectory of the UAV's movement is in a three-dimensional environment. The three-dimensional environment is more complicated than the two-dimensional environment. The amount of calculation will also be tremendous. To reduce the time of UAV path calculation, the establishment of a suitable model has an important influence on the calculation of the optimal path. This study adopts the modelling method in the literature [35]. Each time the position is selected, it will move forward by one unit in the x-axis direction, simplifying the three-dimensional path problem into a two-dimensional path planning problem.Assuming that the velocity of the UAV flight is variable and disregarding the effect of the structure of the UAV on the flight, the square tall building in the real environment is equated to a square obstacle, and the cylindrical building is equated to a cylindrical obstacle, as shown in Figure1.Figure 1
Environment modelling.


### 2.2. Adaptability Calculation

The trajectory of the UAV flight is usually close to the line between the start point and the endpoint (start-end line) when avoiding obstacles, while the path should be as smooth as possible. The distance and the safety of UAV from the obstacles are considered in the literature [14]. However, the computational effort also increases with the increase in obstacles, which is not conducive to finding the globally optimal path. Considering the energy loss of UAV, a new fitness calculation is proposed as follows:(1)E=Epath+Eturning+Eclimb.The fitness value of UAV flightE is the total energy required for UAV path planning. Epath is the energy consumed for all planned paths assuming that the UAV flies at a constant speed. Eturning indicates the additional energy consumed for UAV flight turning. Eclimb indicates the energy is required for UAV climbing and landing. Eclimb represents the energy consumption for climbing and landing. It is assumed that the energy of the UAV flight consists of three parts, and one part is the energy of uniform flight, and it is assumed that the energy consumption of this part is proportional to the distance flown. The second part is that when turning, there will be additional turning energy loss in addition to the first part of energy. When the turning angle is larger, as the speed remains the same centripetal force is needed to do work, more energy is needed to maintain a constant speed and complete the flight turning. Similarly, more work is required to move the aircraft in the vertical direction, assuming that the energy required by the UAV is proportional to the distance travelled in the vertical direction. Each part of the solution equation is as follows:(2)Epath=k0·∑n=1s−1xn−xn+12+yn−yn+12+zn−zn+12,Eturning=k1·∑n=1s−1μ0∗1+cosθ,Eclimb=k2·∑s=0s−1Δz.Here,xs, ys, and zs denote the coordinates of x, y, and z axes of the nodes, respectively, μ0 denotes the turning angle coefficient, and θ denotes the angle between two adjacent line segments. When the angle is larger, the trajectory is smoother, and the fuel cost is lower. When the turn is smaller, the UAV needs to slow down, steer, and accelerate the process, which will consume more fuel. Δz denotes the variation on the z-axis between two adjacent nodes, where k0, k1, and k2 are scale factors. The fitness is performed by cubic spline interpolation, and the summation is performed for each slice of the fitness, which is similar to the energy consumption in the real situation.As the UAV flight in the actual situation of variable speed flight needs to adjust the route to avoid trees, buildings, and other obstacles, UAV flight steering requires more energyEturning, while for the flight trajectory without substantial height oscillation, the flight altitude constantly changes will also consume more energy. In general, the optimal adaptation in UAV flight corresponds to a smooth and smooth flight trajectory.


## 2.1. Environmental Model Building

The movement of the UAV is less restricted by the terrain and can reach the target point quickly in a complex environment, but the trajectory of the UAV's movement is in a three-dimensional environment. The three-dimensional environment is more complicated than the two-dimensional environment. The amount of calculation will also be tremendous. To reduce the time of UAV path calculation, the establishment of a suitable model has an important influence on the calculation of the optimal path. This study adopts the modelling method in the literature [35]. Each time the position is selected, it will move forward by one unit in the x-axis direction, simplifying the three-dimensional path problem into a two-dimensional path planning problem.Assuming that the velocity of the UAV flight is variable and disregarding the effect of the structure of the UAV on the flight, the square tall building in the real environment is equated to a square obstacle, and the cylindrical building is equated to a cylindrical obstacle, as shown in Figure1.Figure 1
Environment modelling.


## 2.2. Adaptability Calculation

The trajectory of the UAV flight is usually close to the line between the start point and the endpoint (start-end line) when avoiding obstacles, while the path should be as smooth as possible. The distance and the safety of UAV from the obstacles are considered in the literature [14]. However, the computational effort also increases with the increase in obstacles, which is not conducive to finding the globally optimal path. Considering the energy loss of UAV, a new fitness calculation is proposed as follows:(1)E=Epath+Eturning+Eclimb.The fitness value of UAV flightE is the total energy required for UAV path planning. Epath is the energy consumed for all planned paths assuming that the UAV flies at a constant speed. Eturning indicates the additional energy consumed for UAV flight turning. Eclimb indicates the energy is required for UAV climbing and landing. Eclimb represents the energy consumption for climbing and landing. It is assumed that the energy of the UAV flight consists of three parts, and one part is the energy of uniform flight, and it is assumed that the energy consumption of this part is proportional to the distance flown. The second part is that when turning, there will be additional turning energy loss in addition to the first part of energy. When the turning angle is larger, as the speed remains the same centripetal force is needed to do work, more energy is needed to maintain a constant speed and complete the flight turning. Similarly, more work is required to move the aircraft in the vertical direction, assuming that the energy required by the UAV is proportional to the distance travelled in the vertical direction. Each part of the solution equation is as follows:(2)Epath=k0·∑n=1s−1xn−xn+12+yn−yn+12+zn−zn+12,Eturning=k1·∑n=1s−1μ0∗1+cosθ,Eclimb=k2·∑s=0s−1Δz.Here,xs, ys, and zs denote the coordinates of x, y, and z axes of the nodes, respectively, μ0 denotes the turning angle coefficient, and θ denotes the angle between two adjacent line segments. When the angle is larger, the trajectory is smoother, and the fuel cost is lower. When the turn is smaller, the UAV needs to slow down, steer, and accelerate the process, which will consume more fuel. Δz denotes the variation on the z-axis between two adjacent nodes, where k0, k1, and k2 are scale factors. The fitness is performed by cubic spline interpolation, and the summation is performed for each slice of the fitness, which is similar to the energy consumption in the real situation.As the UAV flight in the actual situation of variable speed flight needs to adjust the route to avoid trees, buildings, and other obstacles, UAV flight steering requires more energyEturning, while for the flight trajectory without substantial height oscillation, the flight altitude constantly changes will also consume more energy. In general, the optimal adaptation in UAV flight corresponds to a smooth and smooth flight trajectory.


## 3. Basic Theoretical Algorithms

The choice of the algorithm has an essential impact on path planning. A suitable algorithm can improve the convergence of the optimal path and avoid local optima. This section describes the specific implementation of the involved sparrow search algorithm and particle swarm algorithm.


### 3.1. Basic Sparrow Search Algorithm

The sparrow search algorithm is a novel bionic algorithm with fast convergence and merit-seeking solid ability. Sparrows are divided into producers and scroungers. The identities of producers and scroungers can be interchanged, but the weight remains the same in the population. The producer with good adaptation in the sparrow search algorithm will get food first. The producers' positions are updated by the following equation(3)Pi,jt+1=Pi,jt·exp−iα⋅itermax,ifR2<ST,Pi,jt+Q⋅L,ifR2≥ST.Here,t denotes the current iteration, i denotes the serial number of the current scrounger, j denotes the dimension, α is a random number, and itermax denotes the maximum number of iterations. r2 and ST denote the warning value and safety value, which are constants, Q is a random number, and L is a 1 × d matrix, and each element is 1. When R2<ST, it means there are no predators around the foraging environment, and the scrounger can conduct an extensive search. If R2≥ST, it means that some sparrows in the population found the predator and alerted other sparrows, and then, the sparrows needed to fly to other places for foraging.The scrounger will watch the scrounger, and if it perceives that the scrounger has found better food, it will leave its present position to grab the food, and if it wins, it gets the scrounger's food. The scrounger's position is updated as follows:(4)Pi,jt+1=Q·expPworstt−Pi,jtt2,ifi>n/2,Pi,jt+1+Pi,jt−PPt+1·A+·L,otherwise.Here,Pi,jt+1 denotes the optimal position of the next iteration, Pworstt is the worst position in the current iteration, and n is the number of scroungers, where A denotes a 1 × d matrix where each element is randomly assigned to 1 or -1, and A+=ATAAT−1. When i>n/2, the less adapted scroungers need to fly elsewhere in search of food.Sparrows aware of the danger account for 10% to 20% of the total population. The locations of these sparrows are updated as follows:(5)Pi,jt+1=Pbestt+β⋅Pi,jt−Pbestt,iffi>fg,Pi,jt+1+K⋅Pi,jt−Pbesttfi−fw+ε,iffi=fg..Here,Pbestt is the current global best position, β and K are random numbers, fg and fw are the current global best and worst fitness values, and ε is a constant to avoid the denominator being zero.The presence of obstacles in the environment of UAV path planning can interfere with the sparrow search algorithm to search the optimal and worst paths, resulting in the presence of unsearchable target points and loss of good search routes. Since the absolute value of each element inA+ is the same, the presence of obstacles in the planned path loses the number of individuals.


### 3.2. Basic Particle Swarm Algorithm

The particle swarm algorithm is an algorithm that is studied by imitating the predatory behaviour of a flock of birds. The particle swarm algorithm uses massless particles to simulate the birds in a flock, and the particles have velocity and position properties. The optimal solution obtained by each particle searching for a single individual in space is used as the individual's extremum, and the extremum of all individuals is used as the optimal global solution. All particles in the swarm adjust their velocity and position according to the current individual extreme value and the optimal global solution.The particle swarm algorithm first initializes the position of the particle itself and adjusts its position by iteration. In each iteration, the particle adjusts its speed by the extreme individual value and the optimal global solution, thus changing its position. The particle swarm algorithm velocity and position updates are shown in equations (6) and (7) as follows:(6)Vijt+1=Vijt+1+c1·Rand·Pl best_ij−Pij+c2·Rand·Pg best_j−Pij,(7)Pijt+1=Pijt+Vijt+1.Here,Vij denotes the velocity in j-dimensional space of the particle with index i, Pl best_ij denotes the position in j-dimension corresponding to the particle with index i obtaining the local extremum, and Pg best_j denotes the position in j-dimension corresponding to the optimal global solution obtained by all particles. Rand is a random number from 0 to 1, and c1 and c2 are learning factors.The corresponding pseudocode for the basic particle swarm algorithm1 is shown below.Algorithm 1: Basic particle swarm algorithm pseudocode.
InitializeSet the basic parametersFor each particle iInitialize velocity and position of particlesCalculate fitnessfi and set pBesti=fiEnd Forg Best = fiFor each iterationFor each particleUpdate the position and velocity using by (6) and (7)Calculate the fitnessfiIffi < pBestipBesti = fiEnd IfIfpBesti < g Bestg Best = pBestiEnd IfEnd ForEnd ForReturn resultsTerminate


## 3.1. Basic Sparrow Search Algorithm

The sparrow search algorithm is a novel bionic algorithm with fast convergence and merit-seeking solid ability. Sparrows are divided into producers and scroungers. The identities of producers and scroungers can be interchanged, but the weight remains the same in the population. The producer with good adaptation in the sparrow search algorithm will get food first. The producers' positions are updated by the following equation(3)Pi,jt+1=Pi,jt·exp−iα⋅itermax,ifR2<ST,Pi,jt+Q⋅L,ifR2≥ST.Here,t denotes the current iteration, i denotes the serial number of the current scrounger, j denotes the dimension, α is a random number, and itermax denotes the maximum number of iterations. r2 and ST denote the warning value and safety value, which are constants, Q is a random number, and L is a 1 × d matrix, and each element is 1. When R2<ST, it means there are no predators around the foraging environment, and the scrounger can conduct an extensive search. If R2≥ST, it means that some sparrows in the population found the predator and alerted other sparrows, and then, the sparrows needed to fly to other places for foraging.The scrounger will watch the scrounger, and if it perceives that the scrounger has found better food, it will leave its present position to grab the food, and if it wins, it gets the scrounger's food. The scrounger's position is updated as follows:(4)Pi,jt+1=Q·expPworstt−Pi,jtt2,ifi>n/2,Pi,jt+1+Pi,jt−PPt+1·A+·L,otherwise.Here,Pi,jt+1 denotes the optimal position of the next iteration, Pworstt is the worst position in the current iteration, and n is the number of scroungers, where A denotes a 1 × d matrix where each element is randomly assigned to 1 or -1, and A+=ATAAT−1. When i>n/2, the less adapted scroungers need to fly elsewhere in search of food.Sparrows aware of the danger account for 10% to 20% of the total population. The locations of these sparrows are updated as follows:(5)Pi,jt+1=Pbestt+β⋅Pi,jt−Pbestt,iffi>fg,Pi,jt+1+K⋅Pi,jt−Pbesttfi−fw+ε,iffi=fg..Here,Pbestt is the current global best position, β and K are random numbers, fg and fw are the current global best and worst fitness values, and ε is a constant to avoid the denominator being zero.The presence of obstacles in the environment of UAV path planning can interfere with the sparrow search algorithm to search the optimal and worst paths, resulting in the presence of unsearchable target points and loss of good search routes. Since the absolute value of each element inA+ is the same, the presence of obstacles in the planned path loses the number of individuals.


## 3.2. Basic Particle Swarm Algorithm

The particle swarm algorithm is an algorithm that is studied by imitating the predatory behaviour of a flock of birds. The particle swarm algorithm uses massless particles to simulate the birds in a flock, and the particles have velocity and position properties. The optimal solution obtained by each particle searching for a single individual in space is used as the individual's extremum, and the extremum of all individuals is used as the optimal global solution. All particles in the swarm adjust their velocity and position according to the current individual extreme value and the optimal global solution.The particle swarm algorithm first initializes the position of the particle itself and adjusts its position by iteration. In each iteration, the particle adjusts its speed by the extreme individual value and the optimal global solution, thus changing its position. The particle swarm algorithm velocity and position updates are shown in equations (6) and (7) as follows:(6)Vijt+1=Vijt+1+c1·Rand·Pl best_ij−Pij+c2·Rand·Pg best_j−Pij,(7)Pijt+1=Pijt+Vijt+1.Here,Vij denotes the velocity in j-dimensional space of the particle with index i, Pl best_ij denotes the position in j-dimension corresponding to the particle with index i obtaining the local extremum, and Pg best_j denotes the position in j-dimension corresponding to the optimal global solution obtained by all particles. Rand is a random number from 0 to 1, and c1 and c2 are learning factors.The corresponding pseudocode for the basic particle swarm algorithm1 is shown below.Algorithm 1: Basic particle swarm algorithm pseudocode.
InitializeSet the basic parametersFor each particle iInitialize velocity and position of particlesCalculate fitnessfi and set pBesti=fiEnd Forg Best = fiFor each iterationFor each particleUpdate the position and velocity using by (6) and (7)Calculate the fitnessfiIffi < pBestipBesti = fiEnd IfIfpBesti < g Bestg Best = pBestiEnd IfEnd ForEnd ForReturn resultsTerminate


## 4. Sparrow Particle Swarm Algorithm

### 4.1. Path Initialization

UAV path planning is a pathfinding optimization that considers multiple environmental constraints and the UAV's dynamics. The selection of the next adjacent path node is affected by obstacles and the current node position constraints, and from safety considerations, the UAV cannot cross obstacles from the current node to the next node. The path initialization of the sparrow particle swarm algorithm has an essential impact on the convergence of the subsequent sparrow search algorithm. A good path initialization can effectively improve the search efficiency and prevent the path from generating large oscillations that do not conform to the characteristics of the smooth movement of the UAV in the real environment, for which a path initialization method is proposed.Assuming a variable speed of the UAV, the UAV should tend to fly to the target point if the target point is known. As shown in Figure2, Pa denotes the current position and PTarget denotes the position of the target point. Xa denotes the x-axis coordinates corresponding to the current position, and Pa+1 is the next point to be determined, and it is the orange point in Figure 2. Pt is the centre of the following available coordinate range determined from the current point Pa and the coordinates of the target point. Pt is calculated according to the following equation:(8)Pt=Pa+PTarget−Pam.Figure 2
Path selection schematic.Here,m is the difference between the horizontal coordinate Xa+m of the target point and the horizontal coordinate Xa of the current point Pa. Pa+1 is chosen by the following formula:(9)Pa+1=roundPt+2∗rand∗Δh−Δh,(10)Pt−Δh≤Pa+1≤Pt+Δh.Here,round denotes rounding. rand is a random value from 0 to 1. Δh denotes half of the square length of the range of selectable coordinate points.During the initialization process, each time the individual confirms the following position based on the current point and the target point, this improved method can avoid too much difference between two adjacent nodes during the UAV movement, interfering with the subsequent convergence.


### 4.2. Improving the Producer Location Update Formula

The traditional sparrow search algorithm with better pathfinding capability can lead to stagnant search in an environment with more obstacles, thus losing more individuals. The intelligence body has weaker search capability in an environment with more obstacles, leading to local convergence of the path search. The current speed of the particle swarm algorithm is affected by the globally optimal path, assuming that there are no obstacles between the start point and the target point. The optimal path is start-end line. If there is an obstacle, the shortest path should be closer to the start-end line. Using the start-end line as an idealized global optimal path increases the influence of this optimal global path on the producer and enhances the producer's ability to find the optimal solution in the start-end line and enhance the ability to search near the start-end line by changing the producer's function.(11)Pi,jt+1=Pi,jt+exp−iα·intermax+rand·PST−Pi,jt,iffi>fg,Pi,jt+1+rand·PST−Pi,jt,iffi=fg,Here,PST is the corresponding coordinate position on the start-end line. rand is a random number from 0 to 1. By increasing the difference between the current path and the start-end line, the searchability around the start-end line is strengthened to avoid falling into the local optimum.


### 4.3. Adaptive Variable Speed Escape Search

In the sparrow search algorithm, wheni>n/2, it indicates that the sparrow needs to fly to other places to find food for more energy, since each element in A+ has the same absolute value and is a number from 0 to 1 (excluding 0 and 1). Since the values of formula (4) running to Pi,jt+1, PPt+1, A+, and L have been fixed, when the next node is unreachable due to obstacles, even if the search is carried out again, it still cannot reach the next node, which is the same as the last one, and at this time, the path search is stalled. For this stagnation, the adaptive variable speed escape exploration is inspired by the particle swarm algorithm.When the scrounger flies to other places in search of food, if the next node is unreachable, the scrounger searches at the lowest speed and searches ten times, and if a moveable node cannot be found, the speed of movement is increased. If there is a moveable node, the search stops, and the point is taken as the current point. Every ten searches are no moveable point, and then, the speed increases by one until it reaches the maximum search speed. If it still cannot find a moveable node, then the search ends.(12)Pi,jt+1=Pi,jt+2·rand⋅≤Vcur−Vcur.Here,Vcur denotes the current velocity, increasing from the lowest velocity, since the globally optimal path corresponds to the smallest possible distance between two adjacent points.The pseudocode for the variable speed escape search Algorithm2 is shown below.Algorithm 2: Variable speed escape search algorithm pseudocode.
Update the position by equation (4)Initialize the velocityVcur of individual: Vcur =  VminSetT = 0While the position can not reachIfT = TmaxVcur = Vcur + 1IfVcur > VmaxbreakEnd IfSetT = 0End IfT = T + 1IfVcur ≤ VmaxUpdate the position by equation (12)End IfEnd While


### 4.4. Adaptive Oscillation Optimization

Since there are random numbers in the selection of paths and significant differences between other paths and the current path, it leads to the planning with oscillation. The oscillation of the drone trajectory will interfere with the judgment of the optimal path adaptation value and easily fall into local minima. The oscillating trajectory will also consume more energy of the UAV and is not suitable as the actual UAV flight trajectory.For addressing this problem, an adaptive oscillation optimization method is proposed to optimize the planned original path with adaptive oscillation to reduce the trajectory oscillation of the UAV. To reduce the path oscillation at certain points, the overall trajectory trend is judged by its multiple adjacent points to reduce the path oscillation better. The trajectory optimization equation is as follows:(13)Pi,j′=roundPi,j−1+Pi,j+…+Pi,j+NP−2NP.Here,round means rounding the value. NP is the number of adjacent nodes that will have an impact on the current position (including the node itself), the maximum value of NP is 5, and the minimum value is 3. Initially, the value of NP is 5. The optimization of the current position is influenced by the position of the previous node, this node, and the next three nodes. If the optimized position Pi,j′ has obstacles, then the value of NP is subtracted by 1 and re-optimized. If NP is less than 3, no position optimization is performed for the current point. As shown in Figure 3, the original trajectory is blue, and the path after adaptive oscillation optimization is red, which shows that the smooth trajectory has better smoothness.Figure 3
Comparison of before and after adaptive trajectory optimization.


### 4.5. Simplification of Path Nodes and Smoothing

The paths after adaptive oscillation optimization have lower oscillation compared with the original paths. The UAV should move in a straight line or smoothly as much as possible in the actual environment. To make the path more realistic, the SPSA finally converges and simplifies the optimal path nodes found to facilitate the subsequent smoothing process with the third spline interpolation.In Figure4(a), a simplified diagram of the nodes is shown, where the black line represents the planned path and the blue line represents the simplified path nodes. Point A can reach points B, C, and D, and cannot reach points E and F. Assuming that the UAV reaches point F from point A, which subsequent nodes can be reached from point A is first determined. The corresponding vector is (1, 1, 1, 0, 0), where 1 represents that it can be reached safely and 0 means that it cannot be reached safely, and there are obstacles in the linear path. The last one among these nodes sorted to represent the node that can be reached is D, and it is taken as the current node. When the current node is D, judging the subsequent nodes is continued, assuming that point D can reach point E and point F, the corresponding path vector is (1, 1), and then F is selected as the next node.Figure 4
Simplified schematic diagram of UAV trajectory nodes.This method can effectively avoid the situation that the path is not streamlined enough due to path oscillation, etc. For example, point A′ in Figure4(b) can reach points B′, C′, D′, and F′, corresponding to the vectors (1, 1, 1, 0, 1). Due to the presence of obstacles, point A′ cannot reach point E′, so directly choose F′ as the next node. Points A′, D′, and F′ form a triangle in space, by the triangle. The sum of line segment A′D′ and line segment D′F′ is greater than A′F′ by the law, from which it can be concluded that this optimization method can minimize the path.The triple spline interpolation function can improve the path's smoothness and reduce the path's twists and turns, and the path is more consistent with the flight path of the UAV as a real environment. The simplified path can be smoothed better by the cubic spline interpolation function, which reduces the turn amplitude in the path and saves the energy consumption of the UAV.


## 4.1. Path Initialization

UAV path planning is a pathfinding optimization that considers multiple environmental constraints and the UAV's dynamics. The selection of the next adjacent path node is affected by obstacles and the current node position constraints, and from safety considerations, the UAV cannot cross obstacles from the current node to the next node. The path initialization of the sparrow particle swarm algorithm has an essential impact on the convergence of the subsequent sparrow search algorithm. A good path initialization can effectively improve the search efficiency and prevent the path from generating large oscillations that do not conform to the characteristics of the smooth movement of the UAV in the real environment, for which a path initialization method is proposed.Assuming a variable speed of the UAV, the UAV should tend to fly to the target point if the target point is known. As shown in Figure2, Pa denotes the current position and PTarget denotes the position of the target point. Xa denotes the x-axis coordinates corresponding to the current position, and Pa+1 is the next point to be determined, and it is the orange point in Figure 2. Pt is the centre of the following available coordinate range determined from the current point Pa and the coordinates of the target point. Pt is calculated according to the following equation:(8)Pt=Pa+PTarget−Pam.Figure 2
Path selection schematic.Here,m is the difference between the horizontal coordinate Xa+m of the target point and the horizontal coordinate Xa of the current point Pa. Pa+1 is chosen by the following formula:(9)Pa+1=roundPt+2∗rand∗Δh−Δh,(10)Pt−Δh≤Pa+1≤Pt+Δh.Here,round denotes rounding. rand is a random value from 0 to 1. Δh denotes half of the square length of the range of selectable coordinate points.During the initialization process, each time the individual confirms the following position based on the current point and the target point, this improved method can avoid too much difference between two adjacent nodes during the UAV movement, interfering with the subsequent convergence.


## 4.2. Improving the Producer Location Update Formula

The traditional sparrow search algorithm with better pathfinding capability can lead to stagnant search in an environment with more obstacles, thus losing more individuals. The intelligence body has weaker search capability in an environment with more obstacles, leading to local convergence of the path search. The current speed of the particle swarm algorithm is affected by the globally optimal path, assuming that there are no obstacles between the start point and the target point. The optimal path is start-end line. If there is an obstacle, the shortest path should be closer to the start-end line. Using the start-end line as an idealized global optimal path increases the influence of this optimal global path on the producer and enhances the producer's ability to find the optimal solution in the start-end line and enhance the ability to search near the start-end line by changing the producer's function.(11)Pi,jt+1=Pi,jt+exp−iα·intermax+rand·PST−Pi,jt,iffi>fg,Pi,jt+1+rand·PST−Pi,jt,iffi=fg,Here,PST is the corresponding coordinate position on the start-end line. rand is a random number from 0 to 1. By increasing the difference between the current path and the start-end line, the searchability around the start-end line is strengthened to avoid falling into the local optimum.


## 4.3. Adaptive Variable Speed Escape Search

In the sparrow search algorithm, wheni>n/2, it indicates that the sparrow needs to fly to other places to find food for more energy, since each element in A+ has the same absolute value and is a number from 0 to 1 (excluding 0 and 1). Since the values of formula (4) running to Pi,jt+1, PPt+1, A+, and L have been fixed, when the next node is unreachable due to obstacles, even if the search is carried out again, it still cannot reach the next node, which is the same as the last one, and at this time, the path search is stalled. For this stagnation, the adaptive variable speed escape exploration is inspired by the particle swarm algorithm.When the scrounger flies to other places in search of food, if the next node is unreachable, the scrounger searches at the lowest speed and searches ten times, and if a moveable node cannot be found, the speed of movement is increased. If there is a moveable node, the search stops, and the point is taken as the current point. Every ten searches are no moveable point, and then, the speed increases by one until it reaches the maximum search speed. If it still cannot find a moveable node, then the search ends.(12)Pi,jt+1=Pi,jt+2·rand⋅≤Vcur−Vcur.Here,Vcur denotes the current velocity, increasing from the lowest velocity, since the globally optimal path corresponds to the smallest possible distance between two adjacent points.The pseudocode for the variable speed escape search Algorithm2 is shown below.Algorithm 2: Variable speed escape search algorithm pseudocode.
Update the position by equation (4)Initialize the velocityVcur of individual: Vcur =  VminSetT = 0While the position can not reachIfT = TmaxVcur = Vcur + 1IfVcur > VmaxbreakEnd IfSetT = 0End IfT = T + 1IfVcur ≤ VmaxUpdate the position by equation (12)End IfEnd While


## 4.4. Adaptive Oscillation Optimization

Since there are random numbers in the selection of paths and significant differences between other paths and the current path, it leads to the planning with oscillation. The oscillation of the drone trajectory will interfere with the judgment of the optimal path adaptation value and easily fall into local minima. The oscillating trajectory will also consume more energy of the UAV and is not suitable as the actual UAV flight trajectory.For addressing this problem, an adaptive oscillation optimization method is proposed to optimize the planned original path with adaptive oscillation to reduce the trajectory oscillation of the UAV. To reduce the path oscillation at certain points, the overall trajectory trend is judged by its multiple adjacent points to reduce the path oscillation better. The trajectory optimization equation is as follows:(13)Pi,j′=roundPi,j−1+Pi,j+…+Pi,j+NP−2NP.Here,round means rounding the value. NP is the number of adjacent nodes that will have an impact on the current position (including the node itself), the maximum value of NP is 5, and the minimum value is 3. Initially, the value of NP is 5. The optimization of the current position is influenced by the position of the previous node, this node, and the next three nodes. If the optimized position Pi,j′ has obstacles, then the value of NP is subtracted by 1 and re-optimized. If NP is less than 3, no position optimization is performed for the current point. As shown in Figure 3, the original trajectory is blue, and the path after adaptive oscillation optimization is red, which shows that the smooth trajectory has better smoothness.Figure 3
Comparison of before and after adaptive trajectory optimization.


## 4.5. Simplification of Path Nodes and Smoothing

The paths after adaptive oscillation optimization have lower oscillation compared with the original paths. The UAV should move in a straight line or smoothly as much as possible in the actual environment. To make the path more realistic, the SPSA finally converges and simplifies the optimal path nodes found to facilitate the subsequent smoothing process with the third spline interpolation.In Figure4(a), a simplified diagram of the nodes is shown, where the black line represents the planned path and the blue line represents the simplified path nodes. Point A can reach points B, C, and D, and cannot reach points E and F. Assuming that the UAV reaches point F from point A, which subsequent nodes can be reached from point A is first determined. The corresponding vector is (1, 1, 1, 0, 0), where 1 represents that it can be reached safely and 0 means that it cannot be reached safely, and there are obstacles in the linear path. The last one among these nodes sorted to represent the node that can be reached is D, and it is taken as the current node. When the current node is D, judging the subsequent nodes is continued, assuming that point D can reach point E and point F, the corresponding path vector is (1, 1), and then F is selected as the next node.Figure 4
Simplified schematic diagram of UAV trajectory nodes.This method can effectively avoid the situation that the path is not streamlined enough due to path oscillation, etc. For example, point A′ in Figure4(b) can reach points B′, C′, D′, and F′, corresponding to the vectors (1, 1, 1, 0, 1). Due to the presence of obstacles, point A′ cannot reach point E′, so directly choose F′ as the next node. Points A′, D′, and F′ form a triangle in space, by the triangle. The sum of line segment A′D′ and line segment D′F′ is greater than A′F′ by the law, from which it can be concluded that this optimization method can minimize the path.The triple spline interpolation function can improve the path's smoothness and reduce the path's twists and turns, and the path is more consistent with the flight path of the UAV as a real environment. The simplified path can be smoothed better by the cubic spline interpolation function, which reduces the turn amplitude in the path and saves the energy consumption of the UAV.


## 5. Structure and Flow chart of the Sparrow Particle Swarm Algorithm

### 5.1. Structure of the Sparrow Particle Swarm Algorithm

The pseudocode of the sparrow particle swarm algorithm Algorithm3 is shown below.Algorithm 3: Sparrow particle swarm algorithm (SPSA) pseudocode.
InitializeSet the basic parametersSet the start point and target pointInitialize the positionPi of each individual in the population using equations (10)–(12)Oscillation optimization of all individuals trajectoriesFor each iterationInitialize optimal fitness and worst fitnessFor each producerFor each dimensionUpdate the position ofPi by the equation (11)SetT = 0While the position can not reach and T < TmaxUpdate the position ofPi by the equation (11)T = T + 1End WhileEnd ForEnd ForFor each scroungerFor each dimensionUpdate the position ofPi by the equation (4)SetT = 0While the position can not reach and T < TmaxUpdate the position ofPi by the equation (4)T = T + 1End WhileIfT ≥ TmaxSearch for the next position by adaptive escape using equation (12)End IfEnd ForEnd ForFor each individual that finds dangerFor each dimensionUpdate the position ofPi by the equation (5)SetT = 0While the position can not reach and T < TmaxUpdate the position ofPi by the equation (5)T = T + 1End WhileEnd ForEnd ForOptimize adaptive oscillation using equation (13)Update position of all individualsCalculate and sort fitness valuesEnd ForPerform node optimization on the optimal path and smooth optimizationReturn resultsTerminate


### 5.2. Flow chart of the Sparrow Particle Swarm Algorithm

The sparrow particle swarm algorithm flow chart is shown in Figure5.Figure 5
Sparrow particle swarm algorithm flow chart.


## 5.1. Structure of the Sparrow Particle Swarm Algorithm

The pseudocode of the sparrow particle swarm algorithm Algorithm3 is shown below.Algorithm 3: Sparrow particle swarm algorithm (SPSA) pseudocode.
InitializeSet the basic parametersSet the start point and target pointInitialize the positionPi of each individual in the population using equations (10)–(12)Oscillation optimization of all individuals trajectoriesFor each iterationInitialize optimal fitness and worst fitnessFor each producerFor each dimensionUpdate the position ofPi by the equation (11)SetT = 0While the position can not reach and T < TmaxUpdate the position ofPi by the equation (11)T = T + 1End WhileEnd ForEnd ForFor each scroungerFor each dimensionUpdate the position ofPi by the equation (4)SetT = 0While the position can not reach and T < TmaxUpdate the position ofPi by the equation (4)T = T + 1End WhileIfT ≥ TmaxSearch for the next position by adaptive escape using equation (12)End IfEnd ForEnd ForFor each individual that finds dangerFor each dimensionUpdate the position ofPi by the equation (5)SetT = 0While the position can not reach and T < TmaxUpdate the position ofPi by the equation (5)T = T + 1End WhileEnd ForEnd ForOptimize adaptive oscillation using equation (13)Update position of all individualsCalculate and sort fitness valuesEnd ForPerform node optimization on the optimal path and smooth optimizationReturn resultsTerminate


## 5.2. Flow chart of the Sparrow Particle Swarm Algorithm

The sparrow particle swarm algorithm flow chart is shown in Figure5.Figure 5
Sparrow particle swarm algorithm flow chart.


## 6. Experimental Simulation and Result Analysis

To verify the feasibility of the sparrow particle swarm algorithm for path planning, experimental simulations are conducted in three different environments with increasing complexity, and each algorithm is simulated 30 times in each case. The equipment parameters of this simulation experiment are as follows: CPU is Intel(R) Xeon(R) E5-2450H @ 2.10 GHz; graphic card is GTX 1050 Ti; memory space is 32G; and simulation software is MATLAB 2020b.To verify the performance of the algorithms, we need to avoid the effect of path initialization and perform the same path initialization for all the compared algorithms. In the initialization of the search path, the path shifted one unit in thex-axis direction (corresponding to a horizontal movement of 20 m) and by ten units in the y-axis and z-axis (corresponding to a movement of 200 m in the y-axis direction and 100 m in the z-axis direction, respectively). In Table 1, Tmax is the maximum number of cycles. For improving the efficiency of all path searches, when the search reaches the next path point, it is determined whether the next path point is an obstacle, and if it is an obstacle, it is reselected. If the reselected times reached Tmax, then the search is deadlocked, and the search for that individual ends, and the path search continues for the next individual. For reflecting the fairness of each algorithm comparison, the method is used for each algorithm individual if it encounters an obstacle when searching for the next path. The results of the initialization of the experimental data are shown in the following table.Table 1
Initialization of SPSA parameters.
ParametersSymbolValueWarning valueST0.6Scrounger ratioJD0.3Producer ratioPD0.7The proportion of sparrows who are aware of the dangerSD0.2Total group numberG30Number of iterationsM1000Maximum speedV5Minimum speedV1Maximum number of cyclesTmax10


### 6.1. Algorithm Complexity Analysis

The complexity analysis of the algorithm is one of the criteria to evaluate the performance of the algorithm. SPSA is divided into the initialization phase and the algorithm iteration phase: the initialization phase is executed only once and the algorithm iteration phase is executed according to the iteration cycle. The dimension to be calculated for each individual isD, the number of individuals is N, the maximum number of iterations is M, the range of movement in the y-axis and z-axis directions selected during initialization is A and B, respectively, and SD is the proportion of sparrows found to be in danger. The structure of the sparrow search algorithm for path planning in three-dimensional space is ON×D×A×B+M×N×D, where the complexity of the initialized path is ON×D×A×B. The computational complexity of the path iterative search optimization is OM×N×D. The SPSA increases some computational complexity due to the enhanced ability to optimize the search path, and the complexity of the adaptive oscillation optimization algorithm is OM×N×D considering the worst case. The complexity of adaptive variable speed escape search is OSD×M×N×D, and the computational complexity of path simplification and smoothing is OD only for the final converged minimum value path. Since the SPSA does not improve the structure of the sparrow algorithm, the maximum computational complexity is ON×D×A×B+M×N×D, so the computational complexity of this SPSA is ON×D×A×B+M×N×D. It shows that the SPSA also has a fast convergence rate.


### 6.2. Analysis of Experimental Results

To verify the effect of the simplified node on the path, the experimental results are shown in Figure6. The red line is the trajectory curve of the path without the simplified node after three times of spline interpolation, and the blue line is the curve after three times of spline interpolation after the simplified node. It can be seen that there is almost no oscillation in the x-axis and y-axis directions, and there is oscillation in the z-axis direction for the nodes of the un-simplified path, which shows that the simplified path is more suitable as the flight path of the UAV.Figure 6
Comparison before and after simplifying nodes.It can be seen in Figures7–9 that the SPSA has better convergence than other algorithms. The SSA has better smoothness than the paths planned by CSO, DE, GWO, and PSO algorithms, which all show different degrees of oscillation, and the altitude of the flight trajectory keeps changing with less smoothness. Oscillation optimizes and simplifies the nodes, improves the smoothness of the trajectory, and is more suitable for smooth operation as a UAV. The fitness values of SPSA in Figures 10–12 can converge to the optimal value faster than other algorithms. For the presence of different obstacles in the UAV-specific constrained environment, increasing the influence of the start-end line on the producer strengthens the searchability of the individuals near the start-end line, leading to a path that can converge quickly. The SPSA has significantly better results in the first iteration due to the start-end line guidance, which makes the path shorter than other algorithms. For the stability of the actual UAV flight path, the adaptive oscillation optimization makes it possible that there is no excessive distance difference between two adjacent path nodes, making the path length much shorter and achieving better results than other algorithms. The exploration of the optimal path is avoided by oscillatory optimization to avoid missing the optimal path. Figures 13–15 show that the SPSA is highly robust in different environments.Figure 7
Comparison of path planning trajectories of different algorithms in environment 1.Figure 8
Comparison of path planning trajectories of different algorithms in environment 2.Figure 9
Comparison of path planning trajectories of different algorithms in environment 3.Figure 10
Adaptation of different algorithms in environment 1 with iterations.Figure 11
Adaptation of different algorithms in environment 2 with iterations.Figure 12
Adaptation of different algorithms in environment 3 with iterations.Figure 13
Comparison of the results of path planning in environment 1.Figure 14
Comparison of the results of path planning in environment 2.Figure 15
Comparison of the results of path planning in environment 3.From the mean, worst, optimal, and standard deviation of different algorithms in Table2, we can see that the CSO algorithm has the worst convergence effect in path planning. Because in the CSO algorithm, there are differences in the routes between each individual, the smooth paths may be affected by other paths leading to oscillations instead of easy convergence. DE algorithm, PSO algorithm, and SSA have better convergence effect as the iteration increases, and the iterative oscillation of the path makes it difficult to converge to a better path. By comparison, the SPSA has better convergence stability and the lowest fitness value due to the directional nature of the path search, which strengthens the ability of individuals to search near the start-end line. The smoothness of the paths is improved by continuously optimizing the paths and avoiding the oscillating paths from interfering with the convergence of subsequent paths.Table 2
Simulation results of various algorithms.
CSODEGWOPSOSSASPSAMean6201.824408.463763.384676.342686.432008.42Worst6756.894938.993973.665128.232993.092009.55Optimal4970.683907.563421.284427.572614.562006.73Standard413.09243.0183.02218.58127.610.89Mean6271.974233.723718.734710.892882.402043.68Worst6854.164781.974160.035323.784895.462057.16Optimal5105.153757.253291.774304.022616.612028.70Standard465.75244.00177.03233.50631.238.10Mean6221.224562.373958.704683.832784.552004.95Worst6702.696625.816902.465182.993081.592024.60Optimal5251.673473.633294.274143.352525.771999.51Standard381.40752.85578.59297.68183.075.84


## 6.1. Algorithm Complexity Analysis

The complexity analysis of the algorithm is one of the criteria to evaluate the performance of the algorithm. SPSA is divided into the initialization phase and the algorithm iteration phase: the initialization phase is executed only once and the algorithm iteration phase is executed according to the iteration cycle. The dimension to be calculated for each individual isD, the number of individuals is N, the maximum number of iterations is M, the range of movement in the y-axis and z-axis directions selected during initialization is A and B, respectively, and SD is the proportion of sparrows found to be in danger. The structure of the sparrow search algorithm for path planning in three-dimensional space is ON×D×A×B+M×N×D, where the complexity of the initialized path is ON×D×A×B. The computational complexity of the path iterative search optimization is OM×N×D. The SPSA increases some computational complexity due to the enhanced ability to optimize the search path, and the complexity of the adaptive oscillation optimization algorithm is OM×N×D considering the worst case. The complexity of adaptive variable speed escape search is OSD×M×N×D, and the computational complexity of path simplification and smoothing is OD only for the final converged minimum value path. Since the SPSA does not improve the structure of the sparrow algorithm, the maximum computational complexity is ON×D×A×B+M×N×D, so the computational complexity of this SPSA is ON×D×A×B+M×N×D. It shows that the SPSA also has a fast convergence rate.


## 6.2. Analysis of Experimental Results

To verify the effect of the simplified node on the path, the experimental results are shown in Figure6. The red line is the trajectory curve of the path without the simplified node after three times of spline interpolation, and the blue line is the curve after three times of spline interpolation after the simplified node. It can be seen that there is almost no oscillation in the x-axis and y-axis directions, and there is oscillation in the z-axis direction for the nodes of the un-simplified path, which shows that the simplified path is more suitable as the flight path of the UAV.Figure 6
Comparison before and after simplifying nodes.It can be seen in Figures7–9 that the SPSA has better convergence than other algorithms. The SSA has better smoothness than the paths planned by CSO, DE, GWO, and PSO algorithms, which all show different degrees of oscillation, and the altitude of the flight trajectory keeps changing with less smoothness. Oscillation optimizes and simplifies the nodes, improves the smoothness of the trajectory, and is more suitable for smooth operation as a UAV. The fitness values of SPSA in Figures 10–12 can converge to the optimal value faster than other algorithms. For the presence of different obstacles in the UAV-specific constrained environment, increasing the influence of the start-end line on the producer strengthens the searchability of the individuals near the start-end line, leading to a path that can converge quickly. The SPSA has significantly better results in the first iteration due to the start-end line guidance, which makes the path shorter than other algorithms. For the stability of the actual UAV flight path, the adaptive oscillation optimization makes it possible that there is no excessive distance difference between two adjacent path nodes, making the path length much shorter and achieving better results than other algorithms. The exploration of the optimal path is avoided by oscillatory optimization to avoid missing the optimal path. Figures 13–15 show that the SPSA is highly robust in different environments.Figure 7
Comparison of path planning trajectories of different algorithms in environment 1.Figure 8
Comparison of path planning trajectories of different algorithms in environment 2.Figure 9
Comparison of path planning trajectories of different algorithms in environment 3.Figure 10
Adaptation of different algorithms in environment 1 with iterations.Figure 11
Adaptation of different algorithms in environment 2 with iterations.Figure 12
Adaptation of different algorithms in environment 3 with iterations.Figure 13
Comparison of the results of path planning in environment 1.Figure 14
Comparison of the results of path planning in environment 2.Figure 15
Comparison of the results of path planning in environment 3.From the mean, worst, optimal, and standard deviation of different algorithms in Table2, we can see that the CSO algorithm has the worst convergence effect in path planning. Because in the CSO algorithm, there are differences in the routes between each individual, the smooth paths may be affected by other paths leading to oscillations instead of easy convergence. DE algorithm, PSO algorithm, and SSA have better convergence effect as the iteration increases, and the iterative oscillation of the path makes it difficult to converge to a better path. By comparison, the SPSA has better convergence stability and the lowest fitness value due to the directional nature of the path search, which strengthens the ability of individuals to search near the start-end line. The smoothness of the paths is improved by continuously optimizing the paths and avoiding the oscillating paths from interfering with the convergence of subsequent paths.Table 2
Simulation results of various algorithms.
CSODEGWOPSOSSASPSAMean6201.824408.463763.384676.342686.432008.42Worst6756.894938.993973.665128.232993.092009.55Optimal4970.683907.563421.284427.572614.562006.73Standard413.09243.0183.02218.58127.610.89Mean6271.974233.723718.734710.892882.402043.68Worst6854.164781.974160.035323.784895.462057.16Optimal5105.153757.253291.774304.022616.612028.70Standard465.75244.00177.03233.50631.238.10Mean6221.224562.373958.704683.832784.552004.95Worst6702.696625.816902.465182.993081.592024.60Optimal5251.673473.633294.274143.352525.771999.51Standard381.40752.85578.59297.68183.075.84


## 7. Conclusions

The traditional SSA algorithm is suitable for the optimization search algorithm performed in an unconstrained environment. In the real environment, various environmental factors will affect the SSA algorithm planning path, resulting in poor convergence of the algorithm and loss of more individuals. To address this situation, strengthening the search efficiency and improving the path smoothing are the main problems that need to be solved for UAV path planning. In this study, we combine the sparrow search algorithm and particle swarm algorithm to propose the SPSA, and the main contributions of this study are as follows:(1)
Path initialization has a guiding role in the convergence of the subsequent algorithm. The next node's range is calculated according to the spatial geometry, and then, the node that can be moved within the range is randomly selected as the next node. This method avoids the interference of the initialization path trajectory oscillation on the convergence of the subsequent algorithm and can ensure the search capability of the algorithm.(2)
Position update of the producer. The start-end line as the globally optimal path, combined with the particle swarm algorithm, improves the position update of the producer in the sparrow particle swarm algorithm, strengthening the searchability of the algorithm near the start-end line.(3)
The searchability of discovering dangerous individuals. Due to the existence of A^+ in the position update formula of the sparrow found to be dangerous in the algorithm, the path may not reach the target point and lose the searched individuals. Inspired by the particle swarm algorithm, a variable speed escape search method is proposed to improve the sparrow search algorithm when the next node is unreachable, improve the path's exploration ability, and reduce the loss of the searched individuals.(4)
Adaptive oscillation optimization. For the randomness on path selection resulting in oscillation, an adaptive oscillation optimization method is proposed to reduce the interference of path oscillation to the subsequent path search and improve the smoothness of the path.(5)
Simplify node and smoothing processing. Node optimization can reduce the path turning points and improve the smoothness of the path, making the path suitable as the actual flight trajectory of the UAV.Through simulation experiments, it can be concluded that the sparrow particle swarm algorithm has better convergence and stronger searchability in complex environments, and the smoothed path is suitable as the flight path of the UAV.



---

*Source: 5158304-2021-12-09.xml*