Ralf Borndörfer, Martin Weiser
01.01.2022 − 31.12.2023
We aim at extending our discrete-continuous flight planning algorithm DisCOptER from project AA3-3 to an adaptive method using graph refinements based on a posteriori error estimators. A demonstrator will allow solving 4D instances with realistic physics to assess the benefits of free flight jointly with Lufthansa Systems.
The algorithm DisCOptER allows to find a globally optimal solution for the Free Flight Trajectory Optimization Problem in finite time. I.e. it finds the best route from A to B with respect to the wind conditions.
Global Optimization is usually done with stochastic methods like for example Rapidly Exploring Random Trees (RRT) and its variants or Particle Swarm Optimization (PSO). Some, but not all, of these approaches will converge to the optimal solution given enough time.
Deterministic approaches, on the other hand, are usually based on the principle of Branch and Bound, which makes them converge in finite time, but also renders them infeasible for high dimensional problems.
With the algorithm DisCOptER we fill this cap. Using an artificial locally connected digraph (blue dots) we implicitely define a set of routes in the space of admissible trajectories (e.g. red path). With state-of-the-art shortest path algorithms, namely Yen’s algorithm based on the A*-variant of Dijkstra’s algorithm, this set can be scanned efficiently. Routes that are identified as promising candidates serve as initial guess for a subsequent local optimization stage involving well known Optimal Control methods (leading to the green route) (for more details please be referred to the predecessor project AA3-3).
The crucial question is: How dense need the graph? On one hand it needs to be sufficiently dense to capture all relevant regions. On the other hand it should be as sparse as possible in order to be searched quickly.
It turns out that in practically relevant cases a relatively sparse graph suffices. Assumptions based on a priori information, however, significantly overshoot. This is why we need to develop an adaptive algorithm that successively refines the graph taking local information into account.