In recent years, Unmanned Aerial Vehicles (UAVs) have rapidly integrated into daily life, transforming the world in unprecedented ways. From military to agriculture, logistics, mapping, and rescue operations, their technology and applications are experiencing rapid growth. Among these, path planning for Unmanned Aerial Vehicles is a critical component for executing flight missions. Efficient and reliable path planning algorithms are essential for the successful operation of UAVs. Commonly used path planning algorithms can be categorized into three types: graph-based search methods such as A* and D* algorithms, intelligent algorithms like ant colony and particle swarm optimization, and sampling-based algorithms such as Probabilistic Roadmap Method (PRM) and Rapidly-exploring Random Tree (RRT). Sampling-based algorithms do not require pre-processing of the space, making them more suitable for three-dimensional path planning. The RRT algorithm is known for its simplicity and reliability, but it is only probabilistically complete and suffers from issues like suboptimal path quality and low convergence efficiency. To address these limitations, Karaman et al. proposed the RRT* algorithm, which incorporates parent node reselection and rewiring steps to optimize the tree structure iteratively, thereby improving path quality. Gammell et al. further advanced this with the Informed-RRT* algorithm, which confines sampling to an elliptical region after an initial feasible path is found. However, challenges remain, including long initial feasible paths and low optimization efficiency. This paper proposes an improved Informed-RRT* algorithm for three-dimensional path planning of Unmanned Aerial Vehicles, specifically designed to enhance performance in complex environments.
The improved algorithm introduces several key innovations. First, a dynamic artificial potential field guided by fuzzy inference is used to direct tree growth, reducing the length of the initial path and avoiding ineffective iterations near obstacles. Second, the sampling area is restricted to a layered ellipsoid, with sampling probabilities adjusted based on obstacle density to improve convergence efficiency. Third, the neighboring region radius is optimized using a feedforward neural network combined with a genetic algorithm to reduce computation time. These enhancements are validated through simulations in both sparse and dense obstacle environments, demonstrating the algorithm’s practicality for Unmanned Aerial Vehicle applications. The JUYE UAV, as a representative platform, benefits from these advancements in navigating complex three-dimensional spaces.
Path planning for Unmanned Aerial Vehicles must account for various constraints, such as maximum heading and pitch angles, to ensure feasible and safe trajectories. The maximum heading angle constraint ensures that the angle between consecutive path segments in the horizontal plane does not exceed a specified limit, while the maximum pitch angle constraint limits the vertical ascent or descent. These constraints are critical for real-world UAV operations, and the proposed algorithm incorporates them to generate practical paths. The performance of the improved algorithm is compared against standard RRT*, Informed-RRT*, and A* algorithms, highlighting its superiority in terms of path quality and computational efficiency. This work contributes to the ongoing development of robust path planning solutions for Unmanned Aerial Vehicles, with potential applications in sectors like logistics and surveillance using platforms like the JUYE UAV.
The remainder of this paper is organized as follows. Section 2 reviews related work on path planning algorithms. Section 3 details the methodology of the improved Informed-RRT* algorithm. Section 4 presents simulation results and analysis. Finally, Section 5 concludes the paper and discusses future work.
Related Work
Path planning for Unmanned Aerial Vehicles has been extensively studied, with various algorithms proposed to address the challenges of three-dimensional environments. Sampling-based algorithms, such as RRT and its variants, are particularly popular due to their ability to handle high-dimensional spaces without discretization. The basic RRT algorithm builds a tree by randomly sampling points in the configuration space and connecting them to the nearest node in the tree. While probabilistically complete, RRT often produces suboptimal paths. RRT* addresses this by introducing asymptotic optimality through rewiring, which minimizes the cost of paths by considering nearby nodes. The cost function for a path is typically defined as the cumulative distance between nodes, and for a path consisting of nodes \( x_0, x_1, \ldots, x_n \), the cost \( c \) is given by:
$$ c = \sum_{i=0}^{n-1} \| x_{i+1} – x_i \| $$
Informed-RRT* improves upon RRT* by restricting sampling to an ellipsoidal region once an initial path is found. The ellipsoid is defined with foci at the start and goal points, and the major axis length is set to the current best path length \( c_{\text{best}} \). This focuses the sampling on regions that could contain better paths, enhancing convergence. The sampling process in Informed-RRT* can be described algorithmically as shown in Algorithm 1. However, Informed-RRT* may still suffer from slow convergence in cluttered environments due to random sampling. Various modifications have been proposed, such as incorporating heuristic information or adjusting sampling strategies based on environmental features. For instance, some approaches use artificial potential fields to guide sampling towards the goal while avoiding obstacles, but these can lead to local minima. Others optimize parameters like the neighboring region radius to balance computation time and path quality. Despite these advances, there is a need for more efficient algorithms that can handle the dynamic constraints of Unmanned Aerial Vehicles like the JUYE UAV in real-time.
Methodology
The improved Informed-RRT* algorithm proposed in this paper integrates three main components: a dynamic artificial potential field for guided tree growth, a layered ellipsoid sampling strategy, and an optimized neighboring region radius using neural networks and genetic algorithms. Each component is designed to address specific limitations of existing methods, resulting in a robust path planner for Unmanned Aerial Vehicles.
Dynamic Artificial Potential Field Guidance
To reduce the length of the initial feasible path and avoid ineffective iterations near obstacles, a dynamic artificial potential field is introduced. The potential field generates an attractive force towards the goal, guiding the expansion of the tree. The new node \( x_{\text{new}} \) is computed as:
$$ x_{\text{new}} = x_{\text{nearest}} + \eta \left( \frac{x_{\text{goal}} – x_{\text{nearest}}}{\| x_{\text{goal}} – x_{\text{nearest}} \|} + \frac{x_{\text{rand}} – x_{\text{nearest}}}{\| x_{\text{rand}} – x_{\text{nearest}} \|} \right) $$
where \( \eta \) is an attraction coefficient that regulates the influence of the goal direction. A fixed \( \eta \) can cause issues in obstacle-dense areas, so a fuzzy inference system dynamically adjusts \( \eta \) based on the number of random points generated per iteration, denoted as \( n_{\text{rand}} \). This number reflects obstacle density; a high \( n_{\text{rand}} \) indicates significant obstacle interference, suggesting a smaller \( \eta \) to enhance exploration, while a low \( n_{\text{rand}} \) allows for a larger \( \eta \) to strengthen goal attraction. The fuzzy system uses Gaussian membership functions with input \( n_{\text{rand}} \in [0, 10] \) and output \( \eta \in [0, 10] \). The fuzzy sets are defined as Positive Small (PS), Positive Medium (PM), and Positive Large (PB). The rules are:
- If \( n_{\text{rand}} \) is PS, then \( \eta \) is PB.
- If \( n_{\text{rand}} \) is PB, then \( \eta \) is PS.
This approach ensures adaptive behavior in various environments, improving the efficiency of path planning for Unmanned Aerial Vehicles.
Layered Ellipsoid Sampling
After finding an initial path, Informed-RRT* limits sampling to an ellipsoid defined by the start \( x_{\text{start}} \), goal \( x_{\text{goal}} \), and current best path length \( c_{\text{best}} \). The improved algorithm divides this ellipsoid into two layers: an inner ellipsoid and an outer ellipsoid, with the region between them termed the inter-ellipsoid layer. The outer ellipsoid \( X^1_{\text{ellipse}} \) has a major axis length of \( c_{\text{best}} \), and the inner ellipsoid \( X^2_{\text{ellipse}} \) is a scaled-down version with major axis length proportional to the Euclidean distance between start and goal, \( c_{\min} = \| x_{\text{goal}} – x_{\text{start}} \| \). The scaling factor is:
$$ \frac{a_2}{a_1} = \frac{b_2}{b_1} = \frac{c_2}{c_1} = \frac{c_{\min}}{c_{\text{best}}} $$
where \( a, b, c \) are the semi-axes of the ellipsoids. The sampling probability is adjusted based on obstacle density, quantified by the ratio \( a = c_{\text{best}} / c_{\min} \). For sparse environments (\( a < 1.2 \)), higher sampling probability is assigned to the inner ellipsoid to exploit shorter paths. For dense environments (\( a > 1.5 \)), higher probability is given to the outer ellipsoid to facilitate detours. This stratified sampling enhances convergence by focusing on relevant regions, crucial for applications like the JUYE UAV operating in variable terrains.
Optimized Neighboring Region Radius
The neighboring region radius \( R \) in RRT* affects both convergence speed and path optimality. A large \( R \) increases computation time, while a small \( R \) may limit optimization. The standard approach sets \( R \) as:
$$ R = \min \left\{ \gamma_{\text{RRT*}} \left( \frac{\ln V}{V} \right)^{1/d}, \eta \right\} $$
where \( \gamma_{\text{RRT*}} \) is an expansion coefficient, \( V \) is the number of tree nodes, \( d \) is the space dimension, and \( \eta \) is a fixed upper bound. To optimize this, a feedforward neural network is first trained to model the relationship between \( V \) and \( R \). The network has two hidden layers with Sigmoid activation functions. The forward propagation is expressed as:
$$ \begin{bmatrix} z_{11} \\ z_{12} \end{bmatrix} = \begin{bmatrix} w^{(1)}_{11} \\ w^{(1)}_{12} \end{bmatrix} x_1 + \begin{bmatrix} b^{(1)}_{11} \\ b^{(1)}_{12} \end{bmatrix} $$
$$ \begin{bmatrix} z_{21} \\ z_{22} \end{bmatrix} = \begin{bmatrix} w^{(1)}_{21} & w^{(1)}_{22} \\ w^{(1)}_{23} & w^{(1)}_{24} \end{bmatrix} \begin{bmatrix} \sigma(z_{11}) \\ \sigma(z_{12}) \end{bmatrix} + \begin{bmatrix} b^{(1)}_{21} \\ b^{(1)}_{22} \end{bmatrix} $$
$$ y = w^{(2)}_1 \sigma(z_{21}) + w^{(2)}_2 \sigma(z_{22}) + b^{(2)} $$
where \( \sigma(\cdot) \) is the Sigmoid function. The network is trained using the Levenberg-Marquardt algorithm with mean squared error loss. Then, a genetic algorithm optimizes the neural network parameters (weights and biases) to minimize a fitness function combining path length and computation time:
$$ f(\cdot) = w_1 \cdot l + w_2 \cdot t $$
with weights \( w_1 = 0.3 \) and \( w_2 = 0.7 \). The genetic algorithm uses binary encoding and roulette wheel selection, evolving 20 individuals over 20 generations. This hybrid approach yields an optimized \( R \) that reduces runtime while maintaining path quality for Unmanned Aerial Vehicle path planning.
UAV Path Constraints
For practical Unmanned Aerial Vehicle operations, path constraints must be enforced. The maximum heading angle constraint ensures that the angle between consecutive path segments in the horizontal plane does not exceed \( \psi_{\max} \). For path segments \( p_i \) and \( p_{i+1} \), the constraint is:
$$ \arccos \left( \frac{p_i \cdot p_{i+1}}{\| p_i \| \| p_{i+1} \|} \right) \leq \psi_{\max} $$
The maximum pitch angle constraint limits the vertical angle to \( \theta_{\max} \). For coordinates \( (x_i, y_i, z_i) \) and \( (x_{i+1}, y_{i+1}, z_{i+1}) \), the constraint is:
$$ \frac{| z_{i+1} – z_i |}{\sqrt{(x_{i+1} – x_i)^2 + (y_{i+1} – y_i)^2}} \leq \tan \theta_{\max} $$
These constraints are integrated into the path planning process to ensure feasible trajectories for UAVs like the JUYE UAV.
Simulation and Results
To validate the improved algorithm, simulations are conducted in three-dimensional environments with varying obstacle densities. The algorithm is compared against RRT*, Informed-RRT*, and A* algorithms. The map size is set to \( 1470 \times 1470 \times 900 \) units, with start at \( (80, 80, 0) \) and goal at \( (760, 760, 720) \). The step size is 100 units, and the maximum iteration count is 6000. Path constraints are \( \psi_{\max} = 45^\circ \) and \( \theta_{\max} = 40^\circ \). For A* algorithm, two grid resolutions are tested: low (\( 10 \times 10 \times 15 \)) and high (\( 30 \times 30 \times 15 \)), with Euclidean distance as the heuristic.
Sparse Obstacle Environment
In sparse obstacle environments, the improved algorithm demonstrates faster initial path finding and shorter final paths compared to RRT* and Informed-RRT*. The use of dynamic artificial potential field reduces ineffective iterations, while layered sampling improves optimization efficiency. Table 1 summarizes the average results over 50 simulations.
| Algorithm | Initial Length (m) | Iterations to Initial | Initial Time (s) | Final Length (m) | Final Time (s) |
|---|---|---|---|---|---|
| RRT* | 1930 | 622 | 0.341 | 1640 | 5.402 |
| Informed-RRT* | 1910 | 617 | 0.314 | 1510 | 6.211 |
| A* (Low Res) | — | — | — | 1707 | 4.938 |
| A* (High Res) | — | — | — | 1238 | 18.681 |
| Improved Algorithm | 1620 | 340 | 0.158 | 1220 | 5.585 |
The improved algorithm achieves a shorter initial path in fewer iterations, and the final path length is superior to other methods. The optimized neighboring radius reduces computation time, making it suitable for real-time Unmanned Aerial Vehicle applications. The effect of inner sampling probability on path length is analyzed, showing that higher inner probability improves path quality in sparse environments, as it increases the number of effective nodes.
Dense Obstacle Environment
In dense obstacle environments, the improved algorithm maintains performance by adapting sampling probabilities to favor the outer ellipsoid, facilitating obstacle avoidance. Table 2 presents the results for dense environments.
| Algorithm | Initial Length (m) | Iterations to Initial | Initial Time (s) | Final Length (m) | Final Time (s) |
|---|---|---|---|---|---|
| RRT* | 2310 | 866 | 0.474 | 1880 | 7.262 |
| Informed-RRT* | 2340 | 842 | 0.452 | 1720 | 7.835 |
| A* (Low Res) | — | — | — | 1832 | 6.038 |
| A* (High Res) | — | — | — | 1322 | 19.686 |
| Improved Algorithm | 1900 | 424 | 0.227 | 1310 | 7.392 |
The improved algorithm achieves a shorter initial path and faster convergence, with the final path length comparable to high-resolution A* but with significantly lower computation time. This highlights its efficiency for Unmanned Aerial Vehicles like the JUYE UAV in complex scenarios. Analysis of inner sampling probability shows that lower values (below 0.3) yield better paths in dense environments, as effective nodes are primarily in the outer region.
Varying Obstacle Densities
To further evaluate robustness, simulations are conducted with varying numbers of obstacles. The improved algorithm consistently outperforms RRT* and Informed-RRT* in both initial and final path lengths across different densities. The dynamic artificial potential field and layered sampling adapt to environmental changes, ensuring reliable performance for Unmanned Aerial Vehicle path planning.
Conclusion
This paper presents an improved Informed-RRT* algorithm for three-dimensional path planning of Unmanned Aerial Vehicles. The key contributions include a dynamic artificial potential field for guided tree growth, a layered ellipsoid sampling strategy, and an optimized neighboring region radius using neural networks and genetic algorithms. Simulations in sparse and dense obstacle environments demonstrate that the improved algorithm achieves shorter initial and final paths with reduced computation time compared to existing methods. The integration of path constraints ensures practical applicability for UAVs like the JUYE UAV. Future work will focus on extending the algorithm to dynamic environments and multi-UAV coordination, further enhancing its utility in real-world scenarios.