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

Technical Deep Dive: An Effective Genetic Programming Hyper-Heuristic for Uncertain Agile Satellite Scheduling

Overview

This work addresses the Uncertain Agile Earth Observation Satellite Scheduling Problem (UAEOSSP), a novel problem that accounts for various uncertainties such as task profit, resource consumption, and task visibility. The authors propose an effective Genetic Programming Hyper-Heuristic (GPHH) method to automatically generate robust scheduling policies that can adapt to dynamic conditions.

Problem & Context

• Traditional satellite scheduling relies on ground control, leading to issues like lengthy scheduling cycles, poor timeliness, and weak resilience to interference.
• Agile Earth Observation Satellites (AEOS) offer greater flexibility with 3 degrees of freedom (roll, pitch, yaw), allowing them to adjust their posture rapidly and observe tasks for longer time windows.
• However, AEOS face numerous uncertainties during task execution, such as varying task profit, resource consumption, and task visibility.
• Conventional scheduling methods may produce pre-planned solutions that deteriorate or become infeasible under uncertain conditions.

Methodology

UAEOSSP Model

• The UAEOSSP model accounts for uncertainties in task profit, resource consumption, and task visibility.
• Decision variables include whether to observe a task, the observation start and end times, and the next task to observe.
• The objective is to maximize the expected total profit over all scheduling scenarios.

Genetic Programming Hyper-Heuristic (GPHH)

• GPHH is used to automatically generate effective scheduling policies that can be embedded in a dynamic scheduling algorithm.
• The GPHH process involves:
  1. Initializing a population of scheduling policy individuals represented as executable programs or expression trees.
  2. Evaluating the performance of each policy using a dynamic scheduling algorithm on a mini-batch of training instances.
  3. Applying genetic operators (selection, crossover, mutation) to evolve the population.
  4. Evaluating the final policies on a test set.

Dynamic Scheduling Algorithm

• The dynamic scheduling algorithm constructs feasible solutions based on the evolved scheduling policies.
• It includes mechanisms to:
  • Rapidly filter out infeasible tasks.
  • Efficiently compute the earliest observable time window for each candidate task using binary search.

Data & Experimental Setup

• The authors generated a set of UAEOSSP instances based on a simulated AEOS scenario using STK.
  • Task profit and resource consumption were modeled using Gamma distributions.
  • Task visibility was represented as a binary variable.
• The experiments compared the GPHH approach against two types of heuristics:
  1. Look-Ahead Heuristics (LAHs): Greedy rules that consider a limited number of future tasks.
  2. Manually Designed Heuristics (MDHs): Rules based on expert knowledge.

Results

• The scheduling policies generated by GPHH achieved an average improvement of 5.03% compared to LAHs and 8.14% compared to MDHs across the test instances.
• GPHH outperformed the comparison algorithms consistently across instances with varying task scales (50, 100, 150, 200 tasks).

Limitations & Uncertainties

• While GPHH demonstrated strong performance, the evolved scheduling policies can be complex and less interpretable compared to manually designed heuristics.
• The authors note that the practicality of the algorithm needs to be further validated using real satellite scheduling data.

What Comes Next

• Future research will focus on developing methods to generate more interpretable scheduling policies while maintaining high performance.
• The authors plan to collaborate with satellite operators to obtain real-world data and further validate the practicality of the proposed approach.