In recent years, Unmanned Aerial Vehicles have become integral to various fields such as military operations, logistics, and surveying. Autonomous navigation and path planning are critical for the efficient operation of Unmanned Aerial Vehicles, especially in complex environments. However, traditional path planning algorithms often struggle with issues like excessive redundant sampling points, slow convergence, and paths that do not comply with actual Unmanned Aerial Vehicle motion constraints. This paper addresses these challenges by proposing an improved Bidirectional Rapidly-exploring Random Tree algorithm, termed SAT-RRT, which integrates the Artificial Potential Field method, three-dimensional Separating Axis Theorem for collision detection, and an adaptive B-spline smoothing strategy. Our approach aims to enhance the efficiency, safety, and practicality of path planning for Unmanned Aerial Vehicles, ensuring that the generated paths are feasible for real-world applications like those involving JUYE UAV systems.
Path planning for Unmanned Aerial Vehicles involves generating a collision-free trajectory from a start point to a goal point while adhering to dynamic and kinematic constraints. Traditional algorithms, such as A*, PRM, and RRT, have been widely used, but they often exhibit limitations in high-dimensional spaces. For instance, the Bidirectional RRT algorithm improves convergence speed by growing two trees simultaneously from the start and goal points. However, it still suffers from random sampling inefficiencies, leading to redundant nodes and non-optimal paths. Moreover, these algorithms typically do not account for the physical volume of Unmanned Aerial Vehicles or their motion constraints, making the paths impractical for real-world deployment. In contrast, our SAT-RRT algorithm introduces a guided sampling mechanism using Artificial Potential Fields to reduce randomness, incorporates 3D collision detection with the Separating Axis Theorem to ensure safety, and applies an adaptive B-spline method for smooth path generation. This comprehensive approach ensures that the path planning process is not only efficient but also aligns with the operational requirements of Unmanned Aerial Vehicles like JUYE UAV.
The key contributions of this work include the development of a novel sampling strategy that leverages attractive and repulsive forces from the Artificial Potential Field to direct the growth of random trees, thereby minimizing unnecessary explorations. Additionally, we extend the Separating Axis Theorem to three-dimensional spaces for rapid collision detection, considering the Unmanned Aerial Vehicle’s volume to avoid infeasible paths. Finally, we enhance the path smoothing process using cubic B-splines with adaptive collision correction, which dynamically adjusts control points to prevent intersections with obstacles. Through extensive simulations in both 2D and 3D environments, we demonstrate that SAT-RRT significantly reduces sampling points by up to 88%, shortens path lengths by 8-16%, and produces smoother paths compliant with Unmanned Aerial Vehicle kinematics. These improvements make SAT-RRT particularly suitable for applications in complex scenarios, such as urban navigation or search-and-rescue missions using JUYE UAV platforms.
Background and Preliminaries
To provide a foundation for our improved algorithm, we first review the Bidirectional RRT method and the kinematic constraints of Unmanned Aerial Vehicles. The Bidirectional RRT algorithm operates by constructing two trees—one from the start point and another from the goal point—which expand towards each other through random sampling. This bidirectional approach accelerates convergence compared to unidirectional RRT, as it reduces the exploration space. The algorithm can be summarized by the following steps: initialize two trees, sample random points, extend trees towards these points, and attempt to connect the trees when they are close. However, the random nature of sampling often leads to inefficiencies, especially in cluttered environments, resulting in numerous redundant nodes and suboptimal paths.
For Unmanned Aerial Vehicles, kinematic constraints must be considered to ensure feasible paths. In three-dimensional space, the position of a Unmanned Aerial Vehicle is represented by Cartesian coordinates (x, y, z), and its velocity vector is denoted as $\vec{v} = (v_x, v_y, v_z)$. The motion constraints include altitude limits, pitch angle, and turning angle. The altitude h must satisfy $H_{max} > h > H_{min}$, where $H_{max}$ and $H_{min}$ are the maximum and minimum allowable flight heights, respectively. The pitch angle $\gamma$, which is the angle between the Unmanned Aerial Vehicle’s longitudinal axis and the horizontal plane, must be bounded by $|\gamma| < \gamma_{max}$ to prevent excessive tilting. It can be calculated as:
$$ \tan\gamma = \frac{|z + \Delta t \cdot v_z|}{\sqrt{(x + \Delta t \cdot v_x)^2 + (y + \Delta t \cdot v_y)^2}} $$
The turning angle $\theta$, which defines the change in heading direction, is constrained to ensure stable maneuvers and is given by:
$$ \cos\theta = \frac{v_x v_{tx} + v_y v_{ty} + v_z v_{tz}}{|\vec{v}| \cdot |\vec{v_t}|} $$
where $\vec{v_t} = (v_{tx}, v_{ty}, v_{tz})$ is the velocity vector at the next time step. These constraints are crucial for path planning, as they directly impact the Unmanned Aerial Vehicle’s ability to follow generated trajectories safely. In our SAT-RRT algorithm, we integrate these constraints into the sampling and collision detection phases to ensure that all paths are kinematically feasible for Unmanned Aerial Vehicles like JUYE UAV.
Proposed SAT-RRT Algorithm
The SAT-RRT algorithm enhances the standard Bidirectional RRT by incorporating three key components: an Artificial Potential Field-guided sampling strategy, 3D Separating Axis Theorem-based collision detection, and an improved cubic B-spline adaptive smoothing technique. Below, we detail each component and its integration into the path planning process for Unmanned Aerial Vehicles.
Artificial Potential Field-Guided Sampling
Traditional Bidirectional RRT relies on random sampling, which can lead to inefficient exploration in complex environments. To address this, we introduce the Artificial Potential Field method to guide the sampling process. The APF generates a virtual force field composed of attractive forces from the goal and repulsive forces from obstacles, directing the Unmanned Aerial Vehicle towards the target while avoiding collisions. The total force $\vec{F}$ acting on the Unmanned Aerial Vehicle is given by:
$$ \vec{F} = \vec{F}_{att} + \vec{F}_{rep} $$
where $\vec{F}_{att}$ is the attractive force and $\vec{F}_{rep}$ is the repulsive force. The attractive force is derived from the potential field function $U_{att}$ as:
$$ \vec{F}_{att}(\vec{M}) = -\nabla U_{att}(\vec{M}) = K \cdot (\vec{M_g} – \vec{M}) $$
Here, $\vec{M} = [x, y, z]^T$ represents the current position of the Unmanned Aerial Vehicle, $\vec{M_g} = [x_g, y_g, z_g]^T$ is the goal position, and K is the gain coefficient for the attractive field. The potential function $U_{att}$ is defined as:
$$ U_{att}(\vec{M}) = \frac{1}{2} K \|\vec{M} – \vec{M_g}\|^2 $$
The repulsive force $\vec{F}_{rep}$ accounts for both static and dynamic obstacles and is expressed as:
$$ \vec{F}_{rep} = \vec{F}_{rep_s} + \vec{F}_{rep_d} $$
where $\vec{F}_{rep_s}$ is the force from static obstacles and $\vec{F}_{rep_d}$ from dynamic obstacles. For a static obstacle, the repulsive potential $U_{rep_s}$ is:
$$ U_{rep_s}(\vec{M}) = \begin{cases}
\frac{1}{2} K_r \left( \frac{1}{d_{ob}} – \frac{1}{d_o} \right)^2, & \text{if } d_{ob} \leq d_o \\
0, & \text{if } d_{ob} > d_o
\end{cases} $$
where $d_{ob} = \sqrt{(x – x_{ob})^2 + (y – y_{ob})^2 + (z – z_{ob})^2}$ is the distance to the obstacle, $d_o$ is the influence distance, and $K_r$ is the repulsive gain. The repulsive force components are calculated as:
$$ \vec{F}_{rep_s} = F_{rep_x} \cdot \vec{a_x} + F_{rep_y} \cdot \vec{a_y} + F_{rep_z} \cdot \vec{a_z} $$
with
$$ F_{rep_x} = K_r \left[ \frac{1}{d_{ob}} – \frac{1}{d_o} \right] \frac{1}{d_{ob}^2} (x – x_{ob}) $$
and similarly for $F_{rep_y}$ and $F_{rep_z}$. For dynamic obstacles, the repulsive force considers relative velocities and directions to avoid collisions proactively. The parameters K and $K_r$ are tuned based on environmental density; for sparse obstacles, $K_r = 0.5K$ to reduce detours, and for dense environments, $K_r = 0.8K$ to enhance obstacle avoidance. This guided sampling approach significantly reduces redundant points by focusing the search towards promising regions, improving the efficiency of path planning for Unmanned Aerial Vehicles.
3D Separating Axis Theorem for Collision Detection
In path planning for Unmanned Aerial Vehicles, it is essential to consider the physical volume of the vehicle to prevent collisions. Traditional algorithms often treat the Unmanned Aerial Vehicle as a point, which is unrealistic. We model the Unmanned Aerial Vehicle as a sphere with radius R and employ the Separating Axis Theorem for efficient 3D collision detection. SAT determines whether two convex objects intersect by checking for overlaps in their projections onto various axes. If no overlap exists on any axis, the objects are separated; otherwise, they collide.
For a Unmanned Aerial Vehicle represented as a sphere centered at $\vec{M_u}$ and an obstacle as a convex polyhedron with center $\vec{M_{ob}}$, we generate separation axes from the face normals of the polyhedron, the vector $\vec{d} = \vec{M_{ob}} – \vec{M_u}$, and the cross products of edge vectors with $\vec{d}$. The projections of the sphere and polyhedron onto each axis are computed, and if for any axis, the maximum projection of one object is less than the minimum of the other, no collision occurs. Mathematically, for a separation axis $\vec{n}$, the projections are given by:
$$ \min_A = \min(\vec{p_A} \cdot \vec{n}), \quad \max_A = \max(\vec{p_A} \cdot \vec{n}) $$
$$ \min_B = \min(\vec{p_B} \cdot \vec{n}), \quad \max_B = \max(\vec{p_B} \cdot \vec{n}) $$
where $\vec{p_A}$ and $\vec{p_B}$ are the vertex sets of the Unmanned Aerial Vehicle and obstacle, respectively. If $\max_A < \min_B$ or $\max_B < \min_A$ for any axis, the objects are collision-free. This method efficiently handles 3D geometries and integrates with the sampling process to reject invalid points, ensuring that all paths are safe for Unmanned Aerial Vehicles like JUYE UAV. In cases where a collision is detected, we dynamically adjust the repulsive force by increasing the gain $K_r$ to steer the Unmanned Aerial Vehicle away from obstacles.
Improved Cubic B-Spline Adaptive Smoothing
Paths generated by sampling-based algorithms often contain sharp turns and redundant points, making them unsuitable for Unmanned Aerial Vehicles. We address this by applying an improved cubic B-spline smoothing technique that adaptively corrects for collisions. The cubic B-spline curve C(t) is defined by control points $P_i$ and basis functions $N_{i,3}(t)$:
$$ C(t) = \sum_{i=0}^n N_{i,3}(t) P_i, \quad t \in [0,1] $$
After generating an initial path, we discretize the B-spline curve into points $Q_j$ at intervals $\Delta s$. For each point, we check the distance to nearby obstacles. If the distance is less than the safe distance (e.g., the Unmanned Aerial Vehicle radius), we mark it as a conflict point and adjust the control points using gradient descent to minimize a cost function E that balances smoothness and obstacle avoidance:
$$ E = \int \| C”(t) \|^2 dt + \lambda \sum \max(0, d_{safe} – d(Q_j, O_j))^2 $$
Here, the first term penalizes high curvature to ensure smoothness, and the second term penalizes proximity to obstacles. The control points are updated iteratively as:
$$ P_k \leftarrow P_k – \eta \left[ \sum_j \left( \int N_{k,3}”(t) N_{j,3}”(t) dt \right) P_j + 2\lambda \sum_j (d_{safe} – d(Q_j, O_j)) \frac{\partial Q_j}{\partial P_k} \right] $$
where $\eta$ is the learning rate. This adaptive smoothing ensures that the final path is both smooth and collision-free, meeting the kinematic constraints of Unmanned Aerial Vehicles. For instance, in complex environments, this method prevents the smoothed path from intersecting obstacles, which is critical for the safe operation of JUYE UAV systems.
Simulation and Experimental Results
We evaluated the SAT-RRT algorithm through simulations in both 2D and 3D environments, comparing it with existing algorithms like Goal-RRT, Dynamic RRT, and improved RRT-Connect. The experiments were conducted on a system with an AMD Ryzen 5 3600 processor using MATLAB 2021. We measured performance metrics including the number of sampling points, computation time, path length, and path smoothness. The Unmanned Aerial Vehicle was modeled with a radius of 0.3 m, and environments varied from simple to complex, including static and dynamic obstacles.
In 2D environments, we used a 200 m × 200 m map with start point (0,0) and goal point (190,190). The results, summarized in Table 1, show that SAT-RRT consistently reduced the number of sampling points compared to other algorithms. For example, in simple environments, SAT-RRT used 61 sampling points, which is 54.48% fewer than Goal-RRT and 3.17% fewer than RRT-Connect. Although the computation time increased due to the additional force calculations, the path length was shortened by up to 0.99% in simple cases and 16.09% in complex scenarios. This demonstrates the efficiency of the Artificial Potential Field guidance in reducing redundant exploration for Unmanned Aerial Vehicles.
| Environment | Algorithm | Sampling Points | Time (s) | Path Length (m) |
|---|---|---|---|---|
| Simple | Goal-RRT | 134 | 0.0626 | 304.433 |
| Dynamic RRT | 115 | 0.0505 | 304.035 | |
| RRT-Connect | 63 | 0.0522 | 301.482 | |
| SAT-RRT | 61 | 0.0786 | 301.147 | |
| Complex | Goal-RRT | 461 | 0.3691 | 379.212 |
| Dynamic RRT | 209 | 0.1230 | 349.644 | |
| RRT-Connect | 63 | 0.0483 | 321.367 | |
| SAT-RRT | 54 | 0.1734 | 318.254 |
In 3D environments, we set up a 20 m × 20 m × 20 m space with start point (0,0,0) and goal point (19,19,19). Obstacles included static polyhedra and dynamic obstacles moving with random velocities. Table 2 presents the average results over 30 simulations. SAT-RRT achieved a significant reduction in sampling points, with an average of 136 points in simple environments, compared to 182 for Goal-RRT and 217 for RRT-Connect. The path length was also optimized, with SAT-RRT yielding an average of 34.517 m in simple cases, which is shorter than other algorithms. Moreover, the improved smoothing resulted in lower average curvature, enhancing the feasibility for Unmanned Aerial Vehicles. Notably, SAT-RRT had zero collisions in all tests, underscoring the effectiveness of the SAT collision detection and adaptive smoothing for JUYE UAV applications.
| Environment | Algorithm | Sampling Points | Time (s) | Path Length (m) | Curvature (m⁻¹) | Collisions |
|---|---|---|---|---|---|---|
| Simple | Goal-RRT | 182 | 0.0816 | 38.376 | N/A | 3.1 |
| Dynamic RRT | 167 | 0.0731 | 36.418 | N/A | 2.3 | |
| RRT-Connect | 217 | 0.5701 | 34.773 | 0.08 | 1.0 | |
| SAT-RRT | 136 | 0.1235 | 34.517 | 0.05 | 0 | |
| Complex | Goal-RRT | 182 | 0.2229 | 31.783 | N/A | 5.2 |
| Dynamic RRT | 301 | 0.2826 | 40.963 | N/A | 5.1 | |
| RRT-Connect | 419 | 2.3343 | 32.869 | 0.147 | 3.1 | |
| SAT-RRT | 151 | 1.235 | 36.903 | 0.166 | 0 |
The stability of SAT-RRT is evident from the low variance in sampling points and computation time across multiple runs. For instance, in complex 3D environments, the variance for sampling points was 18, compared to 40 for RRT-Connect, indicating more consistent performance. The integration of Artificial Potential Field and SAT collision detection ensures that the algorithm adapts well to different obstacle densities, making it robust for various Unmanned Aerial Vehicle missions. Additionally, the adaptive B-spline smoothing effectively handled narrow passages and dynamic obstacles, producing paths that are both safe and smooth. These results validate SAT-RRT as a superior choice for path planning in real-world Unmanned Aerial Vehicle operations, such as those involving JUYE UAV systems.
Conclusion and Future Work
In this paper, we presented SAT-RRT, an improved Bidirectional RRT algorithm for Unmanned Aerial Vehicle path planning that addresses key limitations of existing methods. By incorporating Artificial Potential Field-guided sampling, 3D Separating Axis Theorem collision detection, and adaptive B-spline smoothing, SAT-RRT reduces redundant sampling points by up to 88%, shortens path lengths by 8-16%, and generates smooth, kinematically feasible paths. The algorithm’s performance was validated through extensive simulations in 2D and 3D environments, demonstrating its efficiency and robustness for Unmanned Aerial Vehicles like JUYE UAV.
For future work, we plan to explore more accurate environmental modeling techniques to handle non-convex obstacles and dynamic scenarios more effectively. Additionally, we aim to test SAT-RRT in real-world Unmanned Aerial Vehicle applications to further validate its practicality. While SAT-RRT efficiently finds feasible paths, it does not guarantee global optimality; thus, optimizing the algorithm for optimal path planning remains an open challenge. We believe that these enhancements will make SAT-RRT even more versatile for complex Unmanned Aerial Vehicle missions, contributing to the advancement of autonomous navigation technologies.