Applying quantum algorithms to satellite mission planning optimization
Earth imaging satellites are a crucial part of our everyday lives, impacting services such as connectivity, navigation, and media. Therefore, it is critical that satellites are employed efficiently and reliably. As they receive dynamic instructions on how to execute their mission in orbit, optimally planning the exact sequence of tasks is a complex endeavour, known as the satellite mission planning problem, which may be computationally prohibitive to solve at scale. While close-to-optimal algorithms such as greedy reinforcement learning and optimization algorithms can be used to address this problem, through Terra Quantum’s work with Thales Group, we introduce a quantum-enhanced approach to satellite mission planning optimization using hybrid quantum algorithms in the areas of machine learning and optimization, demonstrating their superior performance and potential for unlocking significant additional revenue.
Key takeaway
A hybridized quantum-enhanced reinforcement learning approach achieves a completion rate of 98.5% over high-priority tasks, outperforming the baseline greedy methods. These results pave the way to quantum-enabled solutions in the space industry and, more generally, future mission planning problems across industries.
The problem
The satellite mission planning problem consists of maximising the number of images captured by satellites based on a list of task requests and available time. Each task is chosen at the expense of others and has long- term effects on the orientation of the satellite as it must point its camera in the appropriate direction within its data take opportunity window for the entire acquisition period. The goal is to optimize the order of task requests, maximising the number of completed requests, given numerous constraints, including fuel, opportunity cost, and second-order consequences.
Results
- 98.5% Task completion rate, for 2 satellites tackling 2,000 requests
- 1 Improvement in solution optimality leveraging quantum-enhanced machine learning techniques
- 2x Faster calculation time versus existing optimization solutions
The approach
To solve the challenge, the satellite motion (including orbit number, time stamp, and satellite position and velocity) and task request information are collected and formatted for analysis. Then, to handle the increasing complexity of the problem, clustering was used to stratify the data and reduce the number of calculations.
This hybrid quantum approach involves:
- Hybrid optimization methods Quantum-enhanced reinforcement learning
- Hybrid optimization
Hybrid Optimization
Various hybrid optimization methods were explored, including a few different formulations derived from the quadratic unconstrained binary optimization (QUBO) model. These methods leverage quantum computing techniques to accelerate the optimization process and find the best course of action for maximizing task completion.
Reinforcement Learning
We introduced a novel quantum-enhanced reinforcement learning approach, inspired by the AlphaZero model, consisting of:
• Monte Carlo tree search
• Encoding network
• Quantum policy network
• Value network
Conclusion
Our algorithm achieves a completion rate of 98.5% on high-priority requests in a multi-satellite system, demonstrating significant improvement over the baseline greedy methods and unlocking new revenue potential for the optimization of each satellite.
These results show that Terra Quantum's hybrid quantum algorithms outperform classical approaches in satellite mission planning, overcoming the increasing complexity of scheduling high-priority tasks and demonstrating that through solution-chaining and clustering, quantum-enhanced optimization and machine learning algorithms offer the greatest potential for optimal solutions in satellite mission planning.
The way we have together tackled this problem, for instance through an initial clustering to then maximise the utility of quantum resources, is novel and interesting. - Frédéric Barbaresco, Quantum Technology Program Leader of Thales Group
If you would like to dive into the details of the joint study based on the work of Terra Quantum and Thales Group, access the technical paper here.
Rory Daniels
Rory joined techUK in June 2023 after three years in the Civil Service on its Fast Stream leadership development programme.
Laura Foster
Laura is techUK’s Associate Director for Technology and Innovation.
Elis Thomas
Elis joined techUK in December 2023 as a Programme Manager for Tech and Innovation, focusing on AI, Semiconductors and Digital ID.
