A Voronoi–A* Fusion Algorithm with Adaptive Layering for Efficient UAV Path Planning in Complex Terrain

Abstract

This paper proposes a Voronoi–A* fusion algorithm for UAV path planning in complex terrain. A DEM layering method based on obstacle density is introduced to decompose complex 3D terrain into multiple horizontal flight planes, significantly reducing computational complexity while maintaining 3D flexibility. Within each plane, a greedy Voronoi algorithm constructs a sparse vertex network as path nodes. A weighting function incorporates start/goal proximity, heading consistency, and altitude safety. The algorithm employs greedy heuristics to prioritize high-weight vertices, enabling the rapid generation of safe paths.

What are the main findings?

A DEM layering method based on obstacle density.

A greedy Voronoi algorithm applied within each flight plane.

What is the implication of the main finding?

Computational complexity is minimized, and efficiency is enhanced.

Generated paths closely approximate the optimal path.

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.