Optimizing Earth Observation Satellite Schedules under Unknown Operational Constraints: An Active Constraint Acquisition Approach

Mohamed-Bachir Belaid

cs.AIApr 14, 2026

Optimizing Earth Observation Satellite Schedules under Unknown Operational Constraints: An Active Constraint Acquisition Approach

Authors: Mohamed-Bachir Belaid

Organizations: NILU, Climate and environmental research institute, Kjeller, Norway

Abstract

Earth Observation (EO) satellite scheduling (deciding which imaging tasks to perform and when) is a well-studied combinatorial optimization problem. Existing methods typically assume that the operational constraint model is fully specified in advance. In practice, however, constraints governing separation between observations, power budgets, and thermal limits are often embedded in engineering artefacts or high-fidelity simulators rather than in explicit mathematical models. We study EO scheduling under unknown constraints: the objective is known, but feasibility must be learned interactively from a binary oracle. Working with a simplified model restricted to pairwise separation and global capacity constraints, we introduce Conservative Constraint Acquisition~(CCA), a domain-specific procedure designed to identify justified constraints efficiently in practice while limiting unnecessary tightening of the learned model. Embedded in the Learn&Optimize framework, CCA supports an interactive search process that alternates optimization under a learned constraint model with targeted oracle queries. On synthetic instances with up to 50tasks and dense constraint networks, L&O improves over a no-knowledge greedy baseline and uses far fewer main oracle queries than a two-phase acquire-then-solve baseline (FAO). For $n\leq 30$ , the average gap drops from 65--68% (Priority Greedy) to 17.7--35.8% using L&O. At $n{=}50$ , where the CP-SAT reference is the best feasible solution found in 120s, L&O improves on FAO on average (17.9% vs.\ 20.3%) while using 21.3 main queries instead of 100 and about $5\times$ less execution time.

Figures & tables

$n$	$H$	$\|\mathrm{sep}_{T}\|$	$k$	$w$	$\|B_{0}\|$	CP-SAT ref
10	30	13	2	6	${\approx}430$	optimal
20	60	57	2	12	${\approx}1{,}735$	optimal
30	90	130	4	18	${\approx}3{,}940$	optimal
40	120	234	5	24	${\approx}7{,}045$	best/120s $\dagger$
50	150	367	6	30	${\approx}11{,}050$	best/120s $\dagger$

Table 1: Instance statistics (averaged over 20 seeds). Separation density

{\approx}30\%

of all task pairs.

|B_{0}|

is the initial candidate basis size before vacuous pruning and

k

and

w

are the hidden capacity limit and window width of the true constraint

\mathrm{cap}(k,w)

$n$	Method	Gap%	Main queries	$q^{*}$	Time	Speedup
10	FAO	18.5 (±6.4)	100	—	2.1s	—
10	L&O	17.7 (±5.9)	5.3	5.3	0.1s	21 $\times$
20	FAO	35.8 (±2.1)	100	—	9.3s	—
20	L&O	35.8 (±2.1)	8.2	8.2	0.8s	11 $\times$
30	FAO	29.5 (±9.7)	100	—	40.7s	—
30	L&O	27.1 (±9.3)	14.2	14.2	5.0s	8 $\times$

Table 2: Results averaged over 20 seeds (

\pm

std). FAO : 100 acquisition queries + final CP-SAT solve (total time includes the final solve). L&O : cutoff

Q{=}100

, terminating when the current CP-SAT proposal under

L

is accepted by the oracle. Gap: relative to the CP-SAT reference (

\dagger

= best feasible in 120 s).

q^{*}

: main query at which the best solution was first found during interleaving. Speedup: FAO time / L&O time.

Figure 1: Convergence of L&O on a representative $n{=}50$ instance. Red markers indicate oracle rejections, each followed by a CCA update. The blue curve is the value returned by the time-limited CP-SAT solve under the current learned model $L$ . The black curve is the best oracle-confirmed solution found so far. The plot illustrates the typical anytime behavior of the current implementation: the constraint-model value changes as CCA refines $L$ , while the best accepted solution improves in discrete jumps and the run terminates once the current proposal under $L$ is accepted by the oracle.

Constrained Optimization

Constrained optimization finds the best decisions while satisfying equality, inequality, resource, safety, or fairness requirements.

See all 326 papers

EOS-Bench: A Comprehensive Benchmark for Earth Observation Satellite Scheduling
Apr 28, 2026Qian Yin, Jiaxing Li, Jiaqi Cheng +23Benchmark Construction Benchmark Design
School of Traﬃc and Transportation Engineering, Central South University, Changsha 410083, China · School of Engineering and Materials Science, Queen Mary University of London, London E1 4NS, UK · College of Automation, Central South University, Changsha, 410083, China +20
Why Not? Solver-Grounded Certificates for Explainable Mission Planning
Feb 28, 2026Najeeb KhanCounterfactual Explanations
Serana AI Inc., Vancouver, Canada
Reinforcement Learning-Guided Evolutionary Policy Optimization for Preference-Adjustable Heterogeneous Agile Earth Observation Satellite Scheduling
Aug 25, 2026He Wang, Junyu Wu, Hui Li +3RL for Combinatorial Optimization Multi-Objective Evolutionary Optimization
College of Intelligent Science and Engineering, Harbin Engineering University, Harbin 150001, China · School of Information Science and Technology, Dalian Maritime University, Dalian 116026, China · Silesian University of Technology (SUT), Department of Measurement and Control Systems, Gliwice, Akademicka 2, 44-100 Poland +3

Apr 28, 2026J/K move · Enter open · S save

EOS-Bench: A Comprehensive Benchmark for Earth Observation Satellite Scheduling

Qian Yin, Jiaxing Li, Jiaqi Cheng, Qizhang Luo+22

School of Traﬃc and Transportation Engineering, Central South University, Changsha 410083, China · School of Engineering and Materials Science, Queen Mary University of London, London E1 4NS, UK · College of Automation, Central South University, Changsha, 410083, China+20

Benchmark Construction Benchmark Design Remote Sensing Synthetic Benchmark Generation

Open paper AskPDF arXiv

Earth observation satellite imaging scheduling is a challenging NP-hard combinatorial optimisation problem central to space mission operations. While next-generation agile Earth observation satellites (EOS) increase operational flexibility, they also significantly raise scheduling complexity. The lack of a unified, open-source benchmark makes it difficult to compare algorithms across studies. This paper introduces EOS-Bench, a comprehensive framework for systematic and reproducible evaluation of scheduling methods. By integrating high-fidelity orbital dynamics and platform constraints, EOS-Bench generates 1,390 scenarios and 13,900 benchmark instances, spanning from small-scale validation cases to large coordination problems with up to 1,000 satellites and 10,000 requests. We further propose a scenario characterisation scheme to quantify structural difficulty based on factors such as opportunity density, task flexibility, conflict intensity, and satellite congestion. A multidimensional evaluation protocol is introduced, assessing performance across five metrics: task profit, completion rate, workload balance, timeliness, and runtime. The framework is evaluated using mixed-integer programming, heuristics, meta-heuristics, and deep reinforcement learning across both agile and non-agile settings. Results show that EOS-Bench effectively distinguishes solver performance across scales and conditions, revealing trade-offs between solution quality and computational efficiency, and providing deeper insight into scenario complexity. EOS-Bench offers a unified and extensible open testbed for advancing research in Earth observation satellite scheduling. The code and data are available at https://github.com/Ethan19YQ/EOS-Bench.

Abstract

Constrained Optimization

Explore similar work

EOS-Bench: A Comprehensive Benchmark for Earth Observation Satellite Scheduling

Why Not? Solver-Grounded Certificates for Explainable Mission Planning

Reinforcement Learning-Guided Evolutionary Policy Optimization for Preference-Adjustable Heterogeneous Agile Earth Observation Satellite Scheduling