Navigieren im All: Ein Algorithmus findet die optimale Route
Wie plant man eine Raumfahrtmission zu Asteroiden, die nicht nur weit entfernt sind, sondern sich auch ständig bewegen? Ein Forschungsteam der Universität Bielefeld hat dafür erstmals eine Lösung gefunden. Der Ansatz könnte auch den Verkehr auf der Erde effizienter machen.
Bewegte Asteroiden stellen die Missionsplanung vor komplexe Herausforderungen – neue Algorithmen ermöglichen erstmals eine optimale Routenberechnung.
Foto: Smarterpix/klss
Wie schaffen es Raumsonden eigentlich, die perfekte Route zu finden? Die Planung von Raumfahrtmissionen mit mehreren Zielobjekten gehört zu den anspruchsvollsten Optimierungsproblemen. Ein Forschungsteam der Universität Bielefeld konnte jetzt einen wichtigen Fortschritt erzielen: Das Team um Professor Dr. Michael Römer hat einen mathematischen Ansatz entwickelt, mit dem sich optimale Routen zu mehreren Asteroiden erstmals exakt berechnen lassen.
Im Zentrum steht das Asteroid Routing Problem. Die Grundfrage ist einfach formuliert: In welcher Reihenfolge sollte eine Raumsonde verschiedene Asteroiden anfliegen, damit Zeit und Treibstoff möglichst gering bleiben?
Inhaltsverzeichnis
Dynamik macht Planung extrem aufwendig
Während sich solche Fragestellungen bei statischen Zielen noch vergleichsweise gut lösen lassen, steigt die Komplexität bei bewegten Objekten rapide. Asteroiden bewegen sich kontinuierlich auf ihren Bahnen, wodurch sich die optimalen Flugrouten permanent verändern.
Mathematisch handelt es sich dabei um das Lambert-Problem: die Berechnung der optimalen Flugbahn zwischen zwei Punkten im Raum unter Berücksichtigung von Gravitation und Zeitfenster.
In der Praxis bedeutet das, dass für jede mögliche Verbindung zwischen zwei Asteroiden exakt berechnet werden muss, wie eine Raumsonde diese Strecke am effizientesten zurücklegt. Da sich beide Objekte jedoch kontinuierlich bewegen, verändert sich diese Bahn ständig und daher müssten auch ständig neue Berechnungen durchgeführt werden. Ein Aufwand, der mit der Anzahl der Ziele exponentiell ansteigt.
Neuer Ansatz liefert exakte Lösungen
Das Forschungsteam hat zum Lösen dieser Probleme nun einen neuen Lösungsansatz entwickelt. Die Methode basiert auf sogenannten Decision Diagrams.
Dabei handelt es sich um grafische Modelle, die große Mengen möglicher Lösungen strukturiert darstellen. Vereinfacht gesagt werden alle denkbaren Routen nicht einzeln durchgerechnet, sondern in einer Art Entscheidungsbaum organisiert. Ähnliche Teilentscheidungen werden gebündelt, sodass sich wiederkehrende Muster nur einmal berechnen lassen. Das reduziert den Rechenaufwand erheblich und macht es überhaupt erst möglich, den riesigen Lösungsraum systematisch zu erfassen.
Zusätzlich nutzen die Forschenden eine gezielte Suchstrategie, die den Lösungsraum Schritt für Schritt eingrenzt. Unvorteilhafte Routen werden früh verworfen, während vielversprechende Varianten weiterverfolgt werden. So konzentriert sich die Berechnung auf die relevanten Optionen.
Von einer Idee der ESA zur Veröffentlichung
Der Ausgangspunkt der Arbeit war ein Wettbewerb der Europäischen Weltraumorganisation ESA, bei dem es um innovative Ansätze zur Planung komplexer Raumfahrtmissionen ging. In Bielefeld wurde dieser Ansatz anschließend systematisch weiterentwickelt.
Von den Sternen in den Stau
Potenzial bietet die Methode auch über die Raumfahrt hinaus. Viele Systeme auf der Erde sind ebenso durch zeitabhängige Bedingungen geprägt:
Im Straßenverkehr variieren Fahrzeiten durch Staus oder Baustellen. In der Logistik reagieren Lieferketten empfindlich auf Nachfrage, Verzögerungen oder Engpässe. Auch in der Schifffahrt und Luftfahrt bestimmen dynamische Faktoren wie Wetter, Strömungen oder Luftraumkapazitäten die optimale Route.
Der Bielefelder Ansatz eignet sich insbesondere für solche zeitabhängigen Routing-Probleme. Denn statt mit statischen Annahmen zu arbeiten, berücksichtigt er, dass sich Bedingungen laufend ändern und Entscheidungen zeitabhängig getroffen werden müssen. Das könnte helfen, Routenplanung deutlich präziser zu machen und Systeme besser auszusteuern. Denkbar sind etwa kürzere Fahrzeiten, weniger Energieverbrauch und eine höhere Stabilität gegenüber Störungen.
Ein Beitrag von:
