Dynamic Path Planning for Unmanned Aerial Vehicles under Deadline and Sector Capacity Constraints


The US NationalAirspace System is currentlyoperating at a level close to its maximum potential. The limitation comes from the workload demand on the air traffic controllers. Currently, the air traffic flow management is based on the flight path requests by the airline operators, whereas the minimum separation assurance between flights is handled strategically by air traffic control personnel. In this paper, we propose a scalable framework that allows path planning for a large number of unmanned aerial vehicles (UAVs) taking into account the deadline and weather constraints. Our proposed solution has a polynomial-time computational complexity that is also verified by measuringthe runtime for typical workloads. We further demonstrate that the proposed framework is able to route 80% of the workloads while not exceeding the sector capacity constraints, even under dynamic weather conditions. Due to low computational complexity, our framework is suitable for a fleet of UAVs where decentralizing the routing process limits the workload demand on the airtraffic personnel.


Computer Science


This work was supported by the National Science Foundation, Grant CCF-1725755.

Keywords and Phrases

Air Traffic; Conflict Avoidance; Routing; Simulation; Unmanned Aircraft

International Standard Serial Number (ISSN)


Document Type

Article - Journal

Document Version


File Type





© 2022 Institute of Electrical and Electronics Engineers, All rights reserved.

Publication Date

01 Aug 2022