We present a comprehensive study on the path planning optimization for multi-UAV drone swarms conducting patrol missions in high-altitude plateau regions. The unique challenges of these environments, including low atmospheric pressure, low temperatures, strong winds, and complex terrain, necessitate a robust and efficient path planning framework that prioritizes both safety and operational efficiency. Our research focuses on developing a hierarchical optimization model and a novel hybrid algorithm to address the multi-objective nature of this problem. The proposed method integrates an improved Genetic Algorithm (GA) with a Quantum Particle Swarm Optimization (QPSO) framework, enhanced by a quantum interference mechanism to prevent premature convergence. This approach autonomously determines the optimal fleet size and generates balanced patrol routes that minimize total flight distance and maximum mission completion time while ensuring strict adherence to safety constraints, such as avoiding terrain penetration. We validate our methodology through extensive simulations using a realistic plateau terrain model, demonstrating significant performance improvements over traditional heuristic algorithms like Simulated Annealing (SA), Ant Colony Optimization (ACO), and standard Particle Swarm Optimization (PSO). The results confirm that our improved GA-QPSO algorithm can reduce total flight distance by up to 29.07% and maximum mission completion time by up to 27.71%, showcasing its superior multi-objective collaborative optimization capability for UAV drone swarms operating in challenging plateau environments.
1. Problem Definition and Challenges for UAV Drone Swarms
The path planning for a multi-UAV drone swarm in a plateau environment is a complex combinatorial optimization problem. The primary objective is to assign a series of patrol points to a fleet of heterogeneous UAVs and determine the optimal flight sequence for each UAV, all while navigating within a constrained airspace. This must be achieved while accounting for several critical factors: three-dimensional obstacle avoidance, safe clearance from terrain, energy constraints represented by maximum endurance, time windows for task completion, and the degraded aerodynamic performance of UAV drones due to high altitude and low air density. The fundamental challenge lies in the trade-off between safety and efficiency. For instance, a direct path between two patrol points might cross a mountain peak, posing a collision risk. The UAV drone must then choose between a vertical climb to clear the obstacle or a horizontal detour around it, each option having different implications for flight time and energy consumption.
The complexity is further increased by the requirement for cooperative task allocation. The mission must be divided among the available UAV drones in a way that balances the workload, preventing some units from being overburdened while others remain idle. This load balancing is crucial for maximizing the overall efficiency and reliability of the swarm. The central problem can be characterized as a multi-dimensional, coupled optimization of “fleet size – task allocation – three-dimensional trajectory.” The goal is to generate closed-loop return paths for each UAV drone from a single base point, respecting constraints on endurance, operational time windows, and the required dwelling time at each patrol point.
2. Mathematical Model for Multi-UAV Drone Path Optimization
To formally model this problem, we establish a multi-objective optimization framework. The model incorporates key parameters and constraints that reflect the realities of plateau operations. Below is a table defining the core parameters used in our model.
| Parameter | Description |
|---|---|
| $P = \{P_0, P_1, …, P_n\}$ | Set of all patrol points, where $P_0$ is the single base station. |
| $K = \{K_1, K_2, …, K_m\}$ | Set of UAV drones in the swarm. |
| $dt_j$ | Dwelling time required for UAV drone $j$ at a patrol point. |
| $H_{Min}$ | Minimum safe altitude clearance above terrain. |
| $L_j^{Max}$ | Maximum endurance range of UAV drone $j$. |
| $\Delta L_j$ | Mandatory safety reserve distance for UAV drone $j$. |
| $V_j$ | Ideal cruising speed of UAV drone $j$. |
| $RC_j, RD_j$ | Ideal rate of climb and rate of descent for UAV drone $j$. |
| $W_d, W_t$ | Weight coefficients for total distance and maximum time in the objective function. |
2.1 Performance Correction for Plateau Environment
The performance of UAV drones is significantly degraded in plateau environments. We introduce a comprehensive correction factor $I(H, T)$ to model the impact of high altitude ($H$) and low temperature ($T$) on UAV performance.
$$I(H_i, T_i) = \max\left(0.7, 1 – \frac{H_i – 3000}{10000}\right) \cdot \max\left(0.8, 1 – \frac{|T_i + 15|}{40}\right)$$
The effective performance parameters of a UAV drone are then:
$$V_j^{eff} = V_j \cdot I$$
$$RC_j^{eff} = RC_j \cdot I$$
$$RD_j^{eff} = RD_j \cdot I$$
Wind also plays a crucial role. The ground speed $V_g$ is adjusted based on the wind speed $S_i$ and the angle between the flight direction $\phi$ and the wind direction $\phi_w$.
$$V_g = \max\left(1, V_j^{eff} + S_i \cos(\phi – \phi_w)\right)$$
2.2 Multi-Objective Fitness Function
The overall fitness function is designed to balance flight distance and time while punishing unbalanced workloads and infeasible solutions.
Total Flight Distance: $f_1(x) = \sum_{j=1}^{M} \sum_{i=1}^{N} \sum_{i+1}^{N} X_{i,i+1}^j \cdot l_{i,i+1}$
Maximum Mission Completion Time: $f_2(x) = \max\limits_{j \in K} \left( \sum_{i=1}^{N} X_{i,i+1}^j \cdot (t_{i,i+1}^j + t_i) \right)$
Load Balancing (Standard Deviation of Individual Path Lengths): $f_4(x) = \text{std} \left( f_3^1(x), …, f_3^M(x) \right)$
Endurance Penalty: $f_5(x) = \rho \sum_{j=1}^{M} \max\left(0, f_3^j(x) – L_j^{Max}\right)$, where $\rho >> 1$.
The combined objective function is: $$F(x) = W_d f_1(x) + W_t f_2(x) + W_b f_4(x) + f_5(x)$$
2.3 Key Constraints for UAV Drones
- Task Coverage: Each patrol point must be visited by exactly one UAV drone. $\sum_{j \in K} Y_i^j = 1 \quad \forall i \in P \setminus \{0\}$
- Flow Conservation: For each UAV drone, the number of entries into a patrol point equals the number of exits.
- Terrain Safety: The path altitude must be greater than the terrain height plus a safety margin. $H_{i,i+1}(O) \geq H_i(O) + H_{Min} \quad \forall O \in Path$
- Endurance Constraint: The total flight distance for each UAV drone must not exceed its effective endurance range. $\sum_{i \in P} \sum_{i+1 \in P} X_{i,i+1}^j \cdot l_{i,i+1} \leq L_j$
3. The Hybrid GA-QPSO Algorithm for UAV Drone Swarms
Our algorithm employs a two-layer hierarchical architecture. The upper layer determines the optimal number of UAV drones in the swarm using a Dynamic Multi-Swarm QPSO (DM-QPSO) algorithm. The lower layer then solves the detailed path planning problem for this determined fleet using an improved GA-QPSO algorithm.
3.1 Upper Layer: Fleet Size Optimization with DM-QPSO
The DM-QPSO algorithm operates on different candidate fleet sizes. For each size, it performs the following steps:
- Task Partitioning: Using K-means clustering, the patrol points are divided into spatially independent clusters, one for each candidate UAV drone.
- Parallel Optimization: A separate QPSO sub-population is created for each cluster to solve a single-UAV drone path planning problem. Paths are decoded using the Smallest Position Value (SPV) rule.
- Global Exploration: Periodically, patrol points are migrated between the worst and best clusters, and sub-populations are reset to avoid premature convergence.
3.2 Lower Layer: Path Planning with Improved GA-QPSO
Once the fleet size is fixed, the improved GA-QPSO algorithm generates the final patrol paths. Its core mechanisms include:
- Hybrid Evolution: The algorithm combines GA operators (tournament selection, ordered crossover, composite mutation with 2-opt local search) with the global search capability of QPSO.
- Quantum Interference Injection: Periodically, a quantum perturbation is introduced to non-elite individuals, randomly reconstructing parts of their routes to enhance diversity and escape local optima.
- Multi-Objective Normalization and Adaptive Weighting: To handle the trade-off between distance and time, the algorithm normalizes these objectives using the solution bounds from a “minimum-distance” and a “minimum-time” endpoint scheme. An anchor-guidance term and an adaptive weighting mechanism ensure stable convergence towards a balanced Pareto-optimal solution.
4. Experimental Setup and Simulation Results
We validated our algorithm using a simulated plateau environment with a 20 km by 30 km area containing 62 patrol points. The environmental conditions were set to represent a harsh plateau climate: -15°C ambient temperature and an average wind speed of 8 m/s from a constant direction. We simulated two common UAV types for comparison.
4.1 UAV Drone Configuration
| Parameter | Multirotor (Tianmushan-1) | Fixed-Wing (Swift Wing YC-1380-Y) |
|---|---|---|
| Max Range (km) | 100 | 100 |
| Safety Reserve (km) | 80 | 80 |
| Cruise Speed (m/s) | 12 | 20 |
| Max Climb Rate (m/s) | 8 | 5 |
| Hover/Time Penalty (s) | 5 | 0 |
4.2 Algorithm Convergence and Fleet Size Optimization
The DM-QPSO algorithm was used to find the optimal number of UAV drones. The fitness values for different fleet sizes are shown in the table below.
| Number of UAV Drones | Fitness Value |
|---|---|
| 4 | 0.92 |
| 7 | 0.54 |
| 9 | 0.37 |
| 11 | 0.29 |
| 13 | 0.31 |
| 15 | 0.35 |
The algorithm determined that a fleet of 11 UAV drones provided the best balance between task efficiency and resource cost, achieving the lowest combined fitness value.
4.3 Performance Comparison with Baseline Algorithms
We compared our improved GA-QPSO algorithm against SA, ACO, and PSO. The improvements were measured in terms of percentage savings in the “Balanced Scheme,” which represents the best trade-off between total distance and maximum mission time.
| Metric | vs. SA | vs. ACO | vs. PSO |
|---|---|---|---|
| Total Distance Saved (%) | 23.81 | 29.07 | 18.95 |
| Mission Time Saved (%) | 14.06 | 27.71 | 15.18 |
4.4 Key Quantitative Results for the Balanced Solution
The balanced solution generated for a fleet of 11 multirotor UAV drones was evaluated in detail. Selected quantitative results are summarized below:
| UAV ID | Total Flight Distance (km) | Mission Completion Time (min) |
|---|---|---|
| UAV-1 | 38.2 | 62.0 |
| UAV-2 | 52.1 | 100.5 |
| UAV-3 | 23.9 | 78.8 |
| UAV-4 | 47.5 | 103.2 |
| UAV-5 | 69.5 | 158.6 |
| UAV-6 | 40.4 | 89.3 |
| UAV-7 | 55.6 | 120.1 |
| UAV-8 | 31.0 | 75.4 |
| UAV-9 | 36.8 | 88.0 |
| UAV-10 | 60.2 | 135.5 |
| UAV-11 | 44.1 | 110.3 |
The results confirm that our algorithm successfully distributes the workload among the 11 UAV drones, preventing any single unit from being either over- or under-utilized. Furthermore, all paths strictly adhered to the 80 km effective endurance constraint, with the maximum distance flown being 69.5 km, thus ensuring a safe operational margin.
5. Conclusion
This research successfully developed and validated an improved GA-QPSO algorithm for the multi-objective path planning of multi-UAV drone swarms in high-altitude plateau regions. By integrating a dynamic performance model that accounts for altitude and wind effects with a hierarchical optimization framework, our method autonomously determines the optimal fleet size and generates safe, efficient, and balanced patrol routes. The algorithm intelligently navigates complex terrain, choosing between vertical climbs and horizontal detours to ensure safety while optimizing for both total flight distance and mission completion time. The inclusion of a quantum interference mechanism and an adaptive multi-objective weighting scheme proved highly effective in preventing premature convergence and achieving a high-quality Pareto-optimal solution. Comparative simulations against benchmark heuristic algorithms demonstrated a significant performance advantage, with maximum reductions of 29.07% in total distance and 27.71% in total mission time. While the current model assumes an unrestricted airspace and perfect communication, the proposed framework provides a robust and effective foundation for enhancing the intelligence and automation of UAV drone patrol missions in challenging environments, including applications in high-altitude railway inspections and emergency responses.