dc.contributor.author
Danecker, Fabian
dc.date.accessioned
2024-07-03T09:21:58Z
dc.date.available
2024-07-03T09:21:58Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/43811
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-43526
dc.description.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.
en
dc.description.abstract
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.
de
dc.format.extent
265 Seiten
dc.rights.uri
https://creativecommons.org/licenses/by-nc/4.0/
dc.subject
Trajectory Optimization
en
dc.subject
Shortest Path
en
dc.subject.ddc
500 Naturwissenschaften und Mathematik::510 Mathematik::515 Analysis
dc.subject.ddc
000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::005 Computerprogrammierung, Programme, Daten
dc.subject.ddc
500 Naturwissenschaften und Mathematik::510 Mathematik::518 Numerische Analysis
dc.title
A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization
dc.contributor.gender
male
dc.contributor.firstReferee
Borndörfer, Ralf
dc.contributor.furtherReferee
Anton Schiela
dc.date.accepted
2024-04-29
dc.identifier.urn
urn:nbn:de:kobv:188-refubium-43811-2
refubium.affiliation
Mathematik und Informatik
dcterms.accessRights.dnb
free
dcterms.accessRights.openaire
open access
dcterms.accessRights.proquest
accept