As acknowledged by the SESAR (Single European Sky ATM (Air Traffic Management) Research) program, current Air Traffic Control (ATC) systems must be drastically improved to accommodate the predicted traffic growth in Europe. In this context, the Episode 3 project aims at assessing the performance of new ATM concepts, like 4D-trajectory planning and strategic deconfliction.

One of the bottlenecks impeding ATC performances is the hourly capacity constraints defined on each en-route ATC sector to limit the rate of aircraft. Previous works were mainly focused on optimizing the current ground holding slot allocation process devised to satisfy these constraints. We propose to estimate the cost of directly solving all conflicts in the upper airspace with ground holding, provided that aircraft were able to follow their trajectories accurately.

We present a Constraint Programming model of this large-scale combinatorial optimization problem and the results obtained with the FaCiLe (Functional Constraint Library). We study the effect of uncertainties on the departure time and estimate the cost of improving the robustness of our solutions with the Complete Air Traffic Simulator (CATS). Encouraging results were obtained without uncertainty but the costs of robust solutions are prohibitive. Our approach may however be improved, for example, with a prior flight level allocation and the dynamic resolution of remaining conflicts with one of CATS’ modules.

This paper considers the problem of generating conflict-free movement schedules for a set of vehicles that are operating simultaneously in a common airspace. In both civilian air traffic management and military air campaign planning contexts, it is crucial that the movements of different vehicles be coordinated so as to avoid collisions and near misses. Our approach starts from a view of airspace management as a 4D resource allocation problem, where the space in which vehicles must maneuver is itself managed as a capacitated resource. We introduce a linear octree representation of airspace capacity to index vector-based vehicle routes and efficiently detect regions of potential conflict. Generalizing the notion of contention-based search heuristics, we next define a scheduling algorithm that proceeds by first solving a relaxed version of the problem to construct a spatial capacity profile (represented as an octree), and then using spatio-temporal regions where demand exceeds capacity to make conflict-avoiding vehicle routing and scheduling decisions. We illustrate the utility of this basic representation and search algorithm in two ways. First, to demonstrate the overall viability of the approach, we present experimental results using data representing a realistically sized air campaign planning domain. Second, we define a more abstract notion of ‘encounter set’, which tolerates some amount of conflict on the assumption that on-board deconfliction processes can take appropriate avoidance maneuvers at execution time, and show that generation of this more abstract form of predictive guidance can be obtained without loss in computational efficiency.

The European air traffic flow management problem poses particular challenges on optimization technology as it requires detailed modelling and rapid online optimization capabilities. Constraint programming proved successful in addressing these challenges for departure time slot allocation by offering fine-grained modelling of resource constraints and fast allocation through heuristic-repair strategies.

Safety-critical software must be thoroughly verified before being exploited in commercial applications. In particular, any TCAS (Traffic Alert and Collision Avoidance System) implementation must be verified against safety properties extracted from the anti-collision theory that regulates the controlled airspace. This verification step is currently realized with manual code reviews and testing. In our work, we explore the capabilities of Constraint Programming for automated software verification and testing. We built a dedicated constraint solving procedure that combines constraint propagation with Linear Programming to solve conditional disjunctive constraint systems over bounded integers extracted from computer programs and safety properties. An experience we made on verifying a publicly available TCAS component implementation against a set of safety-critical properties showed that this approach is viable and efficient.

Air traffic management (ATM) under its current paradigm is reaching its structural limits considering the continuously growing demand. The need for a decrease in traffic workload opens numerous problems for optimization, from capacity balancing to conflict solving, using many different degrees of freedom, such as re-routing, flight-level changes, or ground-holding schemes. These problems are usually of a large dimension (there are 30 000 daily flights in Europe in the year 2012) and highly combinatorial, hence challenging for current problem solving technologies. We give brief tutorials on ATM and constraint programming (CP), and survey the literature on deploying CP technology for modelling and solving combinatorial problems that occur in an ATM context.