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

He Wang; Junyu Wu; Hui Li; Yanjie Song; Witold Pedrycz; Liang Li

cs.AIAug 25, 2026

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

Authors: He Wang, Junyu Wu, Hui Li, Yanjie Song, Witold Pedrycz, Liang Li

Organizations: 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 · Department of Electrical and Computer Engineering, University of Alberta, Edmonton, AB T6G 2R3, Canada ·

Abstract

Heterogeneous agile Earth observation satellite (AEOS) scheduling requires task selection, satellite assignment, and observation sequencing under satellite-dependent visibility windows, attitude maneuvering requirements, energy consumption, and onboard storage constraints. Since satellites differ in orbital access, maneuvering capability, and payload resources, the same task may have different feasible windows, transition costs, and resource-consumption patterns on different platforms, which increases the difficulty of unified modeling and efficient optimization. To address this problem, this paper proposes an evolutionary policy optimization framework for heterogeneous AEOS scheduling with preference-adjustable weighted objectives. In the modeling layer, assignment-based indirect encoding is combined with decoder-based equivalent-cost evaluation to retain satellite-dependent constraints while integrating task gain, energy saving, and load balance into an interpretable scalar utility. In the optimization layer, schedule decoding, population-based search, and online actor-critic operator control are decoupled, so that reinforcement learning selects high-level search operators rather than constructing schedules directly. Based on this framework, a reinforcement-learning-assisted operator-selection memetic evolutionary algorithm (RLOSMEA) is developed to coordinate global exploration, feasibility recovery, and local refinement under a limited function-evaluation budget. Experiments on different heterogeneous AEOS scenarios show that RLOSMEA achieves higher overall weighted utility and more stable convergence than representative metaheuristic baselines. Sensitivity and learning-behavior analyses further confirm the robustness of the proposed method and the effectiveness of reinforcement-learning-guided operator selection.

Figures & tables

Fig. 1: Overall scheduling process for heterogeneous AEOS systems, including visibility analysis, satellite–task assignment, scheduling optimization, and final schedule generation.

Symbol	Description
$\mathcal{S}$	Set of agile satellites
$\mathcal{T}$	Set of observation tasks
$N_{s}$ , $N_{t}$	Numbers of satellites and tasks
$x_{j}$	Assignment variable of task $j$
$y_{ij}$	Binary indicator that task $j$ is assigned to satellite $i$
$\mathcal{W}_{ij}$	Visibility window set between satellite $i$ and task $j$

TABLE I: Main notation

Fig. 2: Evolutionary policy optimization framework for heterogeneous AEOS scheduling

Action	Mode	Main Function
$\alpha_{1}$	gain-bootstrap	Gain construction
$\alpha_{2}$	rare-shaping	Rare-task enhancement
$\alpha_{3}$	repair-feasible	Feasibility recovery
$\alpha_{4}$	cluster-reorder	Conflict resolution
$\alpha_{5}$	elite-intensify	Elite exploitation
$\alpha_{6}$	diverse-explore	Diversity recovery

TABLE II: Operator-mode actions

Scenario	$N_{\mathrm{task}}$	$N_{\mathrm{sat}}$
scenario_01	100	5
scenario_02	150	5
scenario_03	200	7
scenario_04	250	9
scenario_05	300	10
scenario_06	350	12

TABLE III: Heterogeneous AEOS scenarios

Panel of Figure 6 — Fig. 3: Weighted-utility convergence curves in six representative heterogeneous scenarios. The solid curves show the mean results over 30 independent runs, and the shaded bands indicate the corresponding standard deviations.

Panel of Figure 7 — Fig. 4: Component-wise utility evolution in representative heterogeneous scenarios. The solid curves show the mean results over 30 independent runs, and the shaded bands indicate the corresponding standard deviations.

Panel of Figure 8 — Fig. 5: Mean weighted utility under different weight settings in three representative heterogeneous scenarios. The solid curves show the mean results over 30 independent runs, and the shaded bands indicate the corresponding standard deviations.

Panel of Figure 9 — Fig. 6: Component-wise response of RLOSMEA under different weight settings in three representative heterogeneous scenarios.

Fig. 7: Parameter sensitivity of RLOSMEA on representative heterogeneous scenario_04. Each marker denotes the mean objective value over repeated runs, and the shaded band indicates the corresponding standard deviation.

Panel of Figure 11 — Fig. 8: RL diagnostics of RLOSMEA in representative scenario_04

RL for Combinatorial Optimization

Reinforcement learning for combinatorial optimization learns sequential decisions and search strategies for difficult discrete problems.

See all 102 papers

Apr 14, 2026

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

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.

Mohamed-Bachir Belaid

NILU, Climate and environmental research institute, Kjeller, Norway

Constrained Optimization Learning to Optimize Remote Sensing

Ask PDF

Apr 28, 2026

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

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.

Qian Yin, Jiaxing Li, Jiaqi Cheng +23

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

Ask PDF

Mar 9, 2026

Efficient Policy Learning with Hybrid Evaluation-Based Genetic Programming for Uncertain Agile Earth Observation Satellite Scheduling

The Uncertain Agile Earth Observation Satellite Scheduling Problem (UAEOSSP) is a novel combinatorial optimization problem and a practical engineering challenge that aligns with the current demands of space technology development. It incorporates uncertainties in profit, resource consumption, and visibility, which may render pre-planned schedules suboptimal or even infeasible. Genetic Programming Hyper-Heuristic (GPHH) shows promise for evolving interpretable scheduling policies; however, their simulation-based evaluation incurs high computational costs. Moreover, the design of the constructive method, denoted as Online Scheduling Algorithm (OSA), directly affects fitness assessment, resulting in evaluation-dependent local optima within the policy space. To address these issues, this paper proposes a Hybrid Evaluation-based Genetic Programming (HE-GP) for effectively solving UAEOSSP. A Hybrid Evaluation (HE) mechanism is integrated into the policy-driven OSA, combining exact and approximate filtering modes: exact mode ensures evaluation accuracy through elaborately designed constraint verification modules, while approximate mode reduces computational overhead via simplified logic. HE-GP dynamically switches between evaluation models based on real-time evolutionary state information. Experiments on 16 simulated instance sets demonstrate that HE-GP significantly outperforms handcrafted heuristics and single-evaluation based GPHH, achieving substantial reductions in computational cost while maintaining excellent scheduling performance across diverse scenarios. Specifically, the average training time of HE-GP was reduced by 17.77% compared to GP employing exclusively exact evaluation, while the optimal policy generated by HE-GP achieved the highest average ranks across all scenarios.

Junhua Xue, Yuning Chen, Mingyan Shao +3

Genetic Programming Automated Heuristic Design Decision-Making under Uncertainty Remote Sensing

Ask PDF

Abstract

RL for Combinatorial Optimization

Explore similar work

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

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

Efficient Policy Learning with Hybrid Evaluation-Based Genetic Programming for Uncertain Agile Earth Observation Satellite Scheduling