Cette page est aussi disponible en francais.
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 stochastic 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 CAYS/OPAS traffic simulator to test them on rela traffic data. Now, ERCOS can solve all conflict in the european airspace. The publications below give more accurate description of the project results.
ERCOS has been one of the main project of our lab for many years. It was not implemented in operational systems, but had a serious influence on ATM research. Its ideas are, for example, the basis of the ERASMUS resolution algorithm (see Jacques Villiers original paper on the SAGES project homepage).
All publications of LOG are available here.