A Voronoi–A* Fusion Algorithm with Adaptive Layering for Efficient UAV Path Planning in Complex Terrain
Boyu Dong, Gong Zhang, Yan Jun Yang, Peiyuan Yuan, Sukui Lu · Drones · 2025
Unmanned Aerial Vehicles (UAVs) face significant challenges in global path planning within complex terrains, as traditional algorithms (e.g., A*, PSO, APF) struggle to balance computational efficiency, path optimality, and safety. This study proposes a Voronoi–A* fusion algorithm, combining Voronoi-vertex-based rapid trajectory generation with A* supplementary expansion for enhanced performance. First, an adaptive DEM layering strategy divides the terrain into horizontal planes based on obstacle density, reducing computational complexity while preserving 3D flexibility. The Voronoi vertices within each layer serve as a sparse waypoint network, with greedy heuristic prioritizing vertices that ensure safety margins, directional coherence, and goal proximity. For unresolved segments, A* performs localized searches to ensure complete connectivity. Finally, a line-segment interpolation search further optimizes the path to minimize both length and turning maneuvers. Simulations in mountainous environments demonstrate superior performance over traditional methods in terms of path planning success rates, path optimality, and computation. Our framework excels in real-time scenarios, such as disaster rescue and logistics, although it assumes static environments and trades slight path elongation for robustness. Future research should integrate dynamic obstacle avoidance and weather impact analysis to enhance adaptability in real-world conditions.