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.

Blue: Global optimum; Green (solid and dashed): High frequency deviation; Red (solid and dashed): Low frequency deviation.

The performance of the DisCOptER algorithm directly depends on the problem-specific size of the convergence domain of the nonlinear optimization method. Rough wind fields (large spatial derivatives) usually come with a large number of local optima, each with a small convergence domain. This consequently requires a relatively dense graph and higher computational effort.

The deviation of discrete paths from a continuous optimum are characterized by two factors: distance and angular error. We investigate a 2D subspace of the total trajectory space in order to separate the impact of these two factors. The subspace is anchored at the global optimum (blue) and spanned by a high frequency deviation (green) and a low frequency deviation (red).

A high frequency deviation results in a route that zig-zags around the optimum, but stays relatively close. It introduces mostly angular error and little distance error. The opposite is true for a low frequency deviation. Almost shifting the trajectory parallel to the optimum, it introduces mostly distance and little angular error.

Hence, this subspace allows us to study the effect of both factors independently.

The resulting routes are used as an initial guess for the nonlinear optimization stage (e.g., using a Newton-KKT approach). The illustration on the right indicates whether it converged back to the optimum (white) or not (gray) and therefore shows the domain of convergence in this 2D subspace.
Two findings can be highlighted:
i) In practical application the domain of convergence is several orders of magnitude larger than suggested by theory.
ii) Both error terms are equally important in order to assess convergence. This confirms the analysis presented in our publications.

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. DOI: 10.3390/a14010004.
  • Ralf Borndörfer and Fabian Danecker and Martin Weiser. Error Bounds for Discrete-Continuous Shortest Path Problems with Application to Free Flight Trajectory Optimization. Journal of Optimization Theory and Applications 198:830-856, 2023. DOI: 10.1007/s10957-023-02264-7.
  • Ralf Borndörfer and Fabian Danecker and Martin Weiser. A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization. 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022); 2:1–2:13; 106. DOI: 10.4230/OASIcs.ATMOS.2022.2.
  • Ralf Borndörfer and Fabian Danecker and Martin Weiser. Newton’s Method for Global Free Flight Trajectory Optimization. Operations Research Forum 4: 63, 2023. DOI: 10.1007/s43069-023-00238-z
  • Ralf Borndörfer and Fabian Danecker and Martin Weiser. Convergence Properties of Newton’s Method for Globally Optimal Free Flight Trajectory Optimization. In D. Frigioni, P. Schiewe (eds.): 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). pp. 3:1-3:6, 2023. DOI: 10.4230/OASIcs.ATMOS.2023.3

Related Picture