acasxu

The Detect and Avoid system is considered as a fundamental component to allow drones integration in the civil airspace. This system should perform three functions: provide traffic awareness to the remote pilot (TA); support the pilot to Remain Well Clear (RWC); detect conflicts, provide guidance and possibly execute Collision Avoidance maneuvers (CA). To answer this last problem, the Lincoln Laboratory (MIT) developed the ACAS X family of algorithms, and more specifically ACAS Xu for unmanned aircraft. Though we won’t enter in the details of ACAS Xu working, its general architecture is described in the above diagram.

Unlike other ACASs (ACAS II, ACAS X), ACAS Xu can provide both vertical (orange) and horizontal (red) resolutions. The challenge is: how to choose between vertical and horizontal maneuvers? According to the above diagram, the choice is done by a module called Nucleus (green). However, little information on what Nucleus might be was publicly available until last September. During the DASC2016 conference, M.J. Kochenderfer and M.J. Owen (the main developers of the ACAS X algorithms) presented a paper describing a method to dynamically choose between horizontal and vertical resolutions. Considering that this could be the basis for a future Nucleus, we hereafter propose a summary of the method described in [1].

First it is useful to remember that the logics used to compute a resolution rely on a set of state variables describing the encounter. These variables are different for vertical and horizontal logics (Table hereafter, “Vertical” and “Horizontal”). The number of state variables is limited to keep the problem tractable. For this reason, mixed maneuvers combining vertical and horizontal components are not considered as the resulting state space would be too large. So the problem boils down to choosing if the maneuver should be vertical or horizontal.

acasxu_vars_table

In [1], the authors first explain why the two solutions which first come to mind, always following the first alerting logic or the last alerting logic, are unsatisfactory. Indeed, the first logic to alert is doing so because it detects the greatest collision risk and this may come from the fact that it is unsure about its capability to solve the encounter. So the first alerting logic may be the least capable of solving the encounter. On the opposite, the logic alerting last is the one which recognized the least risk in the encounter, it may be underestimating the collision risk and alerting late. To provide an answer to the logic selection problem, the authors generate 10 million encounters sampled from the Lincoln Laboratory Correlated Encounter Model (LLCEM) [2], and select a set of state variables describing the encounter (Table above, “Selection”). Based on these encounters, they compute probabilities of NMAC with vertical and horizontal maneuvers. These are used to tune, for each state variable, a series of weights dependent on the safety contribution provided by the variable (in terms of probability of NMAC), the sensor providing the information, and the noise expected from the sensor. Once a logic is selected, it remains selected until the conflict has been solved. The authors show that such approach yields a lower probability of NMAC than the vertical or horizontal logics alone with a reasonable probability of alerting. However, this approach loses the optimal properties of the logics provided by the dynamic programming plus Markov Decision Process combination; so the resolution obtained are no longer optimal.

Though there is no certainty, we believe this work will be the basis for the future Nucleus module. One should note that this method relies heavily on the choice of an encounter model to tune the selection logic. This means that the algorithm needs to be trained to the skies it will be flying in.

References:

[1] Owen, M. P., & Kochenderfer, M. J. (2016, September). Dynamic logic selection for unmanned aircraft separation. In Digital Avionics Systems Conference (DASC), 2016 IEEE/AIAA 35th (pp. 1-8). IEEE.

[2] Kochenderfer, M. J., Espindle, L. P., Kuchar, J. K., & Griffith, J. D. (2008). Correlated encounter model for cooperative aircraft in the national airspace system version 1.0. Project Report ATC-344, Lincoln Laboratory.