In the rapidly evolving landscape of low-altitude economies, the application of UAV drones in fields such as agriculture, logistics, search and rescue, and air traffic has become increasingly prevalent. However, the complexity of three-dimensional (3D) environments, coupled with numerous constraints including obstacle avoidance, terrain following, and dynamic threats, poses significant challenges for generating safe, efficient, and high-quality flight paths. Traditional algorithms often struggle to balance computational speed with path optimality, particularly in high-density threat zones. To address these challenges, we propose a novel multi-strategy fusion algorithm, the Improved Particle Swarm-Butterfly Optimization Algorithm (IPSOBOA), designed specifically for UAV drone path planning in intricate 3D spaces. Our approach enhances the standard Butterfly Optimization Algorithm (BOA) through several key innovations: (1) Tent chaotic mapping combined with opposition-based learning for superior population initialization; (2) a nonlinear parameter adjustment strategy and dynamic switching probability to balance exploration and exploitation; and (3) the integration of particle swarm optimization (PSO) velocity dynamics into the local search phase to accelerate convergence and improve solution quality. In this paper, we detail the mathematical formulation of the cost function, the algorithmic improvements, and present comprehensive simulation results in both static and dynamic environments, demonstrating the clear superiority of IPSOBOA over multiple state-of-the-art optimization methods for UAV drone path planning.
Table 1 summarizes the notation used throughout this paper to describe the path planning problem and the proposed algorithm.
| Symbol | Description |
|---|---|
| $W_i$ | The $i$-th complete flight path consisting of $N$ waypoints |
| $P_{i,j}$ | The $j$-th waypoint of path $W_i$, coordinate $(x_{i,j}, y_{i,j}, z_{i,j})$ |
| $F_1, F_2, F_3, F_4$ | Path length cost, threat cost, flight height cost, and smoothness cost |
| $d_r$ | Distance from the UAV drone to a radar threat source |
| $R_{max}, R_{min}$ | Maximum and minimum radar detection radii |
| $p$ | Switching probability in BOA for balancing global and local search |
| $a$ | Power exponent in BOA controlling the intensity of fragrance |
| $\omega_1, \omega_2$ | Inertia weights for global and local search phases in IPSOBOA |
| $v_{ij}(t)$ | Velocity component for the $i$-th individual at the $j$-th dimension at time $t$ |
2. Fitness Function and Problem Formulation
The core of any optimization-based path planning method is a well-defined fitness function. For a UAV drone, the path must minimize length, avoid threats, maintain a suitable altitude, and ensure smooth turning and climbing. We define the total cost $F(W_i)$ for a path $W_i$ as a weighted sum of four sub-costs, as shown in Equation (1).
$$ F(W_i) = \sum_{k=1}^{4} c_k F_k(W_i) $$
Here, $c_1, c_2, c_3, c_4$ are the weights for path length, threat, flight height, and smoothness costs, respectively. A smaller $F(W_i)$ indicates a superior path. The path length cost $F_1$ is simply the sum of Euclidean distances between consecutive waypoints, as given in Equation (2).
$$ F_1(W_i) = \sum_{j=1}^{N-1} \|P_{i,j} P_{i,j+1}\| $$
The threat cost $F_2$ encapsulates the risk from radar detection, no-fly zones (NFZs), and physical obstacles like terrain or buildings. For a UAV drone, the probability of detection by a radar $P_r(d_r)$ is modeled as a function of distance $d_r$, shown in Equation (3). When $d_r$ is less than the minimum safe radius $R_{min}$, detection is certain.
$$ P_r(d_r) = \begin{cases} 0, & d_r > R_{max} \\ \frac{1}{d_r^4}, & R_{min} \leq d_r \leq R_{max} \\ 1, & d_r < R_{min} \end{cases} $$
The total threat cost $F_2(W_i)$ combines the radar threat and the obstacle threat $T(W_i)$, as defined in Equation (4). The obstacle threat $T(W_i)$ is computed by checking the proximity of each path segment to every obstacle $k$ with radius $R_k$.
$$ F_2(W_i) = T(W_i) + F_i(P_r) $$
The flight height cost $F_3$ penalizes deviations from a desired altitude band, as defined in Equation (5). The optimal altitude is the midpoint between the maximum and minimum allowable heights $h_{max}$ and $h_{min}$.
$$ F_3(W_i) = \sum_{j=1}^{N} H_{i,j}, \quad H_{i,j} = \begin{cases} |h_{i,j} – (h_{max}+h_{min})/2|, & h_{min} \leq h_{i,j} \leq h_{max} \\ \infty, & \text{otherwise} \end{cases} $$
The smoothness cost $F_4$ is crucial for the maneuverability of a UAV drone. It penalizes sharp turns and abrupt changes in climbing angle. The turning angle $\phi_{i,j}$ and climbing angle $\theta_{i,j}$ are defined in Equations (6) and (7), respectively.
$$ \phi_{i,j} = \arctan\left( \frac{\| \overrightarrow{P’_{i,j}P’_{i,j+1}} \times \overrightarrow{P’_{i,j+1}P’_{i,j+2}} \|}{\overrightarrow{P’_{i,j}P’_{i,j+1}} \cdot \overrightarrow{P’_{i,j+1}P’_{i,j+2}}} \right) $$
$$ \theta_{i,j} = \arctan\left( \frac{z_{i,j+1} – z_{i,j}}{\|\overrightarrow{P’_{i,j}P’_{i,j+1}}\|} \right) $$
The total smoothness cost is then given by Equation (8), where $a_1$ and $a_2$ are penalty coefficients for turning and climbing, both set to 1.
$$ F_4(W_i) = \sum_{j=1}^{N-2} (a_1 \phi_{i,j} + a_2 |\theta_{i,j+1} – \theta_{i,j}|) $$
Table 2 summarizes the four sub-cost functions and their primary purposes in the context of UAV drone path planning.
| Cost Function | Equation | Primary Purpose |
|---|---|---|
| Path Length ($F_1$) | $ \sum \|P_{i,j}P_{i,j+1}\| $ | Minimize flight distance and energy consumption |
| Threat ($F_2$) | $ T(W_i) + F_i(P_r) $ | Avoid radar detection, no-fly zones, and obstacles |
| Flight Height ($F_3$) | $ \sum H_{i,j} $ | Maintain safe and efficient altitude |
| Smoothness ($F_4$) | $ \sum ( \phi_{i,j} + |\theta_{i,j+1} – \theta_{i,j}| ) $ | Ensure feasible and stable UAV drone maneuvers |
3. The Proposed IPSOBOA Algorithm
To overcome the limitations of the standard BOA, which suffers from slow convergence and a tendency to get trapped in local optima, we propose IPSOBOA. This algorithm integrates three key strategies: enhanced population initialization, adaptive parameter control, and a hybrid search mechanism with PSO.
3.1 Population Initialization via Tent Chaotic Mapping and Opposition-Based Learning
The quality of the initial population significantly affects the convergence speed and final solution quality of metaheuristic algorithms. We use an improved Tent chaotic map to generate a more uniformly distributed set of initial positions for the UAV drone path candidates. The standard Tent map often suffers from short cycles and unstable fixed points. To mitigate this, we introduce a random component, as shown in Equation (9).
$$ x_{i+1} = \begin{cases} 2x_i + \text{rand}(0,1)/N, & 0 \leq x_i < 0.5 \\ 2(1-x_i) + \text{rand}(0,1)/N, & 0.5 < x_i \leq 1 \end{cases} $$
After generating the chaotic sequence, we apply an opposition-based learning strategy to generate corresponding opposite solutions, as defined in Equation (10). This increases population diversity and prevents premature convergence.
$$ x_i’ = \frac{ub+lb}{2} + \frac{ub+lb}{2k} – \frac{x_i}{n} $$
Here, $ub$ and $lb$ are the upper and lower bounds of the search space, $n$ is a scaling factor that changes with iterations, and $k$ is a control parameter. The initial population is formed by selecting the best $N$ individuals from the union of the chaotic solutions and their opposites.
3.2 Nonlinear Parameter Adjustment and Dynamic Switching Probability
In the standard BOA, the power exponent $a$ and switching probability $p$ are static. A fixed $a$ cannot optimally control fragrance intensity throughout the search, and a fixed $p$ fails to balance exploration and exploitation effectively. We introduce a dynamically changing $a$, defined by the sinusoidal function in Equation (11).
$$ a_t = a_{min} + (a_{max} – a_{min}) \sin\left( \frac{\pi r_3}{2} \cdot \frac{t}{T_{max}} \right)^2 $$
Similarly, the switching probability $p$ is adjusted dynamically as a function of the iteration number $t$, as shown in Equation (12). This allows the algorithm to favor global search in early iterations and local development in later iterations.
$$ p = 0.9 – 0.5 \left( \frac{t}{T_{max}} \right)^2 $$
3.3 Hybridization with Particle Swarm Optimization
To further enhance search efficiency, we embed the velocity concept from PSO into BOA’s position update rules. In the global search phase, the position update incorporates the individual’s historical best position ($pbest$) and the global best ($g$), weighted by a random inertia weight $\omega_1$, as shown in Equation (13).
$$ x_i^{t+1} = \omega_1 x_i^t + [(r_2 \cdot pbest – x_i^t) + (r_2 \cdot g – x_i^t)] \cdot f_i $$
In the local search phase, a dynamic inertia weight $\omega_2$ and a velocity term $v_{ij}(t+1)$ are introduced, leading to the velocity-dynamic position update in Equation (14). This directly leverages PSO’s ability to control step size via velocity.
$$ x_i^{t+1} = \omega_2 x_i^t + (r_2 \cdot x_j^t – x_k^t) \cdot f_i + v_{ij}(t+1) $$
The inertial weights $\omega_1$ and $\omega_2$ are defined in Equations (15) and (16) to ensure a smooth transition from exploration to exploitation.
$$ \omega_1 = \omega_{max} – \left( \frac{\omega_{max} – \omega_{min}}{T_{max}} \right) \cdot t $$
$$ \omega_2 = 1 + \cos\left( \frac{\pi t}{2T_{max}} + \pi \right) $$
The algorithmic steps of the IPSOBOA are presented in the pseudo-code. The time complexity of IPSOBOA remains $O(NT_{max})$, which is identical to the standard BOA, but with significantly improved convergence characteristics.
Table 3 provides a comparative overview of the algorithmic components of standard BOA and the proposed IPSOBOA.
| Component | Standard BOA | Proposed IPSOBOA |
|---|---|---|
| Population Initialization | Random | Tent Chaotic Map + Opposition-Based Learning |
| Power Exponent ($a$) | Fixed (e.g., 0.1) | Nonlinear, dynamically adjusted (Eq. 11) |
| Switching Probability ($p$) | Fixed (e.g., 0.6) | Dynamic, iteration-dependent (Eq. 12) |
| Global Search Position Update | Standard BOA equation | Incorporates pbest, gbest, and inertia ($\omega_1$) |
| Local Search Position Update | Standard BOA equation | Incorporates velocity term and dynamic inertia ($\omega_2$) |
| Time Complexity | $O(NT_{max})$ | $O(NT_{max})$ |
4. Simulation Results and Analysis
We conducted extensive simulations to evaluate the performance of IPSOBOA for 3D path planning of UAV drones. The experimental setup included static environments with varying numbers of threats and dynamic environments with moving obstacles. We compared IPSOBOA against BOA, PSO, IBOA, HPSBA, and HPSOBOA. The common parameters were: population size $N=30$, maximum iterations $T_{max}=200$, and waypoints $N=10$. Cost weights were set to $c_1=10, c_2=18, c_3=1, c_4=5$.
4.1 Static Environment Path Planning
Three static scenarios with increasing complexity (3, 6, and 10 obstacles) were used. The performance metrics were the best fitness value and the shortest path length. The results are summarized in Table 4.
As shown in Table 4, IPSOBOA consistently achieved the lowest (best) fitness values and the shortest path lengths across all three scenarios. The improvements became more pronounced as the environment complexity increased.
| Scenario (Complexity) | Algorithm | Best Fitness (m) | Shortest Path Length (m) |
|---|---|---|---|
| 1 (3 Obs, 1 Radar, 1 NFZ) | IPSOBOA | 623.20 | 997.12 |
| BOA | 634.40 | 1014.57 | |
| IBOA | 642.10 | 1022.38 | |
| HPSBA | 766.34 | 1088.26 | |
| HPSOBOA | 747.81 | 1008.28 | |
| PSO | 744.13 | 1066.11 | |
| 2 (6 Obs, 1 Radar, 1 NFZ) | IPSOBOA | 751.06 | 970.55 |
| BOA | 881.15 | 1381.91 | |
| IBOA | 855.19 | 1360.90 | |
| HPSBA | 1267.44 | 1763.38 | |
| HPSOBOA | 918.64 | 1230.01 | |
| PSO | 1199.90 | 1715.16 | |
| 3 (10 Obs, 1 Radar, 1 NFZ) | IPSOBOA | 667.88 | 943.54 |
| BOA | 960.88 | 1522.02 | |
| IBOA | 764.67 | 1219.24 | |
| HPSBA | 882.66 | 1142.87 | |
| HPSOBOA | 718.39 | 951.30 | |
| PSO | 1145.77 | 1581.67 |
The convergence curves demonstrated that IPSOBOA converged to a lower fitness value in significantly fewer iterations than the other algorithms, indicating a faster and more effective search process. For instance, in Scenario 3, IPSOBOA reached its optimal value by the 108th iteration, while other algorithms either stagnated earlier or continued to oscillate.
4.2 Dynamic Environment Path Planning with IDWA
To handle dynamic threats, we integrated IPSOBOA with an improved Dynamic Window Approach (IDWA). The IDWA incorporates a linear velocity change cost and adaptively adjusts the weight for the direction cost. This allows the UAV drone to track the global path generated by IPSOBOA while reacting to moving obstacles in real-time. We tested two scenarios: multiple drones to multiple targets and multiple drones to a single target.
The simulation results showed that the hybrid IPSOBOA-IDWA system enabled UAV drones to effectively replan their paths in the presence of moving obstacles. The resulting flight trajectories were smoother and safer compared to those using other planning algorithms. The adaptive nature of the IDWA prevented unnecessary sharp turns and maintained a more stable flight altitude, crucial for the efficient operation of a UAV drone in a dynamic low-altitude airspace.
5. Conclusion
In this work, we addressed the complex problem of 3D path planning for UAV drones operating in environments with multiple static and dynamic threats. We proposed the IPSOBOA, a multi-strategy fusion algorithm that significantly enhances the standard BOA. The key contributions include a Tent chaotic map with opposition-based learning for better population diversity, a nonlinear parameter and dynamic probability mechanism for balanced search, and a hybrid PSO-BOA local search strategy with velocity dynamics for faster convergence.
Our comprehensive simulations in three static environments demonstrated that IPSOBOA consistently outperformed other leading optimization algorithms, including BOA, PSO, IBOA, HPSBA, and HPSOBOA, in terms of both best fitness value and path length. The improvement was most dramatic in the most complex scenario, where IPSOBOA achieved a 44% lower fitness value and a 61.3% shorter path length compared to the basic BOA. In dynamic environments, the fusion of IPSOBOA with an improved DWA proved highly effective, allowing a UAV drone to seamlessly integrate global path tracking with local reactive obstacle avoidance, resulting in smooth, safe, and flight-ready trajectories. The proposed methodology offers a robust and efficient solution for autonomous UAV drone navigation in challenging and dynamic real-world conditions.