Project
PaA-4
Free Flight Global Optimization via Eikonal Discretizations
Project Heads
Ralf Borndörfer, Martin Weiser
Project Members
Arturas Jocas
Project Duration
15.06.2024 − 31.12.2025
Located at
ZIB
Description
Optimal flight paths to three different destinations in a wind field consisting of many vortexes. Estimated cut loci are shown in red. Globally optimal paths to destinations positioned on cut loci are not unique.
Airlines demand globally optimal continuous flight paths in free flight areas under arbitrary wind conditions; this renders airway network based methods unfavorable. We develop a novel eikonal-based method solving the Hamilton-Jacobi-Bellman (HJB) equation governing a planar Free Flight Trajectory Optimization Problem (FFTOP). A linear FE discretization is applied and the resulting system is successfully solved via Hopf-Lax updates in a Jacobi type iteration. In such a way, travel time and predecessor approximations are obtained, the latter one being used for computing approximate candidate trajectories by integrating the predecessor field backwards. Finally, the candidate trajectories are further refined to obtain arbitrarily accurate solutions using a fast optimal control solver based on the results of AA3-3 and TrU-4.
A streamline plot of optimal trajectories originating in New York on 06/04/2024. Estimated singularities (cut loci) are shown in red.
Our method is motivated by the existence of destinations having non-unique minimizing trajectories. Such destinations correspond to the singularities of the HJB equation. Localizing them is of paramount importance when aiming to identify the candidate trajectory that converges to the globally optimal solution, and failure to do so can lead to the computation of only locally optimal solutions. The theoretical investigation of the singularities of the HJB equation is based on an analysis of the corresponding Hamiltonian system. In particular, the set of cut loci of FFTOP coincides with the sets Σ of singular and Γ of conjugate points of this system. By using numerical approximation of the predecessor field, cut loci can be identified as simplices Σh ∪Γh having predecessor directions differing from some threshold angle value.
A key component in deriving global optimality guarantees is identifying where the destination is located relative to Σ ∪ Γ. First, we extend a linear discretization error estimate ε = O(h) of the HJB equation to hold everywhere except on arbitrarily small regions around conjugate points. Then, using the aforementioned error estimate, we define a 2ε trust region (Σ ∪ Γ)2ε around the singular and conjugate points. Mirroring this result gives a practical tool for evaluating where the destination is located relative to the cut loci estimate Σh ∪Γh. If the destination is outside of this region, the numerical HJB solution provides a provably good approximation of the unique globally optimal trajectory.
Related Publications
- Arturas Jocas. Global Free Flight optimization by a Hamilton-Jacobi-Bellman approach. Master’s thesis, TU Berlin, 2024.
- R. Borndörfer, A. Jocas, and M. Weiser. An Eikonal Approach for Globally Optimal Free Flight Trajectories. In Computational Methods in Applied Sciences (under review). Springer, 2026. arXiv:2603.11830