Schedule

Schedule Overview

Celest is designed for mission planning of Earth observation satellites. A key part of this problem is the scheduling of observations. The following sections describe the concept of a scheduling request, the scheduling framework, and the scheduling algorithm.

Concept of Requests

A scheduling request is a formal description of a desired observation that outlines the constraints that must be met for the observation to be viable. The parameters that govern a request include the following:

  1. The ground location of the satellite-ground encounter,

  2. The deadline for the request to be fulfilled by,

  3. The duration required for the observation,

  4. The priority of the request compared to other requests,

  5. The minimum quality of the imaging data,

  6. A specific look-angle for the observation, and

  7. The lighting condition for the request.

Schedule Class

The purpose of the scheduler is take a series of scheduling requests and find a near-optimal set of viable observations that fulfill the highest number of requests. In generating the schedule, the scheduler will ensure all request constraints are met and that there exist no conflicts between scheduled observations. The Scheduler class documentation can be found below and an example usage can be found in the Scheduling Workflow tutorial.

The Scheduler class can be imported via the following:

from celest.schedule import Scheduler
class Scheduler(satellite, vis_threshold)

Bases: ALNS

Encounter scheduler.

This class implements an adaptive large neighborhood search metaheuristic for scheduling satellite observations.

Parameters

  • satellite (Satellite) – The satellite executing the scheduled observations.

  • vis_threshold (float) –

    Visibility threshold in degrees.

    The visibility threshold is the minimum elevation angle of the satellite as seen from location where the satellite will be in visual range of location.

add_request(location, deadline, duration, priority, quality, look_ang=None, lighting=Lighting.DAYTIME)

Add a request to be scheduled.

Parameters

  • location (GroundLocation) – The location associated with the encounter.

  • deadline (float) – The deadline for the request to be scheduled by in the jd2000 epoch.

  • duration (float) – The desired duration of the encounter in seconds.

  • priority (int) – The priority of the request on a scale of 1 to 10 where higher priority requests are scheduled first.

  • quality (int) – The quality of the request on a scale of 1 to 10. A higher quality request will occur with a smaller look_angle. For imaging requests, the imaging will be taken closer to nadir for a higher quality.

  • look_ang (float, optional) – The desired look angle of the encounter in degrees, default is None.

  • lighting (Lighting, optional) – The lighting condition of the encounter, default is DAYTIME.

Return type

None

generate(max_iter, annealing_coeff, react_factor)

Generate the schedule for the given satellite and requests.

Parameters

  • max_iter (int) – The maximum number of iterations to perform in search for an improved solution.

  • annealing_coeff (float) – The annealing coefficient between 0 and 1 for the simulated annealing process.

  • react_factor (float) –

    Decay parameter within the range [0, 1].

    The decay parameter dictates the effect of previous iterations on the current iteration. A react_factor of 1 will cause the algorithm to ignore previous iterations and a react_factor of 0 will cause the algorithm to only consider the previous iterations.

Returns

A container holding the scheduled windows.

Return type

WindowCollection

Scheduling Algorithm

The scheduling algorithm used by the Scheduler class is an adaptive large neighborhood search (ALNS) metaheuristic with a simulated annealing acceptance criterion and is adapted from the work of Xiaolu Liu, et al. (2017). [Liu+17] The following gives a brief overview to the algorithm which can be read in greater detail from the paper by Liu et al. [Liu+17]

Liu+17(1,2)

Xiaolu Liu et al. “An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time”. en. In: Computers Operations Research 86 (Oct. 2017), pp. 41–53. issn: 03050548. doi: 10.1016/j.cor.2017.04.006. url: https://linkinghub.elsevier.com/retrieve/pii/S0305054817300977.

Initial Solution

The scheduling algorithm measures the quality of a solution by the sum of scheduled request priorities (i.e. the objective function). That is, the goal of the algorithm is to determine the highest sum of priorities of all scheduled observations. As a result, a good initial solution is greedy one. The Scheduler’s ALNS algorithm sorts all requests in decreasing order by priority and then in increasing order of start time; the scheduler then attempts to schedule all tasks in order whilst adhering to the request constraints. The resulting solution is taken to be the initial solution.

Note that if all requests are scheduled in the initial solution, the algorithm stops and returns the initial solution.

Scheduler Iteration

The general methodology of a neighborhood search algorithm is to create a new solution in the neighborhood of the current solution by making small modifications through the use of destroy and repair operations. In each iteration, the scheduler will apply a destroy and repair operation to the current solution to change it slightly. The cost of the resulting solution (the sum of the priorities of scheduled requests) is determined and compared to the cost of the current solution. The new solution is accepted by the simulated annealing acceptance criterion. If the new solution is better than the best solution to date, the best solution is updated.

Acceptance Criterion

A new solution is accepted or rejected based on the simulated annealing acceptance criterion. If the cost of the new solution is better than the cost of the current solution, the new solution is accepted. Otherwise, the new solution is accepted with the following probability:

\[\rho = \exp\left(\frac{100}{T}\frac{f(s)' - f(s)}{f(s)}\right)\]

where \(T\) is the current temperature, \(f(s)\) is the cost of the current solution and \(f(s)'\) is the cost of the new solution.

Allowing non-improving solutions to be occasionally accepted builds robustness against getting stuck in a local optimum.

Adaptive Strategy

The adaptive strategy of the algorithm is incorporated into the selection of the destroy and repair operations using weights. Initially the weights are all set to be equal but as the algorithm progresses, the weights are adjusted based on their impact in improving the cost of the solution. The weight for the \(i^{th}\) destroy or repair function, \(w_i\) from a total of \(H\) destroy or repair functions is adjusted using the following formula:

\[w_i = (1 - \lambda)w_i + \lambda\frac{\pi_i}{\sum_{j=1}^H\pi_j}\]

where \(\lambda\) is the reactivity number and \(\pi_i\) is the weight of the \(i^{th}\) destroy operator.

The reactivity number governs the effect that previous iterations have on the current wight and can be passed into the scheduler as a parameter. A reactivity number of one will cause the algorithm to disregard the success of the operator on previous iterations. A zero reactivity factor will prevent the wights from being updated and will retain the initial and equal weights.

Both the destroy and repair operators are chosen using a probability distribution based on the weights where the probability of each operator is defined as:

\[p_i = w_i/\sum_{j=1}^Hw_j\]