In recent years, the rapid advancement of drone technology has positioned Unmanned Aerial Vehicles (UAVs) as critical tools in various industrial applications, including surveillance, logistics, and environmental monitoring. Path planning is a fundamental challenge in autonomous UAV operations, particularly for obstacle avoidance in complex environments. Among existing algorithms, the Rapidly-exploring Random Tree (RRT) algorithm is widely adopted due to its adaptability and ability to handle high-dimensional spaces without explicit environment modeling. However, traditional RRT suffers from issues such as unguided tree expansion, inefficiency in dense obstacle regions, and excessive redundant nodes, which can hinder the performance of Unmanned Aerial Vehicle systems. To address these limitations, we propose an enhanced algorithm termed IAPF-GRRT, which integrates artificial potential field-guided sampling, gradient-constrained convergence, adaptive step-size adjustment, greedy pruning, and B-spline smoothing. This approach significantly improves the efficiency and quality of path planning for drone technology, as demonstrated through simulations in both 2D and 3D environments.
The basic RRT algorithm operates by iteratively expanding a tree from an initial point $X_{\text{init}}$ to a goal $X_{\text{goal}}$. It generates a random sample $X_{\text{rand}}$, finds the nearest node $X_{\text{near}}$ in the tree, and extends toward $X_{\text{rand}}$ with a fixed step size $\lambda$ to produce a new node $X_{\text{new}}$. Collision detection is performed to ensure feasibility, and the process repeats until the goal is reached or the maximum iterations are exceeded. The algorithm’s random nature often leads to inefficient paths with numerous unnecessary nodes, especially in cluttered environments common in Unmanned Aerial Vehicle applications. For collision detection, we employ an enhanced Axis-Aligned Bounding Box (AABB) method that projects obstacles onto the path segment and reconstructs the coordinate system for accurate assessment, reducing false positives and improving reliability for drone technology implementations.
To enhance the guidance of tree expansion, we introduce an improved target bias strategy combined with artificial potential field (APF) principles. In traditional APF, the attractive force $F_{\text{att}}$ from the goal and repulsive forces $F_{\text{rep}}$ from obstacles guide the path. We modify the repulsive force function to address local minima issues common in drone technology. The attractive force is defined as:
$$ F_{\text{att}}(X) = \eta \rho(x, x_g) $$
where $\eta$ is a positive gain coefficient, and $\rho(x, x_g)$ is the Euclidean distance between the current position $x$ and the goal $x_g$. The repulsive force is reformulated as:
$$ F_{\text{rep1}} = m \left( \frac{1}{\rho(q, q_0)} – \frac{1}{\rho_0} \right) \frac{\rho_g^n}{\rho^2(q, q_0)} $$
and
$$ F_{\text{rep2}} = \frac{n}{2} m \left( \frac{1}{\rho(q, q_0)} – \frac{1}{\rho_0} \right)^2 \rho_g^{n-1} $$
with the total repulsive force $F_{\text{rep}} = F_{\text{rep1}} + F_{\text{rep2}}$, where $m$ is the repulsive gain, $\rho(q, q_0)$ is the distance to the obstacle, $\rho_0$ is the obstacle’s influence distance, $\rho_g$ is the distance between start and goal, and $n$ is the number of obstacles. The resultant force $F = F_{\text{att}} + F_{\text{rep}}$ directs the sampling point $X_{\text{guided}}$ when a random value exceeds a bias probability $P_{\text{goal}}$, otherwise $X_{\text{goal}}$ is used directly. This strategy enhances the target-oriented expansion of the tree, crucial for efficient Unmanned Aerial Vehicle navigation in obstacle-rich environments.
Next, we incorporate a gradient-constrained convergence strategy to refine the search process and accelerate iteration speed. This involves gradient search and a local escape operator (LEO) to balance global exploration and local optimization. Using Taylor series expansion, the numerical gradient is computed as:
$$ f'(x) = \frac{f(x + \Delta x) – f(x – \Delta x)}{2 \Delta x} $$
which in iterative form becomes:
$$ x_{n+1} = x_n – \frac{2 \Delta x \cdot f(x_n)}{f(x_n + \Delta x) – f(x_n – \Delta x)} $$
In our algorithm, $x_n$, $x_n + \Delta x$, and $x_n – \Delta x$ correspond to $X_T$, $X_{\text{guided}}$, and $X_{\text{near}}$, respectively. To avoid local optima, we introduce stochastic elements and direction vectors. The modified search update is:
$$ \text{MSN} = \text{rand} \times \rho_1 \times \frac{2 \Delta x \cdot x_n}{(x_{\text{worst}} – x_{\text{best}} + \epsilon)} $$
where $\Delta x = \text{rand}(1:N) \times \text{Step}$, and $\rho_1$ is a gradient convergence coefficient. The direction vector PQ is added to guide movement toward the goal:
$$ \text{PQ} = \text{rand} \times \rho_2 \times (X_{\text{goal}} – X_{\text{guided}}) $$
Thus, the position update formula is:
$$ X_n^m = x_n^m – \text{MSN} + \text{PQ} $$
Additionally, LEO optimizes the solution by combining multiple candidates:
$$ x_{\text{best}} = L \times X_{\text{goal}} + (1 – L) \times X_{\text{guided}} $$
where $L$ is a dynamic escape coefficient. This approach improves search efficiency in dense obstacle regions, which is vital for Unmanned Aerial Vehicle operations in complex scenarios.
We further propose an adaptive step-size adjustment strategy based on obstacle proximity to enhance exploration capabilities. Instead of a fixed step size $\lambda$, we dynamically adjust it according to the distance $d$ between the node $X_T$ and the nearest obstacle, relative to a threshold $\omega$. The step size $\lambda_x$ is updated as:
$$ \lambda_x = \begin{cases}
\lambda (1 + \alpha) \Delta k, & \text{if } \omega \leq d \\
\lambda (1 – \beta), & \text{if } \omega > d
\end{cases} $$
where $\alpha$ and $\beta$ are dynamic coefficients, and $\Delta k$ is the absolute difference between $\omega$ and $d$. This allows the algorithm to take larger steps in safe regions and smaller steps near obstacles, reducing redundant nodes and improving path quality for drone technology applications. The process ensures that the Unmanned Aerial Vehicle can navigate efficiently without compromising safety.
After generating an initial path, we apply a greedy pruning strategy to eliminate redundant nodes. This involves checking non-adjacent nodes $X_i$ and $X_j$ (with $i < j$) for direct connectivity without collisions. If no collision is detected, intermediate nodes are removed, and $X_i$ and $X_j$ are connected directly. This simplifies the path and reduces its length, which is essential for optimizing the performance of Unmanned Aerial Vehicles. Finally, we smooth the path using cubic B-spline curves to ensure continuity and feasibility. The B-spline curve is defined as:
$$ P(t) = \sum_{i=0}^{n} N_{i,3}(t) P_i $$
where $P_i$ are the path nodes, and $N_{i,3}(t)$ is the cubic B-spline basis function computed recursively:
$$ N_{i,0}(t) = \begin{cases}
1, & t_i \leq t \leq t_{i+1} \\
0, & \text{otherwise}
\end{cases} $$
and
$$ N_{i,k}(t) = \frac{(t – t_i) N_{i,k-1}(t)}{t_{i+k} – t_i} + \frac{(t_{i+k+1} – t) N_{i+1,k-1}(t)}{t_{i+k+1} – t_{i+1}} $$
This smoothing step enhances path smoothness, critical for stable Unmanned Aerial Vehicle flight.
To validate our IAPF-GRRT algorithm, we conducted simulations in MATLAB for both 2D and 3D environments. In the 2D scenario, a 350 m × 350 m map was used with a start point at (0, 350) and a goal at (300, 30). The target bias probability $P_{\text{goal}}$ was set to 0.5. We compared our algorithm against basic RRT, Goal-RRT, and RRT* over 30 independent runs. The results, summarized in the table below, demonstrate significant improvements in path nodes, planning time, and path length.
| Algorithm | Path Nodes | Planning Time (s) | Path Length (m) |
|---|---|---|---|
| Basic RRT | 98 | 34.687 | 566.276 |
| Goal-RRT | 76 | 5.864 | 579.877 |
| RRT* | 47 | 40.381 | 491.847 |
| IAPF-GRRT | 6 | 0.733 | 452.064 |
Our IAPF-GRRT algorithm reduced the number of path nodes by 93.88%, 92.11%, and 87.23% compared to basic RRT, Goal-RRT, and RRT*, respectively. Planning time was shortened by 97.89%, 87.50%, and 98.18%, and path length decreased by 20.17%, 22.04%, and 8.01%. These enhancements highlight the algorithm’s efficiency in 2D path planning for drone technology.
In the 3D environment, we used a 150 m × 150 m × 150 m space with a start at (0, 0, 0) and a goal at (150, 150, 150), with $P_{\text{goal}} = 0.7$. The simulations involved 30 runs for each algorithm, and the results are presented in the following table.
| Algorithm | Path Nodes | Planning Time (s) | Path Length (m) |
|---|---|---|---|
| Basic RRT | 90 | 64.771 | 566.276 |
| Goal-RRT | 51 | 8.105 | 579.877 |
| RRT* | 36 | 40.381 | 491.847 |
| IAPF-GRRT | 5 | 49.762 | 452.064 |
In 3D, IAPF-GRRT achieved reductions in path nodes of 94.44%, 90.20%, and 86.11% compared to basic RRT, Goal-RRT, and RRT*. Planning time decreased by 97.80%, 82.38%, and 97.13%, and path length was shortened by 26.07%, 15.41%, and 20.28%. These results confirm the algorithm’s robustness and superiority in complex 3D environments, which are typical for Unmanned Aerial Vehicle applications.
The integration of artificial potential field guidance, gradient constraints, adaptive step sizing, and path optimization techniques enables our IAPF-GRRT algorithm to overcome the limitations of traditional RRT. This is particularly beneficial for drone technology, where efficient and safe path planning is paramount. The algorithm’s ability to reduce redundant nodes and computation time while producing shorter, smoother paths makes it highly suitable for real-time Unmanned Aerial Vehicle operations. Future work will focus on incorporating dynamic obstacle avoidance and environmental factors like wind resistance to enhance practicality further.
In conclusion, the proposed IAPF-GRRT algorithm represents a significant advancement in path planning for Unmanned Aerial Vehicles. By addressing key issues such as unguided expansion and inefficiency in dense obstacles, it offers a reliable solution for autonomous navigation. The simulation results underscore its effectiveness, paving the way for improved drone technology in diverse industrial fields. As Unmanned Aerial Vehicle applications continue to expand, such innovations will play a crucial role in ensuring operational efficiency and safety.