Quantum Algorithms applied to Satellite Mission Planning for Earth Observation

Efficient satellite mission planning is crucial for maximizing the utilization of expensive and complex Earth-orbiting satellites. These satellites provide essential services such as connectivity, navigation, and media, but their deployment and operation present significant computational challenges. The core problem is optimizing the sequence of tasks—image acquisitions in this case—to maximize the number of completed tasks within available time and resource constraints. Classical optimization and reinforcement learning algorithms offer some solutions, but they can become computationally prohibitive for large-scale missions involving numerous tasks and multiple satellites. This research explores the potential of quantum computing to address these limitations. While some prior work has investigated quantum approaches to satellite scheduling, they have not demonstrated a practical advantage over classical methods. This work differs by focusing on a hybrid approach combining classical and gate-based quantum computing algorithms, leveraging the strengths of both to overcome limitations in current quantum hardware. This hybrid approach has shown promising results in prior work by some of the authors, and this paper seeks to extend those findings to the challenging domain of satellite mission planning for Earth observation.

Existing literature explores various classical optimization and machine learning techniques for satellite mission planning. Studies have employed deep reinforcement learning, ant colony optimization, and simulated annealing algorithms to optimize task scheduling and image selection. However, many of these methods struggle with the computational complexity inherent in large-scale missions. Some research has investigated the use of quantum annealers for solving this type of scheduling problem, but without demonstrating a clear advantage over classical alternatives. This paper builds on previous work demonstrating practical application-specific advantages of hybrid quantum computing, specifically in the context of machine learning model optimization. This previous research motivates the current study's hybrid approach combining classical and quantum algorithms, aiming for tangible improvements in solution quality and efficiency for satellite mission planning.

This research employs three primary algorithmic approaches to address the satellite mission planning problem: a greedy baseline algorithm, classical optimization methods, and quantum-enhanced reinforcement learning. 1. **Data Formatting and Preprocessing:** The input data comprises information on satellite motion (position, velocity, timestamps) and acquisition requests (ID, priority, DTO windows, coordinates). The requests are clustered using both simple bunching algorithms (DTO bunching, priority bunching, bunch sort) and the K-means algorithm to reduce computational complexity. 2. **Greedy Algorithm:** This baseline algorithm serves as a point of comparison. It iteratively selects the highest-priority request within an available DTO window, considering the time required for satellite rotation (relaying time) and acquisition. The algorithm’s simplicity facilitates quick execution but limits its ability to anticipate optimal future task selections. 3. **Optimization Methods:** An integer optimization model is formulated, encoding the problem as a maximization problem subject to constraints on satellite movement, DTO windows, and acquisition times. This model uses the Orekit space flight dynamics library for accurate calculations of attitude pointing, acquisition duration, and maneuver duration. The model is structured to be adaptable to QUBO (quadratic unconstrained binary optimization) formulation, suitable for quantum annealing machines. The model is solved using the Gurobi solver. 4. **Reinforcement Learning:** Two reinforcement learning environments are designed: a satellite-centric environment and a request-centric environment. The PPO (Proximal Policy Optimization) algorithm is utilized to train the reinforcement learning agents. A hybrid quantum-classical neural network, incorporating a parameterized quantum circuit (PQC), is developed as a policy model for improved performance. The hybrid AlphaZero algorithm, which leverages Monte Carlo Tree Search (MCTS), is also implemented, combining classical and quantum components to further enhance the reinforcement learning approach.

The research evaluates the performance of the different algorithms on two datasets: a single-satellite dataset with 462 requests and a two-satellite dataset with 2000 requests. The focus is primarily on the completion rate of high-priority (π1) requests. 1. **Greedy Algorithm:** On the two-satellite dataset, the greedy algorithm achieves a π1 completion rate of 75.8%, while the performance with K-means clustering drops to 63.6%. On the single-satellite dataset, performance is better, but still provides a baseline for comparison. 2. **Optimization Algorithm:** Using the Gurobi solver, the integer optimization model achieves a π1 completion rate of 98.1% on the two-satellite dataset and 100% for π1, π2, and π3 requests (96.2% for π4) on the single-satellite dataset. While QUBO formulation was explored, the current limitations of quantum devices hindered its practical application in this context. 3. **Reinforcement Learning:** The hybrid quantum-enhanced PPO agent shows notable improvement over the classical counterpart in terms of learning speed and reward achievement. The hybrid AlphaZero algorithm, combining MCTS with a quantum policy network, exhibits the highest performance, reaching a π1 completion rate of 98.5% on the two-satellite dataset. This demonstrates a significant improvement over the greedy baseline and comparable performance to the optimization method.

The results clearly demonstrate that both optimization and hybrid quantum-enhanced reinforcement learning methods significantly outperform the greedy baseline in the satellite mission planning problem. The hybrid AlphaZero algorithm shows the most promising performance, achieving a near-optimal solution with a 98.5% π1 completion rate. This improvement is attributed to the combined strengths of MCTS, which allows for exploration of a large solution space, and the quantum-enhanced policy network, which may offer advantages in learning complex decision-making strategies. While the QUBO-formulated optimization model is theoretically suited to quantum annealing, practical limitations of current quantum devices prevent its direct application in this experiment. The success of the hybrid reinforcement learning approach underscores the potential of integrating quantum computing into classical algorithms to address complex optimization challenges in the space industry and other related fields.

This research showcases the efficacy of quantum-enhanced algorithms for satellite mission planning. Hybrid approaches, combining classical optimization/reinforcement learning with quantum components, demonstrate significant improvements in task completion rates over classical baselines. The hybrid AlphaZero algorithm stands out, achieving near-optimal performance. Future research could investigate the application of these methods to larger-scale, more realistic satellite constellations and explore the utilization of more advanced quantum computing hardware as it becomes available. Further investigation of different QUBO solving approaches and the design of specialized quantum algorithms for this task may lead to even greater efficiency and optimality.

The study uses simulated satellite dynamics and simplified models of satellite maneuvers and acquisition constraints. The computational cost of the optimization algorithm could be a limiting factor for very large-scale problems. The implementation of the QUBO formulation was limited by the capabilities of current quantum hardware. Future research should address these limitations by using more detailed, real-world data and exploring advanced scaling techniques for the algorithms.