Scalable FastMDP for Pre-departure Airspace Reservation and Strategic
  De-conflict
  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
