Data-driven Onboard Scheduling for an Autonomous Observation Satellite

Chao Li, Yingwu Chen, Patrick De CausmaeckerIJCAI 2018 · DOI

TL;DR

This paper tackles the challenge of efficiently scheduling observations for autonomous satellites with limited onboard computing power. They propose a novel data-driven approach that uses a trained neural network to prioritize observation requests, significantly improving the total profit of completed observations compared to traditional greedy methods.

What Problem Does This Paper Address?

Autonomous observation satellites are increasingly tasked with dynamically responding to new targets and unexpected events. This requires sophisticated onboard decision-making, particularly in scheduling observations. However, these satellites operate under severe computational constraints, making it difficult to run complex optimization algorithms in real-time. Traditional methods often rely on simple heuristics that might not maximize the satellite's scientific return (e.g., total profit from observations). The core problem is how to achieve near-optimal scheduling performance with limited onboard resources, adapting to a constantly changing stream of observation requests.

Methods

The authors introduce a two-phase data-driven onboard scheduling method:

  • Offline Learning Phase: This phase occurs on the ground where computational resources are abundant.
  • Genetic Algorithms (GA): Used to generate "optimized historical schedules" from past observation data. This serves as a gold standard for training.
  • Feature Extraction: Key attributes of observation requests (profit, time windows, conflicts) and satellite status (angle, storage, energy) are extracted.
  • Request Filter Training: A back-propagation (BP) neural network classifier is trained on this extracted data. The network learns to predict a "label" (positive/negative) indicating whether a request was successfully included in the GA-optimized schedules. This trained network acts as a "request filter."
  • Onboard Scheduling Phase: This phase runs on the satellite with limited resources.
  • Priority Assignment: The trained "request filter" is used to assign priorities to incoming observation requests based on their features and the satellite's current state.
  • Heuristic Scheduling: A greedy heuristic, based on the earliest possible start time of requests (with O(n²) complexity), is then applied. Crucially, this heuristic now uses the priorities assigned by the data-driven request filter, meaning higher-priority requests are considered first.

The novelty lies in using a pre-trained AI model (the request filter) to guide a computationally inexpensive onboard heuristic, effectively injecting intelligence learned offline into real-time decision-making.

Datasets

The paper describes simulations using dynamically generated observation requests within a 45-minute simulation period. No specific public datasets are mentioned; rather, the authors generated their own simulation data for evaluation.

Key Insights and Ideas

  • Bridging the Gap: The core idea is to leverage powerful offline optimization (like GA) to create a "knowledge base" and then distill that knowledge into a lightweight AI model (neural network) that can run efficiently onboard.
  • Intelligent Prioritization: Instead of just relying on simple rules (like earliest start time), the data-driven approach allows the satellite to learn which requests are more likely to contribute to a high-profit schedule based on historical patterns.
  • Computational Efficiency: The trained neural network's prediction is a simple sum of products, making it computationally very cheap to run onboard. This allows the satellite to make more informed decisions without exceeding its resource limits.

Key Results

The simulations compared the proposed Data-Driven Onboard Scheduling (DDOS) method against a standard Greedy Heuristic Scheduling (GHS) method.

  • Profit Improvement: DDOS achieved at least a 23% higher total profit than GHS in scenarios with 50 and 70 requests, where not all requests could be completed.
  • Scalability: The performance difference became more pronounced as the number of dynamic observation requests increased.
  • Speed: Both DDOS and GHS were found to be fast, indicating that the data-driven approach does not introduce significant computational overhead during the onboard execution phase.

Limitations and Future Work

  • Limitations: The paper acknowledges that the offline scheduling (using GA) is computationally demanding and not suitable for onboard execution. The current onboard heuristic is a greedy method, which, while improved by prioritization, is still a heuristic and not guaranteed to be globally optimal.
  • Future Work:
    • Explore incorporating more advanced heuristics, such as local search, into the data-driven framework to further enhance optimization.
  • Investigate features for training even more accurate classification models.
  • Apply the proposed method to other domains, like multi-satellite scheduling and general machine scheduling problems.

Summary updated

BibTeX
@inproceedings{li2018data,
  author = {Chao Li and Yingwu Chen and Patrick De Causmaecker},
  title = {{Data-driven Onboard Scheduling for an Autonomous Observation Satellite}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/830},
}
Figure