Abstract
With the development of UAV technology and the low-altitude economy, path planning has become a critical component for UAVs performing tasks in urban mission spaces. In these environments, UAVs face challenges such as complex building layouts and restricted zones. The Rapidly-exploring Random Tree (RRT) algorithm is a common stochastic search method used for these tasks, but traditional RRT often suffers from long exploration times and poor path quality. This paper proposes a new improved algorithm, RRT-FieldPrune, which combines artificial potential field (APF) guided exploration with a pruning strategy. Simulation results demonstrate that RRT-FieldPrune saves 73.0% in path search time, reduces path length by 20.86%, and eliminates 91.30% of unnecessary turns, significantly improving path quality and operational performance.
Introduction
As urban drone operations become more frequent, the need for efficient navigation through dense cityscapes is paramount. The standard RRT algorithm is valued for its ability to find paths in complex spaces, yet it is fundamentally flawed by its reliance on pure randomness. This leads to inefficient "blind" exploration and jagged trajectories that are difficult for physical drones to follow, resulting in wasted energy and increased flight risk. The RRT-FieldPrune algorithm aims to solve these issues by making the search process more intentional and the final path more refined.
Methodology: The RRT-FieldPrune Algorithm
The RRT-FieldPrune algorithm enhances the standard RRT framework through two primary interventions:
Artificial Potential Field (APF) Guidance
Instead of sampling points purely at random, the algorithm incorporates a "gravitational" model. The destination point acts as an attractor, increasing the probability that the tree structure will grow toward the goal. This heuristic approach reduces the time spent exploring dead ends and speeds up the initial discovery of a valid path.
Pruning Strategy Optimization
Once a path is found, it is typically composed of many jagged, random segments. The pruning step applies the triangle inequality principle—the shortest distance between two points is a straight line. The algorithm evaluates groups of nodes; if a direct connection can be made between non-adjacent nodes without intersecting an obstacle, the intermediate nodes are removed.
This process repeats iteratively until the path length stabilizes (changing by less than 0.1%), ensuring a smooth trajectory suitable for flight.
Simulation and Results
The algorithm was tested in a 2D simulation environment representing a 700m x 700m urban block. To ensure statistical significance, 50 simulation runs were performed for both the traditional RRT and the new RRT-FieldPrune algorithm.
Performance Metrics
- Search Time: Dropped from 10.33 seconds to 2.79 seconds (a 73% improvement).
- Path Length: Reduced from 1365.37m to 1080.61m (a 20.86% reduction).
- Bending Times: Slashed from 46 turns to just 4 (a 91.3% reduction in trajectory complexity).
Qualitatively, the visual results show a transition from a chaotic, spiderweb-like path in traditional RRT to a clean, purposeful line that navigates efficiently between buildings.
Conclusion
The RRT-FieldPrune algorithm significantly enhances urban UAV path planning by combining directed randomness with iterative refinement. By reducing search time and path complexity, the algorithm directly addresses the energy and efficiency constraints of modern drones. Future research will focus on extending this logic to 3D environments and accounting for dynamic obstacles like other aircraft or changing weather conditions.
Summary updated