Unmanned aerial vehicle (UAV) path planning is a fundamental component of autonomous flight systems. It enables a UAV to navigate from a starting point to a target point while avoiding obstacles and satisfying kinematic and dynamic constraints. The rapid proliferation of UAV applications in civilian and military domains has driven the need for robust, efficient, and safe path planning algorithms. In this work, we focus on two primary categories of path planning: global path planning in a known environment and local path planning in an environment with dynamic obstacles. We propose enhanced algorithms based on the Rapidly-exploring Random Tree (RRT) and the Dynamic Window Approach (DWA), and we validate their effectiveness through extensive simulations.
This article is organized as follows. Section 2 reviews the fundamental concepts of graph-based and sampling-based global planners, as well as local planners. Section 3 presents the BGO-RRT algorithm for global path planning and discusses its performance in complex static environments. Section 4 introduces a fusion framework combining BGO-RRT-Connect and an enhanced DWA (EA-DWA) algorithm for dynamic scenarios. Finally, Section 5 concludes the paper and outlines future research directions.
1. Preliminaries and Related Work
Several classical algorithms exist for global path planning. Dijkstra’s algorithm finds the shortest path in a weighted graph by greedily expanding the nearest unvisited node. Its search, however, is exhaustive and computationally expensive. The A* algorithm improves Dijkstra’s approach by incorporating a heuristic function \(h(x)\) to guide the search. The cost function is given by
$$ f(x) = g(x) + h(x), $$
where \(g(x)\) is the actual cost from the start to node \(x\), and \(h(x)\) is an estimated cost from \(x\) to the goal. A* can dramatically reduce the search space compared to Dijkstra when the heuristic is admissible.
Sampling-based planners such as RRT and Probabilistic Roadmap (PRM) are well suited for high-dimensional configuration spaces. RRT grows a tree rooted at the start configuration by randomly sampling points in the free space and connecting them to the nearest tree node. The basic expansion step is
$$ P_{\mathrm{new}} = P_{\mathrm{near}} + \mu \frac{P_{\mathrm{rand}} – P_{\mathrm{near}}}{\|P_{\mathrm{rand}} – P_{\mathrm{near}}\|}, $$
where \(\mu\) is the step size, \(P_{\mathrm{near}}\) is the closest node in the tree, and \(P_{\mathrm{rand}}\) is a uniformly random sample. RRT is simple and effective, but it suffers from high randomness, excessive path length, and poor smoothness.
The RRT-Connect algorithm improves RRT by growing two trees simultaneously, one from the start and one from the goal. This bidirectional search substantially increases convergence speed, especially in narrow passages. However, its sampling strategy remains unconstrained, leading to unnecessary detours and sharp turns.
The DWA algorithm is a popular local planner that optimizes velocity commands based on the current dynamic state of the robot or UAV. It samples linear and angular velocities within a dynamically feasible window, simulates trajectories over a short time horizon, and evaluates each trajectory using a cost function
$$ C(v,w) = \alpha_1 \mathrm{Heading}(v,w) + \alpha_2 \mathrm{Dis}(v,w) + \alpha_3 \mathrm{Vel}(v,w). $$
While DWA is effective for avoiding unexpected obstacles, it lacks global guidance and can become trapped in local minima in cluttered environments.
To overcome the limitations of RRT and DWA, we designed a series of improvements. First, we developed the BGO-RRT algorithm that combines an attractive potential field with RRT to guide sampling, applies greedy pruning to eliminate redundant nodes, and uses cubic B-spline curves to smooth the final path. Second, we enhanced the RRT-Connect algorithm by adopting the same goal-oriented sampling strategy, yielding BGO-RRT-Connect. Third, we improved DWA by introducing dual danger-range detection, an enhanced velocity space, and a modified evaluation function, resulting in EA-DWA. Finally, we fused BGO-RRT-Connect with EA-DWA so that the global path provides waypoints for the local planner, enabling both global near-optimality and dynamic obstacle avoidance.
2. Problem Formulation
Let \(\mathcal{P} \subset \mathbb{R}^2\) represent the 2D workspace, discretized as an occupancy grid map. The obstacle region is denoted by \(\mathcal{P}_{\mathrm{obs}}\), and the free space is \(\mathcal{P}_{\mathrm{free}} = \mathcal{P} \setminus \mathcal{P}_{\mathrm{obs}}\). A UAV path is a continuous mapping \(\sigma : [0,1] \rightarrow \mathcal{P}_{\mathrm{free}}\) with \(\sigma(0) = P_s\) and \(\sigma(1) = P_g\), where \(P_s \in \mathcal{P}_{\mathrm{free}}\) and \(P_g \in \mathcal{P}_{\mathrm{free}}\) are the start and goal positions, respectively. The optimal path planning problem is to find
$$ \sigma^* = \arg\min_{\sigma \in \Sigma} c(\sigma), $$
where \(\Sigma\) is the set of all feasible paths and \(c(\sigma)\) is a cost function, typically the total path length.
For dynamic environments, obstacles may move with time. We model each dynamic obstacle as a circle of radius \(r_o\) moving with constant velocity vector \(v_o = (v_{ox}, v_{oy})\). The UAV is modeled as a point but inflated obstacles compensate for its physical size. The objective is to plan a global path that avoids static obstacles and then use a local planner to modify the trajectory in real time when dynamic obstacles are detected by on-board sensors.
3. BGO-RRT for Global Path Planning
3.1 System Model
We use an occupancy grid map of size \(n \times n\). Each cell is either free or occupied. To account for the UAV’s physical size, we dilationally inflate obstacles by a safety margin. The UAV is treated as a point moving in the 2D plane. The map coordinates are computed from cell indices using
$$ x_i = \mathrm{mod}(N_i, N) – 1, \quad y_i = \lceil N_i / N \rceil – 1, $$
where \(N_i\) is the cell index and \(N\) is the number of cells per row/column.
3.2 Algorithm Design
The traditional RRT algorithm suffers from three main deficiencies: (i) high sampling randomness, (ii) redundant path segments, and (iii) sharp turning points. The BGO-RRT algorithm addresses all three issues through the following modifications.
3.2.1 Goal-Oriented Sampling with Artificial Potential Field
We integrate an attractive potential field into the node expansion process. The attractive force directs \(P_{\mathrm{new}}\) toward the goal \(P_g\). The attractive potential is defined as
$$ U_{\mathrm{att}}(P) = \frac{1}{2} \alpha D(P, P_g)^2, $$
where \(\alpha\) is the attraction coefficient and \(D(P, P_g) = \|P – P_g\|\) is the Euclidean distance. The corresponding gravity force is
$$ F_{\mathrm{att}}(P) = -\nabla U_{\mathrm{att}}(P) = -\alpha (P – P_g). $$
During each expansion, a random sample \(P_{\mathrm{rand}}\) is generated as usual, but the growth direction is biased by a fraction of the attractive force. The new node is generated by
$$ P_{\mathrm{new}} = P_{\mathrm{near}} + \mu \frac{P_{\mathrm{rand}} – P_{\mathrm{near}}}{\|P_{\mathrm{rand}} – P_{\mathrm{near}}\|} + \beta \frac{P_g – P_{\mathrm{near}}}{\|P_g – P_{\mathrm{near}}\|}, $$
where \(\beta\) is a weighting factor. This modification significantly reduces exploration randomness and accelerates convergence toward the goal, especially in large open spaces.
3.2.2 Greedy Pruning
After the RRT search converges, the resulting path consists of many intermediate nodes. To remove redundant nodes, we apply a greedy pruning procedure. Starting from the goal node \(P_g\), we attempt to connect it directly to its ancestry nodes as far as possible without intersecting obstacles. If a direct connection to a farther ancestor is collision-free, all intermediate nodes are removed. The procedure is shown in Algorithm 1.
| Step | Operation |
|---|---|
| 1 | Initialize \(P_{\mathrm{start}} = P_s\), \(P_{\mathrm{end}} = P_g\). |
| 2 | Trace ancestors from \(P_{\mathrm{end}}\) to \(P_{\mathrm{start}}\). |
| 3 | For each ancestor \(P_i\), check whether the segment \(P_i P_{\mathrm{start}}\) is collision-free. |
| 4 | If collision-free, remove all nodes between \(P_i\) and \(P_{\mathrm{start}}\); set \(P_{\mathrm{start}} = P_i\). |
| 5 | Continue until \(P_{\mathrm{start}} = P_g\). |
The greedy pruning reduces the path length by keeping only the essential turning points, thereby improving flight efficiency and reducing energy consumption.
3.2.3 B-Spline Smoothing
The pruned path may still contain sharp corners, which are not feasible for a fixed-wing UAV due to limited turn radius. We apply a cubic B-spline curve to smooth the trajectory. A B-spline curve of degree \(k\) is defined by
$$ P(x) = \sum_{i=0}^{n} P_i B_{i,k}(x), $$
where \(P_i\) are control points and \(B_{i,k}(x)\) are the B-spline basis functions given by the Cox–de Boor recursion:
$$ B_{i,0}(x) = \begin{cases} 1, & x_i \le x < x_{i+1}, \\ 0, & \text{otherwise}, \end{cases} $$
$$ B_{i,k}(x) = \frac{x – x_i}{x_{i+k} – x_i} B_{i,k-1}(x) + \frac{x_{i+k+1} – x}{x_{i+k+1} – x_{i+1}} B_{i+1,k-1}(x), $$
where \(x_i\) are knots. We use \(k=3\) because cubic B-splines ensure \(C^2\) continuity, resulting in a smooth path with continuous curvature.
3.3 Simulation Results for Global Planning
We compared BGO-RRT with A*, original RRT, and ant colony optimization (ACO) in two scenarios: a narrow-corridor environment and a complex obstacle environment. The simulation parameters are listed in Table 1 and Table 2.
| Parameter | Value |
|---|---|
| Map size | 100 × 100 |
| Start point | (10, 15) |
| Goal point | (90, 85) |
| Step size \(\mu\) | 2 |
| Attraction coefficient \(\alpha\) | 2 |
| Parameter | Value |
|---|---|
| Map size | 50 × 50 |
| Start point | (0, 0) |
| Goal point | (45, 20) |
| Step size \(\mu\) | 1 |
| Attraction coefficient \(\alpha\) | 1 |
For each algorithm, we ran 50 independent simulations and recorded the average number of nodes, planning time, and failure rate. Table 3 summarizes the results in the narrow-corridor scenario.
| Algorithm | Total nodes | Planning time (s) | Failures |
|---|---|---|---|
| A* | 3776 | 34.51 | 0 |
| RRT | 1014 | 13.49 | 9 |
| ACO | N/A | 9.45 | 12 |
| BGO-RRT | 709 | 6.82 | 0 |
Table 4 reports the results in the complex obstacle scenario.
| Algorithm | Total nodes | Planning time (s) | Failures |
|---|---|---|---|
| A* | 702 | 16.19 | 0 |
| RRT | 866 | 9.29 | 2 |
| ACO | N/A | 8.32 | 0 |
| BGO-RRT | 654 | 7.62 | 0 |
The results demonstrate that BGO-RRT reduces the number of nodes by about 30% compared to RRT in the narrow-corridor case and by 24.5% in the complex case. Planning time is improved by 49.4% and 18.0%, respectively. More importantly, BGO-RRT has zero failures, whereas RRT and ACO exhibit non-negligible failure rates. The path produced by BGO-RRT is also visibly smoother and more suitable for fixed-wing UAV flight.
4. Dynamic Planning with BGO-RRT-Connect and EA-DWA
4.1 Global Planner: BGO-RRT-Connect
RRT-Connect grows two trees simultaneously, which greatly improves convergence speed. We augment RRT-Connect with the same goal-biased sampling strategy as BGO-RRT. The modified algorithm, denoted BGO-RRT-Connect, generates nodes using
$$ P_{\mathrm{new}} = P_{\mathrm{near}} + \mu \frac{P_{\mathrm{nearest}} – P_{\mathrm{near}}}{\|P_{\mathrm{nearest}} – P_{\mathrm{near}}\|} + \beta \frac{P_g – P_{\mathrm{near}}}{\|P_g – P_{\mathrm{near}}\|}, $$
where \(P_{\mathrm{nearest}}\) is the nearest node of the opposite tree. This accelerates the connection of the two trees while maintaining exploration capability.
We compared BGO-RRT-Connect with conventional RRT, RRT-Connect, and BGO-RRT in the 100×100 map. Table 5 lists the comparative results.
| Algorithm | Total nodes | Path length (m) | Planning time (s) | Failures |
|---|---|---|---|---|
| RRT | 796 | 143.8 | 6.65 | 3 |
| RRT-Connect | 316 | 125.3 | 1.64 | 0 |
| BGO-RRT | 242 | 127.9 | 1.35 | 0 |
| BGO-RRT-Connect | 125 | 118.7 | 0.98 | 0 |
BGO-RRT-Connect reduces the number of nodes by 84.3% compared to RRT, and shortens the planning time by 85.3%. The path is also shorter than that of RRT-Connect and BGO-RRT. This global plan serves as an excellent reference for the local planner.
4.2 Local Planner: EA-DWA
The traditional DWA has three major drawbacks: (i) it cannot handle fast-moving obstacles that approach from the rear, (ii) its velocity space only accounts for the first period of motion, and (iii) its evaluation function tends to select paths that are unnecessarily far from obstacles, leading to long detours. We address these issues as follows.
4.2.1 Dual Danger Range Judgment
We define two concentric danger zones around the UAV. The controllable danger radius \(r_1\) and the extreme danger radius \(r_2\) (with \(r_2 < r_1\)). Let \(d\) be the distance between the UAV and a dynamic obstacle.
- If \(d > r_1\), the obstacle is in the safe zone. The UAV continues with its planned trajectory.
- If \(r_2 < d \le r_1\), the obstacle is in the controllable danger zone. The UAV reduces its speed to half of the initial speed and re-evaluates after one control cycle. If the obstacle moves away, the UAV resumes its previous speed.
- If \(0 \le d \le r_2\), the obstacle is in the extreme danger zone. The UAV immediately stops and replans a new local path toward the next global waypoint.
This dual-threshold strategy provides an early response to fast-moving obstacles and avoids unnecessary abrupt maneuvers.
4.2.2 Enhanced Velocity Space
The traditional DWA constructs the velocity window based on the velocities achievable after one time step. We extend this to consider the entire prediction horizon. The enhanced velocity space is
$$ V_p = \left\{ (v,w) \middle| \begin{aligned} &v \in [\max(0, v_0 – \dot{v}_{\max} T), \min(v_{\max}, v_0 + \dot{v}_{\max} T)], \\ &w \in [\max(-w_{\max}, w_0 – \dot{w}_{\max} T), \min(w_{\max}, w_0 + \dot{w}_{\max} T)] \end{aligned} \right\}, $$
where \(v_0, w_0\) are the current velocities, \(\dot{v}_{\max}, \dot{w}_{\max}\) are the maximum linear and angular accelerations, \(v_{\max}, w_{\max}\) are the velocity limits, and \(T\) is the prediction horizon. This expanded velocity space allows the DWA to explore a wider range of feasible maneuvers and produces more realistic trajectory predictions over multiple time steps.
4.2.3 Modified Evaluation Function
We introduce an additional cost term \(A(v,w)\) that penalizes large changes in heading angle between the start of the trajectory and its end. The new evaluation function is
$$ C(v,w) = \alpha_1 \mathrm{Heading}(v,w) + \alpha_2 \mathrm{Dis}(v,w) + \alpha_3 \mathrm{Vel}(v,w) + \alpha_4 \mathrm{Ang}(v,w), $$
where
$$ \mathrm{Ang}(v,w) = \left| 180^\circ – (\theta_{gi} – \theta_{si}) \right|, $$
with \(\theta_{gi}\) being the direction angle at the end of the predicted trajectory and \(\theta_{si}\) the direction angle at the start. All sub-functions are normalized before combination to remove dimensional bias. The coefficient \(\alpha_4\) is empirically set to 0.15 in our simulations, while the other coefficients remain the same as the traditional DWA.
4.3 Fusion Strategy
The fusion framework proceeds as follows:
- Use BGO-RRT-Connect to generate a global path from \(P_s\) to \(P_g\) in the known static map.
- Extract key waypoints from the global path using a collinearity check and obstacle clearance criterion. Nodes that lie on the same straight line are removed, and remaining nodes that are greater than a safety threshold from all obstacles are retained.
- Set the first key waypoint as the current sub-goal for EA-DWA.
- Run EA-DWA to generate local trajectories while sensing dynamic obstacles.
- When the UAV reaches the current sub-goal, move to the next key waypoint until the final goal is reached.
This strategy ensures that the UAV maintains the global traveling direction while adapting to unexpected obstacles in real time.
4.4 Simulation Results for Dynamic Scenarios
We first evaluated EA-DWA against the traditional DWA in a 10×10 map with four moving obstacles. The simulation parameters are given in Table 6 and Table 7.
| Parameter | Value |
|---|---|
| Map size | 10 × 10 |
| Start point | (0, 0) |
| Goal point | (10, 8) |
| Obstacle radius | 0.5 |
| Obstacle speed | 1 m/s |
| Parameter | Value |
|---|---|
| Initial heading (rad/s) | \(\pi/4\) |
| Max linear velocity | 2 m/s |
| Max angular velocity | \(\pi/9\) rad/s |
| Linear acceleration | 0.2 m/s² |
| Angular acceleration | \(5\pi/18\) rad/s² |
Table 8 shows the comparison between DWA and EA-DWA after 10 runs.
| Algorithm | Path length (m) | Planning time (s) | Total turning angle (°) | Failures |
|---|---|---|---|---|
| DWA | 14.55 | 54.7 | 95 | 4 |
| EA-DWA | 13.64 | 43.2 | 68 | 0 |
EA-DWA reduces the planning time by 21%, the path length by 6.25%, and the total turning angle by 28.4%. More importantly, the traditional DWA failed in 4 out of 10 runs due to collisions with obstacles approaching from behind, whereas EA-DWA succeeded in all runs.
Next, we tested the fused algorithm against two baseline fusion methods in a larger 100×100 map. The dynamic obstacles were square blocks moving back and forth along specified segments. Table 9 lists the parameters.
| Parameter | Value |
|---|---|
| Map size | 100 × 100 |
| Start point | (0, 0) |
| Goal point | (50, 90) |
| Obstacle size | 5 × 5 |
| Dynamic obstacle 1 | between (27.5,22.5) and (27.5,12.5) |
| Dynamic obstacle 2 | between (57.5,72.5) and (67.5,72.5) |
| Obstacle speed | 2 m/s |
We compared the proposed fused BGO-RRT-Connect + EA-DWA with three baselines: fused BGO-RRT-Connect + traditional DWA, the algorithm in Ref. [57] (artificial potential field guided RRT), and the algorithm in Ref. [58] (improved A* + DWA). Table 10 shows the results without dynamic obstacles.
| Algorithm | Planning time (s) | Path length (m) | Total turning angle (°) |
|---|---|---|---|
| BGO-RRT-Connect + DWA | 187.2 | 142.5 | 426.5 |
| Ref. [57] | 174.3 | 132.9 | 497.2 |
| Ref. [58] | 186.1 | 124.7 | 161.5 |
| BGO-RRT-Connect + EA-DWA | 172.7 | 128.4 | 103.6 |
The proposed fusion achieves the shortest planning time and the smallest total turning angle, indicating a smoother trajectory. The path length is slightly longer than that of Ref. [58] by 3%, but the improvement in smoothness is substantial.
Table 11 presents the results with dynamic obstacles included.
| Algorithm | Planning time (s) | Path length (m) | Total turning angle (°) | Failures |
|---|---|---|---|---|
| BGO-RRT-Connect + DWA | 196.5 | 168.3 | 483.4 | 3 |
| Ref. [57] | 185.7 | 147.7 | 455.2 | 0 |
| Ref. [58] | 194.5 | 143.5 | 257.0 | 1 |
| BGO-RRT-Connect + EA-DWA | 178.1 | 140.7 | 253.0 | 0 |
Our fusion algorithm not only achieves the smallest planning time and path length among the four, but also has the lowest total turning angle along with Ref. [58]. Moreover, it is the only algorithm that never fails in the 10 runs, demonstrating strong robustness against dynamic disturbances.
5. Conclusion and Future Work
In this paper, we addressed the challenges of global and local path planning for unmanned aerial vehicles using enhanced sampling-based and velocity-based algorithms. We proposed BGO-RRT for static environments by fusing an attractive potential field, greedy path pruning, and cubic B-spline smoothing. The algorithm significantly reduces search randomness and produces shorter and smoother paths. We then extended the idea to BGO-RRT-Connect for faster global planning. For dynamic obstacles, we developed EA-DWA with dual danger-range detection, an expanded velocity space, and a new heading-change cost term. By combining BGO-RRT-Connect and EA-DWA, we achieved a complete planning framework that preserves global optimality while reacting to unexpected obstacles in real time.
Extensive simulations in multiple scenarios demonstrated that BGO-RRT-Connect + EA-DWA outperforms several state-of-the-art planners in terms of planning time, path length, path smoothness, and robustness. The proposed algorithms are particularly suitable for UAV applications such as search and rescue, surveillance, and autonomous delivery.
Future research directions include extending the algorithms to three-dimensional environments, incorporating dynamic constraints such as minimum turning radius and climb angle, and validating the methods on real UAV platforms with onboard sensors. The addition of higher-order dynamics and wind disturbance models would also improve the practical applicability of the proposed planners.