The relentless advancement of technology and the growing demand for exploration in complex environments have propelled Unmanned Aerial Vehicles (UAVs), or drones, to the forefront of modern applications. The inherent flexibility and efficiency of UAV drone path planning make them indispensable tools across diverse fields such as reconnaissance, logistics, infrastructure inspection, and search and rescue operations. In complex three-dimensional terrains, the path planning algorithm must not only chart a course but also meticulously avoid obstacles to guarantee both safety and operational efficiency.
The landscape of path planning algorithms is broadly categorized into three groups. First, traditional algorithms like A*, Dijkstra, and Rapidly-exploring Random Trees (RRT) are theoretically mature and straightforward to implement. However, they often suffer from poor adaptability to dynamic environments and slow convergence rates. Second, swarm intelligence algorithms, such as Artificial Bee Colony (ABC), Particle Swarm Optimization (PSO), and Ant Colony Optimization (ACO), simulate the collective behavior of biological organisms. These methods are celebrated for their self-adaptability, rapid convergence, and structural simplicity, making them particularly effective for complex path planning challenges. Third, deep reinforcement learning algorithms, like Deep Q-Networks (DQN), possess the capacity for autonomous learning but are hampered by long training times, massive data requirements, and a propensity to converge to local optima. Among these, swarm intelligence algorithms have emerged as a primary research focus due to their balanced performance profile in intricate scenarios.
The Particle Swarm Optimization (PSO) algorithm is widely adopted for UAV drone navigation due to its simple structure and fast convergence. However, its performance is highly sensitive to parameter settings, and it is notoriously prone to becoming trapped in local optima. Numerous scholars have proposed enhancements. Some have introduced mutation strategies and compression factors with adaptive parameter tuning to bolster population diversity and global search capability. Others have hybridized PSO with Beetle Antennae Search (BAS) algorithms within a spherical coordinate system to constrain heading and pitch angles, thereby avoiding suboptimal solutions. Further improvements have focused on modifying cognitive factors, incorporating perpendicular bisector methods with explosion particle strategies to accelerate convergence, and integrating grouping strategies inspired by chicken swarm optimization alongside simulated annealing operations. While these modifications offer performance gains, significant room for improvement remains.
This work focuses on three-dimensional path planning for UAV drones, establishing a comprehensive fitness function that considers obstacle avoidance, path length, curvature, climb angle constraints, and collision penalties. The proposed Improved Particle Swarm Optimization (IPSO) algorithm introduces several key innovations to overcome the limitations of traditional PSO. First, a Terrain-Aware Randomly Permuted Halton sequence is employed for initialization to enhance the uniformity of particle distribution and coverage of the solution space. Second, nonlinear dynamic adjustments for inertia weight and learning factors are implemented to better balance global exploration and local exploitation. Third, a logarithmic spiral term and Laplace perturbation are incorporated into the velocity and position update processes, respectively, to significantly improve the algorithm’s ability to escape local optima. Finally, an elite retention strategy combined with a partial inferior solution re-initialization mechanism is adopted to maintain population diversity in later optimization stages.
1. Environmental Modeling and Fitness Formulation
1.1 Terrain Modeling
The first step involves constructing a realistic three-dimensional environment. A mountainous terrain is simulated using a superposition of Gaussian functions, where each peak is defined by its center coordinates, height, and slope parameters. The terrain height $z(x,y)$ at any point $(x, y)$ is given by:
$$ z(x,y) = \sum_{i=1}^{n} h_i \exp\left[ -\left( \frac{x – x_i}{x_{s_i}} \right)^2 – \left( \frac{y – y_i}{y_{s_i}} \right)^2 \right] $$
where $n$ is the total number of peaks; $(x_i, y_i)$ are the coordinates of the $i$-th peak’s center; $h_i$ controls the peak’s height; and $x_{s_i}$ and $y_{s_i}$ are attenuation coefficients controlling the slope of the $i$-th peak along the x and y axes, respectively.
1.2 Fitness Function Design
The fitness function is the core metric for evaluating path quality in UAV drone navigation. It must balance multiple, often competing, objectives: shortness, smoothness, feasibility, and safety. A path is first defined by a start point, an end point, and $k=4$ randomly selected waypoints in between. This sparse representation is then interpolated using a spline to generate $n=100$ discrete sampling nodes for fine-grained evaluation. The total fitness $F_{total}$ is the sum of four penalty components:
$$ F_{total} = F_{length} + F_{curvature} + F_{climb} + F_{collision} $$
1.2.1 Path Length Cost ($F_{length}$): This is the cumulative Euclidean distance between consecutive sampling points, encouraging shorter paths.
$$ F_{length} = \sum_{i=1}^{n-1} l_i = \sum_{i=1}^{n-1} \sqrt{(x_{i+1} – x_i)^2 + (y_{i+1} – y_i)^2 + (z_{i+1} – z_i)^2} $$
1.2.2 Path Curvature Cost ($F_{curvature}$): Curvature measures the path’s smoothness and turning demand. Lower curvature is essential for stable UAV drone flight. A graded penalty mechanism is applied. The curvature $\kappa(t)$ at a path parameter $t$ is:
$$ \kappa(t) = \frac{|| \mathbf{v}(t) \times \mathbf{a}(t) ||}{|| \mathbf{v}(t) ||^3} $$
where $\mathbf{v}(t)$ and $\mathbf{a}(t)$ are the velocity (first derivative) and acceleration (second derivative) vectors of the path, respectively. With a maximum allowable curvature $\kappa_{max} = 0.5$, the penalty is accumulated as: if $\kappa > \kappa_{max}$, $p_{\kappa}(t+1) = p_{\kappa}(t) + 1000(\kappa – \kappa_{max})^3$; if $\kappa \leq \kappa_{max}$, $p_{\kappa}(t+1) = p_{\kappa}(t) + 50(\kappa / \kappa_{max})^2$. The total curvature penalty is:
$$ F_{curvature} = \sum_{t=2}^{n-1} p_{\kappa}(t)^2 $$
1.2.3 Climb Angle Cost ($F_{climb}$): This restricts the path’s steepness to respect the UAV drone‘s climb rate limitations. The climb angle $\theta_i$ for segment $i$ is:
$$ \theta_i = \arctan\left( \frac{|\Delta z_i|}{h_i} \right) $$
where $\Delta z_i = z(t_{i+1}) – z(t_i)$ is the vertical change and $h_i = \sqrt{\Delta x_i^2 + \Delta y_i^2}$ is the horizontal distance. With a maximum climb angle $\theta_{max} = \pi/3$, the penalty $p_i$ for segment $i$ is:
$$
p_i =
\begin{cases}
(\theta_i – \theta_{max})^2, & \text{if } \theta_i > \theta_{max} \text{ and } h_i > 0 \\
1000, & \text{if } h_i = 0 \text{ and } \Delta z_i \ne 0 \text{ and } \theta_{max} < \pi/2 \\
0, & \text{otherwise}
\end{cases}
$$
The total climb penalty is $F_{climb} = \sum_{i=1}^{n-1} p_i$.
1.2.4 Ground Collision Cost ($F_{collision}$): This is a severe penalty applied if the UAV drone‘s path flies below the terrain height, ensuring safety.
$$
F_{collision} =
\begin{cases}
1000 \cdot \left(1 + \frac{F_{length}}{1000}\right), & \text{if } z(t_i) < z_{\text{terrain}}(x(t_i), y(t_i)) \text{ for any } i \\
0, & \text{otherwise}
\end{cases}
$$
where $z_{\text{terrain}}(x, y)$ is the interpolated ground height at coordinates $(x, y)$.
2. The Improved Particle Swarm Optimization (IPSO) Algorithm
2.1 Terrain-Aware Initialization with Permuted Halton Sequences
The quality of initial particle distribution critically impacts PSO’s convergence speed and final solution quality. Traditional random initialization often leads to uneven coverage. While chaotic maps like the Logistic map offer some improvement, a more effective method is proposed here. Halton sequences are low-discrepancy sequences known for high uniformity. To break their inherent periodicity and enhance randomness, a random bijection (permutation) is applied to the digit expansion process. For a base $b_d$, a random permutation $\sigma_d$ is generated: $\sigma_d: \{0,1,…,b_d-1\} \rightarrow \{0,1,…,b_d-1\}$, where $\sigma_d$ is a one-to-one mapping. The $d$-th coordinate of the $n$-th point in the permuted Halton sequence is:
$$ p^{(n)}_d = \sum_{k=0}^{K} \frac{\sigma_d(a_k)}{b_d^{k+1}} $$
where $K = \lfloor \log_{b_d} n \rfloor$, and $a_k = \lfloor n / b_d^k \rfloor \mod b_d$ is the $k$-th digit of $n$ in base $b_d$. Crucially, this mathematical uniformity is combined with terrain awareness. The initial height coordinate $Z^{(i)}_{\text{raw}}$ from the sequence is adjusted to ensure a safe clearance above the terrain:
$$
\begin{aligned}
Z^{(i)}_{\text{safe}} &= \max\left( Z^{(i)}_{\text{raw}},\ Z^{(i)}_{\text{terrain}} + H_{\text{safe}} \right) \\
H_{\text{safe}} &= \alpha \cdot \max_{k}\left( Z^{(k)}_{\text{terrain}} \right)
\end{aligned}
$$
where $Z^{(i)}_{\text{terrain}}$ is the terrain height at the $(x, y)$ coordinate of the particle, $\alpha \in (0,1)$ is a safety coefficient, and $\max_{k}(Z^{(k)}_{\text{terrain}})$ is the maximum terrain height in the entire map. This dual strategy ensures particles are not only uniformly distributed in the search space but also initialized in feasible, safe regions from the outset, providing a superior starting point for the UAV drone path optimizer.
| Metric | Logistic Chaotic Map | Proposed Halton + Terrain-Aware | Improvement |
|---|---|---|---|
| 3D Uniformity | Baseline | +37.6% | Significant |
| XY Plane Uniformity | Baseline | +107% | Very High |
| Spatial Coverage | Baseline | +33.3% | Substantial |
2.2 Nonlinear Dynamic Adjustment of Inertia Weight and Learning Factors
The core PSO update equations for velocity $\mathbf{v}$ and position $\mathbf{x}$ of a particle are:
$$
\begin{aligned}
\mathbf{v}_{t+1} &= \omega \cdot \mathbf{v}_t + c_1 r_1 (\mathbf{pbest} – \mathbf{x}_t) + c_2 r_2 (\mathbf{gbest} – \mathbf{x}_t) \\
\mathbf{x}_{t+1} &= \mathbf{x}_t + \mathbf{v}_{t+1}
\end{aligned}
$$
where $\omega$ is the inertia weight, $c_1$ and $c_2$ are the cognitive and social learning factors, and $r_1, r_2$ are random numbers. To optimally balance exploration and exploitation for the UAV drone path search, these parameters are made dynamically adaptive over the iteration count $t$ (with $T_{max}$ as the maximum iteration).
The inertia weight $\omega(t)$ controls the momentum. A high value favors global exploration, while a low value favors local refinement. A nonlinear decreasing strategy with a sinusoidal perturbation is used:
$$ \omega(t) = \omega_{\text{max}} – \frac{\omega_{\text{max}} – \omega_{\text{min}}}{1 + \exp\left(-\alpha \cdot \left(\frac{t}{T_{max}} – 0.5\right)\right)} + A \cdot \sin(\omega_1 \cdot t) $$
where $\omega_{\text{max}}=0.9$, $\omega_{\text{min}}=0.4$. The sinusoidal term $A \cdot \sin(\omega_1 \cdot t)$ helps the algorithm periodically “jiggle” to escape shallow local optima.
The learning factors are adjusted oppositely. $c_1(t)$, associated with the particle’s personal best ($\mathbf{pbest}$), encourages individual exploration early on. $c_2(t)$, associated with the swarm’s global best ($\mathbf{gbest}$), promotes convergence and social learning later. Their update rules are based on sigmoid functions:
$$
\begin{aligned}
c_1(t) &= 0.8 + (2.5 – 0.8) \cdot \frac{1}{1 + \exp\left(\frac{t – 50}{10}\right)} \\
c_2(t) &= 0.8 + (2.5 – 0.8) \cdot \frac{1}{1 + \exp\left(-\frac{t – 50}{10}\right)}
\end{aligned}
$$
This design ensures $c_1$ decays from 2.5 to 0.8 while $c_2$ grows from 0.8 to 2.5, seamlessly transitioning the swarm’s focus from broad exploration to concentrated exploitation around the best-found UAV drone path.
2.3 Logarithmic Spiral Velocity Update Term
Inspired by spiral foraging patterns in nature, a logarithmic spiral term $\mathbf{S}$ is added to the velocity update equation. This term introduces a rotational component around the global best solution, enhancing the exploration of the surrounding space and providing a powerful mechanism to circumvent local optima. The modified velocity update becomes:
$$
\begin{aligned}
\mathbf{S} &= c_3 \cdot \text{rand}_3 \cdot r_{\theta} \left[ \cos(\theta) (\mathbf{gbest} – \mathbf{x}) + \sin(\theta) \mathbf{D} \right] \\
\mathbf{v}_{new} &= \omega \mathbf{v} + c_1 r_1 (\mathbf{pbest} – 2\mathbf{x} + \mathbf{x}_{l}) + c_2 r_2 (\mathbf{gbest} – 2\mathbf{x} + \mathbf{x}_{l}) + \mathbf{S}
\end{aligned}
$$
Here, $\mathbf{x}_l$ is the particle’s previous position, $\mathbf{D}$ is a random directional vector, and $\text{rand}_3$ is a uniform random number. The spiral parameters are also adaptive: the spiral weight $c_3$ decays from an initial value $c_{3\text{initial}}=1$ to zero ($c_3 = c_{3\text{initial}}(1 – t/T_{max})$); the spiral radius $r_{\theta}$ decays exponentially ($r_{\theta} = a e^{-b t / T_{max}}$, with $a=2, b=1$); and the angle $\theta$ increases linearly ($\theta = 2\pi t / T_{max}$). This design allows for large, explorative spirals early in the optimization to survey the complex 3D space for the UAV drone, which gradually tighten to fine-tune the path near the promising region in later stages.
2.4 Laplace Perturbation for Position Update
To further bolster the ability to escape local optima and prevent premature convergence, a perturbation based on the Laplace distribution is introduced into the position update. The Laplace distribution is heavy-tailed, meaning it has a higher probability of generating large, exploratory jumps compared to a Gaussian distribution. This is highly beneficial for a UAV drone searching a vast 3D space. The perturbation magnitude is also dynamically controlled.
First, a scale parameter $b_t$ is computed: $$ b_t = 1 + 1.5 \cdot \frac{1}{1 + e^{(t-50)/10}} $$
This parameter adjusts the spread of the perturbation over time. A Laplace random variate $L$ is generated using the inverse transform method: $$ L = b_t \cdot \ln\left( \frac{1}{u} – 1 \right) $$ where $u \sim U(0,1)$. The perturbation step size $\delta$ decays linearly: $$ \delta = \delta_{\text{min}} + (\delta_{\text{max}} – \delta_{\text{min}}) \cdot \left(1 – \frac{t}{T_{max}}\right) $$ with $\delta_{\text{max}}=1.0$ and $\delta_{\text{min}}=0.5$. Finally, the position is updated as: $$ \mathbf{x}_{new} = \mathbf{x} + b_t \cdot \mathbf{v} + L \cdot \delta $$ This injection of controlled, heavy-tailed noise helps particles break away from stagnation, especially when combined with the following diversity preservation strategy.
2.5 Elite Retention and Diversity Maintenance
As the algorithm progresses, population diversity can decrease, leading to stagnation. To counter this, a dual-strategy mechanism is implemented. An elite retention strategy preserves the top 20% of particles (those with the best fitness) unchanged across generations, ensuring that valuable path information is not lost.
Simultaneously, a stagnation detection mechanism monitors the global best fitness. If the improvement over the last 3 generations is less than a threshold (e.g., $10^{-4}$), the algorithm judges the swarm to be stagnating. In response, the non-elite particles (the remaining 80%) are either subjected to a strong Laplace perturbation or are completely re-initialized using the terrain-aware Halton method. This strategy effectively “resets” part of the swarm, injecting fresh potential UAV drone paths into the population while protecting the best solutions found so far, thereby maintaining a healthy balance between convergence and exploration.
| Step | Description |
|---|---|
| 1 | Generate 3D terrain (e.g., 20 random Gaussian peaks) and define start/goal. |
| 2 | Initialize a swarm of $M=50$ particles using the Terrain-Aware Permuted Halton sequence. |
| 3 | Set velocity and position boundaries, maximum iterations $T_{max}=100$. |
| 4 | Define the composite fitness function $F_{total}$ (Eq. 1-8). |
| 5 | For iteration $t = 1$ to $T_{max}$ do |
| 6 | Update adaptive parameters $\omega(t)$, $c_1(t)$, $c_2(t)$ (Eq. 12-14). |
| 7 | For each particle, update velocity using Eq. 18 (with Spiral term $\mathbf{S}$ from Eq. 15-17). Apply velocity clamping $[-10, 10]$. |
| 8 | For each particle, update position using Eq. 22 (with Laplace perturbation from Eq. 19-21). Apply position boundaries. |
| 9 | Evaluate $F_{total}$ for all particles. Update personal best ($\mathbf{pbest}$) and global best ($\mathbf{gbest}$). |
| 10 | If stagnation detected (global best change < $10^{-4}$ for 3 gens) then Retain top 20% as elites. Perturb or re-initialize the remaining 80% of particles. |
| 11 | End If |
| 12 | End For |
| 13 | Output the optimal path corresponding to the final $\mathbf{gbest}$, and smooth it using cubic spline interpolation. |
3. Experimental Validation and Analysis
To rigorously validate the efficacy of the proposed IPSO algorithm for UAV drone navigation, comprehensive simulation experiments were conducted in a MATLAB environment. The terrain was a 100x100x150 unit 3D space with multiple Gaussian peaks. The IPSO was compared against three established algorithms: the Classic PSO (CPSO), the Artificial Fish Swarm Algorithm (AFSA), and the Artificial Bee Colony (ABC) algorithm. The parameters for all algorithms were carefully tuned as summarized below.
| Algorithm | Key Parameters |
|---|---|
| IPSO (Proposed) | Swarm size $M=50$, $T_{max}=100$, Adaptive $\omega$, $c_1$, $c_2$, $c_{3initial}=1$, $a=2$, $b=1$, Elite rate=20%. |
| Classic PSO (CPSO) | $M=50$, $T_{max}=100$, Fixed $\omega=1.5$, Fixed $c_1=c_2=2$. |
| Artificial Fish Swarm (AFSA) | Fish population=50, Visual scope=50, Step size=3, Crowding factor=10, Try number=50. |
| Artificial Bee Colony (ABC) | Colony size=100 (Employed Bees=50, Onlookers=50), Limit=5. |
Each algorithm was executed 60 independent times to gather statistically significant performance data. The primary metrics for comparison were the average best fitness value (lower is better) and the standard deviation of the fitness (lower indicates more stable and reliable performance).
The 3D path visualization clearly demonstrates the superiority of IPSO. While CPSO, AFSA, and ABC all manage to find a complete path from start to finish, their trajectories often show unnecessary detours, sharp turns, or dangerously close proximity to obstacles, indicative of convergence to sub-optimal solutions. In contrast, the path generated by IPSO is notably more direct, smoother, and maintains a safer clearance from the mountainous terrain. This visual evidence confirms that the introduced mechanisms—the improved initialization, adaptive parameters, spiral exploration, and Laplace perturbation—collectively empower the IPSO to better navigate the complex 3D cost landscape and locate a higher-quality path for the UAV drone.
| Algorithm | Average Best Fitness | Standard Deviation of Fitness |
|---|---|---|
| ABC | 253.57 | 26.83 |
| AFSA | 325.59 | 47.43 |
| Classic PSO (CPSO) | 191.77 | 29.32 |
| Improved PSO (IPSO) | 160.41 | 5.05 |
The quantitative results in Table 4 are conclusive. The proposed IPSO achieves the lowest average fitness value of 160.41, outperforming CPSO by 16.35%, ABC by 36.74%, and AFSA by a remarkable 50.73%. More importantly, the standard deviation for IPSO is merely 5.05, which is 82.78% lower than that of CPSO, 81.18% lower than ABC, and 89.35% lower than AFSA. This exceptionally low variance signifies that IPSO is not only finding better paths on average but is doing so with remarkable consistency and robustness across different random seeds and initial conditions. This stability is a critical attribute for real-world UAV drone deployment, where reliable and predictable performance is paramount.
The convergence curves and boxplot distribution of final fitness values from the 60 runs further illustrate this point. The IPSO convergence curve descends more rapidly and stabilizes at a significantly lower value. The boxplot for IPSO shows a very narrow interquartile range (IQR) positioned low on the fitness scale, with virtually no outliers. In contrast, the boxplots for CPSO, ABC, and AFSA are much wider, positioned higher, and exhibit numerous outliers, confirming their instability and susceptibility to poor local optima.
4. Conclusion
This study has presented a comprehensive Improved Particle Swarm Optimization (IPSO) algorithm specifically tailored for the challenging problem of three-dimensional path planning for Unmanned Aerial Vehicles (UAVs). The proposed method systematically addresses the key shortcomings of traditional PSO, namely premature convergence and sensitivity to parameters. The integration of a Terrain-Aware Randomly Permuted Halton sequence ensures a high-quality, feasible starting population. The nonlinear dynamic adjustment of the inertia weight and learning factors provides an intelligent balance between exploring the vast 3D space and exploiting promising regions. The introduction of the logarithmic spiral term in the velocity update and the Laplace perturbation in the position update equips particles with powerful mechanisms to escape local optima, a crucial capability for navigating complex environments. Finally, the elite retention and partial re-initialization strategy safeguards population diversity, preventing stagnation in later search stages.
Extensive simulation experiments in a complex mountainous terrain have demonstrated the superior efficacy of IPSO. It consistently generates shorter, smoother, and safer paths compared to the Classic PSO, Artificial Bee Colony, and Artificial Fish Swarm algorithms. The quantitative results—a 16.35% improvement in average fitness and an 82.78% reduction in standard deviation over traditional PSO—provide strong evidence of its enhanced global search capability, convergence speed, and, most importantly, its stability and reliability. Therefore, the IPSO algorithm establishes itself as a robust and effective solution for autonomous 3D path planning in UAV drone applications, promising significant benefits for missions conducted in intricate and hazardous operational environments.