Generalized Path Planning for UTM Systems With a Space-Time Graph

Abstract

Motivated by the increased use of UAS in commercial applications, in this paper we tackle the problem of path planning when requests are submitted by UAS managed by different operators. We propose the new problem of generalized path planning for UAS Traffic Management, where the UAS path is described by operators with a sequence of waypoint groups and a solution trajectory must pass through a waypoint in each group. This problem is typical for applications where multiple charging stations and pickup/drop-off locations are distributed in a flight area. Our solution builds upon prior work on discretized space-time graph path planning and proposes a novel multi-source/multi-destination graph search algorithm that generates collision-free trajectories for pre-flight CDR. Our efficient algorithm has runtime proportional to the number of groups and avoids combinatorial explosion. We apply our mechanism to the energy-constrained UAS package delivery problem with multiple warehouses and battery charging stations. Simulation results show that our algorithm is efficient and scalable with the number of requests and graph size. The addition of charging stations and the option for multiple warehouses increases the request admission ratio and reduces the overall trajectory duration, effectively improving both the planner’s quality of service and the efficiency of airspace usage.

Keywords

• UAS path planning
• UTM system
• space-time graph
• pre-flight CDR