Search

International audience; In this article, we test a horizontal detect and avoid algorithm for UASs flying in Terminal Control Areas. We have used recorded commercial traffic trajectories and randomly built thousands of conflict scenarios with UASs to check the ability of such an algorithm to ensure the separation with commercial aviation. We consider two different types of UASs, flying at 80kn or 160kn, with six different missions: flying straight or turning and leveled, climbing or descending. We only focus on horizontal maneuvers at constant speed in order to not interfere with the TCASs of aircraft, nor rely on most UASs poor ability to change speed. The article investigates the influence of the various parameters on the separation achieved and the amount of maneuvers required, especially the strategy used to select the best maneuver among the allowed headings. The analysis of our results shows that, amid two basic and “extreme” strategies that favor either minimal heading changes or the robustness of the maneuvers, the combination of both, switching from the first one to the second whenever the distance between the UAS and aircraft falls under a given threshold, gives the best results with very few remaining airproxes, while keeping low the amount and amplitude of maneuvers.

Study of interactions between two consecutive layers of ATM under increased traffic.Results highlight an exponential growth in delay costs if constant network capacity.Results highlight an unmanageable controller workload if network capacity is high.We find a compromise by controlling delay costs growth with a sector capacity growth.We quantify research objectives for future work on air traffic control optimization. Air traffic in Europe is predicted to increase considerably over the next decades. In this context, we present a study of the interactions between the costs due to ground-holding regulations and the costs due to en-route air traffic control. We dulator that considers the regulation delays, aircraft trajectories, and air conflict resolution. Through intensive simulations based on traffic forecasts extrapolated from French traffic data for 2012, we compute the regulation delays and avoidance maneuvers according to two scenarios: the current regulations and no regulations. The resulting cost analysis highlights the exponential growth in regulation costs that can be expected if the procedures and the airspace capacity do not change. Compared to the delay costs, the costs of the air traffic control are negligible with or without regulation. The analysis reveals the heavy controller workloads when there are no regulations, suggesting the need for regulations that are appropriate for large traffic volumes and an improved ATC system. These observations motivate the design of a third scenario that computes the sector capacities to find a compromise between the increase in the delay costs due to ground-holding regulations and the increase in the controller workload. The results reveal the sensitivity of the delay costs to the sector capacity; this information will be useful for further research into ATM sector capacity and ATC automated tool design. Finally, because of the growing interest in the free flight paradigm, we also perform a traffic and cost analysis for aircraft following direct routes. The results obtained highlight the fuel and time savings and the spatial restrictions that companies use to avoid congested areas.

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.

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.

The en-route conflict resolution problem has been modeled in many different ways, generally depending on the tools that were proposed to solve it. For instance, with purely analytic mathematical solvers, models tend to be very restrictive (constant speeds, linear trajectories) to respect the inherent limitations of the technology. This paper introduces a new framework that separates the model from the solver so as to be able to: first, enhance the model with as many refinements (e.g. wind and trajectory uncertainties) as necessary to comply with operational constraints; second,compare different resolution methods on the same data, which is one of the crucial aspects of scientific research. To this aim, our framework can generate a benchmark of conflict resolution problems built with various scenarios involving a given number of aircraft, level of uncertainties and number of maneuvers. We then compare two different optimization paradigms, Evolutionary Algorithm and Constraint Programming, which can efficiently solve difficult instances in near real time, to illustrate the usefulness of our approach.

As acknowledged by the SESAR program, current ATC systems must be drastically improved to accommodate the predicted traffic growth in Europe. This study aims at assessing the performance of 4D-trajectory planning and strategic deconfliction, two of the key concepts identified to meet SESAR capacity objectives. Among the possible degrees of freedom, we focus here on the flight level (FL) optimization to avoid en-route conflicts between intersecting flights. The resulting problem can be reduced to Graph Coloring with a specific cost function minimizing the discrepancies to requested FLs. This FL allocation leads to very large combinatorial optimization problems when applied at the continental scale, especially when considering temporal uncertainties. The instances were solved with a Tabu Search algorithm in a few seconds to a few minutes, depending on size and conflict density. Our results shows that the global conflict resolution workload is alleviated by at least 20 %, while bounding the individual FL discrepancies to three levels for a small proportion of the traffic.

To overcome the traffic growth predicted by current ATM research programs in Europe and the US, we propose a new model to avoid conflicts based on small speed regulations, as depicted in the ERASMUS project [6], with interval conflict constraints as in [2]. After a first conflict detection phase, a centralized solver computes new RTAs to dynamically adjust the flight plans during the flight, taking operational costs for airlines and for ATC into account. The resolution would be iteratively performed over a rolling horizon to handle the uncertainties inherent to trajectory prediction. The described model is currently being implemented using Constraint Programming and Local Search as optimization techniques. Simulations will be carried out with Europe-wide traffic data.

As acknowledged by the SESAR program, current ATC systems must be drastically improved to accommodate the predicted traffic growth in Europe. This study aims at assessing the performance of 4Dtrajectory planning and strategic deconfliction, two of the key concepts identified to meet SESAR capacity objectives. Among the possible degrees of freedom, we focus here on the flight level (FL) optimization to avoid en-route conflicts between intersecting flights. The resulting problem can be reduced to Graph Coloring with a specific cost function minimizing the discrepancies to requested FLs. This FL allocation leads to very large combinatorial optimization problems when applied at the continental scale, especially when considering temporal uncertainties. The instances were solved with a Tabu Search algorithm in a few seconds to a few minutes, depending on size and conflict density. Our results shows that the global conflict resolution workload is alleviated by at least 20 %, while bounding the individual FL discrepancies to three levels for a small proportion of the traffic.

In the SESAR traffic growth predictions, traffic complexity will become an issue that the current Air Traffic Management organization is not able to handle. The 4D trajectory concept offers new perspectives for deconflicting the traffic by ground-holding aircraft before they take-off. This paper studies the possible complexity reduction achievable by optimizing the aircraft take-off times. Therefore a simple model is introduced to detect pairwise 3D possible conflicts and define conflicting take-off time differences. Two resolution algorithms are tested on a real traffic data sample collected in the French airspace. The first one is based on a Constraint Programming model of the problem and ensures the optimality of the maximum delay required to solve every conflict. The second one uses an evolutionary computation algorithm to minimize the mean delay among the aircraft population. A sliding window model is introduced to reduce the size of the problem and to regularly update the current situation. Experimental results performed in the French airspace with fast time simulation show that with perfect 4D trajectory, every conflict over flight level 290 can be solved by delaying less than a quarter of the traffic within a range of delays varying from 1 to 90 minutes and a mean delay of 4 minutes. The Constraint Programming approach gives better results than the evolutionary computation approach. Adding uncertainty around 4D trajectories dramatically degrades the results.

International audience; En-route conflict resolution is a good example of a large-scale combinatorial optimization problem. On the one hand, it has been modeled in many different ways, most of the time depending on the tools that were proposed to solve it. On the other hand, many different resolution methods can be tested and compared on such problems but a common model needs to be used to validate the comparison. In this paper we extend the 2D-framework introduced in 2013, which separates the model from the solver. First, we introduce a 3D-model and add new refinements on the uncertainty model taking into account, inter alia, delays due to human factors. Second, we compare the performance of a complete Constraint Programming solver and an approximation algorithm based on a Memetic Algorithm, an efficient metaheuristic combining Genetic Algorithm with Tabu Search. To this aim, we generate a benchmark of conflict resolution problems built with scenarios involving 15 to 100 aircraft, 3 different levels of uncertainty and maneuvers in both horizontal and vertical planes. The two methods are able to efficiently solve moderate size problems in near real time, but the execution time of the complete algorithm exponentially rockets with larger instances whereas the metaheuristic scales much better with the number of aircraft. However, the former is able to prove optimality or infeasibility on reasonable problems, which allows the assessment of the quality of the solutions produced by the latter.

National audience