Optimization and parallelism

Many air traffic problems involve an optimization method in their treatment. Some are even directly modeled as optimization problems under constraints (see the Optimization page in the Research / Mathematics menu for the formalization of these problems). Typically, for a set of conflicting aircraft, we seek all maneuvers to separate trajectories predicted by minimizing deviations from the initial trajectory.

Some of these problems are large, sometimes combinatorial and NP-hard, and processed information is usually uncertain or incomplete (meteorological factors, human intervention).

To deal with these difficult issues, we seek to improve the existing optimization methods, for example by combining a mechanism for cooperative parallelism. This research is conducted in close collaboration with the team Parallel Algorithms and Optimization (APO) of the Institute for Research in Computer Science of Toulouse (IRIT).


Genetic algorithm (left) and branch and bound interval (right) minimizing Griewank function

Choice of models

The approach to address the problems of air traffic management requires first a modeling stage. As the physical reality of phenomena is too rich to be treated as a whole, we need to extract a mathematical or computing model, more or less detailed, depending on the desired degree of realism.

Preferences modeling generally determine the selection of the optimization method. For example, the choice between discrete or continuous variables is essential, such as modeling uncertainties in the variables (probability density, confidence intervals, tolerance intervals).

Some air traffic problems can be addressed by modeling and mathematical methods (see the Mathematics tab ). For optimization problems, it usually requires that the objective function and constraints are represented in an analytical form.

Other problems may be more directly accessible using standard computer models (graphs, trees, CSP, etc.). For example:

For practical applications, the model must be sufficiently close to reality. When the analytical approach is not feasible, it is necessary to rely on computational models, sometimes complex. This is for example the case where analytical expressions of stress and / or the function to be minimized is not directly accessible.Then, they must be evaluated by a computer simulation. Here are some examples:

methods

Among the optimization methods used by MAIAA to solve air traffic management problems, we can find:

When possible, we apply an existing method directly. For example, the sequences are optimized off with a branch and bound algorithm, the optimal path on the network taxiways is calculated by a backtracking algorithm (A *, for example). For sufficiently small instances, the problem of optimal partitioning of space can also be treated with a tree search method.

The methods mentioned in the above applications, exhaustively traverse the space of candidate solutions. In other cases, approaches introducing a random walk in the search space, with a heuristic to guide the random walk towards the best solutions are used. This type of approach has proved particularly effective in optimizing the route network, resolving air conflicts or aircraft taxxiing conflicts, for example.

These methods ("meta-heuristics") are essentially iterative stochastic algorithms, operating in continuous or discrete variables, and advance an individual or a population of individuals to a global optimum of the objective function that is sought to minimize or maximize, but prove the optimality of found solutions.

Research on optimization methods

In their canonical form, the optimization methods mentioned above often work poorly on realistic instances of addressed problems . Much of our expertise is to find a suitable modeling and specific operators to the addressed problem , hybridizing different methods to achieve a satisfactory result.

For example, the definition of a crossover operator tailored to partially separable functions for the evolutionary algorithm, has greatly improved the solutions found for the resolution of air and taxiing conflicts. However, as with any meta-heuristic, the solutions optimality is not guaranteed for a finite number of iterations.

A more recent focus of our research is to combine comprehensive methods such as branch and bound intervals with meta-heuristics and a cooperative parallelism. The meta-heuristic (evolutionary algorithm, and differential evolution, for example) can quickly find good solutions, seeking in the eligible area maintained by the method of intervals. These solutions are possibly used by the interval method as terminal cut, to remove parts of the field whose image is worse by an inclusion function than the best solution found.

In this context, we also seek to improve the interval method of propagating constraints of the problem (or the necessary conditions of optimality) in the tree search, conducted by the branch and bound at intervals. This hybridization uses constraint programming techniques.

The objective is to find the global optima of multi-modal functions difficult to optimize, and especially to prove global optimality. From a practical point of view, these innovative methods could guarantee optimal solutions for problems such as velocity control aircraft. See also the optimization page in mathematics research, for other ongoing research at MAIAA on optimization methods.