Constraint programming
Constraint Programming (CP)—see Rossi et al. (Reference Rossi, van Beek and Walsh2006), for instance—is a powerful technology to model and solve combinatorial (optimization) problems, which are ubiquitous in industry. CP works either via systematic tree search interleaved with constraint propagation (the elimination of impossible values) at every node of the search tree, or via constraint-based local search. CP is an ideal integration technology for hybrid solving, including methods from classical operations research as well, such as mixed integer programming (IP), and Boolean satisfiability. CP is now a mature technology and has been successfully used for tackling a wide range of real-life complex applications, especially for short-term scheduling, personnel rostering, and configuration problems.
Air traffic management
The aim of this special issue was to collect original papers on applying constraint programming within the area of air traffic management (ATM), including air traffic control (ATC).
Given the demands on today's ATM system, there is a constant need to optimize its performance in terms of costs, efficiency (minimal delay), or environmental impact. These performance criteria are often conflicting—many noise reduction measures at airports reduce capacity; many capacity enhancing measures carry a large cost—and therefore finding an optimal trade-off becomes the real objective.
A wide array of techniques have been used in ATM optimization research, spanning expert systems, queuing models, heuristics, dynamic programming, (mixed) IP, constraint programming, and even evolutionary computation paradigms. A growing body of research is reported on in specialized conferences and journals, the most notable being the biannual USA/Europe ATM R&D Seminar Footnote 2 and the ATC Quarterly Footnote 3.
Because of the importance to their business operation, most of the ATM stakeholders will fund relevant studies. Air navigation service providers (in Europe, these are often national agencies responsible for civilian ATC) are constantly looking for optimizations in their airspace structure and sectorization, conflict detection and resolution, arrival and departure sequencing, or staff rostering. The European Central Flow Management Unit Footnote 4 is concerned with optimal slot allocation to minimize ground delays in periods (or areas) of insufficient control capacity. Airports are concerned with minimal turnarounds at their stands or optimal taxiway and runway usage. Even airlines will be involved in schedule or route optimization studies.
Besides specific research requirements from these stakeholders, the European Commission and the EUROCONTROL agency (the European Organisation for the Safety of Air Navigation Footnote 5) both have a remit for research in ATM and fund many projects, mainly through the Single European Sky ATM Research (SESAR) Joint Undertaking, which they recently co-founded. For advanced research, in particular the work package E, dedicated to innovation and the long term, is of relevanceFootnote 6. In addition, there is a network of national research laboratories dedicated to air trafficFootnote 7, mainly in the larger European countries, who have their own research agendas (often aligned with the European agendas, but catering for national priorities) and associated budgets. In other countries, funding may be available through national transport research or innovative technology programmes.
ATM is a global undertaking, with high requirements of interoperability: the same planes should be able to fly everywhere with the same equipment. The United States of America has an equally active research community, centred around the Federal Aviation Authority (a single entity roughly equivalent to a grouping of responsibilities of national service providers and EUROCONTROL on the European side), its university network NEXTOR, and the research programmes of NASA (National Aeronautics and Space Administration) and MITRE.
Workshop
This special issue is a follow-up to the International Workshop on Constraint Programming for Air Traffic Control and Management Footnote 8, which the first two guest editors organized on 2 December 2008 at the 7th EUROCONTROL Innovative ATM Research Workshop and Exhibition (INO'08)Footnote 9, which was held at the EUROCONTROL Experimental Centre in Brétigny-sur-Orge, France. At our workshop, the proceedings consisted only of the slides of the presentations given. Towards generating a formal compilation of such research, we organized this special issue, which had an open call for papersFootnote 10 and was thus not restricted to the participants of our workshop. The special issue topics included, but were not limited to, airspace sectorization, arrival management, traffic complexity resolution, departure management, flow management, route network design, runway allocation, and slot allocation.
Accepted papers
After two rounds of reviewing to the standards of the usual Knowledge Engineering Review (KER) refereeing process, the four papers in this special issue were accepted for publication. Each paper was reviewed by two experts in constraint programming and at least one expert in ATM. The editors-in-chief of KER made the final acceptance/rejection decisions.
In the first paper, Barnier and Allignol (Reference Barnier and Allignol2012) study the cost of resolving in advance, only through ground holding, all the trajectory conflicts occurring in upper airspace for an entire day of traffic, with successful experiments on the entire French airspace. The assumption is that flights will be able to follow their planned trajectories accurately. Initially studies conduct towards handling the actual uncertainty about this assumption, by widening the conflict parameters, but unacceptable take-off delays result when aiming at even only marginal robustness. CP is judged to be a technology of choice for implementing such work, as its approach to systematic search is best-suited for such purely combinatorial problems.
In the second paper, Hildum and Smith (Reference Hildum and Smith2012) also aim at resolving in advance all the trajectory conflicts occurring in a common airspace, but they do so not by ground holding (as in the first paper) but by horizontally and minimally re-routing flights. Successful experiments are conducted over realistically sized sets of flight plans. The uncertainty and robustness issue is here tackled in the opposite fashion compared with the first paper, namely by actually shrinking the conflict parameters, relying instead on on-board deconfliction processes.
In the third paper, Junker (Reference Junker2012) explains the heuristic-repair problem solving principles that helped to achieve the good results of a prior study on departure time slot allocation (ground holding) using CP rather than IP. Like in the first paper, successful experiments were conducted on entire days of traffic in the entire French airspace, but capacity constraints rather than trajectory conflicts are taken into account here. The experiments show that the CP model scales much better than the IP model, which was designed using standard IP modelling practices.
In the fourth paper, Gotlieb (Reference Gotlieb2012) uses CP not on conventional operational research problems such as those of the first three papers, but he exploits the wide scope of CP towards automatically verifying properties of a safety-critical software system for traffic alert and collision avoidance Traffic Alert and Collision Avoidance System (TCAS). He shows how a complete test suite covering all possible executions of an imperative program can be automatically obtained from a declarative constraint model that is automatically extracted from the program in a collaboration between a CP solver and a linear programming solver. Previously unknown errors were found efficiently in this fashion in a publicly available TCAS module.
In addition, Allignol et al. (Reference Allignol, Barnier, Flener and Pearson2012) was submitted to the KER editors-in-chief and accepted by them independently of the other papers in the special issue following anonymous independent review. The paper surveys the use of constraint programming for ATM, after initial tutorials on both ATM and constraint programming. We thank the unknown reviewers for their comments.
Acknowledgements
The authors wish to thank the members of the programme committee of our workshop as well as the anonymous referees of this special issue for all their help. Many thanks also to Peter McBurney and Simon Parsons, the KER editors-in-chief, for agreeing to run this special issue, and for supervising the review process of the paper co-written by some of the guest editors.
