ERCOS

Summary

Description

The ERCOS project started in 1992, along with the CATS project. One of the reason of developping ERCOS was the result of the ongoing ERATO project at CENA and ENAC. ERATO did an extensive analysis of the controller work, and showed that a large part of his workload was devoted to the monitoring of trajectories, because of the large uncertainties that he was not able to handle. One of ERATO goal was to develop tools for controllers to help them in their work, without perturbing their "mental perception" of the situation.

Most of ERATO subsequent work was done with cognitive ingeneering methods and tools. On the opposite, our team worked on a more brute force approach, trying to apply some of the results of research in the Artificial Intelligence field in the 80s and early 90s. The brute force approach had significant results in this area, especially in game theory and related computer programs, showing that "many things for which we had at best anthropomorphic solutions, which in many cases failed to capture the real gist of a human's method, could be done by more brute-forcish methods that merely enumerated until a satisfactory solution was found" (Berliner).

Our modelling of uncertainty is partly based on ERATO results, and on the analysis of aircraft trajectories compared to the result of traffic prediction tools; in our model, the uncertainty increases linearly with time along the axis of the aircraft movement, while it remains constant along the axis orthogonal to the displacement. This is consistant with aircraft navigation, which is extremely precise regarding the heading, while uncertainties on speed are high for many different reasons.

We say that planes are likely to be in conflict (we call this "potential conflict") when their uncertainties bounding box have an intersection in the future (around 10 to 20 minutes, depending on the simulations made). However, potential conflicts do not always become real conflicts, and it is then useful to wait before solving the conflict until uncertainties diminish. However, waiting too long might turn the conflict into an unsolvable one (this dilemna is well known by air traffic controllers).

On the following example, the behaviour of our model is demonstrated:

At the start of the computation window (when planes are still far from the resolution point), the uncertainties bounding box is large, and thus a potential conflict is detected. The algorithm finds a solution, but also finds that it is not urgent to solve the conflict. So nothing is done. A few minutes later, uncertainties have diminished, and the potential conflict disappears, making resolution useless.

The algorith was designed to minimize the number of manoeuvers to solve conflicts, and also to minimize also the total length of deviations. On the example below, the algorithm finds a solution for a 4 aircraft conflict by just moving 2 of them.

The algorithm uses only very simple manoeuvers: ddeviation of 20, 20 or 30 degrees and offsets. The following example shows an offset resolution for a 5 aircraft conflict.

The conflict resolution problem is too complex to be solved by deterministic algorithm (it is NP complete), and we are using evolutionary algorithms to find solutions. These algorithms do not always find the best solution, so we tested them on classical cases where the optimal solution is known. On the following example, the algorithm is tested on a classical symmetric problem where the best solution is known (all aircraft must turn of the same amount in the same direction). That's exactly what the algorithm finds:

The algorithm was also tested on more complex problems, such as the following ones:

All the above examples are only "toy examples", to demonstrate the behaviour of the algorithm on simple problems. One of the main task of the ERCOS project was to integrate these algorithms in the CATS/OPAS traffic simulator to test them with real flight plan data. Since 2002, ERCOS was able to solve all conflict in the european airspace. The publications below give a more accurate description of the project results.

ERCOS has been one of the main project of our lab for many years. It had a serious influence on ATM research. Its ideas were, for example, the basis of the ERASMUS project (see the SAGES project homepage for more informations).

ERCOS algorithms are now the basis of a collaboration with Thalès ATM with the GENESE project.

Software

Useful links

Main publications

All publications of the POM team are available here.

All publications of the former LOG (Global optimization lab) are available there.


Last Update: