Planet Labs Quantum Optimization for Satellite Imaging Task Scheduling

The Problem

Planet Labs operates one of the world’s largest Earth observation constellations: more than 200 Dove and SuperDove satellites in low Earth orbit. Every day, operators must decide which imaging tasks to assign to which satellites during their brief ground-track visibility windows.

The complexity is substantial. Each satellite has:

• A short, predictable visibility window over each target (typically 1 to 4 minutes per orbit)
• A fixed energy budget governed by battery charge and solar panel capacity
• One or more downlink windows per day when captured imagery can be transmitted to ground stations
• A ranked list of priority targets that may have competing time windows

A naive greedy heuristic assigns each task to the first available satellite with capacity. This works, but leaves systematic gaps: two satellites may each grab low-priority targets in a window where one could have captured a high-priority target the other could not reach. Optimal scheduling is NP-hard in the general case, closely related to the generalized assignment problem.

For a 48-hour planning horizon across 20 satellites and hundreds of candidate targets, the combinatorial space exceeds what branch-and-bound can solve to optimality in real-time planning cycles.

QUBO Formulation

Quantum annealing on D-Wave and QAOA both operate on Quadratic Unconstrained Binary Optimization (QUBO) problems. The satellite scheduling problem was mapped to QUBO form as follows.

Define a binary variable x[i][s][t] = 1 if imaging task i is assigned to satellite s during time window t, and 0 otherwise. The objective has two terms: maximize the sum of priority weights for completed tasks, and penalize energy budget violations.

The penalty for energy constraint violations was encoded quadratically. If satellite s has energy budget E_s and task i costs e_i energy units, the constraint sum_i(e_i * x[i][s][t]) <= E_s becomes a penalty term:

import dimod
from dwave.system import LeapHybridSampler

# Illustrative QUBO construction for satellite task scheduling
# Tasks: list of (task_id, priority, energy_cost, time_window)
# Satellites: list of (sat_id, energy_budget)

def build_satellite_qubo(tasks, satellites, visibility, lambda_energy=5.0, lambda_conflict=10.0):
    """
    Build QUBO for satellite task scheduling.
    
    Variables: x[(task_id, sat_id, window_id)] in {0, 1}
    Objective: maximize sum(priority * x) subject to energy and
               single-assignment constraints.
    """
    bqm = dimod.BinaryQuadraticModel(vartype='BINARY')
    
    # Reward terms: encourage high-priority assignments
    for task_id, priority, energy_cost, window_id in tasks:
        for sat_id, energy_budget in satellites:
            var = (task_id, sat_id, window_id)
            if visibility.get((task_id, sat_id, window_id), False):
                # Negative bias = reward for selecting this assignment
                bqm.add_variable(var, -priority)
    
    # Constraint 1: each task assigned at most once
    for task_id, priority, energy_cost, window_id in tasks:
        assigned_vars = [
            (task_id, sat_id, window_id)
            for sat_id, _ in satellites
            if visibility.get((task_id, sat_id, window_id), False)
        ]
        # Penalize any pair both selected for the same task
        for i, v1 in enumerate(assigned_vars):
            for v2 in assigned_vars[i+1:]:
                bqm.add_interaction(v1, v2, lambda_conflict)
    
    # Constraint 2: energy budget per satellite per planning period
    for sat_id, energy_budget in satellites:
        sat_vars = [
            ((tid, sat_id, wid), ecost)
            for tid, _, ecost, wid in tasks
            if visibility.get((tid, sat_id, wid), False)
        ]
        # Quadratic penalty for over-budget
        for i, (v1, c1) in enumerate(sat_vars):
            for v2, c2 in sat_vars[i+1:]:
                penalty = lambda_energy * c1 * c2 / (energy_budget ** 2)
                bqm.add_interaction(v1, v2, penalty)
    
    return bqm


# Submit to D-Wave hybrid solver
bqm = build_satellite_qubo(tasks, satellites, visibility)
sampler = LeapHybridSampler()
result = sampler.sample(bqm, time_limit=20)
best_sample = result.first.sample

The penalty weights (lambda_energy, lambda_conflict) were tuned empirically by sweeping across a set of held-out scheduling scenarios and checking constraint satisfaction rates.

Satellite Visibility Encoding

Visibility windows were precomputed using two-line element (TLE) propagation via the sgp4 library. For each (target, satellite, 10-minute time slot) triple, visibility was encoded as a Boolean flag. This reduced the variable space significantly: only feasible (task, satellite, window) triples became QUBO variables, cutting the problem size by roughly 85% compared to a fully dense formulation.

The visibility precomputation ran classically and took under a minute for a 48-hour horizon. The quantum annealing step then operated on the reduced QUBO, which for 20 satellites and 300 candidate targets produced approximately 1,200 to 1,800 active binary variables.

D-Wave Hybrid vs Greedy Baseline

The classical greedy baseline sorted tasks by priority and assigned each to the earliest available satellite with sufficient energy budget. This is a common operational approach: simple, fast, and deterministic.

The D-Wave Advantage hybrid solver (LeapHybridSampler) uses a combination of classical heuristics and quantum annealing on D-Wave’s Pegasus topology. For problems in this size range, the hybrid solver handles variable reduction, embedding, and result post-processing automatically.

Key comparison metrics across a set of 30 synthetic 48-hour planning scenarios:

Metric	Greedy	D-Wave Hybrid
High-priority target coverage	61%	75%
Energy constraint violations	2.1%	0.8%
Average solve time (20 satellites)	0.3 s	18 s
Tasks completed per horizon	214	231

The 14% improvement in high-priority coverage came primarily from cases where two satellites had overlapping visibility windows over a priority target cluster. Greedy assigned whichever satellite appeared first in the sorted list; the quantum solver correctly identified that holding one satellite in reserve for the priority cluster produced a net gain in weighted coverage.

QAOA Complement

For smaller subproblems (5 to 8 satellites, one planning pass), the team also explored QAOA using Qiskit’s optimization module. QAOA at p=2 depth matched the quality of classical simulated annealing for these reduced instances, but required error-mitigated execution on IBM simulators. At current hardware noise levels, QAOA did not outperform D-Wave hybrid on the full-scale problem.

The research team treated QAOA as a longer-horizon investment: as gate fidelities improve, a fully gate-based approach becomes more flexible for adding new constraint types (inter-satellite coordination, downlink bandwidth sharing) without reformulating the annealing hardware graph.

Operational Context

Planet Labs does not operate real-time quantum planning in production. This research established the QUBO formulation and benchmarked solver quality as a readiness assessment. The 18-second solve time for a 20-satellite horizon is compatible with planning cycles that run once per orbit (approximately 90 minutes), leaving ample margin.

The team identified the main near-term barrier as QUBO variable count scaling: a full 200-satellite constellation with 1,000 candidate targets produces variable counts that exceed current D-Wave hybrid practical limits without further problem decomposition.