Dual-Scale Grid-Based Adaptive Trajectory Planning for UAVs in Urban Low-Altitude Airspace

With the rapid growth of the low-altitude economy, the number of unmanned aerial vehicles (UAVs) has grown rapidly. It is challenging to plan substantial UAV trajectories in complex urban low-altitude airspace, considering the airspace capacity, inter-vehicle safety, and communication reliability. To deal with this challenge, we propose a dual-scale grid-based trajectory planning approach that separates the global routing and local refinement. Specifically, we discretize the three-dimensional airspace into coarse macro-grids for capacity-constrained routing and high-quality communication-aided fine micro-grids for collision-free trajectory refinement. Both consider an altitude-dependent energy model. To handle the complex dual-scale grid trajectory planning of UAVs, we propose a priority-driven dual-grid Theta* with adaptive relaxation (DGTAR) to balance the global planning efficiency and local obstacle avoidance accuracy. First, we design a priority-driven capacity allocation mechanism to enforce safe separation among UAVs. Then, a combined planner is proposed, which integrates a Theta*-enhanced global search with a sampling-based refinement algorithm, invoking on-demand boundary relaxation to ensure the feasibility. Simulation results reveal that the proposed method DGTAR achieves reductions in many aspects compared with benchmark mechanisms, while maintaining a high planning success rate in congested scenarios.