Distributed (Air) Traffic Control

This work aims to develop

  • (i) uNet: a new scalable Unmanned Aerial Vehicle (UAV) operation paradigm to enable a large number of relatively low-cost UAVs to fly beyond-line-of-sight and

  • (ii) provably-safe (conflict resolution) procedures for distributed air traffic control.

A Scalable Low-Cost-UAV Traffic Network (uNet)

Background: Low-cost beyond line of sight flight

Under current free-flight-like paradigm, wherein a Unmanned Aerial Vehicle (UAV) can travel along any route as long as it avoids restricted airspace and altitudes. However, this requires expensive on-board sensing and communication as well as substantial human effort in order to ensure avoidance of obstacles and collisions. The increased cost serves as an impediment to the emergence and development of broader UAV applications.


 
photo
Schematic routing of the kth UAV U(k) through the uNet from the initial location Li(k) in the initial sector-level uNet Sk(1) to the final location Lf(k) in the final sector-level uNet Sk(ns,k). For a given expected time of arrival ETA(k) into the uNet, the router negotiates between multiple sNets to determine the scheduled time of arrival STA(k) and a conflict-free flight route R(k) that spans multiple sNets Sk(i) for i=1 to i=ns,k. While in a current sNet Sk(i) at time t, the UAV U(k) receives GPS information and communicates its position P[U(k)](t) to the sNet Sk(i).
 

The main contribution of this work (Ref 6) is to propose the use of pre-established route network for UAV traffic management, which allows: (i) pre- mapping of obstacles along the route network to reduce the onboard sensing requirements and the associated costs for avoiding such obstacles; and (ii) use of well-developed routing algorithms to select UAV schedules that avoid conflicts. Available GPS-based navigation can be used to fly the UAV along the selected route and time schedule with relatively low added cost, which therefore, reduces the barrier to entry into new UAV-applications market.

Air Traffic Control

Background: It is challenging to prove safety

A challenge in the design of conflict resolution procedures (CRP) used in Air Traffic Control (ATC) is to guarantee the overall safety and efficiency of a route network with multiple intersections — where each CRP acts locally, in space and in time.

CRPs tend to be decoupled (spatially-and-temporally) because of a substantial increase in computational and modeling complexity with a single global CRP (due to increased number of aircraft and conflicts) when compared to decoupled CRPs. Additionally, a global CRP over a large airspace is inefficient (with lower overall capacity) because of the need to handle the larger uncertainty. The uncertainty tends to be larger, e.g., because of ground-speed sensitivity to wind and temperature that depend, in turn, on forecasts of dynamic weather conditions with substantial uncertainties over time. Therefore, decoupled CRPs are needed to manage the complexity and uncertainty in air traffic control (ATC).

It is challenging to guarantee overall stability in a route network with multiple conflicts (especially if the CRP solves each one locally). In particular, a challenge is to ensure that modifications of flight trajectories, for resolving a local conflict, do not lead to a domino effect; i.e., resolution of a conflict should not lead to new conflicts. Moreover, for guaranteeing safety, the procedure should always lead to a solution of the conflict resolution problem. Developing such provably-safe, decoupled CRPs remains a challenging problem in ATC.

Issue 1: Necessary and Sufficient Conditions for Decoupled, Provably-Safe Conflict Resolution

Our work (Ref 1) identifies necessary and sufficient conditions for provably-safe decoupled CRP. Additionally, this work demonstrates the existence of decentralized en-route CRPs that satisfy the decoupling conditions for each local conflict and, thereby, guarantee global conflict resolution. An advantage of the proposed CRPs is that they do not require a reduction in the aircraft flow levels in the intersecting routes for conflict resolution, which can aid in increasing the efficiency of en-route ATC.

The Always-On De-Centralized CRP
The key concept is to split the main routes into multiple paths for generating larger spacing between aircraft -- thereby, enabling sufficient space between aircraft on intersecting routes for conflict free intersections. These paths are then merged back into original route to avoid additional conflicts in the region beyond the local space needed for the CRP. The CRP is illustrated in the following video.
 


 
Note that the circles represent a 5 Nautical Mile (NM) diameter disc centered around the aircraft.

The goal is to ensure that these disc do not overlap, i.e., a minimal separation distance of 5NM is maintained at all times.

The aircraft, at the center of each circle, is not shown to scale and is much smaller than it appears here.
 
Additional information is available in these presentation slides.

No Capacity Loss: A major advantage of the proposed approch is that it does not require reduction in the capacity in each of the intersecting routes. This can enable the design of air traffic management schemes that are more efficient.

Issue 2: General Intersections

Including Roll Dynamics

The initial work in (Ref 1) did not bound the aircraft turn-rate, i.e., the heading angle was assumed to change instantly. While the roll dynamics (that leads to an aircraft turn) is relatively fast and can be ignored in the CRP design, the turn dynamics places an upper bound on the turn-rate, which could affect the CRP design. The design of provably-safe CRPs in (Ref 1) was extended in (Ref 2) by including the bounded-turn-rate limitation. The resulting CRP is illustrated in the following video (see middle intersection between blue and magenta aircraft.)

Accomodating Different Speeds and Non-perpendicular Intersections

Ref 3 removes two limitations in these decoupled provably-safe CRP approaches by: (i) developing procedures for non-perpendicular intersections; and (ii) removing the requirement that aircraft on each intersecting route have the same speed. The resulting CRP is illustrated in the above video. See top intersection between blue and red aircraft for non-perpendicular with same speed case and the bottom intersection between blue and green aircraft for non-perpendicular with different speed case. Additional details, such as synchronization issues (and application to intermittent conflicts) are discussed in Ref 5


 

 
The top intersection is non-perpendicular with same aircraft speed in each route.

The middle intersection is perpendicular with same aircraft speed in each route.

The bottom intersection is non-perpendicular with different aircraft speeds in the two intersecting routes.
 

 
Note, again, that the circles represent a 5 Nautical Mile (NM) diameter disc centered around the aircraft. The goal is to ensure that these disc do not overlap, i.e., a minimal separation distance of 5NM is maintained at all times. The aircraft, at the center of the circle, is not shown to scale and is much smaller than it appears here.

 

The above provably-safe CRPs solve the conflict resolution problem for intersecting routes in a local manner that leads to decoupling of CRPs for different intersections.

Issue 3: On-demand Conflict Resolution

The above CRP is inefficient because it is always on — even in the absence of conflicts. This always-on CRP (even without conflicts) leads to unwanted CRP maneuvers resulting in increased travel time, travel distance and required fuel. Ref 4 removes the inefficiency of always-on CRPs by developing provably-safe CRPs that can be activated on-demand (when conflicts appear) to accommodate an impending conflict. Conditions are developed to guarantee safety during activation and deactivation of the CRP, and the proposed on-demand approach is illustrated through an example route intersection shown in the following video. Application to the non-perpendicular case is discussed in Ref 5
 


 
Note that the circles represent a 5 Nautical Mile (NM) diameter disc centered around the aircraft.

The goal is to ensure that these disc do not overlap, i.e., a minimal separation distance of 5NM is maintained at all times.

The aircraft, at the center of each circle, is not shown to scale and is much smaller than it appears here.
 

The main idea is to allow deactivation when sufficient space is available and ensuring the ability to activate the CRP in a safe manner, which can also be extended to non-perpendicular CRP designs or cases when the nominal speed of the aircraft are different along the two routes, e.g., in CRP designs studied in Ref 3 .

Issue 4: Centralized vs. De-Centralized Implementation

The use of on-demand CRP increases the need for information sharing and increased centralization of the CRP implementation. For example, with the always-on 2-path CRP, an aircraft arriving at the initial waypoint can choose a CRP path based on the arrival time. The choice of the path can be made in a de-centralized manner because it does not depend on previous arrivals on the same route or arrivals in the other route in the intersection.

In contrast, with the on-demand CRP, additional information about aircraft in both routes is needed to make the decision to activate or deactivate the CRP. Thus, the increase in efficiency of the on-demand CRP (compared to the always-on CRP) is at the cost of increased need for information-of and co-ordination-between aircraft in the two routes.

Issue 5: Robustness

Timing is critical to maintain the minimal spacing needed to avoid conflict in the proposed CRP approach and the activation and deactivation procedures. The robustness of the proposed CRP can be increased by using larger (minimal) separation distances in the CRP design as discussed, e.g., in (Ref 1) and (Ref 2) , to create additional buffer space and thereby, allow for uncertainty/error in the aircraft arrival timing as well as aircraft velocities — at the cost of increased space needed for the CRP.

Issue 6: Exploit No-Capacity-Loss with CRP for Adverse-Weather-Rerouting Playbook Design

Current approaches to reroute aircraft around adverse weather includes merges, which leads to loss of capacity. For example, under current traffic flow management (TFM), standardized procedures in the National Severe Weather Playbook allow aircraft to be rerouted around a region with adverse weather. For route simplicity, air routes (even those going to different destinations) tend to be merged before rerouting around the adverseweather region. For example, Fig. a shows the West Watertown' procedure, can be used to merge and reroute aircraft from the west coast when a large area in the Midwest is affected by adverse weather. Merges simplify conflict resolution in nearby regions (e.g., with the route represented by a dashed line in Fig. a) and ease the interfacing with human controllers. However, the restriction on the acceptable aircraft-flow level on the merged route leads to a reduction of the acceptable aircraft-flow levels in the routes that are merged.
 
photo
 

Our work in (Ref 1) suggests that rerouting should be considered through nearby sectors without the use of undesirable merges, and thereby avoiding the reduction in aircraft-flow levels in the routes that aim to pass through the affected region, e.g., as illustrated in Fig. b.

The increase in number of reroutes (when compared to the case with merges) can increase the number of intersections with preexisting routes, and thereby increase potential conflicts, in the nearby region. However, the results in (Ref 1) enable the use potentially automated conflict resolution procedures (CRPs) with guaranteed solutions to the nearby conflicts. Furthermore, these CRPs do not require a reduction in the aircraft-flow levels (i.e., capacity of the reroutes) for conflict resolution, which can improve the ATC efficiency when compared to existing merge-based procedures.

Contact Santosh Devasia: devasia@u.washington.edu

Presentations and Videos

photo
Provably safe air traffic control;
Adverse weather rerouting

References

Ref 1: S. Devasia, D. Iamratanakul, G. Chatterji, and G. Meyer "Decoupled Conflict- Resolution Procedures for Decentralized Air Traffic Control" IEEE Transactions on Intelligent Transportation Systems, Vol. 12 (2), pp. 422-437, June 2011.

Ref 2: J. Yoo and S. Devasia "Provably Safe Conflict Resolution With Bounded Turn Rate for Air Traffic Control" IEEE Transactions on Control Systems Technology, Vol. 21 (6), pp. 2280-2289, November 2013.

Ref 3: J. Yoo and S. Devasia "Decoupled Conflict Resolution Procedures for Non-pependicular Air Traffic Intersections with Different Speeds," 2013 Conference on Decision and Control.

Ref 4: J. Yoo and S. Devasia "On-demand Confict Resolution Procedures for Air Traffic Intersections," IEEE Transactions on Intelligent Transportation Systems, Vol. 15 (4), pp. 1538-1549, August 2014.

Ref 5: J. Yoo "Flow-Capacity-Maintaining, Decoupled Conflict Resolution Procedures for Air Traffic Control," Ph.D. Thesis, U. of Washington, 2014.

Ref 6: S. Devasia and A. Lee "Scalable Low-Cost-Unmanned-Aerial-Vehicle Traffic Network" AIAA Journal of Air Transportation, Vol. 24 (3), pp. 74-83, July 2016. Also see ArXiv pdf version