A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization

Abstract

This thesis introduces the novel hybrid algorithm DisCOptER for globally optimal flight planning. DisCOptER (Discrete-Continuous Optimization for Enhanced Resolution) com- bines discrete and continuous optimization in a two-stage approach to find optimal trajectories up to arbitrary precision in finite time. In the discrete phase, a directed auxiliary graph is created in order to define a set of candidate paths that densely covers the relevant part of the trajectory space. Then, Yen’s algorithm is employed to identify a set of promising candidate paths. These are used as starting points for the subsequent stage in which they are refined with a locally convergent optimal control method. The correctness, accuracy, and complexity of DisCOptER are intricately linked to the choice of the switch-over point, defined by the discretization coarseness. Only a sufficiently dense graph enables the algorithm to find a path within the convex domain surrounding the global minimizer. Initialized with such a path, the second stage rapidly converges to the optimum. Conversely, an excessively dense graph poses the risk of overly costly and redundant computations. The determination of the optimal switch-over point necessitates a profound understanding of the local behavior of the problem, the approximation properties of the graph, and the convergence characteristics of the employed optimal control method. These topics are explored extensively in this thesis. Crucially, the density of the auxiliary graph is solely dependent on the en- vironmental conditions, yet independent of the desired solution accuracy. As a consequence, the algorithm inherits the superior asymptotic convergence properties of the optimal control stage. The practical implications of this computational efficiency are demonstrated in realistic environments, where the DisCOptER algorithm consistently delivers highly accurate globally optimal trajectories with exceptional computational efficiency. This notable improvement upon existing approaches underscores the algorithm’s significance. Beyond its technical prowess, the DisCOptER algorithm stands as a valuable tool contributing to the reduction of costs and the overall enhancement of flight operations efficiency.

In dieser Dissertation wird der neuartige hybride Algorithmus DisCOptER für global optimale Flugplanung vorgestellt. DisCOptER (Discrete-Continuous Optimization for Enhanced Resolution) verbindet diskrete und kontinuierliche Optimierung in einem zweistufigen Ansatz um optimale Trajektorien unter strengen Genauigkeitsanforderungen in endlicher Zeit zu finden. Im ersten Schritt wird ein gerichteter Graph erzeugt und damit implizit eine Menge potentieller Pfade definiert, die den relevanten Teil des Trajektorienraumes gleichmäßig abdeckt. Vielversprechende Kandidaten werden mithilfe von Yen’s Algorithmus identifiziert. Diese dienen als Startpunkte für die zweite Stufe, in welcher lokal konvergente Methoden der Optimalsteuerung eingesetzt werden um kontinuierliche Lösungen zu generieren. Die Korrektheit, Genauigkeit und Komplexität der DisCOptER Methode sind untrennbar verknüpft mit der Wahl des Umschaltpunktes, definiert durch die Dichte des Graphen. Nur auf einem ausreichend dichten Graphen kann ein Pfad gefunden werden, der innerhalb des Konvergenzbereichs um ein globales Optimum liegt. Ausgehend von einem solchen Pfad konvergiert die zweite Stufe schnell zum Optimum. Demgegenüber birgt ein übermäßig dichter Graph das Risiko für aufwändige und redundante Berechnungen. Die Identifikation dieses Umschaltpunktes verlangt nach einem tiefgehenden Verständnis des lokalen Problemverhaltens, der Approximationseigenschaften des benutzten Graphen, sowie der Konvergenzeigenschaften der eingesetzten kontinuier- lichen Optimierungsmethode. Diese Aspekte werden in der vorliegenden Arbeit ausführlich untersucht. Eine zentrale Stärke des vorgestellten diskret-kontinuierlichen Ansatzes ist, dass die nötige Graphendichte ausschließlich von den Umgebungsbedingungen, jedoch nicht von der geforderten Lösungsgüte, abhängt. Dies hat zur Folge, dass asymptotisch die vorteilhaften Konvergenzeigenschaften der kontinuierlichen Op- timierung beibehalten werden. Die Effizienz der vorgestellten Methode wird unter realistischen Bedingungen praktisch nachgewiesen. Es wird demonstriert, dass der DisCOptER Algorithmus mit minimalem Aufwand konsistent hochpräzise global optimale Lösungen erzielt und so einen doppelten Vorteil im Vergleich zu bestehenden Methoden bietet. Einerseits wird eine gesteigerte algorithmische Effizienz erreicht. Andererseits trägt die verbesserte Qualität der Trajektorien wesentlich dazu bei, den Luftfahrtsektor effizienter und umweltfreundlicher zu gestalten.