Source-linked AI summary
A two-stage approach to satellite constellation optimization: classical and QUBO formulations
Carlo Novara
TL;DR
Designing orbits for a fixed satellite constellation to improve spatial and temporal resolution is computationally challenging. The paper proposes a two-stage method, including continuous and discretized QUBO variants. Preliminary experiments compare the continuous two-stage approach with nonlinear and Walker designs; the discretized and quantum-inspired tests are still underway.
Problem
The paper addresses how to design orbits for a fixed number of satellites to maximize spatial and temporal resolution over targets despite nonlinear, non-convex optimization and potentially exponential solution complexity.
Source: §3.5 · pp. 7–8Method
The approach first optimizes coverage and then revisit times, with a second variant discretizing orbital variables to formulate the first stage as a QUBO.
Source: §4 · p. 8, §4.1 · p. 8, §5 · p. 10Results
Preliminary experiments compare the continuous two-stage method with a general nonlinear approach and Walker designs, while tests of the discretized and quantum-inspired methods remain underway.
Source: §7 · pp. 12–13Takeaways & Limitations
The QUBO formulation is compatible with QUBO solvers and can be used directly on quantum annealers.
Source: §6 · p. 11Discretization trades computational complexity against approximation accuracy and neither removes nonconvexity nor guarantees a global optimum; the formulation also focuses on circular repeat-ground-track orbits.
Source: §3.5 · p. 7, §5 · p. 10
Abstract
from arXiv · showhide
The design of satellite constellations for Earth observation requires balancing spatial coverage, revisit time, cost, and operational complexity. This paper considers the problem of designing the orbits of a given number of Low Earth Orbit (LEO) or Very Low Earth Orbit (VLEO) satellites to maximize the spatial and temporal resolution achieved over a prescribed set of ground targets. This kind of problem is inherently nonconvex and possibly combinatorial, making its solution computationally demanding for large constellations and target sets. To address this challenge, we propose a two-stage optimization strategy that separates spatial-coverage design from temporal-resolution optimization, thereby reducing the complexity of the overall problem. Two variants of the method are developed. The first employs continuous decision variables during the spatial-optimization stage, whereas the second discretizes these variables and reformulates the problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem. The latter formulation enables the use of efficient classical QUBO solvers and is directly compatible with quantum-annealing hardware. The proposed framework provides a scalable approach to the design of heterogeneous LEO and VLEO Earth-observation constellations and establishes a pathway for exploiting emerging quantum-optimization technologies in satellite mission design. Preliminary simulation results are presented to demonstrate the effectiveness of the strategy.
1 Introduction
Earth-observation constellations must balance high spatial and temporal resolution across target sets, while accounting for coupled design choices and computational difficulty. The paper proposes separating spatial-coverage design from temporal-resolution optimization, with continuous and QUBO-based variants.
1 Introduction
- Growing demand for high spatial- and temporal-resolution imagery makes single satellites or homogeneous constellations insufficient for the anticipated Earth-observation needs.The passage points to coordinated satellite networks across different orbits, sensors, and users with competing priorities.Source: §1 · p. 1
- Given a fixed satellite count, the design problem is to maximize spatial and temporal resolution over a prescribed set of Earth targets.A related formulation seeks the minimum satellite count needed to meet prescribed spatial and temporal resolutions.Source: §1 · p. 2
- The optimization is challenging because design decisions are coupled and general solutions can have exponential or combinatorial complexity.Standard algorithms may require very long computation times or fail to produce satisfactory results.Source: §1 · pp. 1–2
- The proposed two-stage strategy optimizes spatial coverage first and temporal resolution second, with continuous-variable and discretized QUBO variants.The authors present preliminary numerical experiments to demonstrate the strategy's effectiveness.Source: §1 · p. 2
2 Preliminaries
The preliminaries establish abbreviations and variables, mathematical notation, and reference frames used to describe satellite orbits and Earth-surface geometry.
2.1 Acronyms
- The paper identifies ECI, RAAN, and VLEO as Earth-Centered Inertial, Right Ascension of the Ascending Node, and Very Low Earth Orbit.Source: §2.1 · pp. 2–3
2.2 Main parameters/variables
- The main parameters distinguish satellite and target counts, satellites per orbit, orbit revolutions, and inclination.Source: §2.2 · p. 3
2.3 Notation
- The notation section specifies vector and matrix forms, row and column indexing, all-ones matrices, identity matrices, and geodesic distance.Source: §2.3 · pp. 3–4
2.4 Reference frames
- The paper describes perifocal and ECI J2000 reference frames using their origins and selected axes.Source: §2.4 · p. 4
3 Problem setting
The problem setting specifies how orbits, ground tracks, target visits, and revisit times are represented. It formulates constellation design as a weighted optimization over orbital variables under circular repeat-ground-track assumptions.
3.1 Orbit description
- Each orbit is described by six orbital elements, and the paper uses a simple orbit equation for optimization before validating optimized orbits with a high-fidelity simulator.The simulator represents Earth gravity harmonics, atmospheric drag, solar radiation pressure, and other perturbations.Source: §3.1 · pp. 4–5
3.2 Ground-track
- A ground track is the projection of a satellite's path onto the rotating Earth's surface, represented by its longitude and latitude over time.Source: §3.2 · p. 5
3.3 Coverage
- A target visit depends on geodesic proximity to the target, and the Visit-Count matrix records how often each satellite observes each target.The paper defines mean and minimum constellation coverage from target visit counts.Source: §3.3 · pp. 5–6
3.4 Revisit time
- For circular repeat-ground-track orbits, revisit times are formed from successive target-visit instants over the design interval, with mean and maximum values used to characterize the constellation.Targets with no visits are assigned an infinite revisit-time set.Source: §3.4 · pp. 6–7
3.5 Problem formulation
- The formulation assumes circular orbits with fixed common semi-major axis and eccentricity, while inclinations, RAANs, and initial true anomalies are decision variables.A weighted objective combines spatial coverage and revisit-time criteria; the problem is nonlinear, non-convex, and has exponential complexity for a global solution.Source: §3.5 · pp. 7–8
4 Two-stage constellation optimization
The approach separates orbit-geometry design for coverage from timing adjustments for revisit performance. Stage 2 optimizes initial true-anomaly shifts while preserving the Stage 1 ground tracks through RAAN adjustments.
4.1 Stage 1: Coverage maximization
- Stage 1 maximizes ground-track coverage over orbit inclinations and RAANs, reducing the search domain by excluding initial true anomalies.The paper describes the resulting Stage 2 revisit-time optimization as a fast linear-programming problem.Source: §4.1 · p. 8
4.2 Stage 2: Revisit time minimization
- Stage 2 reduces revisit times by optimizing initial true-anomaly time shifts for the orbits obtained in Stage 1.The visit times are shifted according to each satellite's time shift, and fixed chronological ordering with a cyclic boundary condition permits a linear-programming reformulation.Source: §4.2 · pp. 8–9
- Because changing initial true anomalies changes ground tracks, Stage 2 adjusts RAANs to retain Stage 1 ground tracks while reducing revisit times.The approach also extends to multiple satellites per orbit by combining the revisit-time sets for the satellites sharing each orbit.Source: §4.2 · p. 9
5 Two-stage constellation optimization with discretized orbits
The approach discretizes inclination and RAAN to turn the first-stage coverage search into a finite combinatorial problem, then minimizes revisit times using the orbits selected in that stage. Its grid resolution trades computational size against approximation accuracy.
5 Two-stage constellation optimization with discretized orbits
- Discretizing inclination and RAAN makes the first-stage continuous, nonconvex search finite and combinatorial, while allowing broad exploration of orbital configurations.Nonlocal moves can change several discrete variables or jump between grid points without traversing intermediate configurations.Source: §5 · p. 10
- Grid spacing trades computational complexity against accuracy: coarse grids may miss the continuous optimum, while fine grids rapidly increase candidate configurations.The method does not eliminate nonconvexity or guarantee a global optimum; coarse-to-fine refinement is also possible.Source: §5 · p. 10
- In the discretized orbit approach, after Stage 1, Stage 2 is exactly the one of Section 4.2.Source: §5 · p. 10
- The method uniformly samples inclination and RAAN domains, generates orbital ground tracks, and uses a binary orbit-selection vector to calculate each target’s visit count.The grid contains N_P^2 inclination–RAAN points; the selected-orbit vector is used with the Visit-Count matrix to obtain total visits per target.Source: §5 · p. 10
- The coverage objective combines weighted mean and minimum coverage terms with a penalty that keeps the number of employed orbits near N_des.The penalty coefficient Λ is chosen sufficiently large.Source: §5 · pp. 10–11
6 Quantum-inspired constellation optimization
The quantum-inspired variant retains the two-stage design and expresses its first-stage orbit-selection problem in QUBO form. It replaces the minimum-coverage term with a surrogate because the minimum operation is not quadratic.
6 Quantum-inspired constellation optimization
- Stage 1 uses a QUBO cost of the form ξ⊤Qξ, with binary decision vector ξ and a real square matrix Q; Stage 2 remains the approach from Section 4.2.The QUBO form can be used directly on quantum annealers.Source: §6 · p. 11
- The mean-coverage contribution is recast in QUBO form, using the fact that the entry-wise square of a binary vector equals the vector itself.The passage identifies this identity as ξ² = ξ.Source: §6 · p. 11
- Because minimum coverage is not quadratic, the method uses a low-cost surrogate that promotes orbits visiting targets with relatively small visit counts.The surrogate is intended to increase minimum coverage.Source: §6 · pp. 11–12
- The authors state that quantum annealers may improve computational speed and/or solution quality compared with classical computers, rather than claiming a demonstrated improvement here.The numerical experiments reported are preliminary and the discretized and quantum-inspired tests are underway.Source: §6 · pp. 11–12
7 Simulation results
The preliminary simulations compare one-stage, two-stage, and Walker constellation designs for minimizing maximum revisit time while maintaining full target coverage. The reported setup covers randomly located targets and constellations of varying sizes; the supplied passages give no numerical outcome values.
7 Simulation results
- The authors characterize the results as preliminary, with more comprehensive simulation campaigns in progress.The simulations used Particle Swarm optimization on a specified workstation.Source: §7 · pp. 12–13
- The simulations target minimum maximum revisit time while requiring 100% coverage of all targets.They compare the general nonlinear approach, the two-stage approach, and classical Walker designs.Source: §7 · p. 13
- Tests use 10–100 randomly distributed targets and 6–25 satellites in 554.38 km repeat-ground-track orbits.Targets span latitudes −60° to 60° and longitudes −180° to 180°; discretized-orbit and quantum-inspired tests were still underway.Source: §7 · p. 13
- Runtime comparisons report mean and maximum times for the one-stage and two-stage approaches over target sets ranging from 10 to 100.The figure compares maximum revisit time against target count for Walker, one-stage, and two-stage designs at N_S = 10; the passages provide no plotted values.Source: §7 · p. 13, Table 1 · p. 13, Figure 1 · p. 13