Optimization of Image Acquisition for Earth Observation Satellites via Quantum Computing

Simple item page
dc.contributor.authorMakarov, Antón
dc.contributor.authorTaddei, Márcio M.
dc.contributor.authorOsaba, Eneko
dc.contributor.authorFranceschetto, Giacomo
dc.contributor.authorVillar-Rodríguez, Esther
dc.contributor.authorOregi, Izaskun
dc.contributor.editorQuaresma, Paulo
dc.contributor.editorGonçalves, Teresa
dc.contributor.editorCamacho, David
dc.contributor.editorYin, Hujun
dc.contributor.editorJulian, Vicente
dc.contributor.editorTallón-Ballesteros, Antonio J.
dc.contributor.institutionQuantum
dc.date.accessioned2024-07-24T11:58:03Z
dc.date.available2024-07-24T11:58:03Z
dc.date.issued2023
dc.descriptionPublisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.
dc.description.abstractSatellite 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.en
dc.description.sponsorshipThis 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.
dc.description.statusPeer reviewed
dc.format.extent12
dc.identifier.citationMakarov , 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
dc.identifier.citationconference
dc.identifier.doi10.1007/978-3-031-48232-8_1
dc.identifier.isbn9783031482311
dc.identifier.issn0302-9743
dc.identifier.urihttps://hdl.handle.net/11556/2799
dc.identifier.urlhttp://www.scopus.com/inward/record.url?scp=85177859904&partnerID=8YFLogxK
dc.language.isoeng
dc.publisherSpringer Science and Business Media Deutschland GmbH
dc.relation.ispartofIntelligent Data Engineering and Automated Learning – IDEAL 2023 - 24th International Conference, Proceedings
dc.relation.ispartofseriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.relation.projectIDGovernment of Spain, MIG-20211005-FIS2020-TRANQI
dc.relation.projectIDSevero Ochoa CEX2019-000910S
dc.relation.projectIDFundación Cellex
dc.relation.projectIDEuropean Research Council, ERC
dc.relation.projectIDGeneralitat de Catalunya
dc.relation.projectIDFundación Mig-Puig
dc.rightsinfo:eu-repo/semantics/openAccess
dc.subject.keywordsD-Wave
dc.subject.keywordsEarth Observation
dc.subject.keywordsQuantum Annealer
dc.subject.keywordsQuantum Computing
dc.subject.keywordsSatellite Image Acquisition
dc.subject.keywordsTheoretical Computer Science
dc.subject.keywordsGeneral Computer Science
dc.titleOptimization of Image Acquisition for Earth Observation Satellites via Quantum Computingen
dc.typeconference output
Files