Paper: QUARGS ‒ Quantum Reinforced ground Station Scheduling
Daniel Alexander Leidreiter · Andreas Petrak · Michael Alexander Anderle · Sven Prüfer
CSA · SpaceOps · 2025
Man betrachte eine Konstellation von n Satelliten in einer mittleren Erdumlaufbahn sowie k Bodenstationen, die über die Erde verteilt sind. Solche Satelliten benötigen halbregelmäßige Kontakte mit der Missionskontrolle, um Telekommandos zu übermitteln oder allgemeine Wartungsarbeiten durchzuführen, was über Bodenstationen geschieht. Zur Planung der Bodenstationskontakte für eine solche Konstellation müssen die möglichen Sichtbarkeiten zwischen den Satelliten-Bodenstationspaaren berechnet und dann aus diesen Daten ein gültiger Zeitplan erstellt werden, der alle missionsspezifischen Einschränkungen erfüllt. Dies ist eine typische Herausforderung für das Missionsplanungssystem einer Satellitenkonstellation. Darüber hinaus gibt es oft eine Art von relevantem Optimierungsziel, z.B. Fairnessbedingungen oder Minimierung der Gesamtzahl der Kontakte, um mehr Zeit für die eigentlichen Missionsziele zur Verfügung zu haben.
Abhängig von den Randbedingungen für solche Bodenstations-Kontaktpläne sowie der Größe von n und k kann es schwierig sein, dieses Problem optimal zu lösen. Insbesondere, wenn k viel kleiner als n ist, kann es nicht trivial sein, überhaupt eine Lösung zu finden. Für solche Probleme werden oft globale Optimierer wie Gurobi, CPLEx oder SCIP oder problemspezifische heuristische Suchalgorithmen eingesetzt, die versuchen, eine Lösung zu finden, die für praktische Zwecke gut genug ist.
Während solche Ansätze für die meisten realen Szenarien geeignet sind, haben klassische Lösungsverfahren bei sehr großen Satellitenkonstellationen Schwierigkeiten, in angemessener Zeit Lösungen zu finden. Aus diesem Grund untersuchen wir in dieser Arbeit mögliche Anwendungen von Quantencomputern für größere Instanzen dieses Problems.
Zu diesem Zweck haben wir eine Bibliothek namens QUARGS (Quantum Reinforced Ground Station Scheduling) entwickelt, die es ermöglicht, Beispiele für solche Bodenstationsplanungsprobleme mit verschiedenen Quantenalgorithmen zu lösen. In diesem Papier vergleichen und bewerten wir diese verschiedenen Lösungen untereinander sowie mit einer klassischen Lösung unter Verwendung des globalen Optimierers SCIP.
Nach einem Überblick über ähnliche Probleme in der Literatur definieren wir das konkrete Problem mit allen Nebenbedingungen und möglichen Optimierungsfunktionen. Dann geben wir einen kurzen Überblick über Quantenalgorithmen, die zur Lösung solcher Scheduling-Probleme verwendet werden können. Dazu gehören insbesondere Quantenglühen (QA), Quantenapproximativer Optimierungsalgorithmus (QAOA), Variations-Quanten-Eigensolver (VQE), sowie evolutionäre Variations-Quanten-Eigensolver (E-VQE). Insbesondere letzterer wurde in einer Open-Source-Python-Bibliothek QUEASARS (Quantum Evolving Ansatz Variational Solver) implementiert und veröffentlicht.
Neben der Evaluierung dieser Algorithmen an Fallbeispielen hinsichtlich ihrer Lösungsqualität und Quantenschaltungen
werden Schwierigkeiten bei der Implementierung verschiedener Nebenbedingungen in den Algorithmen und deren mögliche Lösungen diskutiert.
Lösungen.
CSA · SpaceOps (2025)
https://elib.dlr.de/218752/
