The rapid advancement of multi-rotor UAV drone technology has catalyzed its integration into a multitude of sectors, including precision agriculture, search and rescue operations, and logistics. At the core of enabling these autonomous or semi-autonomous missions lies the critical challenge of path planning. Efficient trajectory generation is paramount, not only for maximizing operational efficiency and minimizing energy consumption but also for ensuring the safety and reliability of the UAV drone throughout its flight. However, existing planning algorithms often struggle in complex, three-dimensional environments, grappling with issues such as high computational complexity, slow convergence, and the generation of suboptimal paths that may be unsafe or impractical to execute. The fundamental problem extends beyond merely finding the shortest collision-free route; it involves solving a multi-constrained optimization problem that must simultaneously account for path length, safety margins, altitude restrictions, and kinematic smoothness to produce a flyable trajectory for the UAV drone.
Traditional approaches to UAV drone path planning, such as Artificial Potential Field methods and Dijkstra’s algorithm, alongside metaheuristic techniques like Ant Colony Optimization and Genetic Algorithms, have laid important groundwork. Yet, they frequently exhibit limitations in scalability and solution quality within intricate 3D terrains. More recent innovations, including various sampling-based and learning-based methods, continue to push boundaries but often face trade-offs between global optimality, computational efficiency, and robustness in cluttered or highly constrained environments. A persistent gap exists for a method that can efficiently navigate the vast search space of a 3D world while reliably producing high-quality paths under multiple physical and mission-specific constraints for a UAV drone.
To address these challenges, this work proposes a novel hierarchical planning framework that synergistically combines the strengths of deterministic and probabilistic planning paradigms. Our method introduces a “coarse-to-fine” strategy built upon a multi-resolution map representation. In the first stage, a global, guiding path is rapidly generated on a down-sampled, low-resolution map using an enhanced bidirectional A* algorithm. This path provides macro-level feasibility. In the second stage, this guide path is used to construct a confined spatial corridor within the high-resolution map, where a modified RRT* algorithm, termed M-RRT*, performs detailed local exploration and optimization. This “global guidance + local refinement” architecture effectively balances exploration and exploitation. Key innovations within this framework include a dynamic beam-width constraint and a composite cost function for the global A* search to improve efficiency, and a hybrid sampling strategy informed by the global prior alongside a comprehensive multi-objective cost function for the local M-RRT* optimizer to enhance path quality. Furthermore, we design a dedicated backtracking mechanism to bolster the algorithm’s robustness when confronting extreme scenarios where discrepancies between map resolutions might lead to planning failures. The primary objective is to develop a reliable and efficient planner that enables a UAV drone to navigate complex 3D environments, yielding trajectories that are not only collision-free but also short, safe, smooth, and compliant with altitude regulations.
The efficacy of the proposed MA-RRT* (Multi-resolution A*-RRT*) framework is rigorously validated through extensive simulations across seven distinct 3D terrain scenarios of varying complexity, constructed from real Digital Elevation Model (DEM) data. Comparative analyses against several state-of-the-art metaheuristic algorithms, including Genetic Algorithm (GA), Whale Optimization Algorithm (WOA), Safety-enhanced PSO (SPSO), and a Multi-Objective Evolutionary Algorithm (MOEA), demonstrate the superior performance of our method in terms of path cost, computational time, and stability. Additionally, specialized “adversarial” scenarios are designed to test the backtracking mechanism, confirming its critical role in ensuring planning success and path quality under highly challenging conditions. The results substantiate that our hierarchical, hybrid approach offers a compelling solution for advanced 3D path planning for autonomous UAV drone operations.
Environmental Modeling and Problem Formulation
The foundation of any robust path planning algorithm is a precise and computationally tractable model of the environment. For a UAV drone operating in near-earth airspace, this model must accurately capture the terrain’s topography and the spatial distribution of static obstacles. Our modeling approach is designed to balance realism with efficiency, providing a faithful representation of the challenges a UAV drone would face.
We base our environment on a real-world Digital Elevation Model (DEM), which provides a georeferenced grid where each cell $(x, y)$ holds a terrain elevation value $z$. This defines a continuous, three-dimensional topographic surface $H(x, y)$, effectively modeling mountains, valleys, and hills. To represent anthropogenic or natural obstacles like buildings, towers, or dense vegetation, we abstract them as vertical cylinders. This simplification, while not capturing exact shapes, provides a conservative safety model that is efficient for collision checking. Each cylindrical obstacle $k$ is parameterized by its center ground coordinates $(x_k, y_k)$, its height above the local terrain $h_k$, its threat radius $R_k$, a collision radius $D$ (incorporating the UAV drone’s physical size), and a buffer safety radius $S$. The absolute height of the obstacle is thus $Z_k = H(x_k, y_k) + h_k$.
The planned path for the UAV drone is defined as a sequence of $n$ waypoints $X = \{U_1, U_2, …, U_n\}$, where each waypoint $U_i$ has 3D coordinates $(x_i, y_i, z_i)$. The quality and feasibility of this path are evaluated against a set of critical constraints, formulated as cost functions to be minimized.
1. Path Length Constraint: Minimizing flight distance is crucial for extending the UAV drone’s endurance. The total path length $F_1(X)$ is the sum of Euclidean distances between consecutive waypoints:
$$F_1(X) = \sum_{i=1}^{n-1} ||U_{i+1} – U_i||.$$
2. Safety Constraint: This ensures the UAV drone maintains a safe distance from all obstacles. For a path segment between $U_i$ and $U_{i+1}$, we calculate the threat cost based on the minimum distance $d_k$ from the segment to each obstacle $k$’s central axis. A piecewise function $T_k$ assigns infinite cost for penetration into the collision zone ($d_k \leq D+R_k$), a linearly decaying cost within the buffer zone ($D+R_k < d_k \leq S+D+R_k$), and zero cost outside the safety margin. The total safety cost $F_2(X)$ is aggregated over all segments and obstacles:
$$F_2(X) = \sum_{i=1}^{n-1} \sum_{k=1}^{K} T_k(U_i, U_{i+1}).$$
3. Flight Altitude Constraint: The UAV drone’s altitude must remain within permissible bounds $[h_{min}, h_{max}]$ relative to the terrain for safety and regulatory compliance. The altitude cost $H(U_i)$ for a waypoint is zero if its height above ground $z_i – H(x_i, y_i)$ is within bounds, and infinite otherwise. The total altitude cost is:
$$F_3(X) = \sum_{i=1}^{n} H(U_i).$$
4. Kinematic Smoothness Constraint: Sharp turns and steep climbs/descents are inefficient and may exceed the UAV drone’s dynamic capabilities. We penalize the turning angle $\alpha_i$ (horizontal change in direction) and the change in climb angle $\beta_i$ (vertical change in direction) between path segments. The smoothness cost $F_4(X)$ is:
$$F_4(X) = \sigma_1 \sum_{i=1}^{n-2} |\alpha_i| + \sigma_2 \sum_{i=1}^{n-2} |\beta_{i+1} – \beta_i|,$$
where $\sigma_1$ and $\sigma_2$ are weighting coefficients.
The overall objective of the UAV drone path planning problem is to find a path $X$ that minimizes a weighted sum of these cost functions, representing the total flight cost:
$$F(X) = \sum_{k=1}^{4} \tau_k F_k(X),$$
where $\tau_k$ are user-defined weights balancing the importance of each objective (path length, safety, altitude, and smoothness).
| Parameter Description | Symbol / Value |
|---|---|
| Smoothness Cost Weights | $\sigma_1=1$, $\sigma_2=1$ |
| Total Cost Function Weights | $\tau_1=0.2, \tau_2=0.2, \tau_3=0.2, \tau_4=0.1$ |
| UAV Drone Flight Altitude Range | 50 m – 200 m |
| UAV Drone Diameter | 5 m |
| Safety Buffer Distance | 10 m |
The Hybrid Hierarchical Planning Framework: MA-RRT*
To solve the complex multi-constraint optimization problem efficiently, we propose the MA-RRT* algorithm—a hierarchical planner that operates on a two-level map structure. The core idea is to decompose the problem: first, obtain a globally sensible guide path quickly using a low-resolution map, and second, refine this path locally within a high-resolution map to achieve high quality and precision. This approach mitigates the curse of dimensionality and combines the goal-directedness of graph search with the flexibility of sampling-based planning for the UAV drone.
Stage 1: Global Guiding Path Search with Beam-Constrained Bidirectional A*
In this stage, the original high-resolution DEM is down-sampled to create a low-resolution map. This significantly reduces the number of grid cells, shrinking the search space. To efficiently find a path on this map from start $s$ to goal $g$, we employ a bidirectional A* search enhanced with two key strategies.
Dynamic Beam-Width Constraint: To prevent the open lists from growing prohibitively large, we impose an adaptive beam width $W_i$ at iteration $i$:
$$W_i = \max(W_{base} \cdot e^{-\phi i}, W_{min}).$$
Here, $W_{base}$ is the initial width, $\phi$ controls the decay rate, and $W_{min}$ is a minimum width to preserve some exploration. During each expansion step, if the number of nodes in the open list exceeds $W_i$, only the $W_i$ nodes with the lowest $f$-values are retained. This dramatically reduces memory usage and computation time while maintaining a high probability of finding a feasible path.
Enhanced Cost Function: The traditional cost $g(n)$ from start to node $n$ is replaced with a composite cost that incorporates early proxies for our objectives:
$$g(n) = \omega_1 \cdot C_{threat}(n) + \omega_2 \cdot C_{height}(n).$$
$C_{threat}(n)$ is based on the distance to the nearest obstacle in the low-res map, applying a similar penalty model as $T_k$. $C_{height}(n)$ penalizes large changes in altitude between a node and its parent, discouraging unnecessarily steep climbs/descents for the UAV drone. The heuristic $h(n)$ remains the Euclidean distance to the goal. This modified $g(n)$ guides the search towards safer and more terrain-following paths even at the coarse level.
The bidirectional search runs until the forward and backward frontiers meet. The resulting path $\Gamma$, while coarse, provides a strong topological guide for the next stage, indicating promising regions of free space for the UAV drone.
Stage 2: Local Path Refinement with Improved RRT* (M-RRT*)
The global guide path $\Gamma$ is mapped back to the high-resolution coordinate system. A spatial corridor is constructed around it, defining a constrained volume for detailed planning. Within this corridor, the M-RRT* algorithm performs local optimization.
Hybrid Sampling Strategy: Instead of uniform random sampling, M-RRT* uses a mixture of three sampling distributions to accelerate convergence:
$$P_{sample} = \begin{cases}
\mathcal{N}(\Gamma(t); \sigma_g^2), & \text{with probability } p_g \quad \text{(Guide-biased)}\\
q_c – \alpha \nabla C(q_c), & \text{with probability } p_l \quad \text{(Gradient-biased)}\\
\mathcal{U}(Corridor), & \text{with probability } p_u \quad \text{(Uniform)}
\end{cases}.$$
1. Guide-biased: Samples are drawn from a Gaussian distribution centered at a randomly chosen point on the global guide path $\Gamma(t)$. This exploits the prior information.
2. Gradient-biased: In areas of high local obstacle density (high complexity gradient $\nabla C$), sampling is biased away from obstacles to improve escape from cluttered regions.
3. Uniform: A baseline of uniform sampling within the corridor ensures global exploration and probabilistic completeness.
The probabilities $p_g, p_l, p_u$ are tuned parameters. This strategy allows the UAV drone path planner to focus computational effort on promising regions while maintaining robustness.
Multi-Objective Optimization in Tree Rewiring: The core improvement of M-RRT* over standard RRT* lies in its cost function. When extending the tree from a nearest node $U_{near}$ to a new sample $U_{sample}$, or when rewiring the tree, the cost of a path segment or an entire branch is evaluated using the total cost function $F(X)$ defined earlier, not just the path length. This means the algorithm seeks to minimize a weighted sum of length, safety violation, altitude deviation, and smoothness directly during tree growth and refinement. A node $U_{new}$ will choose its parent, and neighboring nodes may be rewired through $U_{new}$, if doing so reduces their total cost $F$. This ensures the final path returned by the tree is optimized against all critical constraints for the UAV drone.
Enhancing Robustness: The Backtracking Mechanism
A potential issue in hierarchical planning is that a path feasible in the low-resolution map might be infeasible in the high-resolution map due to finer obstacles or narrow passages that were averaged out. To counter this, we implement a backtracking mechanism. If the M-RRT* stage fails to find a path within the initial corridor after a specified number of iterations, a discrepancy analysis is triggered. This analysis quantifies differences in obstacle density between the corridor in the high-res map and the vicinity of the guide path in the low-res map. Based on this analysis, the algorithm can:
1. Widen the spatial corridor.
2. Increase the goal-biased sampling probability in the M-RRT* to push through narrow passages.
3. Fall back to the global A* stage to generate an alternative $k$-best global guide path and restart the local refinement.
This mechanism greatly enhances the overall robustness and success rate of the MA-RRT* planner for a UAV drone in challenging environments.
Experimental Results and Analysis
We conducted comprehensive simulations to validate the performance of the proposed MA-RRT* framework. The environment was based on real DEM data, over which we constructed seven distinct 3D scenarios with varying numbers and configurations of cylindrical obstacles to represent increasing complexity for a UAV drone mission. The parameters for these scenarios are summarized below.
| Scenario | Obstacle Set (Center x, y; Height; Radius) |
|---|---|
| 1 | O1(400,300,80,70); O2(700,300,100,60) |
| 2 | O1(500,500,100,80); O2(700,400,150,100) |
| 3 | O1(400,350,100,80); O2(440,530,90,80); O3(600,350,120,80); O4(690,600,150,80) |
| 4 | O1(400,200,90,70); O2(800,500,100,80); O3(600,350,150,80); O4(400,500,180,70) |
| 5 | O1(400,500,80,70); O2(520,350,150,70); O3(700,250,100,70); O4(670,650,130,60) |
| 6 | O1(400,500,60,80); O2(600,200,100,70); O3(500,350,120,80); O4(350,200,120,70); O5(700,550,150,70); O6(650,750,160,80) |
| 7 | O1(390,500,70,70); O2(540,350,80,70); O3(710,350,90,70); O4(450,200,100,60); O5(550,710,120,60); O6(690,520,140,60); O7(700,690,150,50) |
Ablation Study: Global Search Stage
We first evaluated the improvements in the global (low-resolution) search stage. We compared the standard bidirectional A* (Baseline) against: Beam-A* (beam constraint only), g-A* (enhanced cost function only), and All-A* (both improvements). Metrics were the number of expanded nodes, computation time, and resulting path length. Each test was run 10 times. Results for a simple (Scenario 1) and a complex (Scenario 7) case are shown below.
| Scenario & Strategy | Expanded Nodes | Time (ms) | Path Length (m) | Reduction vs Baseline (Nodes/Time/Length) |
|---|---|---|---|---|
| Scenario 1 – Baseline A* | 1928 | 1633 | 182.54 | – |
| Scenario 1 – Beam-A* | 977 | 41 | 175.73 | 48.33% / 97.49% / 3.73% |
| Scenario 1 – g-A* | 1089 | 44 | 171.82 | 43.52% / 97.31% / 5.87% |
| Scenario 1 – All-A* | 1007 | 41 | 172.85 | 47.77% / 97.49% / 5.31% |
| Scenario 7 – Baseline A* | 4631 | 5089 | 179.87 | – |
| Scenario 7 – Beam-A* | 2105 | 95 | 199.92 | 54.55% / 98.13% / -11.15% |
| Scenario 7 – g-A* | 2946 | 105 | 215.44 | 36.39% / 97.94% / -19.78% |
| Scenario 7 – All-A* | 3066 | 104 | 208.35 | 33.79% / 97.96% / -15.83% |
The results are conclusive. The beam constraint (Beam-A*) drastically reduces computation time by over 97% in all cases by limiting the open list size. The enhanced cost function (g-A*) helps find shorter and more terrain-appropriate paths. The combined strategy (All-A*) achieves an excellent balance, offering time savings comparable to Beam-A* while yielding significantly better path quality than Beam-A* alone, especially in complex scenarios. The slight increase in path length compared to the baseline in Scenario 7 is an acceptable trade-off for the orders-of-magnitude faster planning, and this coarse path is merely a guide for the subsequent refinement stage.
Comparative Analysis: Full MA-RRT* Framework
We compared the complete MA-RRT* framework against five prominent metaheuristic algorithms for UAV drone path planning: Genetic Algorithm (GA), Whale Optimization Algorithm (WOA), Safety-enhanced PSO (SPSO), a Navigation-based Multi-Objective PSO (NMOPSO), and a Multi-Objective Evolutionary Algorithm (MOEA). Each algorithm was tasked with minimizing the total cost function $F(X)$. We report the average (avg) and standard deviation (std) of the final path cost $F(X)$ and the planning time over 20 runs per scenario.
| Scen. | Metric | GA | WOA | SPSO | NMOPSO | MA-RRT* | MOEA |
|---|---|---|---|---|---|---|---|
| 1 | Cost (avg) | 7335.55 | 5255.62 | 4597.30 | 4231.45 | 4317.53 | 4785.44 |
| Cost (std) | 415.68 | 303.64 | 395.42 | 144.21 | 108.54 | 172.88 | |
| 4 | Cost (avg) | 8549.67 | 7158.36 | 5015.78 | 5453.25 | 4978.56 | 5011.54 |
| Cost (std) | 619.67 | 299.96 | 455.62 | 209.65 | 196.58 | 229.55 | |
| 7 | Cost (avg) | 9828.66 | 7892.64 | 5799.67 | 6015.44 | 5421.43 | 5952.45 |
| Cost (std) | 512.42 | 417.89 | 514.76 | 525.46 | 275.65 | 289.78 |
| Scen. | Metric | GA | WOA | SPSO | NMOPSO | MA-RRT* | MOEA |
|---|---|---|---|---|---|---|---|
| 1 | Time (avg) | 18.45 | 17.55 | 9.53 | 21.22 | 8.75 | 10.33 |
| Time (std) | 6.17 | 5.10 | 3.59 | 2.49 | 1.68 | 2.11 | |
| 4 | Time (avg) | 24.61 | 22.46 | 11.99 | 24.79 | 10.74 | 14.56 |
| Time (std) | 10.28 | 10.20 | 4.52 | 3.24 | 3.17 | 3.20 | |
| 7 | Time (avg) | 30.26 | 28.18 | 15.44 | 24.28 | 14.38 | 20.34 |
| Time (std) | 12.46 | 12.35 | 4.19 | 4.09 | 3.94 | 4.40 |
The analysis of the data reveals distinct advantages of the MA-RRT* framework for UAV drone path planning. In terms of solution quality, MA-RRT* consistently achieves the lowest or nearly the lowest average total cost $F(X)$ across all scenarios, particularly outperforming others in complex environments (Scenarios 4-7). More importantly, it exhibits the lowest standard deviation in cost in almost every case. This low variance indicates high stability and reliability—the algorithm produces consistently good paths regardless of random seeds, a crucial property for real-world UAV drone deployment. This stability stems from the global guide path, which anchors the stochastic local search, reducing its unpredictability.
Regarding computational efficiency, MA-RRT* is the fastest algorithm overall. Its average planning time is 40-60% lower than that of the compared metaheuristics. This efficiency is a direct result of the hierarchical decomposition: the rapid global search prunes the vast state space, and the local M-RRT* searches within a focused corridor, avoiding wasted exploration. The time standard deviation is also consistently among the lowest, indicating predictable performance. Visual inspection of the generated 3D paths confirms that MA-RRT* produces smooth, terrain-following trajectories that maintain safe clearance from obstacles and adhere to altitude bounds, validating the effectiveness of its multi-objective cost function.
Validation of the Backtracking Mechanism
To stress-test the framework’s robustness, we designed three adversarial scenarios specifically to induce resolution inconsistency: a Narrow Passage scenario, a Small Obstacle Cluster scenario, and a Mixed scenario combining both. We compared the performance of MA-RRT* with and without the backtracking mechanism over 50 runs per scenario.
| Scenario Type | Algorithm | Success Rate | Avg. Planning Time (s) | Avg. Path Length (m) |
|---|---|---|---|---|
| Narrow Passage | No Backtracking | 96.0% | 15.55 | 1450.80 |
| With Backtracking | 100.0% | 18.35 | 1384.80 | |
| Small Obstacle Cluster | No Backtracking | 92.0% | 14.33 | 1354.69 |
| With Backtracking | 98.0% | 15.68 | 1365.52 | |
| Mixed | No Backtracking | 90.0% | 18.75 | 1259.62 |
| With Backtracking | 96.0% | 21.43 | 1295.53 |
The results are decisive. The backtracking mechanism significantly boosts the success rate of the planner in these challenging environments, achieving near-perfect (100%) success in the narrow passage case and markedly higher rates in the others. While it incurs a modest increase in average planning time (as expected when fallback strategies are invoked), this is a worthwhile trade-off for guaranteeing a solution. Furthermore, the paths found with backtracking are often of higher quality (shorter in the Narrow Passage case). This demonstrates that the mechanism not only recovers from failure but can actively guide the search towards better alternatives. It is a critical component for ensuring the operational reliability of the UAV drone path planner in complex, unknown, or cluttered terrains where map abstraction might be imperfect.
Conclusion
This paper presented MA-RRT*, a novel hierarchical and hybrid algorithm for 3D path planning of UAV drones in complex environments. The method addresses key limitations of existing approaches by strategically combining a modified A* algorithm for efficient global guidance on a low-resolution map with an enhanced RRT* algorithm (M-RRT*) for detailed local optimization within a high-resolution map. The core innovations—including the beam-constrained bidirectional search, the hybrid sampling strategy informed by the global prior, and the direct optimization of a multi-objective cost function encompassing length, safety, altitude, and smoothness—work in concert to produce high-quality flight trajectories. The incorporation of a dedicated backtracking mechanism further ensures robustness against the inherent challenges of multi-resolution planning.
Extensive simulation experiments across diverse 3D terrains demonstrate the superiority of the proposed framework. MA-RRT* consistently generates paths with lower total cost and higher stability (lower variance) compared to several state-of-the-art metaheuristic algorithms while also being significantly faster. The successful application of the backtracking mechanism in deliberately crafted adversarial scenarios confirms its vital role in achieving high success rates and maintaining path quality under extreme conditions. In summary, MA-RRT* provides an effective, efficient, and reliable solution for autonomous 3D path planning, enabling UAV drones to navigate safely and optimally through challenging landscapes. Future work will focus on integrating dynamic obstacle avoidance and more refined kinematic models of UAV drone flight to enhance the planner’s applicability to real-time, dynamic missions.