UAS Path Planning with Dynamic Rerouting using a Space-Time Graph

The rapid growth of urban mobility and logistics demands innovative solutions to address congestion, inefficiencies, and sustainability challenges. Unmanned Aerial Systems (UAS) offer a promising alternative for urban transportation, particularly in last-mile deliveries and emergency response. To accommodate the anticipated scale of UAS operations, potentially involving millions of daily flights, the UAS Traffic Management (UTM) ecosystem must support safe, efficient, and fair airspace access while minimizing disruption. UAS operations in dense urban areas must be supported by efficient and scalable path planning and deconflicting mechanisms which compute collision-free trajectories. A dynamic rerouting mechanism allows UAS trajectories to dynamically adapt to real-time deviations caused by environmental factors, communication errors, or dynamic airspace constraints. In this paper, we introduce a UAS Path Planning with Dynamic Rerouting framework that leverages a space-time graph model to ensure safe and efficient variable speed UAS navigation in urban environments. Our approach provides collision-free trajectories by construction and enables real-time path adjustments by dynamically rerouting UAS in case of slowdown events. By incorporating real-time request management and collision-free trajectories, our model enhances the feasibility of integrating UAS into multimodal urban transportation networks. We analyze the computational efficiency of our approach and demonstrate its scalability through simulation experiments using a real-world urban map in very dense scenarios with up to 14000 UAS vehicles. Our results indicate that dynamic rerouting with collision-free trajectory computation improves UAS route availability while maintaining airspace safety and operational efficiency.