Source-linked AI summary
Agile Earth observation satellite scheduling over 20 years: formulations, methods and future directions
Xinwei Wang, Guohua Wu, Lining Xing, Witold Pedrycz
TL;DR
AEOSSP must select and schedule observation tasks to maximize observation profit under complex operational constraints, a problem made increasingly important by growing AEOS use. The paper surveys 62 articles from 1997 to 2019, organizing formulations, variations, solution methods, accomplishments, and future directions. It concludes that time-continuous models dominate, while time-discrete, multi-objective, and autonomous variants remain important research directions.
Problem
AEOSSP selects and schedules satellite observation tasks to maximize total observation profit under complex operational constraints as the number of AEOSs increases.
Method
The paper conducts an in-depth review of 62 AEOSSP articles, covering formulations, three typical variations, and exact, heuristic, metaheuristic, and machine-learning methods.
Results
The review finds that most studies use time-continuous models, while time-discrete models, multiple objectives, and autonomous AEOSSP variants have also received attention.
Takeaways & Limitations
AEOSSP research combines practical operational constraints with multiple modeling and solution perspectives, with autonomous platforms identified as promising for engineering practice.
Takeaways & Limitations
Time-continuous formulations have highly nonlinear transition-time calculations that make tractable exact methods difficult, and they allow at most one observation per visible time window.
Abstract
from arXiv · showhide
Agile satellites with advanced attitude maneuvering capability are the new generation of Earth observation satellites (EOSs). The continuous improvement in satellite technology and decrease in launch cost have boosted the development of agile EOSs (AEOSs). To efficiently employ the increasing orbiting AEOSs, the AEOS scheduling problem (AEOSSP) aiming to maximize the entire observation profit while satisfying all complex operational constraints, has received much attention over the past 20 years. The objectives of this paper are thus to summarize current research on AEOSSP, identify main accomplishments and highlight potential future research directions. To this end, general definitions of AEOSSP with operational constraints are described initially, followed by its three typical variations including different definitions of observation profit, multi-objective function and autonomous model. A detailed literature review from 1997 up to 2019 is then presented in line with four different solution methods, i.e., exact method, heuristic, metaheuristic and machine learning. Finally, we discuss a number of topics worth pursuing in the future.
1. Introduction
Agile Earth observation satellites improve observation flexibility but make scheduling substantially more complex. This survey reviews the growing, multidisciplinary AEOSSP literature and identifies future research directions.
- Motivation: The number of orbiting EOSs reached 769 in March 2019, making EOS scheduling important and attracting attention over the past 20 years.The paper links the growing satellite population with the practical importance of scheduling.
- Satellite capability: Agile EOSs maneuver along three axes, allowing multiple observation tasks within a longer visible time window when operational constraints are satisfied.Conventional EOSs are limited to a fixed visible time window, whereas AEOSs can execute multiple tasks within that interval.
- Scheduling challenge: For AEOSs, each visible time window contains multiple potential observation time windows, increasing scheduling complexity compared with conventional EOS scheduling.Conventional scheduling is treated as visible-window selection, while agile scheduling must choose among multiple feasible observation windows.
- Literature gap: The survey reviews 62 AEOSSP articles published from 1997 to 2019, including 29 articles from the preceding two years.The paper reports that no prior open-literature survey had addressed AEOSSP, partly because of its multidisciplinary character.
- Research scope: AEOSSP research spans aerospace engineering, operational research, computer science, remote sensing, and multidisciplinary sciences.This breadth reflects both the practical space-systems setting and the theoretical combinatorial-optimization perspective.
- Paper objective: The paper provides a comprehensive AEOSSP survey and identifies possible future research directions, while excluding a detailed review of the related range satellite scheduling problem.Potential integration of AEOSSP and range satellite scheduling is discussed rather than fully reviewed.
2. Agile Earth observation satellite scheduling problem
The paper formulates AEOSSP through general models for task-transition constraints, then extends them with realistic operational constraints and typical problem variations.
- General formulation: The paper presents general AEOSSP definitions and two modeling approaches for handling task-transition constraints.These basic models establish the formulation framework before extensions are introduced.
- Operational constraints: The basic AEOSSP models are extended with a series of operational constraints to represent realistic applications.The formulation accounts for practical restrictions beyond the core task-transition structure.
- Problem variations: The paper introduces three typical AEOSSP variations and concludes with a summary of formulation characteristics.The variations are presented after the general models and operational extensions.
2.1. General definitions
AEOSSP selects and sequences observation tasks to maximize total profit under transition and operational constraints. The formulations use either continuous observation start times or discretized candidate tasks, trading model compactness against tractability and flexibility.
- Problem definition: AEOSSP schedules multiple satellites’ observation tasks across targets and a scheduling horizon, with each satellite limited to one task at a time.Scheduled tasks cannot be changed, and each target has a maximum desired observation count, typically one.
- Problem definition: The objective maximizes total observation profit while satisfying target-observation limits, observation-window bounds, task transitions, and flow constraints.When every target profit equals one, maximizing profit becomes maximizing the number of scheduled targets.
- Time-continuous model: The time-continuous model introduces observation start times within visible windows and binary variables indicating whether windows are scheduled.Transition time depends on the specific windows, satellite, and target parameters.
- Time-continuous model: The continuous formulation is a mixed nonlinear integer problem that is difficult to solve exactly and permits at most one observation task per visible window.This restriction can lose the possibility of multiple observations for one target within a single visible window.
- Time-discrete model: The time-discrete model generates multiple fixed observation tasks per visible window and uses binary successor variables with dummy start and end tasks.A preprocessing step removes task pairs whose end time plus transition time exceeds the next task’s start time.
- Time-discrete model: Time discretization allows multiple observations within one visible window but substantially increases model size, making the discretization step important.Each satellite orbit is treated as a machine in a parallel-machine interval-scheduling interpretation.
2.2. Operational constraints
Operationally realistic AEOSSP formulations must handle temporal constraints and onboard resource limitations. These include visibility and transition timing, energy availability, and per-orbit data-storage capacity.
- Constraint categories: Operational constraints comprise temporal restrictions and onboard resource limitations.The resource limitations emphasized in the formulation are energy and data storage.
- Temporal constraints: Visible time windows are limited by orbit geometry and duration, while illumination and resolution requirements make their computation more difficult.The satellite must also download data to a ground station or relay satellite, although download modeling may be omitted under simplifying assumptions.
- Temporal constraints: Sufficient time must separate consecutive observations so the satellite can adjust its imaging field of view from the previous attitude.Without adequate transition time, the resulting schedule is infeasible.
- Onboard resources: The formulation assumes a constant maximum energy capacity for each satellite in every orbit and restricts observation tasks accordingly.Energy consumption includes unit-time imaging and maneuvering consumption.
- Onboard resources: Because download is not modeled, data can be transferred after each orbit, while scheduled observation data occupation is limited by per-orbit capacity.The formulation defines maximum data capacity and unit-time imaging-data occupation parameters.
- Extended formulations: The extended time-discrete formulation incorporates operational constraints into the base objective and scheduling constraints, with analogous extensions for the time-continuous model.Observation duration is included as a formulation parameter.
2.3. Variations
AEOSSP research extends the basic formulation through alternative profit definitions, multiple objectives, and autonomous decision-making. These variations address area coverage, repeated observations, competing user priorities, and real-time events.
- Different definitions of observation profit: Area targets are divided into strips, with observation profit modeled as a nonlinear convex function of acquired surface.This nonlinear profit definition significantly increases formulation complexity.
- Different definitions of observation profit: Point targets may require repeated observations for stereo or time-series applications, making profit nonlinear with respect to observation count.Examples include auroral activity surveillance and environmental assessment.
- Multi-objective function: Multi-objective AEOSSP models incorporate competing criteria such as observation profit, quality, timeliness, scheduled-target quantity, transition time, and energy consumption.These objectives reflect different users and application requirements.
- Autonomous model: Autonomous AEOSSP models allow satellites to consider incoming events dynamically rather than fixing all decisions before real-time information arrives.The reviewed approaches include cloud detection, emergency-level response, and autonomous multi-satellite coordination.
- Autonomous model: Reactive and adaptive intelligent control can support practical satellite scheduling by making decisions after the autonomous AEOS obtains real-time information.Methods proposed to accelerate response include neural networks, iterative LP, edge computing, hierarchical scheduling, and Monte Carlo Tree Search.
2.4. Summary
AEOSSP research commonly uses time-continuous formulations while also adopting time-discrete models for linearity. Recent work increasingly addresses operational constraints, multiple objectives, and autonomous platforms.
- Most AEOSSP research is based on time-continuous models, although time-discrete models are also applied because of their linearity.
- Studies increasingly incorporate complex operational constraints because they are important for practical AEOSSP applications.
- Multiple objectives have received substantial attention in recent AEOSSP research.
- Autonomous AEOSSP platforms represent a promising opportunity for engineering practice.
3. Methods
The reviewed AEOSSP literature is organized into exact, heuristic, metaheuristic, and machine-learning methods. Exact approaches address solution-quality guarantees through linearized or discretized formulations, while reported applications range from small instances to autonomous scheduling.
- The literature review classifies AEOSSP solution methods as exact method, heuristic, metaheuristic, and machine learning.
- Exact method: Heuristic methods often lack quality bounds, motivating exact B&B and MILP approaches that address nonlinear transition constraints.
- Exact method: Gabrel et al. discretize continuous VTWs into a linear directed acyclic graph, using B&B for small instances and a polynomial-time approximation for large-scale problems.
- Exact method: 35% improvement over a general greedy algorithm is reported for a two-step binary LP formulation solved with a standard MILP solver.
- Exact method: MILP formulations model multiple satellites, feasible-interval interdependencies, and operational constraints, producing optimal or near-optimal solutions in reported studies.
- Exact method: A commercial solver obtains an optimal solution within half an hour for instances with up to 55 targets, but larger target sets remain difficult.
- Exact method: An LP solver applied to an autonomous MILP model reportedly performs better than a genetic algorithm while targeting real-time scheduling.
3.2. Heuristic
Heuristic AEOSSP methods prioritize fast construction of satisfactory schedules, especially under complex constraints or real-time autonomous requirements. The literature includes greedy, dynamic-programming, insertion, distributed, and tree-search approaches.
- Heuristics speed up the search for satisfactory AEOSSP solutions and are divided into constructive and autonomous time-efficient methods.
- Constructive heuristic: Constructive heuristics can produce high-quality solutions quickly when complex operational constraints are included.
- Constructive heuristic: Priority-based heuristics with limited backtracking and download-as-needed features efficiently generate feasible plans in very short times.
- Constructive heuristic: Area-target acquisition heuristics combine geometric classification with strip partitioning to reduce strips and enlarge observation windows.
- Constructive heuristic: Graph-based approximate scheduling uses discretized observation windows and network factors, but an early version omits practical real-world constraints.
- Heuristic for autonomous model: Autonomous architectures combine reactive decision making with deliberative planning driven by an iterated stochastic greedy algorithm.
- Heuristic for autonomous model: Emergency-scheduling heuristics distinguish emergency levels and quantities through three quick-insertion algorithms.
- Heuristic for autonomous model: Edge computing distributes constructive heuristics across edge nodes, reducing total computational time according to residual-task density.
3.3. Metaheuristic
Metaheuristics constitute the majority of reviewed AEOSSP solution methods, spanning evolutionary and single-point searches. They address multi-objective, dynamic, emergency, constellation, and uncertain-cloud-coverage settings, with performance varying by instance in some studies.
- Metaheuristics form the majority of AEOSSP solution methods, with evolutionary algorithms and single-point search as the two major categories.
- Evolutionary algorithms: Genetic algorithms and ant colony optimization are widely applied because of their simplicity and efficiency, especially for multi-objective AEOSSP.
- Evolutionary algorithms: A combined genetic algorithm and simulated annealing method outperforms the standalone genetic algorithm and simulated annealing methods in simulations.
- Evolutionary algorithms: Improved ant colony optimization solves constrained travelling-salesman formulations for dynamic area-target observation with drift-angle constraints.
- Evolutionary algorithms: Multi-objective evolutionary models optimize observation profit alongside fairness, image quality, target earliness, or decision-maker preferences.
- Evolutionary algorithms: Hybrid methods combine Gauss pseudospectral optimization with genetic algorithms to address energy-dependent AEOSSP after mapping it to a dynamic TSP.
- Single-point search algorithm: Tabu-ACO jointly considers observation profit and transition time for emergency AEOSSP over one orbit period.
- Single-point search algorithm: Adaptive large-neighborhood and iterated-local-search methods dynamically assign or modify tasks; one ILS study reports a 65% average improvement over a state-of-the-art comparator.
3.4. Machine learning
Machine learning has been introduced into AEOSSP through data-driven scheduling, sequential decision-making, and parallel decomposition approaches, although operational constraints remain difficult to handle.
- Machine learning cannot yet tackle AEOSSP operational constraints.
- A deep learning-based scheduling method uses LSTM feature encoding and classification to generate scheduling schemes for faster autonomous response.
- A data-driven framework combines task assignment, scheduling, and task execution, using machine learning to provide an initial solution for a subsequent scheduling algorithm.
- A data-driven parallel approach predicts task probabilities, assigns tasks, and optimizes decomposed single-AEOSSPs in parallel.
- The parallel approach achieves better overall performance than other state-of-the-art methods on large-scale multi-AEOSSP.
4. Future directions
Future AEOSSP research should address uncertainty, integrate observation scheduling with data downloads, and model the greater capabilities and complexity of super-AEOSs.
- 4.1. Uncertain scheduling: Cloud coverage uncertainty is underrepresented in AEOSSP research, despite its reported impact on image usefulness.About 35% of Landsat-7 images were reported useless due to clouds.
- 4.1. Uncertain scheduling: Existing uncertain AEOSSP models are mainly proactive, motivating combinations with autonomous and reactive platforms and redundant observations.
- 4.2. Integrated scheduling: AEOSSP and RSSP jointly represent observation scheduling and data-download planning in practical Earth observation procedures.
- 4.2. Integrated scheduling: Separate scheduling is practical because AEOSSP is NP-hard, whereas fully integrating observation and download tasks may be intractable.
- 4.2. Integrated scheduling: Existing integrated AEOSSP attempts remain limited: one is difficult to evaluate, while another simplifies transitions and degrades to CEOSSP.
- 4.3. Super-AEOS: Super-AEOSs add nonparallel-ground-track, active pushbroom, and nonlinear-trajectory tasks through real-time attitude adjustment.
- 4.3. Super-AEOS: Super-AEOS scheduling increases complexity and may require area-target decomposition and revised observation-profit definitions, especially with uncertain observation duration.
5. Conclusions
The paper reviews AEOSSP formulations, variations, and solution methods across 62 articles, then identifies uncertainty, integration, redundancy, and super-AEOS scheduling as future priorities.
- The review covers 62 AEOSSP articles published from 1997 to 2019.
- AEOSSP selects and schedules observation tasks to maximize total observation profit under complex operational constraints, and the formulated problem is NP-hard.
- The literature is classified into exact methods, heuristics, metaheuristics, and machine learning.
- Future research should combine uncertainty-aware scheduling with autonomous platforms and investigate redundant observations for task failures.
- Integrated AEOSSP models could better represent the coupled nature of observation scheduling and data-download planning.
- Super-AEOSs may improve Earth observation system performance while greatly increasing scheduling complexity.