The mission planning (MP) is a crucial aspect of Earth Observation (EO) that targets the optimal scheduling of satellites’ orbits for the data collection of Earth information upon endusers' requests. This task is a complex combinatorial problem that involves the optimization of a set of variables, describing both the acquisition of target images of the Earth's surface and the subsequent downloading of the acquired information to ground stations. The MP problem can be formulated as a knapsack problem (NPhard problem), where the cost function consists of binary variables, whose optimal configuration provides the timeordered shortlist of the possible observations and downlinks  the planned mission  according to some selected constraints. This Thesis represents the output of a sixmonth internship within the research division of Thales Alenia Space Italia (TASI). Starting from a mathematical formulation of the MP problem provided by TASI, we first map the original classical problem into a groundstate search for the corresponding quantum manybody Hamiltonian, reminiscent of spin glass models. We then explore the feasibility of reaching the optimal solution for a representative set of small problem instances using quantuminspired algorithms based on Tree Tensor Networks (TTN), which allow for an efficient representation of the ground state of many body systems. This study concludes with a comparison to a Quadratic Program (QP) classical solver.
The mission planning (MP) is a crucial aspect of Earth Observation (EO) that targets the optimal scheduling of satellites’ orbits for the data collection of Earth information upon endusers' requests. This task is a complex combinatorial problem that involves the optimization of a set of variables, describing both the acquisition of target images of the Earth's surface and the subsequent downloading of the acquired information to ground stations. The MP problem can be formulated as a knapsack problem (NPhard problem), where the cost function consists of binary variables, whose optimal configuration provides the timeordered shortlist of the possible observations and downlinks  the planned mission  according to some selected constraints. This Thesis represents the output of a sixmonth internship within the research division of Thales Alenia Space Italia (TASI). Starting from a mathematical formulation of the MP problem provided by TASI, we first map the original classical problem into a groundstate search for the corresponding quantum manybody Hamiltonian, reminiscent of spin glass models. We then explore the feasibility of reaching the optimal solution for a representative set of small problem instances using quantuminspired algorithms based on Tree Tensor Networks (TTN), which allow for an efficient representation of the ground state of many body systems. This study concludes with a comparison to a Quadratic Program (QP) classical solver.
Mission Planning for Earth Observation: a Tree Tensor Network approach
DE MASI, MICHELE
2023/2024
Abstract
The mission planning (MP) is a crucial aspect of Earth Observation (EO) that targets the optimal scheduling of satellites’ orbits for the data collection of Earth information upon endusers' requests. This task is a complex combinatorial problem that involves the optimization of a set of variables, describing both the acquisition of target images of the Earth's surface and the subsequent downloading of the acquired information to ground stations. The MP problem can be formulated as a knapsack problem (NPhard problem), where the cost function consists of binary variables, whose optimal configuration provides the timeordered shortlist of the possible observations and downlinks  the planned mission  according to some selected constraints. This Thesis represents the output of a sixmonth internship within the research division of Thales Alenia Space Italia (TASI). Starting from a mathematical formulation of the MP problem provided by TASI, we first map the original classical problem into a groundstate search for the corresponding quantum manybody Hamiltonian, reminiscent of spin glass models. We then explore the feasibility of reaching the optimal solution for a representative set of small problem instances using quantuminspired algorithms based on Tree Tensor Networks (TTN), which allow for an efficient representation of the ground state of many body systems. This study concludes with a comparison to a Quadratic Program (QP) classical solver.File  Dimensione  Formato  

DeMasi_Michele.pdf
accesso aperto
Dimensione
1.48 MB
Formato
Adobe PDF

1.48 MB  Adobe PDF  Visualizza/Apri 
The text of this website © Università degli studi di Padova. Full Text are published under a nonexclusive license. Metadata are under a CC0 License
https://hdl.handle.net/20.500.12608/64899