The advent of sophisticated multi-UAV drone systems has revolutionized various fields, from logistics and surveillance to complex military operations. At the heart of these systems lies the critical capability of autonomous path planning, which directly dictates mission efficacy, safety, and success. While single-UAV drone navigation presents significant challenges, coordinating multiple UAV drones—ensuring they reach objectives simultaneously without collision while dynamically avoiding threats—represents a vastly more complex multi-objective optimization problem. This complexity is compounded in realistic three-dimensional environments cluttered with static obstacles and unpredictable, emergent threats.
Traditional path planning algorithms often struggle with the high-dimensional search spaces and real-time computational demands of multi-UAV drone scenarios. Sampling-based planners, such as the Rapidly-exploring Random Tree (RRT) algorithm, have gained prominence for their ability to efficiently explore high-dimensional spaces without requiring a pre-defined environmental discretization. The RRT* variant introduced asymptotic optimality, meaning it converges towards an optimal solution given sufficient time. However, its inherent randomness can lead to slow convergence, inefficient node exploration, and suboptimal paths, which are particularly detrimental in time-sensitive multi-UAV drone operations.
This article addresses these limitations by proposing a novel, enhanced RRT* algorithm specifically designed for multi-UAV drone cooperative 3D path planning. The core improvements integrate a goal-biased sampling strategy with an artificial potential field to guide tree growth intelligently, significantly accelerating convergence. Furthermore, we formalize the essential constraints for UAV drone collaboration—including temporal synchronization and spatial separation—into a comprehensive objective function. A dedicated strategy for dynamic re-planning in the face of sudden threats is also developed, ensuring robustness in unpredictable environments. Extensive simulation results across diverse 3D terrains demonstrate that the proposed method effectively generates safe, optimal, and cooperative flight paths for UAV drone fleets, showcasing superior performance in both initial planning and reactive threat avoidance.
1. Modeling the Operational Environment for UAV Drones
Effective path planning for UAV drones begins with an accurate computational representation of the mission environment. This model must encompass both static geographical features and dynamic, unforeseen threats that a UAV drone may encounter.
1.1 Terrain and Static Obstacle Modeling
Natural terrain and mountains are modeled as cumulative Gaussian functions to create a realistic 3D landscape. The elevation \( z \) at any horizontal coordinate \((x, y)\) is given by:
$$
z(x, y) = \sum_{e=1}^{N_{obs}} h_e \cdot \exp\left( -\left( \frac{x – x_{e}}{x_{s_e}} \right)^2 – \left( \frac{y – y_{e}}{y_{s_e}} \right)^2 \right)
$$
where \( N_{obs} \) is the number of peak-like obstacles, \( h_e \) is the peak height of the \( e \)-th obstacle, \( (x_e, y_e) \) are the coordinates of its center, and \( x_{s_e} \), \( y_{s_e} \) control the slope spread in the x and y directions, respectively. This formulation generates a smooth but challenging terrain for UAV drone navigation, as illustrated in the following representative environment parameters:
| Obstacle ID | Center (x, y, z) [km] | \( x_s \) [km] | \( y_s \) [km] | Height \( h \) [m] |
|---|---|---|---|---|
| 1 | (25, 40, 0) | 7 | 8 | 200 |
| 2 | (50, 45, 0) | 6 | 5 | 200 |
| 3 | (30, 60, 0) | 5.5 | 4.5 | 200 |
| 4 | (45, 20, 0) | 6 | 5.5 | 200 |
1.2 Modeling Sudden Threats for UAV Drone Re-planning
During execution, a UAV drone may encounter unpredicted threats such as pop-up radars or adverse weather cells. These are modeled as spherical zones of danger. A threat is considered detected when a UAV drone enters its proximity. The threat model is defined as:
$$
(x – x_{uo})^2 + (y – y_{uo})^2 + (z – z_{uo})^2 \leq r_{uo}^2
$$
where \( (x_{uo}, y_{uo}, z_{uo}) \) is the center of the spherical threat and \( r_{uo} \) is its radius. For safer re-planning, a buffer distance \( \Delta s \) is added, triggering the re-planning routine when:
$$
(x – x_{uo})^2 + (y – y_{uo})^2 + (z – z_{uo})^2 \leq (r_{uo} + \Delta s)^2
$$
This ensures the UAV drone initiates avoidance maneuvers before breaching the actual threat boundary.
2. The Enhanced RRT* Algorithm for UAV Drone Path Planning
The standard RRT* algorithm, while asymptotically optimal, exhibits slow convergence due to undirected exploration. Our enhancements directly address this for more efficient UAV drone path planning.
2.1 Core RRT* Mechanisms: Rewiring and Optimal Parent Selection
The optimality guarantee of RRT* comes from two key steps after generating a new node \( x_{new} \):
1. Optimal Parent Selection: Instead of simply connecting \( x_{new} \) to the nearest node \( x_{near} \), RRT* searches within a local hypersphere centered at \( x_{new} \) with radius \( \gamma \). It evaluates all candidate nodes \( x_{cand} \) in this sphere and chooses the one that minimizes the total cost from the start \( x_{start} \) to \( x_{new} \), i.e., \( \text{min}( \text{Cost}(x_{cand}) + \text{dist}(x_{cand}, x_{new}) ) \), subject to collision-free connection.
2. Rewiring: After \( x_{new} \) is added, the algorithm revisits other nodes within the same hypersphere. For each such node \( x_{node} \), it checks if a path through \( x_{new} \) offers a lower cost than its current parent: \( \text{Cost}(x_{new}) + \text{dist}(x_{new}, x_{node}) < \text{Cost}(x_{node}) \). If true and the connection is collision-free, \( x_{new} \) becomes the new parent of \( x_{node} \), “rewiring” the tree for global optimality.
2.2 Proposed Enhancements for UAV Drone Applications
We introduce three strategic modifications to tailor RRT* for efficient UAV drone path planning.
1. Expanded Ancestry-Based Parent Selection: Inspired by Quick-RRT*, we expand the set of potential parents beyond the immediate neighbor sphere. For each candidate \( x_{cand} \), we also consider its \( n \)-th level ancestors. This broader search within the tree’s history often yields a more direct and lower-cost connection to \( x_{new} \), leading to shorter overall paths for the UAV drone.
2. Goal-Biased Sampling with Adaptive Probability: Pure random sampling wastes iterations exploring irrelevant regions. We introduce a target bias probability \( p_{target} \). For each sampling iteration, a random number \( p \in [0,1] \) is generated. The sample point \( x_{rand} \) is chosen as:
$$
x_{rand} = \begin{cases}
x_{goal} & \text{if } p > p_{target} \\
\text{RandomSample}() & \text{if } p \leq p_{target}
\end{cases}
$$
This simple yet powerful modification actively pulls the tree growth towards the UAV drone’s target, significantly reducing convergence time.
3. Artificial Potential Field Guided Steering: To further refine the growth direction from \( x_{near} \) towards \( x_{rand} \), we incorporate an attractive force from the goal. The attractive potential \( U_{att}(i) \) at a node \( i \) is:
$$
U_{att}(i) = \frac{1}{2} k_a \cdot p_g(i)^2
$$
where \( k_a \) is a positive attractive gain and \( p_g(i) \) is the distance from node \( i \) to the goal \( x_{goal} \). The resulting attractive force \( F_{att}(i) \) is the negative gradient:
$$
F_{att}(i) = -\nabla U_{att}(i) = k_a \cdot p_g(i)
$$
This force vector influences the steering direction when extending from \( x_{near} \) to create \( x_{new} \), bending the new edge slightly towards the goal and creating a more directed and efficient exploration for the UAV drone.
The complete workflow of the Enhanced RRT* algorithm for a single UAV drone is summarized below:
Algorithm: Enhanced RRT* for UAV Drone Path Planning
1. Initialize tree \( T \) with start node \( x_{start} \).
2. For \( k = 1 \) to \( K_{max} \) do
3. Generate random number \( p \).
4. If \( p > p_{target} \) then \( x_{rand} \leftarrow x_{goal} \)
5. Else \( x_{rand} \leftarrow \text{RandomSample}() \)
6. Find nearest node \( x_{near} \) in \( T \) to \( x_{rand} \).
7. Steer from \( x_{near} \) towards \( x_{rand} \), adjusting direction using \( F_{att}(x_{near}) \) to generate \( x_{new} \).
8. If collision-free(\( x_{near} \), \( x_{new} \)) then
9. Find candidate parent set \( X_{cand} \) including nodes near \( x_{new} \) and their ancestors.
10. Choose \( x_{parent} \) from \( X_{cand} \) minimizing \( \text{Cost}(x) + \text{dist}(x, x_{new}) \).
11. Add edge \( (x_{parent}, x_{new}) \) to \( T \).
12. Rewire tree: for nodes \( x_{node} \) near \( x_{new} \), update parent to \( x_{new} \) if cost-effective.
13. End If
14. If \( \text{dist}(x_{new}, x_{goal}) < \text{threshold} \) then Return path.
15. End For
16. Return best path found or failure.
3. Multi-UAV Drone Cooperative Planning Framework
Extending the single-UAV drone planner to a cooperative fleet requires satisfying inter-drone constraints and a unified mission objective.
3.1 Cooperative Constraints for UAV Drone Fleets
Two fundamental constraints must be enforced for safe and effective multi-UAV drone operations:
Temporal Coordination (Simultaneous Time of Arrival – STA): For coordinated action, all UAV drones must arrive at their designated targets within a common time window. Let \( L_j \) be the path length for UAV drone \( j \), and \( [V_{min}, V_{max}] \) be its allowable speed range. Its feasible arrival time interval is \( t_j = [L_j/V_{max}, L_j/V_{min}] \). The feasible simultaneous arrival time \( T_{arrival} \) is the intersection of all individual intervals:
$$
T_{arrival} = \bigcap_{j=1}^{N_{UAV}} t_j
$$
where \( N_{UAV} \) is the number of UAV drones. A feasible cooperative plan exists only if \( T_{arrival} \) is non-empty.
Spatial Coordination (Collision Avoidance): UAV drones must maintain a minimum safe separation distance \( d_{min} \) throughout the flight to avoid mid-air collisions. For any two UAV drones \( j \) and \( k \) at any time \( t \):
$$
\| \mathbf{p}_j(t) – \mathbf{p}_k(t) \| \geq d_{min}
$$
where \( \mathbf{p}_j(t) \) is the 3D position of UAV drone \( j \) at time \( t \).
3.2 Comprehensive Constraint Set and Objective Function
Beyond cooperation, each UAV drone’s path must satisfy physical and mission-specific constraints: maximum path length \( L_{max} \), maximum turning angle \( \phi_{max} \), maximum climb/dive angle \( \theta_{max} \), altitude bounds \( [H_{min}, H_{max}] \), and radar exposure limits. These are aggregated into a constraint violation penalty \( P \). The overall objective function \( J \) to be minimized for the UAV drone team is a weighted sum of normalized path cost and arrival time, plus a large penalty for constraint violations:
$$
\min J = \mu_1 \sum_{j=1}^{N_{UAV}} \frac{L_j}{L_{max}} + \mu_2 \frac{\min(T_{arrival})}{T_{max}} + M \cdot P
$$
where \( \mu_1 + \mu_2 = 1 \) are weighting coefficients, \( T_{max} \) is a normalization factor for time, and \( M \) is a large constant (e.g., 10^5) to strictly enforce constraint feasibility (\( P=0 \)).
3.3 Sequential Planning with Anti-Collision Strategy
To manage complexity, we employ a sequential planning approach integrated with an anti-collision strategy. The path for the first UAV drone is planned using the Enhanced RRT*. Its resulting path nodes are added to a “no-fly” list. When planning for subsequent UAV drones, the planner is forbidden from using these nodes. If a potential path for a new UAV drone intersects or comes too close to an existing path, alternative candidate paths (e.g., offset laterally) are evaluated. If no conflict-free path is found from the candidate set, the planner re-invokes the Enhanced RRT* for that UAV drone with the no-fly zone constraint active, ensuring spatial deconfliction for the entire UAV drone fleet.
3.4 Dynamic Re-planning for Sudden Threats
When a UAV drone detects a sudden threat during flight, it must locally re-plan its path. The process is as follows:
1. Identify the path segment \( [Q_{start}^{re}, Q_{end}^{re}] \) that intersects the threat sphere (including buffer \( \Delta s \)).
2. Use \( Q_{start}^{re} \) as the new start and \( Q_{end}^{re} \) as the new temporary goal.
3. Execute the Enhanced RRT* algorithm within this local corridor, respecting all constraints, to find a bypass.
4. Replace the threatened segment with the new local path. The UAV drone resumes its mission, and the team’s temporal coordination is re-evaluated based on the new path length.
4. Simulation Analysis and Results
The performance of the proposed framework is validated through simulations in two distinct 3D environments.
4.1 Performance of Enhanced RRT* for a Single UAV Drone
We compare the standard RRT*, a Goal-Biased RRT* (GB-RRT*), and our Enhanced RRT* in Environment 1. The UAV drone must navigate from start (5, 70, 5) km to goal (80, 30, 10) km. Each algorithm was run 30 times. The results clearly demonstrate the superiority of the Enhanced RRT* for UAV drone path planning.
| Algorithm | Avg. Path Length [km] | Avg. Runtime [s] | Avg. Iterations |
|---|---|---|---|
| Standard RRT* | 138.51 | 1.122 | 105 |
| GB-RRT* | 98.60 | 0.512 | 22 |
| Enhanced RRT* (Proposed) | 88.36 | 0.209 | 16 |
Our Enhanced RRT* reduced average path length by 36.2%, runtime by 81.4%, and iterations by 84.8% compared to standard RRT*. The improvements over GB-RRT* are also significant: 10.4% shorter paths, 59.2% faster runtime, and 27.3% fewer iterations. This confirms that the integration of potential-field-guided steering and ancestry-based parent selection yields a highly efficient planner for a UAV drone.
4.2 Multi-UAV Drone Cooperative Planning
We plan paths for a team of four UAV drones in Environment 2, which has more obstacles. Each UAV drone has distinct start and target points. The speed range is set to [120, 250] m/s, and the minimum separation \( d_{min} \) is enforced. The Enhanced RRT* planner successfully generates conflict-free paths. The results for cooperative arrival time are shown below:
| UAV Drone ID | Start Point [km] | Target Point [km] | Planned Path Length [km] | Feasible Arrival Window [s] |
|---|---|---|---|---|
| 1 | (5, 45, 5) | (70, 45, 25) | 70.2 | [280.8, 585.0] |
| 2 | (3, 35, 5) | (70, 30, 30) | 72.5 | [290.0, 604.2] |
| 3 | (5, 23, 5) | (65, 20, 20) | 63.0 | [252.0, 525.0] |
| 4 | (4, 5, 5) | (70, 10, 10) | 68.7 | [274.8, 572.5] |
4.3 Dynamic Re-planning for Sudden Threats
During the execution of the planned paths, a sudden spherical threat (modeled as a black sphere) is introduced into the flight path of one UAV drone. The re-planning module is triggered. Using the Enhanced RRT* algorithm locally between the identified segment start and end points, a new, threat-avoiding path is generated within 0.49 seconds in the complex Environment 2. The UAV drone seamlessly deviates onto this new local path and then rejoins its original trajectory, successfully avoiding the threat while maintaining the overall mission structure for the UAV drone team.
5. Conclusion
This article presented a comprehensive framework for multi-UAV drone cooperative 3D path planning in complex environments. The core contribution is an Enhanced RRT* algorithm that synergistically combines goal-biased sampling, artificial potential field guidance, and expanded parent selection to achieve rapid convergence to high-quality, low-cost paths for a single UAV drone. This efficient planner was then embedded within a larger cooperative framework that enforces critical temporal and spatial constraints, formulates a unified team objective function, and incorporates a robust strategy for dynamic re-planning against sudden threats.
Simulation results across varying terrains conclusively demonstrate the effectiveness of the proposed approach. The Enhanced RRT* significantly outperforms its predecessors in path optimality, computation speed, and convergence rate. When applied to multi-UAV drone scenarios, it reliably generates deconflicted flight paths that satisfy simultaneous arrival requirements. Furthermore, the integrated re-planning capability ensures the UAV drone fleet can adapt robustly to unexpected dangers during mission execution.
Future work will focus on extending this framework to more dynamic scenarios involving moving threats and other cooperative agents, further enhancing the robustness and applicability of autonomous planning for advanced UAV drone swarms.