Pre-flight fast hotspot-free and conflict-free trajectory planning for on-demand UAV delivery logistics

With the rapid growth of the drone industry, urban drone logistics is emerging as a highly promising opportunity, accompanied by critical challenges. One of the key challenges is the lack of fast and efficient pre-flight trajectory planning techniques that simultaneously satisfy demand and capacity balancing constraints (operational efficiency) and conflict-free constraints (operational safety) in large-scale, high-density scenarios. This limitation hinders the ability to provide effective services to users with dynamic flight demands, such as food delivery and emergency supply transport. This paper proposes a fast pre-flight hotspot-free and conflict-free trajectory planning method that considers uncertainty to bridge this gap. This method integrates hotspot-free trajectory planning (emphasised in this paper) and conflict-free trajectory planning (applying the reachable spatio-temporal area method from our previous research). To efficiently plan UAV trajectories, a novel low-altitude airspace model based on grids is proposed, and the properties of this airspace model are derived and formalised. A demand count model based on flight uncertainty is established to represent the likelihood of UAVs occupying airspace units mathematically. A probability-based demand and capacity balancing model is introduced, and its iterative formulation is derived for rapid computation. A hotspot-free trajectory planning method based on weighted directed graphs is proposed, taking into account energy consumption costs and airspace usage fees. Results from large-scale simulation experiments demonstrate the efficiency of the proposed method in achieving hotspot-free and conflict-free trajectory planning, with computing times per UAV reaching milliseconds, meeting the requirement for rapid computation. Additionally, preliminary exploration is conducted on the impact of airspace usage prices on airspace operations.