[Paper] An effective Genetic Programming Hyper-Heuristic for Uncertain Agile Satellite Scheduling

Source: arXiv - 2602.15070v1

Overview

The paper tackles a realistic twist on satellite task planning: the Uncertain Agile Earth Observation Satellite Scheduling Problem (UAEOSSP). By accounting for unpredictable factors such as fluctuating task profits, variable resource consumption, and uncertain visibility windows, the authors propose a Genetic Programming Hyper‑Heuristic (GPHH) that automatically learns robust scheduling policies capable of reacting to real‑time changes.

Key Contributions

• Problem formulation of UAEOSSP that explicitly models uncertainty in profit, resources, and visibility.
• Genetic Programming Hyper‑Heuristic (GPHH) framework that evolves high‑level scheduling rules rather than hand‑crafted heuristics.
• Policy‑based scheduling: the evolved policies can be executed on‑the‑fly, enabling dynamic replanning without re‑optimizing from scratch.
• Comprehensive experimental evaluation on benchmark satellite scenarios, showing statistically significant gains over both Look‑Ahead Heuristics (LAHs) and Manually Designed Heuristics (MDHs).
• Open‑source implementation (released by the authors) that can be plugged into existing satellite‑operation simulators.

Methodology

1. Modeling Uncertainty – Each observation task is described by probability distributions for profit, required energy, and visibility interval. The scheduler must maximize expected total profit while respecting resource caps (e.g., battery, memory).
2. Hyper‑Heuristic Layer – Instead of directly searching for a schedule, the system searches for rules (e.g., “if remaining energy > X and task profit > Y, prioritize this task”). These rules are expressed as small programs in a domain‑specific language.
3. Genetic Programming (GP) – A population of candidate rule sets evolves through standard GP operators (crossover, mutation, selection). Fitness is measured by running a fast simulation of the satellite over a set of stochastic scenarios and computing the average achieved profit.
4. Policy Execution – At runtime, the best‑found rule set is applied repeatedly: for each decision point (e.g., a new visibility window appears), the policy evaluates the current state and selects the next task instantly, allowing real‑time adaptation.

The approach abstracts away the low‑level combinatorial explosion of the scheduling problem and lets the evolutionary process discover effective decision logic.

Results & Findings

• The GPHH‑derived policies consistently outperformed the baselines across all tested uncertainty levels.
• Execution time per scheduling decision dropped from seconds (re‑optimizing) to milliseconds, making the method viable for on‑board processors.
• Sensitivity analysis showed the policies remained robust when the underlying probability distributions shifted, indicating good generalization.

Practical Implications

• Real‑time mission control: Satellite operators can embed the evolved policy directly on the spacecraft, enabling autonomous replanning when cloud cover, power fluctuations, or last‑minute task requests occur.
• Reduced ground‑segment load: Less frequent uplink of new schedules translates to lower communication costs and faster response to emerging observation opportunities.
• Transferable framework: The hyper‑heuristic + GP pipeline can be adapted to other resource‑constrained, uncertain scheduling domains—e.g., UAV fleet tasking, edge‑computing job allocation, or factory floor job shop scheduling.
• Developer-friendly integration: The open‑source code provides a plug‑and‑play module that accepts a task list and satellite state, returning the next task in under 5 ms on typical embedded CPUs (ARM Cortex‑A53).

Limitations & Future Work

• Scalability to larger constellations: Experiments focused on a single agile satellite; extending to multi‑satellite constellations may require hierarchical policy structures.
• Assumption of known probability distributions: In practice, the exact distributions for profit or visibility may be hard to estimate; future work could incorporate online learning to update these priors.
• Policy interpretability: While the evolved rules are compact, they can still be opaque to human engineers; integrating explainability techniques could aid validation and certification.
• Hardware validation: The authors plan to test the approach on a flight‑qualified processor to assess power consumption and real‑world latency.

---

Bottom line: By letting a genetic programming engine discover adaptable scheduling policies, this work pushes satellite task planning from static, offline optimization toward truly autonomous, uncertainty‑aware operations—an advance that could ripple into any domain where resources are tight and the future is fuzzy.*

Authors

• Yuning Chen
• Junhua Xue
• Wangqi Gu
• Mingyan Shao

Paper Information

• arXiv ID: 2602.15070v1
• Categories: cs.NE, cs.AI
• Published: February 15, 2026
• PDF: Download PDF