Solving the Agile Earth Observation Satellite Scheduling Problem with CP and Local Search

Valentin Antuori, Damien T. Wojtowicz, Emmanuel HebrardCP 2025 · DOI

TL;DR

This paper tackles the complex problem of scheduling agile Earth observation satellites (AEOS) for image acquisition and data download, especially for large constellations. They introduce a hybrid approach combining local search with a Constraint Programming (CP) solver to efficiently find high-quality schedules, outperforming existing methods on challenging instances.

What Problem Does This Paper Address?

The demand for timely satellite imagery is exploding, driving the development of larger AEOS constellations. This leads to the Earth Observation Satellite Scheduling Problem (AEOSSP), which is NP-hard and becomes even more challenging with more satellites and requests. Existing solutions often struggle with large-scale problems, lack reactivity, or don't adequately handle data download planning and satellite memory constraints. This paper addresses the need for an efficient, reactive solver capable of handling large AEOS constellations (up to 20 satellites) and complex request scenarios, while also managing onboard memory and download logistics.

Methods

The authors propose a two-part approach:

  1. Acquisition Planning: This is tackled using a local search method. It begins with a greedy algorithm to build an initial schedule. The core of the improvement comes from a local search phase that iteratively optimizes sequences of acquisitions for each satellite. Crucially, instead of relying solely on greedy heuristics for sub-problems (like finding optimal acquisition sequences), they leverage a CP-SAT solver (Tempo) to solve these sub-problems, specifically framing them as Traveling Salesman Problems with Time Windows (TSPTW). This allows for more robust optimization when greedy approaches fail.
  2. Download Planning: Once an acquisition plan is established, a greedy algorithm is used to schedule data downloads, assigning acquisitions to available download windows. This phase also includes a procedure to address potential memory overloads on satellites by solving knapsack problems.

The novelty lies in the hybrid approach: using local search for the overall problem structure and integrating a CP solver for critical sub-problems, combined with an integrated approach to acquisition and download planning.

Datasets

The authors evaluated their approach on two sets of instances:

  1. Squillaci et al. instances: These are from existing literature and consist of 32 instances with up to 1140 requests, focusing on Europe with uniform and airport-centric target distributions. They include one-shot, video, and periodic requests.
  2. Generated instances: The authors developed their own simulator to generate 20 instances. These instances feature up to 500 requests over a 6-hour horizon for a constellation of 20 satellites. They use various POI distributions (regional and worldwide) and incorporate realistic orbital parameters.

Key Insights and Ideas

  • CP-SAT for Sub-problems is Key: The paper strongly suggests that while local search is effective for the overall AEOSSP structure, using a CP solver for critical sub-problems (like TSPTW for acquisition sequencing) significantly improves solution quality, especially when greedy methods falter.
  • Integrated Planning Pays Off: Explicitly modeling and solving both acquisition and download planning, along with memory constraints, is crucial for realistic AEOS operations and doesn't significantly degrade performance compared to ignoring these aspects.
  • Instance Type Matters: The effectiveness of the CP solver (Tempo) varies by instance type. It provides significant benefits for some instances but shows less advantage on others, particularly those with periodic requests, where greedy methods might be sufficient.
  • Fail Limit Tuning is Subtle: The performance of the CP solver is not overly sensitive to the fail limit; a small limit can yield good results, indicating that the sub-problems are often solvable with limited search or are too hard for extensive search within the time constraints.

Key Results

  • Improved Solution Quality: The proposed LS-tempo method consistently finds better solutions than the baseline CP Optimizer (CPO) and often outperforms a state-of-the-art Large Neighborhood Search (LNS) method from the literature, particularly on larger and more complex instances.
  • Competitive Performance: On Squillaci et al. instances, LS-tempo achieved a 0.9% better average gap than LNS. On their own generated instances, LS-tempo was on average 0.5% better than LNS.
  • Scalability: While CPO struggles with larger instances, LS-tempo demonstrates better scalability.
  • Memory Management Impact: The inclusion of memory constraints and download planning did not significantly degrade the performance of their solver, unlike CPO which saw a 3.5% increase in average gap.

Limitations and Future Work

  • Periodic Request Instances: The authors note that their solver is not as strong on instances with only periodic requests, attributing this to a lower success rate of acquisition insertion using the CP-SAT solver.
  • CP Solver for Sub-problems: While beneficial, the CP solver (Tempo) doesn't always succeed, and the authors suggest that exploring heuristics specifically designed for TSPTW could potentially yield even better performance.
  • Future Work: The authors suggest exploring different local search moves and variations. They also mention that their CP solver currently doesn't scale well for solving the orienteering problem directly, and they aim to use it more efficiently for insertion of multiple acquisitions.

Summary updated

BibTeX
@inproceedings{antuori2025solving,
  author = {Valentin Antuori and Damien T. Wojtowicz and Emmanuel Hebrard},
  title = {{Solving the Agile Earth Observation Satellite Scheduling Problem with CP and Local Search}},
  booktitle = {CP},
  year = {2025},
  doi = {10.4230/lipics.cp.2025.3},
}
Figure