Unmanned Aerial Vehicle (UAV) technology is widely used in military operations, emergency rescue missions, agriculture, and logistics. An improved sparrow search algorithm is proposed in this paper, inspired by the cooperative work and distributed search behavior of sparrows. Chaotic mapping is introduced into this algorithm to initialize a more homogeneous population distribution, which broadens the search space and improves the chances of finding a globally optimal solution. The biological mechanisms of individual sparrow populations are improved by introducing competitive starvation behavior to optimize the population performance. An adaptive diferential evolution strategy is incorporated to improve the global search capability and convergence speed. The algorithm is compared with other classical and new algorithms on benchmark functions and the results show the superiority of the algorithm. The algorithm is applied to path planning for UAVs and the improved algorithm is compared with other path planning algorithms in simulation tests, the results show that the improved sparrow search algorithm achieves better path planning performance in a shorter number of iterations,with convergence speed improving by approximately 50%. This research is of great significance in improving the eficiency and quality of UAV path planning and is expected to have a positive impact in practical applications.
With the rapid progress and continuous innovation of Unmanned Aerial Vehicle (UAV) technology, its application potential in many fields has been greatly stimulated, triggering a wide range of in-depth application interests and explorations, such as military reconnaissance, emergency rescue, agricultural monitoring, and logistics and distribution [1, 2, 3, 4], and UAVs have become the tool of choice for all kinds of tasks, and their wide application has brought significant economic and social benefits. In this trend, UAV path planning plays a crucial role as a core element to ensure mission execution. However, traditional path planning methods perform poorly when facing problems such as complex environments, dynamic obstacles, and multi-task collaboration, limiting the potential of UAV applications [5, 6].
Currently, several path planning algorithms have been applied to deal with the UAV route planning problem, including the A-algorithm [7], the PRM algorithm [8], the artificial potential field method [9], the Rapidly Exploring Random Trees method [10], and the Dijkstra method [11]. However, these traditional path planning methods often face challenges in complex, unstructured environments. In recent years, researchers have continued to delve into new path planning methods, some of which incorporate bionic population intelligence optimization algorithms, providing new possibilities in the field. Examples include traditional genetic algorithms [ 12], particle swarm algorithms [13], and newly proposed whale optimization algorithms [14], grey wolf algorithms [15], and bat algorithms [16]. However, these algorithms still face a number of challenges, including search eficiency, vulnerability to local optimal solutions.
To address these challenges, an improved sparrow-based search algorithm is proposed in this paper. The sparrow search algorithm [17] is a swarm intelligence algorithm inspired by the behavior of sparrow groups foraging for food and avoiding natural enemies. It is characterized by distributed search and cooperative work, where multiple individuals work cooperatively and collaboratively to quickly and eficiently plan the UAV’s navigational path.
Bionic population intelligence optimization algorithms are widely used in the field of UAVs for their outstanding capabilities. Xu et al. [18] innovatively integrated the theory of co-evolution into the ABC algorithm, and developed a new global optimization-oriented artificial bee colony algorithm. The algorithm demonstrates superior performance in terms of both the efectiveness in finding the optimal solution and the speed of convergence to the solution compared to the original algorithm. On the other hand, Phung and Ha [19] extended a traditional particle swarm optimization algorithm by fusing chemotaxis behavior and relocation strategies, key mechanisms in BFO, with the aim of improving the algorithm’s ability to explore and exploit optimal solutions in the search space. In addition, Zhang et al. [20] proposed a UAV trajectory planning algorithm based on improved Harris Hawk Swarm optimization, which introduces adaptive chaos sums and B-spline curves to improve the performance. While, Jarray et al. [21] proposed an innovative parallel co-evolutionary strategy combined with the gray wolf optimization algorithm to intelligently partition the complex search space into multiple low-dimensional subspaces, which is efective and superior in terms of several performance metrics.
The study of 3D path planning for multi-UAV collaboration is more complex and challenging, Kumar et al. [22] proposed an innovative reinforcement learning-enhanced variable weight gray wolf optimization algorithm for eficient path planning challenges in complex scenarios. Simulation experiments verify that the algorithm generates safe and eficient path planning strategies for UAVs. Li et al. [23] proposed an optimization algorithm that combines a bio-inspired neural network with an augmented Harris hawk optimization algorithm. After experimental validation, the algorithm demonstrates significant superiority during dynamic obstacles. Tan et al. [24] proposed an optimized artificial bee colony algorithm for the multi-objective path planning problem. Through simulation experiments, the algorithm successfully demonstrates its optimization ability in time eficiency and priority processing in a multi-UAV path planning application in a mountainous scenario. Oyana et al. [25] proposed a moth-flame optimization algorithm, which was improved based on reverse learning, and the experimental results showed that the proposed algorithm had good stability. Shi et al. [26] proposed an innovative multi-population Drosophila optimization algorithm for UAV trajectory planning in complex threat environments, which is a nonlinear and constrained optimization problem, and incorporated the ofspring competition mechanism, and the experiments verified that it had excellent results. He et al. [27] proposed a timestamp segmentation model to reduce the cost of multi-UAV coordination, and then improved the combination of particle swarm optimization and symbiotic organism search to efectively combine exploration and exploitation capabilities, and experiments verified the good performance of the proposed algorithm.
In general, these algorithms still face some problems, including search eficiency, the efect of local optimal solutions, and at the same time, 3D path planning in multi-UAV cooperative scenarios is more complicated, in order to solve these problems, this paper proposes an improved sparrow search algorithm based on the multi-individual cooperative work and distributed search behaviors of sparrows in order to improve the eficiency and quality of UAV path planning, and to plan the UAV path planning quickly and eficiently navigation path of UAV.
Xue and Shen [17] proposed the sparrow search algorithm as a new intelligent optimization method. The algorithm simulates the sparrow’s food-seeking mechanism, feeding strategy, and antipredator behavior, which has been widely used in diferent fields [ 28, 29, 30]. The main advantages of the algorithm are that it is easy to implement, has fewer parameters, and has a strong global search capability. Nevertheless, the algorithm still has some drawbacks, including the tendency to fall into local optimal solutions when facing complex, high-dimensional problems, the relatively simple communication foraging strategy among individual sparrows, and the lack of dynamic adjustment mechanism. To cope with these challenges, we introduce chaotic mapping, competitive starvation mechanism, adaptive diferential evolution and other strategies into the proposed ISSA algorithm.
In the preliminary stage of the sparrow search algorithm, the initial location distribution of individuals exerts a significant influence on the algorithm’s global search performance. In order to overcome the search limitations due to the inhomogeneity of the initial position distribution, chaotic sequences are introduced as the initialization strategy. Chaotic sequences are characterized by randomness, uniformity and orderliness, and do not easily fall into a repetitive state, so they can provide more random and uniform initial positions of individuals for population initialization [31].
The generation process of chaotic sequence involves initial individual positions, chaos parameters
and random vectors. First of all, the initial individual position 0 can be initialized by generating a
random vector with dimension dim, rand(1, dim) means to generate a random vector with dimension
dim, as shown in equation (
Then, the new chaotic sequence values are obtained by iteratively using the chaotic sequence
generation rule. 0 is the current value of the chaotic sequence and is the chaos parameter as shown
in equation (
Finally, the individual position new is updated by mapping the chaotic sequence to the specified
search space range, as shown in equation (
0 = rand(1, dim)
0 = · (1 − 0) · 0
new = 0 · (ub − lb) + lb
(
The use of chaotic sequences ensures a rational distribution of individual sparrows and increases population diversity.
In the predatory behavior of sparrows, joiners tend to jump directly to the best position near the ifnder in order to compete for food. However, resources in nature are always limited, and even the best position occupied by the discoverer has a food supply that cannot satisfy the demand of a large number of joiners, and this scarcity of food resources leads to competition among sparrows. In addition, when sparrows face food shortage or encounter unforeseen circumstances that prevent them from obtaining food, they are exposed to the risk of starvation, which may ultimately lead to the death of individuals. To address this biological problem, a model for the mechanism of competitive starvation is proposed in this paper. We set the amount of food found by each finder to be limited, and this amount is determined by the finder’s fitness value. Discoverers with higher fitness values usually find more food. Joiners make choices based on the amount of food they find, prioritizing those with the most food to compete for it. Lower-ranked joiners will turn to finders with less food in order to avoid starvation. This selection strategy reflects the flexibility and adaptability of sparrows during foraging. When an individual encounters an unexpected situation and dies of starvation due to long-term unavailability of food, the original sparrow individual is discarded and a new sparrow individual is generated, and this renewal strategy helps to simulate the turnover of individuals and the dynamic balance of the population in the natural environment in order not to fall into local optimality [32].
The starvation death mechanism is divided into two cases: first, it counts the number of predators of the discoverer and selects the discoverer that is most favorable to it. The second is to generate a new individual sparrow when it encounters an accident that prevents it from obtaining food.
The amount of food that each finder finds during its search determines whether other individuals choose
to follow it. The amount of food reflects the fitness of the finder: the more food means the less fitness.
Joiners tend to choose the finder that finds more food. Define
as the amount of food found by the
-th finder as shown in equation (
1 () =
, = 1, 2, . . . , where represents the number of discoverers and represents the -th discoverer.
The joiner chooses to follow the discoverer according to the selection probability. Denote as the
probability that the -th finder is selected, and the selection probability is proportional to the number
of food items found by each finder, as shown in equation (
Define as the joiner of the -th finder as shown in equation (
∑︀=1 = round ( · ) where is the scale factor and is the rounding operation.
The improved joiner position update formula is shown in equation (
︁( {︃ · exp
(,) worst − (,) ,
︁) +1(, ) + (, ) − +1(, ) · cos( ) · + , if > /2 otherwise
Equation (
Sparrows die when they encounter accidents and cannot obtain food or when they are imprisoned for
an extended duration. denotes the number of iterations without updating the position of individuals.
When the individual in the population exceed the critical threshold and no updates are made to their
positions, the sparrow is deemed to be in an accidental state. At this point, the sparrow will starve to
death. At this juncture, the original sparrow individual is discarded and a novel sparrow individual is
generated to achieve the purpose of resurrection from the dead and better population foraging. The
position update is shown in equation (
,
{︃, + , · randn()
if ≥
otherwise
where , denotes the current position at moment ; randn() is a random number that conforms to
a normal distribution, and denotes the th moment; is a threshold for determining whether to
trigger the state update.
(
In order to enhance the global and local search capabilities of the basic sparrow search algorithm, an adaptive scaling factor is proposed in this paper, which adaptively and dynamically adjusts the magnitude of the variation operation according to the current population fitness. If the distribution of population fitness is more consistent, tends to be close to 1, which reduces the population variability and helps stabilize the local search. If the distribution of population fitnesses is widely diferent, tends to be close to 0, which enhances the population variability and helps to search the whole solution space more extensively [33, 34].
For each individual () in the current population, two individuals 1 and 2 are randomly
selected from the current population, and the diference between these two individuals is calculated
and summed with the current individual to produce a new individual as shown in Equation (
In the diferential evolution operation of global diference enhancement, the historical best position is
globally perturbed. Two individuals 1, 2 , which will be used to introduce diferences, are randomly
selected from the current population. Introducing the adaptive scaling factor , the variance-enhanced
position 0() is calculated by the diferential evolution formula as shown in equation (
Evaluate the adaptive performance of the new location, if it demonstrates superior adaptability,
update the location of the individual to 0(), otherwise keep it unchanged, which helps to cope better
with the optimal solution in complex problems.
(
The ISSA algorithm is compared with other heuristic algorithms, including PSO [13], WOA [14], GWO [15], and SSA [17], on six basic test functions, which are shown in table 1, where F1-F3 represent highdimensional single-peak benchmark functions, F4-F5 depict high-dimensional multiple-peak benchmark functions, and F6 exemplifies a low-dimensional multiple-peak benchmark function. 2() = max {|| , 1 ≤ ≤ } 3() = ∑︀ 4 + random [0, 1) 4() = ∑︀ [︀ 2 − 10 cos (2 ) + 10]︀ 5() = − 20 exp − 0.2 6() = − ∑1=0︀1 [︁( − ) ( − ) +
]︁− 1 ︃( √︃
)︃ 1 ∑︀ 2 − exp =1 =1 ︂( 1 ∑︀ cos (2 ) + 20 + ︂)
A 100 km × 100 km × 80 km digital elevation map is used to build a 3D mountainous terrain in this paper, as shown in Fig. 1. Comparison with other heuristic algorithms, including PSO [13], GWO [15], IGWO [35], SSA [17], and HEGOGWO [36], is made through experiments.
7 obstacle areas with center coordinates (
(
(+1 − )2 + (+1 − )2 + (+1 − )2
Path smoothness is to ensure that the path is smooth. Minimizing the number of path segments
helps to reduce the zigzagging of the path, thus making the UAV flight smoother, which is essential for
improving the stability and navigation eficiency of the whole system. denotes the number of UAVs,
and denotes the number of path segments of the current UAV, the number of diferent parts the
path has been divided into. The overall form of the objective function is a linear combination of the
path length and the number of path segments, and the final fitness value is obtained by summation,
as shown in equation (
= ∑︁ () + ∑︁
=1 =1
By minimizing the objective function, a solution can be obtained that makes UAV path planning more reasonable and optimal while considering multiple factors. The multi-UAV system realizes eficient, safe and cooperative 3D path planning.
The results of the experiments are presented in table 3, and ISSA was the best and stable in each experiment.
The threat region path planning is shown in figure 2, where (a) is SSA path planning and (b) is ISSA path planning. By observing the threat region path planning graph in figure 2, both the improved sparrow search algorithm and the sparrow search algorithm realize the path planning from multiple UAVs to the target point. However, the trajectory of the improved sparrow search algorithm is smoother and the trajectory of the initial sparrow search algorithm is more tortuous. In terms of terrain fluctuations, the enhanced sparrow search algorithm fits the terrain fluctuations more closely and shortens more paths. (a) SSA path planning (b) ISSA path planning
In the course of devising a route to the desired destination, the initial sparrow search algorithm plans a path for the UAV that is more afected by the obstacle environment, and has a larger left-right deviation in the movement toward the target point. And the improved sparrow search algorithm successfully circumvents the obstacle influence.
(a) Top view of SSA path planning (b) Top view of ISSA path planning
The top view of the path planning profile is shown in figure 3, where (a) is SSA path planning and (b) is ISSA path planning. By observing the trajectory projection in figure 3, the sparrow search algorithm planning the UAVs to go to the target point faces the obstacle influence and multi-copter coordinated planning, where one of the UAVs deviates from the shorter distance of traveling in a straight line and travels around the road. The improved sparrow search algorithm coordinates the traveling routes of multiple UAVs extremely well, and the traveling routes of multiple UAVs are roughly kept in the shortest distance. The routes of the improved sparrow search algorithm are smoother compared to the sparrow search algorithm, greatly reducing the traveling distance.
The convergence diagrams of the diferent algorithms are shown in figure 4. ISSA has the best initialization, and in the iteration process, the search eficiency is also better than SSA, and the final iteration is optimal.
When considered in conjunction with figures 2-4, it becomes evident that SSA reaches a local optimum, while ISSA is capable of efectively circumventing the threat range and devising a trajectory with optimal outcomes, enhanced precision, and accelerated convergence. As evidenced in table 3, all indexes of ISSA are optimal, indicating that the algorithm exhibits robust optimization seeking and stability performance. The eficacy of the ISSA algorithm is substantiated, demonstrating its capacity to swiftly and accurately navigate beyond the constraints of the danger zone and plan the UAV’s optimal trajectory.
This paper proposed an improvement to the performance of 3D path planning for UAVs in an obstacle environment through the implementation of an enhanced version of the sparrow search algorithm. In order to overcome the limitations of the sparrow search algorithm, which is susceptible to converging on a local optimum and uneven distribution of initialized population when searching for the optimum, various improvement strategies, such as chaotic sequence, starvation death mechanism and adaptive diferential evolution, were introduced. The initialization stage of the population was augmented with additional randomness to guarantee a more uniform distribution of the initial positions of sparrow individuals, thereby enhancing the diversity of sparrow populations. It was necessary to enhance the biological mechanisms of sparrow populations in order to optimize population performance and circumvent local optima. The objective was to overcome the limitations of traditional search methods, accelerate the search for optimal solutions, and enhance the algorithm’s global search capability. To ascertain the eficacy of the algorithm, the algorithm is tested and compared with other meta-heuristic algorithms on the benchmark function, and the experimental results show that the algorithm has better accuracy and robustness, which verifies its feasibility and efectiveness. The algorithm is applied to UAV path planning and simulated in a simulated environment, considering path length and safety, and the experimental results show that compared with other algorithms, the algorithm outperforms the comparative algorithms in terms of accuracy, smoothness, convergence speed and stability. Specifically, the algorithm achieves better path planning performance in shorter iterations, with convergence speed improving by approximately 50%. The algorithm significantly improves the convergence performance, efectively avoids potentially dangerous paths, obtains superior navigation trajectories, and improves convergence accuracy.
While the algorithm ofers significant improvements in accuracy and search eficiency, it does introduce some computational overhead due to the merging of multiple strategies. In addition, it remains to be seen how it will scale and perform in more diverse and complex environments. Consequently, future work will focus on two aspects: first, optimizing the multi-UAV collaborative route planning scheme to enhance the overall eficiency; second, researching the real-time route replanning strategy in dynamic environments.
Declaration on Generative AI: The authors have not employed any generative AI tools.