TrU – Transfer Unit

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.