RT Conference Proceedings
T1 Optimization of Image Acquisition for Earth Observation Satellites via Quantum Computing
A1 Makarov, Antón
A1 Taddei, Márcio M.
A1 Osaba, Eneko
A1 Franceschetto, Giacomo
A1 Villar-Rodríguez, Esther
A1 Oregi, Izaskun
A2 Quaresma, Paulo
A2 Gonçalves, Teresa
A2 Camacho, David
A2 Yin, Hujun
A2 Julian, Vicente
A2 Tallón-Ballesteros, Antonio J.
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.
PB Springer Science and Business Media Deutschland GmbH
SN 9783031482311
SN 0302-9743
YR 2023
FD 2023
LK https://hdl.handle.net/11556/2799
UL https://hdl.handle.net/11556/2799
LA eng
NO Makarov , A , Taddei , M M , Osaba , E , Franceschetto , G , Villar-Rodríguez , E & Oregi , I 2023 , Optimization of Image Acquisition for Earth Observation Satellites via Quantum Computing . in P Quaresma , T Gonçalves , D Camacho , H Yin , V Julian & A J Tallón-Ballesteros (eds) , Intelligent Data Engineering and Automated Learning – IDEAL 2023 - 24th International Conference, Proceedings . Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) , vol. 14404 LNCS , Springer Science and Business Media Deutschland GmbH , pp. 3-14 , 24th International Conference on Intelligent Data Engineering and Automated Learning, IDEAL 2023 , Évora , Portugal , 22/11/23 . https://doi.org/10.1007/978-3-031-48232-8_1
NO conference
NO Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.
NO This work was supported by the Government of Spain (Misiones CUCO Grant MIG-20211005, FIS2020-TRANQI and Severo Ochoa CEX2019-000910S), Fundació Cellex, Fundació Mir-Puig, Generalitat de Catalunya (CERCA program), and by the European Research Council ERC AdG CERQUTE.
DS TECNALIA Publications
RD 28 jul 2024