TY - GEN
T1 - Optimization of Image Acquisition for Earth Observation Satellites via Quantum Computing
AU - Makarov, Antón
AU - Taddei, Márcio M.
AU - Osaba, Eneko
AU - Franceschetto, Giacomo
AU - Villar-Rodríguez, Esther
AU - Oregi, Izaskun
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.
PY - 2023
Y1 - 2023
N2 - Satellite image acquisition scheduling is a problem that is omnipresent in the earth observation field; its goal is to find the optimal subset of images to be taken during a given orbit pass under a set of constraints. This problem, which can be modeled via combinatorial optimization, has been dealt with many times by the artificial intelligence and operations research communities. However, despite its inherent interest, it has been scarcely studied through the quantum computing paradigm. Taking this situation as motivation, we present in this paper two QUBO formulations for the problem, using different approaches to handle the non-trivial constraints. We compare the formulations experimentally over 20 problem instances using three quantum annealers currently available from D-Wave, as well as one of its hybrid solvers. Fourteen of the tested instances have been obtained from the well-known SPOT5 benchmark, while the remaining six have been generated ad-hoc for this study. Our results show that the formulation and the ancilla handling technique is crucial to solve the problem successfully. Finally, we also provide practical guidelines on the size limits of problem instances that can be realistically solved on current quantum computers.
AB - Satellite image acquisition scheduling is a problem that is omnipresent in the earth observation field; its goal is to find the optimal subset of images to be taken during a given orbit pass under a set of constraints. This problem, which can be modeled via combinatorial optimization, has been dealt with many times by the artificial intelligence and operations research communities. However, despite its inherent interest, it has been scarcely studied through the quantum computing paradigm. Taking this situation as motivation, we present in this paper two QUBO formulations for the problem, using different approaches to handle the non-trivial constraints. We compare the formulations experimentally over 20 problem instances using three quantum annealers currently available from D-Wave, as well as one of its hybrid solvers. Fourteen of the tested instances have been obtained from the well-known SPOT5 benchmark, while the remaining six have been generated ad-hoc for this study. Our results show that the formulation and the ancilla handling technique is crucial to solve the problem successfully. Finally, we also provide practical guidelines on the size limits of problem instances that can be realistically solved on current quantum computers.
KW - D-Wave
KW - Earth Observation
KW - Quantum Annealer
KW - Quantum Computing
KW - Satellite Image Acquisition
UR - https://www.scopus.com/pages/publications/85177859904
U2 - 10.1007/978-3-031-48232-8_1
DO - 10.1007/978-3-031-48232-8_1
M3 - Conference contribution
AN - SCOPUS:85177859904
SN - 9783031482311
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 3
EP - 14
BT - Intelligent Data Engineering and Automated Learning – IDEAL 2023 - 24th International Conference, Proceedings
A2 - Quaresma, Paulo
A2 - Gonçalves, Teresa
A2 - Camacho, David
A2 - Yin, Hujun
A2 - Julian, Vicente
A2 - Tallón-Ballesteros, Antonio J.
PB - Springer Science and Business Media Deutschland GmbH
T2 - 24th International Conference on Intelligent Data Engineering and Automated Learning, IDEAL 2023
Y2 - 22 November 2023 through 24 November 2023
ER -