With the rapid advancement of modern high-tech industries, unmanned aerial vehicle (UAV) drones are widely applied in both military and civilian fields, including low-altitude economy sectors such as agriculture, logistics, search and rescue, and air traffic management. These applications not only enhance mission efficiency but also alleviate ground traffic pressure. However, due to the complex and dynamic nature of UAV drones’ flight environments and the constraints of their own performance, finding a safe and efficient flight route has become a critical technical challenge in UAV drones applications, attracting increasing research attention.
Path planning algorithms for UAV drones typically include traditional classical algorithms and intelligent optimization algorithms. Compared with classical methods, intelligent optimization algorithms exhibit stronger search capabilities in complex three-dimensional environments and can generate higher-quality solutions, making them the primary approach for UAV drones path planning. Examples include particle swarm optimization (PSO), firefly algorithm (FA), grey wolf optimizer (GWO), and butterfly optimization algorithm (BOA). These classic intelligent optimization algorithms have been developed and widely applied to UAV drones path planning. For instance, improved PSO has been applied to UAV drones path planning, significantly enhancing path search accuracy and stability. Similarly, improved FA has been used for multi-robot path planning in static environments, and GWO hybridized with differential evolution has achieved shorter flight paths for UAV drones. Among these, the butterfly optimization algorithm (BOA) demonstrates superior global optimization capabilities due to its simple structure, few parameters, high flexibility, and ease of implementation. However, when applied to UAV drones path planning, BOA suffers from slow convergence in later iterations and a tendency to fall into local optima.
To address these limitations and improve convergence accuracy while avoiding local optima for UAV drones path planning, this work proposes a multi-strategy fusion improved particle swarm-butterfly optimization algorithm (IPSOBOA). The algorithm first formulates an objective function incorporating various requirements and constraints related to UAV drones and their flight paths. Then, IPSOBOA leverages the UAV drones’ navigation environment to generate high-quality solutions. Specifically, Tent chaotic mapping is combined with an opposition-based learning strategy to optimize the initial population, enhancing population diversity. Nonlinear parameter adjustment and dynamic conversion probability mechanisms are introduced to balance global exploration and local exploitation. Furthermore, by integrating particle swarm optimization, a velocity term is introduced in the local search phase, leading to a position update equation with dynamically changing velocity, significantly improving search efficiency. Extensive simulations are conducted in both static and dynamic three-dimensional environments with various threat scenarios to evaluate the performance of IPSOBOA against BOA and other optimization algorithms. The experimental results demonstrate that IPSOBOA outperforms BOA in terms of optimal fitness value and path length, generating smoother and safer paths for UAV drones in complex environments.
The rest of this paper is organized as follows. Section 2 defines the problem formulation including the fitness function for UAV drones path planning. Section 3 presents the proposed IPSOBOA algorithm with detailed improvements. Section 4 describes the improved dynamic window approach for real-time obstacle avoidance. Section 5 shows simulation results and discussions. Finally, Section 6 concludes the paper.
Problem Formulation and Fitness Function
In UAV drones path planning, a fitness function is employed to evaluate the quality of generated paths. This section designs a comprehensive fitness function comprising four cost components: path length cost, obstacle threat cost, flight altitude cost, and smoothness cost. A smaller fitness value indicates a superior path for UAV drones.
Path Length Cost
The path length cost represents the total Euclidean distance between consecutive waypoints along the flight path. Assuming the UAV drones maintain constant speed, this cost also correlates with flight time. For a complete flight path Wi consisting of N waypoints, where each waypoint is denoted as Pi,j = (xi,j, yi,j, zi,j), the path length cost function F1 is defined as:
$$ F_1(W_i) = \sum_{j=1}^{N-1} \|P_{i,j} P_{i,j+1}\| $$
Threat Cost
The planned path must guide UAV drones to effectively avoid various obstacles, comply with airspace regulations, and ensure safe, efficient, and stable flight. The simulated environment includes radar threats (represented as light blue hemispheres), no-fly zones (purple cylinders), and K cylindrical obstacles (red cylinders).
Radar threat probability depends on the distance dr between UAV drones and the radar center. The detection probability is given by:
$$
P_r(d_r) = \begin{cases}
0, & d_r > R_{\max} \\
\frac{1}{d_r^4}, & R_{\min} \le d_r \le R_{\max} \\
1, & d_r < R_{\min}
\end{cases}
$$
$$
F_i(P_r) = \begin{cases}
\infty, & P_r = 1, i \le N \\
T \cdot P_r, & 0 \le P_r < 1, i \le N
\end{cases}
$$
where Rmax is the maximum detection radius, Rmin is the high-risk radius, and T is a constant threat cost multiplier.
For no-fly zones and obstacles, the threat cost is determined by the shortest distance from the threat center to each path segment. Let D be the UAV drones’ diameter, C the safety clearance distance between path nodes, and Rk the projection radius of the k-th obstacle. The threat cost for path Wi is:
$$
T(W_i) = \begin{cases}
0, & d_k > C + D + R_k \\
\sum_{j=1}^{N-1} \sum_{k=1}^K (C + D + R_k – d_k), & D + R_k < d_k \le C + D + R_k \\
\infty, & d_k \le D + R_k
\end{cases}
$$
$$
F_2(W_i) = T(W_i) + F_i(P_r)
$$
Flight Altitude Cost
UAV drones’ flight altitude is constrained between a minimum hmin and maximum hmax. Proper altitude management reduces fuel consumption, improves energy efficiency, and enhances flight safety. The altitude cost for path Wi is defined as:
$$
F_3(W_i) = \sum_{j=1}^N H_{i,j}
$$
$$
H_{i,j} = \begin{cases}
\left| h_{i,j} – \frac{h_{\max} + h_{\min}}{2} \right|, & h_{\min} \le h_{i,j} \le h_{\max} \\
\infty, & \text{otherwise}
\end{cases}
$$
where hi,j is the altitude of waypoint Pi,j above ground.
Smoothness Cost
The smoothness cost evaluates the turning and climbing rates required to follow the path, ensuring trajectory smoothness to improve stability, safety, and energy efficiency. The cost involves turning angle φi,j (projected on horizontal plane) and climbing angle θi,j (vertical plane projection angle with horizontal plane):
$$ P’_{i.j}P’_{i.j+1} = k \times (P’_{i.j}P’_{i.j+1} \times k) $$
$$
\phi_{i,j} = \arctan\left( \frac{\|P’_{i.j}P’_{i.j+1} \times P’_{i.j+1}P’_{i.j+2}\|}{P’_{i.j}P’_{i.j+1} \cdot P’_{i.j+1}P’_{i.j+2}} \right)
$$
$$
\theta_{i,j} = \arctan\left( \frac{z_{i,j+1} – z_{i,j}}{\|P’_{i.j}P’_{i.j+1}\|} \right)
$$
The smoothness cost F4 is then:
$$
F_4(W_i) = \sum_{j=1}^{N-2} (a_1 \phi_{i,j} + a_2 |\theta_{i,j+1} – \theta_{i,j}|)
$$
where a1 and a2 are penalty coefficients (set to 1). The total cost function for path Wi is:
$$
F(W_i) = \sum_{k=1}^{4} c_k F_k(W_i)
$$
| Cost Component | Symbol | Description |
|---|---|---|
| Path Length | F1 | Sum of Euclidean distances between consecutive waypoints |
| Threat | F2 | Combined radar, no-fly zone, and obstacle threat penalty |
| Altitude | F3 | Penalty for deviation from optimal altitude range |
| Smoothness | F4 | Penalty for sharp turning and climbing angles |
Improved Butterfly Optimization Algorithm (IPSOBOA)
To address the issues of premature convergence and slow convergence speed in the traditional butterfly optimization algorithm (BOA) for UAV drones path planning, a multi-strategy fusion improved particle swarm-butterfly optimization algorithm (IPSOBOA) is proposed. The algorithm incorporates several enhancement mechanisms.
Tent Chaotic Mapping with Opposition-Based Learning
To ensure population diversity and uniform distribution in the search space, Tent chaotic mapping combined with opposition-based learning is used to initialize the population positions. Compared to Logistic mapping, Tent mapping generates more uniformly distributed sequences. The improved Tent mapping with a random perturbation is defined as:
$$
x_{i+1} = \begin{cases}
2x_i + \frac{\text{rand}(0,1)}{N}, & 0 \le x_i < 0.5 \\
2(1 – x_i) + \frac{\text{rand}(0,1)}{N}, & 0.5 < x_i \le 1
\end{cases}
$$
After generating initial solutions via chaotic mapping, opposition-based learning is applied to perturb solutions and enhance diversity:
$$
x_i’ = \frac{ub + lb}{2} + \frac{ub + lb}{2k} – \frac{x_i}{n}
$$
where ub and lb are upper and lower bounds, k is a scaling factor, and n is given by:
$$
n = \left(1 + \frac{1}{T_{\max}}\right)^{0.5^{10}}
$$
The final initial population combines forward and backward solutions, selecting the top N individuals based on fitness values.
Nonlinear Parameter Adjustment and Dynamic Conversion Probability
In traditional BOA, a fixed power exponent a controls butterfly search behavior. A nonlinear dynamic adjustment strategy is proposed:
$$
a_t = a_{\min} + (a_{\max} – a_{\min}) \sin\left( \frac{\pi r_3}{2} \left( \frac{t}{T_{\max}} \right)^2 \right)
$$
where r3 is a random number in [0,1], amin = 0.1, amax = 0.9, and Tmax = 500. This function provides steep slope early for fast global search and gradual slope later for refined local search.
A dynamic conversion probability p is also introduced to balance global exploration and local exploitation:
$$
p = 0.9 – 0.5 \left( \frac{t}{T_{\max}} \right)^2
$$
| Parameter | Symbol | Value |
|---|---|---|
| Minimum power exponent | amin | 0.1 |
| Maximum power exponent | amax | 0.9 |
| Sensory modality | c | 0.1 |
| Initial conversion probability | p | 0.6 |
| Maximum inertia weight | ωmax | 0.9 |
| Minimum inertia weight | ωmin | 0.4 |
| Cognitive coefficient | c1 | 0.5 |
| Social coefficient | c2 | 0.5 |
Hybridization with Particle Swarm Optimization
To improve convergence speed and balance global/local search, PSO characteristics are integrated into BOA. In the global search phase, a random inertia weight ω1 is introduced, and the historical best position is considered:
$$
\omega_1 = \omega_{\max} – \left( \frac{\omega_{\max} – \omega_{\min}}{T_{\max}} \right) \cdot t
$$
$$
x_i^{t+1} = \omega_1 x_i^t + [(r_2 \cdot \text{pbest} – x_i^t) + (r_2 \cdot g – x_i^t)] \cdot f_i
$$
where pbest is the personal best position, g is the global best position, r2 is a random number, and fi is the fragrance intensity.
In the local search phase, a dynamic inertia weight ω2 and velocity term vij(t+1) are introduced:
$$
\omega_2 = 1 + \cos\left( \frac{\pi t}{2T_{\max}} + \pi \right)
$$
$$
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 pseudo-code of IPSOBOA is summarized as follows:
Algorithm 1: IPSOBOA for UAV Drones Path Planning
Input: Population size N, maximum iterations Tmax, parameters a, c, ω
Output: Best solution xi and its fitness f(xi)
- Initialize butterfly population using Tent chaotic mapping and opposition-based learning
- Evaluate fitness of each butterfly
- while t < Tmax do
- for each butterfly i do
- Calculate fragrance fi using nonlinear parameter at
- Generate random number r
- Calculate conversion probability p using dynamic formula
- if r < p then
- Global search: update position using Eq. (21)
- else
- Local search: update position using Eq. (22)
- end if
- end for
- Re-evaluate fitness and update global best
- end while
Time Complexity Analysis
The time complexity of IPSOBOA is dominated by the initialization, parameter adjustment, and iterative search. The initialization using chaotic mapping and opposition-based learning is O(N). The nonlinear parameter and probability adjustments are O(1). The iterative search, including fitness evaluation and position updates, is O(NTmax). Therefore, the overall time complexity of IPSOBOA is O(NTmax), which is identical to that of BOA, but with significantly improved optimization capability, especially for high-dimensional problems.
Improved Dynamic Window Approach (IDWA)
In the standard dynamic window approach (DWA), fixed evaluation factors are used to assess velocity windows. However, in dynamic environments, fixed factors may not adapt to changing conditions. An improved DWA (IDWA) is proposed for real-time obstacle avoidance of UAV drones.
Linear Velocity Change Evaluation Function
To reduce frequent velocity changes and energy consumption in UAV drones, a linear velocity change evaluation function is added:
$$
\text{change}(v, \omega_1, \omega_2) = \frac{1}{|v_{i+1} – v_i|}
$$
Adaptive Weight Adjustment
The heading evaluation weight is adjusted adaptively based on obstacle density in the detection area:
$$
\alpha_1 = \alpha \left( \frac{a_{\text{obs}}}{a} + \mu \right)
$$
where α is the base weight, aobs is the obstacle area within the detection region, a is the total detection area, and μ is a constant.
The overall IDWA evaluation function is:
$$
G_1(v, \omega_1, \omega_2) = \sigma[\alpha_1 \text{head}(v, \omega_1, \omega_2) + \beta \text{dist}(v, \omega_1, \omega_2) + \gamma \text{vel}(v, \omega_1, \omega_2) + \delta \text{change}(v, \omega_1, \omega_2)]
$$
where σ is a normalization factor, and β, γ, δ are weight coefficients for distance, velocity, and velocity change, respectively.
Simulation Results and Analysis
Experimental Setup
Simulations are conducted on MATLAB R2020a with a Windows 10 system (Intel Core i9-12900 CPU, 2.4 GHz, 32 GB RAM). The proposed IPSOBOA is compared with BOA, PSO, IBOA, HPSBA, and HPSOBOA. Parameter settings are based on original literature. The UAV drones’ specifications include start point (200, 100, 150) m, end point (800, 800, 150) m, radar center (780, 350, 150) m, no-fly zone center (230, 570, 150) m, airspace range [1000, 800, 400] m, speed range [5, 20] m/s, maximum turning angle 45°, and maximum climbing angle 30°. Population size N = 30, maximum iterations Tmax = 200, and waypoints N = 10. Weight coefficients are b1 = 10, b2 = 18, b3 = 1, b4 = 5.
| Scenario | Algorithm | Best Fitness (m) | Shortest Path Length (m) | Convergence Time (s) |
|---|---|---|---|---|
| 1 (3 obstacles, 1 radar, 1 no-fly zone) | IPSOBOA | 623.20 | 997.12 | 1.01 |
| BOA | 634.40 | 1014.57 | 1.72 | |
| IBOA | 642.10 | 1022.38 | 1.28 | |
| HPSBA | 766.34 | 1088.26 | 1.65 | |
| HPSOBOA | 747.81 | 1008.28 | 2.03 | |
| PSO | 744.13 | 1066.11 | 1.69 | |
| 2 (6 obstacles, 1 radar, 1 no-fly zone) | IPSOBOA | 751.06 | 970.55 | 1.17 |
| BOA | 881.15 | 1381.91 | 2.04 | |
| IBOA | 855.19 | 1360.90 | 1.65 | |
| HPSBA | 1267.44 | 1763.38 | 1.96 | |
| HPSOBOA | 918.64 | 1230.01 | 2.34 | |
| PSO | 1199.90 | 1715.16 | 2.10 | |
| 3 (10 obstacles, 1 radar, 1 no-fly zone) | IPSOBOA | 667.88 | 943.54 | 1.32 |
| BOA | 960.88 | 1522.02 | 2.38 | |
| IBOA | 764.67 | 1219.24 | 1.96 | |
| HPSBA | 882.66 | 1142.87 | 2.82 | |
| HPSOBOA | 718.39 | 951.30 | 2.70 | |
| PSO | 1145.77 | 1581.67 | 2.51 |
In the static environment, IPSOBOA achieves the smallest best fitness values across all three scenarios. Compared to BOA, IPSOBOA optimizes best fitness by 1.8%, 17%, and 44% and path length by 1.8%, 42.4%, and 61.3% for scenarios 1, 2, and 3, respectively. This demonstrates that as environment complexity increases, IPSOBOA maintains superior optimization performance for UAV drones path planning.
| Scenario | IPSOBOA | BOA | IBOA | HPSBA | HPSOBOA | PSO |
|---|---|---|---|---|---|---|
| 1 | 12 | 45 | 38 | 62 | 55 | 70 |
| 2 | 93 | 155 | 132 | 178 | 165 | 180 |
| 3 | 108 | 180 | 160 | 190 | 175 | 195 |
Dynamic Environment Results
In dynamic environments, the IPSOBOA-IDWA fusion algorithm is evaluated for multi-UAV drones path planning under two scenarios: multi-aircraft multi-target and multi-aircraft same-target. Dynamic obstacles with radius 20 m are added with varying trajectories. The simulation results show that the IPSOBOA-IDWA algorithm quickly adjusts initial attitudes, follows pre-planned global paths, and effectively avoids dynamic obstacles in real-time, resulting in smoother and safer paths with reduced turning frequency and flight altitude.
| Scenario | Obstacle | Start (m) | End (m) |
|---|---|---|---|
| Multi-aircraft multi-target | 1 | (500, 700, 250) | (1000, 500, 250) |
| 2 | (800, 500, 250) | (200, 500, 250) | |
| 3 | (200, 400, 250) | (600, 200, 250) | |
| Multi-aircraft same-target | 4 | (800, 500, 250) | (200, 500, 250) |
| Metric | Multi-Aircraft Multi-Target | Multi-Aircraft Same-Target |
|---|---|---|
| Average Path Length (m) | 985.4 | 1023.7 |
| Average Turning Angle (deg) | 22.3 | 25.1 |
| Obstacle Avoidance Success Rate (%) | 100 | 100 |
| Convergence Time (s) | 1.45 | 1.52 |
Conclusion
This paper proposes a multi-strategy fusion improved particle swarm-butterfly optimization algorithm (IPSOBOA) for solving the path planning problem of UAV drones under multiple constraints. The algorithm incorporates Tent chaotic mapping with opposition-based learning for population initialization, nonlinear parameter adjustment and dynamic conversion probability for balancing exploration and exploitation, and hybrid PSO with velocity-assisted position updates. Extensive simulations in both static and dynamic three-dimensional environments demonstrate the effectiveness and superiority of IPSOBOA. In static scenarios, IPSOBOA achieves up to 44% improvement in best fitness and 61.3% reduction in path length compared to BOA. In dynamic environments, the IPSOBOA-IDWA fusion algorithm successfully combines global path tracking with real-time obstacle avoidance, generating smoother, safer, and more efficient trajectories for UAV drones. The proposed approach provides a robust solution for UAV drones path planning in complex threat environments.