Path Planning of UAV in Cities Based on Improved RRT Algorithm

Yifan FengAdvances 2025 · DOI · OpenAlex

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.

The pruning strategy removes redundant nodes to straighten the path while avoiding obstacles.

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).
Final optimized path generated by the RRT-FieldPrune algorithm in a simulated urban environment.

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

Abstract

With the development of UAV technology and low-altitude economy, path planning is an important link for UAVs to perform tasks in urban mission space.In urban environments, UAVs face many challenges, such as complex building layouts, large amounts of green belts and so on.RRT (rapidly exploring random tree) algorithm serves as a stochastic search method that employs randomly generated samples to expand its tree structure incrementally, enabling efficient exploration of task spaces.Aiming at the shortcomings of traditional RRT algorithm, such as long exploration time and poor quality of path, some improved algorithms and strategies for RRT algorithm in the past were summarized, and a new improved RRT algorithm named RRT-FieldPrune combining artificial potential field guided exploration and pruning strategy was proposed.After performing multiple simulation and using the mean value as the final result, the results are then contrasted against the traditional RRT algorithm, The algorithm named RRT-FieldPrune proposed in this paper saves 73.0% in path search time, reduces the path by 20.86%, and 91.30% of the bending times are eliminated, significantly improving the path quality and reflecting better performance.
BibTeX
@inproceedings{feng2025path,
  author = {Yifan Feng},
  title = {{Path Planning of UAV in Cities Based on Improved RRT Algorithm}},
  booktitle = {Advances},
  year = {2025},
  doi = {10.2991/978-94-6463-821-9\_84},
}
Figure