**Project Heads**

Ralf Borndörfer, Martin Weiser

**Project Members**

Fabian Danecker

**Project Duration**

01.01.2022 − 31.12.2023

**Located at**

ZIB

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.

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.

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
- Fabian Danecker. A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization. Doctoral Dissertation, Free University of Berlin. 2023. DOI: 10.17169/refubium-43526

**Related Picture
**