Campus Units

Electrical and Computer Engineering

Document Type


Publication Version

Submitted Manuscript

Publication Date


Journal or Book Title



Pre-departure flight plan scheduling for Urban Air Mobility (UAM) and cargo delivery drones will require on-demand scheduling of large numbers of aircraft. We examine the scalability of an algorithm known as FastMDP which was shown to perform well in deconflicting many dozens of aircraft in a dense airspace environment with terrain. We show that the algorithm can adapted to perform first-come-first-served pre-departure flight plan scheduling where conflict free flight plans are generated on demand. We demonstrate a parallelized implementation of the algorithm on a Graphics Processor Unit (GPU) which we term FastMDP-GPU and show the level of performance and scaling that can be achieved. Our results show that on commodity GPU hardware we can perform flight plan scheduling against 2000-3000 known flight plans and with server-class hardware the performance can be higher. We believe the results show promise for implementing a large scale UAM scheduler capable of performing on-demand flight scheduling that would be suitable for both a centralized or distributed flight planning system.


This is a pre-print of the article Bertram, Joshua R., Peng Wei, and Joseph Zambreno. "Scalable FastMDP for Pre-departure Airspace Reservation and Strategic De-conflict." arXiv preprint arXiv:2008.03518 (2020). Posted with permission.

Copyright Owner

The Author(s)



File Format


Published Version