UAS Path Planning using a Space-Time Graph

UAS provides the platform of many applications such as efficient package delivery, monitoring and surveillance, search and rescue and more. As the number of UAS are expected to increase in the near future, it becomes critical to design an efficient collision-free UAS trajectory scheduling system. In this paper we propose an on-demand, scalable, collision-free trajectory scheduling mechanism using a space-time graph. To model the safety distance requirement, we first transform the input graph to an unit-graph. To avoid conflicts between in transit UAS's, edges are pruned in different time intervals. The performance of our algorithm is analyzed with simulations. We measure metrics such as algorithm running time, request admission ratio, and the delay overhead ratio compared to the optimal path. We simulated 9000 UAS requests arriving at a rate of 4.5/s with average run time of 0.152 seconds per request for a realistic scenario.