PATH PLANNING ALGORITHMS FOR UNMANNED AIRCRAFT SYSTEMS WITH A SPACE-TIME GRAPH

Unmanned Aircraft Systems (UAS) have grown in popularity due to their widespread potential applications, including efficient package delivery, monitoring, surveillance, search and rescue operations, agricultural uses, along with many others. As UAS become more integrated into our society and airspace, it is anticipated that the development and maintenance of a path planning collision-free system will become imperative, as the safety and efficiency of the airspace represents a priority. The dissertation defines this problem as the UAS Collision-free Path Planning Problem.
The overall objective of the dissertation is to design an on-demand, efficient and scalable aerial highway path planning system for UAS. The dissertation explores two solutions to this problem. The first solution proposes a space-time algorithm that searches for shortest paths in a space-time graph. The solution maps the aerial traffic map to a space-time graph that is discretized on the inter-vehicle safety distance. This helps compute safe trajectories by design. The mechanism uses space-time edge pruning to maintain the dynamic availability of edges as vehicles move on a trajectory. Pruning edges is critical to protect active UAS from collisions and safety hazards. The dissertation compares the solution with another related work to evaluate improvements in delay, run time scalability, and admission success while observing up to 9000 flight requests in the network. The second solution to the path planning problem uses a batch planning algorithm. This is a new mechanism that processes a batch of flight requests with prioritization on the current slack time. This approach aims to improve the planning success ratio. The batch planning algorithm is compared with the space-time algorithm to ascertain improvements in admission ratio, delay ratio, and running time, in scenarios with up to 10000 flight requests.