Four Dimensional Auto-routing for Autonomous Flight Planning with Airspace Deconfliction
Tuesday, October 06, 2020: 1:50 PM - 2:35 PM
Autorouting is a decades-old well-known technique for finding paths through obstructed environments such as printed circuit boards or GPS routes. Most autorouters to date have been, for all practical purposes, two-dimensional. In the low altitude 3D airspace of urban environments, the complexity of the airspace obstructions is much higher. While the rural airspace for farming, inspection, and other environments allow for rather simplistic flight plans assuming empty skies, urban environments are not only complex but likely to be crowded and highly utilized by a variety of different vehicles from helicopters to logistics UAVs to human transport. Each will have its own specific capabilities and requirements for its flight plan.
The motivation for this research came from David Vos' AUVSI 2016 comment where he noted that the biggest limitation to cooperative airspace control is “humans have to be involved. If it’s fully automated, it can happen at the speed of processing.” They didn't know how to do that. In order to meet these goals, the flight planning system needs to be automated, programmatically deconflict all vehicles' paths in a correct-by-construction manner, provide for both overall cooperative control and immediate sense-and-avoid maneuvers without disrupting the airspace, include heuristics that tailor the flight path to a given vehicle and application, apply Risk Calculus, regulatory requirements, and it has to know exactly where every vehicle will be at any moment of time.
The system developed by this research is the first Four-Dimensional autorouter ever devised and implements all of the requirements above. Each flight path mathematically defines the flight plan as some number of axes of movement, but always with respect to time. This can be mathematically expressed as:
X = f(T);
Y = f(T);
Z = f(T);
Which provides true four-dimensional control of the flight path. Where simple waypoints can be used to initially define the path, these are then converted to splines, a mathematical description of the path which can be used to find any point in space at a given time, or the time of any given point in space with any level of precision required. The routing itself generally stays pretty simple as compared to a printed circuit board because the 3D nature of the airspace not only allows much more freedom for each path but the fourth dimension provides even more. If two vehicles do desire to pass the same point in the airspace at the same time to meet the most efficient flight requirements, the system can simply modify the velocity of the vehicle slightly such that there is no conflict at the time it passes that point -- the other vehicle arrives ahead of or behind.
In use, the FAA LAANC program currently allows third parties to automatically get the certification of proposed flight plans. This system would allow third parties to provide both the flight plan and the certification through the same system. LAANC could query the system with a proposed flight plan as an additional metric for possible conflicts with all other known aircraft, and input any flight plans into the autorouter so that subsequent flight plans are automatically deconflicted against these as well. Logistics fleet systems would provide the system with start and end coordinates and a window for start time, and the system would provide complete deconflicted flight plans, take-off time, and clearance via LAANC.
The autorouter is implemented and functioning. The research paper provides an introduction to the basic autorouting algorithms and how these are extended to four dimensions. Control diagrams and actual generated flight plans of hundreds of vehicles simultaneously transiting a small area of downtown San Francisco are provided. The analysis then includes error estimates, calculated closest approach and how paths change given different vehicle and risk parameters.
Analyst,Engineering/Technical,Research & Development,Student