TrU – Transfer Unit

Project

TrU-4

Adaptive Methods for Free Flight Planning

Project Heads

Ralf Borndörfer, Martin Weiser

Project Members

Fabian Danecker

Project Duration

01.01.2022 − 31.12.2023

Located at

ZIB

Description

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.

Sparse graph: local optimum

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.

Dense graph: global optimum.

Example with a planar windfield consisting of multiple vortices. Blue dots: graph, locally connected, Red line: path on the graph, Green line: continuous optimal solution, Green area: domain of convergence of the global minimizer.

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.

Related Publications

  • Ralf Borndörfer and Fabian Danecker and Martin Weiser. A Discrete-Continuous Algorithm for Free Flight Planning. Algorithms, 14(1), p. 4, 2021.
  • Ralf Borndörfer and Fabian Danecker and Martin Weiser. Error Bounds for Discrete-Continuous Shortest Path Problems with Application to Free Flight Trajectory Optimization. In preparation.
  • Ralf Borndörfer and Fabian Danecker and Martin Weiser. A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization. Submitted.

Related Picture