Application of Compact Representation of Or- dered Set to Air Traffic Conflict Resolution

Abstract

The motivation of implementing Adaptive Compact Tree is to improve the performance of Constraint Pro- gramming(CP) solvers operations, which is used for en-route conflict resolution in. AC-Trees could not only help CP solver to solve the conflict problem much faster, but also outperform classic BSTs on standard set operations. In addition, we will also present optimizations that improve the performance of the conflict detec- tion for the conflict problem previously mentioned. With these optimizations, the conflict detection phase can be completed in a few seconds. Together with our contribution of the ACTree data structure used in CP solver which accelerates conflict resolution, the total execution time has been reduced significantly, which opens the way to a real-time implementation in an operational context.

Keywords

adaptive data structure / constraint programming / conflict resolution

References

[1] Allignol C., Barnier N., Durand N., & Alliot J.-M. (2013). A new framework for solving en-routes conflicts. In ATM 2013, 10th USA/Europe Air Traffic Management Research and Development Semi- nar.

[2] Allignol C., Barnier N., Flener P., & Pearson J. (2012). Constraint programming for air traffic man- agement: A survey. The Knowledge Engineering Review, 27(03), 361-392.

[3] Baraff D. (1992). Dynamic simulation of non-penetrating rigid bodies. Technical Report. Cornell University.

[4] Barnier N., & Brisset P. (2001). FaCiLe: A Functional Constraint Library. In CICLOPS - Colloqui- um on Implementation of Constraint and Logic Programming Systems, CP’ 01 Workshop, Paphos, Cyprus, December 2001.