Table of Contents -- Index -- PS reprint -- PDF reprint

Astronomical Data Analysis Software and Systems VII
ASP Conference Series, Vol. 145, 1998
Editors: R. Albrecht, R. N. Hook and H. A. Bushouse

Achieving Stable Observing Schedules in an Unstable World

M. Giuliano
Space Telescope Science Institute, 3700 San Martin Drive Baltimore, MD 21218 USA

 

Abstract:

Operations of the Hubble Space Telescope (HST) require the creation of stable and efficient observation schedules in an environment where inputs to the plan can change daily. A process and architecture is presented which supports the creation of efficient and stable plans by dividing scheduling into long term and short term components.

       

1. Introduction

Operations of the Hubble Space Telescope (HST) require the creation and publication of stable and efficient observation schedules in an environment where inputs to the plan can change daily. Efficient schedules are required to ensure a high scientific return from a costly instrument. Stable schedules are required so that PIs can plan for coordinated observations and data analysis. Several factors complicate creating efficient and stable plans. HST proposals are solicited and executed in multi-year cycles. Nominally, all the accepted proposals in a cycle are submitted in a working form at the beginning of the cycle. However, in practice, most proposals are reworked based on other observations, or updated knowledge of HST capabilities. Another source of instability is due to changes in HST operations. As HST is used the capabilities of some components degrade (e.g., the solar panel rotation engines), and some components perform better than expected (e.g., decreases in acquisition times). Changes in component performance lead to different operation scenarios and different constraints on observations. A plan created with one set of constraints may no longer be valid as operations scenarios are adjusted based on an updated knowledge of HST capabilities. A final source of plan instability is that the precise HST ephemeris is not known more than a few months in advance. As a result highly constrained observations cannot be scheduled with accuracy until the precise ephemeris is known. Given these factors, it is not possible to create a single static schedule of observations. Instead, scheduling is considered as an ongoing process which creates and refines schedules as required.

A process and software architecture is presented which achieves stable and efficient observation schedules by dividing the task into long term and short term components. The process and architecture have helped HST obtain sustained efficiencies of over 50 percent when pre-launch estimates indicated a maximum of 35 percent efficiency. The remainder of the paper is divided as follows. Section 2 presents the architecture. Section 3 discusses observation planning as a process and discusses more details on the long range planner as implemented by the SPIKE software system (Johnston & Miller 1994). Section 4 evaluates the approach by comparing the system to other approaches.

2. An Architecture for Creating Efficient and Stable Schedules

Efficient and stable observation schedules are created by dividing the scheduling process into long range planning and short term scheduling. The long range planner creates approximate schedules for observations and handles global optimization criteria, and stability issues. The short term scheduler produces precise one week schedules using the approximate schedule produced by the long range planner as input.

The long range planner creates 4-8 week plan windows for observations. A plan window is a subset of an observation's constraint windows, and represents a best effort commitment by the observatory to schedule in the window. Plan windows for different observations can be overlapping. In addition the windows for a single observation can be non-contiguous. Figure 1 shows sample plan windows for six observations. Constraint windows are long term limitation as to when an observation can be executed due to physical and scientific constraints. Constraint windows include sun avoidance, moon avoidance, user window constraints, phase constraints, roll constraints, guide star constraints, and time linkages between observations. The long range planner picks plan windows based on balancing resources (e.g., observing time, observations which can hide the SAA), and optimizing observation criteria (e.g., maximizing orbital visibility, maximizing CVZ opportunities, maximizing plan window size, minimizing stray light, minimizing off-nominal roll).

The short term scheduler builds efficient week long observation schedules by selecting observations which have plan windows open within the week. The short term scheduler is responsible for keeping track of which observations have already been scheduled in past weeks.

Figure 1 shows a schedule with 6 observations with windows in weeks 1-8. The figure shows that observations 1,2,3, and 5 are potential candidates for scheduling in week 4.

3. Scheduling as a Process

The scheduling process, as illustrated in Figure 2, is an ongoing effort. The long range planner is executed nightly to incorporate the changes made to observing programs during the day. Each week a short term schedule is created which is executed on HST 3 weeks later. Although the long range planner is executed nightly, it must ensure that the resulting plan is stable.

Stability is achieved by considering the long range planner as a function which maps a set of input observing programs, search criteria, and a previous long range plan into a new long range plan. The long range planner partitions observations into those which have windows assigned in the input LRP and those which do not have input windows. In general, the scheduler will assign new windows to those observations which are not scheduled in the input plan and will pass through windows for observations which are scheduled in the input plan. The system assigns windows for observations, which are not scheduled in the input plan, in two steps. First, the system uses user defined criteria to greedily find the best window for each observation. Second, a stochastic search is used to adjust the resource levels.

There are two cases where the plan window for an observation which was planned in the input LRP is changed. First, the system has a special case for linked observations (e.g., OB1 after OB2 by 10-20 days). When the first observation of a link set is executed the system will automatically adjust the plan windows for subsequent observations in the link set based on the actual time the first observation scheduled. A second case occurs when the constraint windows for an observation change. The system measures the percentage of the plan window in the observations current constraint window. If the percentage is below a threshold then, based on a user flag, either the observation is re-planned from scratch or no plan window is written and a status flag is set in the output plan. If the percentage is above a threshold (but some of the plan window is no longer in the constraint window) then the plan window is reduced so that it overlaps with the plan window. The idea is that a minor change in an observations constraint window due to PI adjustments or changes to HST operations will not disrupt the long range plan.

The long range planner must deal with several anomalous cases. First, it may be possible that loading an observation into the system causes a crash or an error. A second anomaly occurs when the input products for an observation are not ready. In either case the problem is caught by the system and any existing plan windows are written to the output plan. A status field is marked so that the anomaly can be investigated. This approach ensures that the LRP process is stable. Problem observations do not drop out of the LRP and an error in one observation does not halt the entire process.

4. Evaluation and Comparison with other Approaches

Using plan windows to communicate between long range planning and short term scheduling has many advantages which are highlighted by contrasting this approach with others. Alternatives are: 1) Short term schedule on demand one week at a time. Do not long range plan; 2) Short term schedule the whole cycle in advance. Do not long range plan; 3) Long range plan to non overlapping bins. Short term schedule using the bin schedule as input. Short term scheduling on demand does not meet the requirement that PIs be informed in advance of the approximate time an observation will be executed. In addition, the approach may run into resource problems as greedy algorithms can schedule all the easy observations first. Short term scheduling the whole cycle in advance does, in principle, tell PIs when observations will be scheduled. However, the schedule would be very brittle. Changing a single observation would require the whole cycle to be rescheduled. The net result would be an unstable plan and lots of rescheduling work for operations staff. Short term scheduling the whole cycle at one time would also result in a combinatorial explosion in the search space effectively preventing optimization of the schedule. Long range planning to week long bins was the approach used in the first four HST observation cycles. The approach was not successful. If the long range planner filled week bins to capacity (or less) then the resulting short term schedules would be inefficient as the short term scheduler would not have the right mixture of observations to select from. If the long range planner oversubscribed week bins then the resulting short term schedules would be efficient. However, the resulting long range plan would be unstable as unscheduled observations in a week bin would have to be rescheduled. This approach would only be feasible if the long range planner knows enough of the short term scheduler constraints to produce week bins with the right mixture of observations.

The plan window approach has advantages over the other approaches. First, it supports the creation of efficient short term schedules without oversubscribing the long range plan. Efficient week long schedules can be created because overlapping plan windows provide a large pool of observations to select from. A second advantage of this approach is stability. It helps to insulate the long range plan from changes in observation specifications and HST operations. A third advantage is that it divides the problem into tractable components. The short term scheduler handles creating efficient schedules while the long range planner handles global resource optimization and stability.

References:

Johnston, M., & Miller, G., 1994, in Intelligent Scheduling, eds. Zweben, M., Fox, M. (San Francisco: Morgan Kaufmann), 391, 422

© Copyright 1998 Astronomical Society of the Pacific, 390 Ashton Avenue, San Francisco, California 94112, USA