FIGURE 1. The range of timescales for HST scheduling constraints, covering more than six orders of magnitude.
In the following we first provide a brief overview of the HST scheduling problem, then we discuss the theoretical and conceptual foundations of : Section 2.0 describes the representation of constraints as "suitability functions", Section 3.0 casts the HST problem as a constraint satisfaction problem (CSP), and Section 4.0 describes the multistart stochastic repair search strategy that is currently the primary scheduling search technique in . In Section 5.0 we discuss the HST science ground system as a whole and the role played therein by . Section 6.0 describes our operational experience and some of the lessons learned from the past two years of HST operations. Section 7.0 provides a brief overview of the adaptation of to other space- and ground-based observatories.
The HST scheduling problem ranks among the largest and most complex scheduling problems faced on a continuing basis: some 10,000 to 30,000 observations are scheduled per year and each is subject to a large number of operational and scientific constraints. Proposers can specify a variety of constraints on exposures in order to express scientific goals: these include relative timing requirements such as precedence, minimum and maximum time separations, ordering, interruptibility and repetition. Some observations must be executed within a certain absolute time interval. Proposers may constrain the orientation of an instrument's aperture relative to the target or require an observation to be made while the HST is in the Earth's shadow. In order to provide flexibility, proposers can mark exposures as "conditional" or "select": "conditional" exposures are contingent upon the results obtained from another exposure in the observing program, or, in some cases, upon the results obtained from ground-based observations. These exposures are not scheduled until the proposer has notified the STScI that the condition has been satisfied. The "select" capability allows the proposer to identify alternative sets of exposures from which one or more will be picked for execution. As with "conditional" exposures, exposures contained in "select" sets will be placed on a timeline only after the proposer informs the STScI of a decision.
The HST spacecraft and its associated ground system components introduce a number of scheduling constraints as well. The observatory is in a low earth orbit (590 km) with the result that the Earth typically blocks the line of sight to a target for slightly less than half of each 95 minute orbit. Targets within a few degrees of the orbital poles are not occulted by the Earth and are suitable for uninterrupted observations. Due to precession of the orbit, the orbital poles move around the sky with a 56 day period, with the result that a target is available for extended observation for no more than about 3 days in each precessional period. When passing over South Atlantic Ocean, the HST encounters a portion of the Earth's radiation belt (called the South Atlantic Anomaly, or SAA) during which instrument operations must be suspended. Sources of bright light such as the Sun, Moon and illuminated Earth must be avoided. Thermal and power restrictions limit how the telescope can be oriented, in order to keep adequate sunlight on the solar panels and off the surfaces which radiate heat.
The primary resource constraint for HST scheduling is the amount of observing time available. Other resources which must not be exceeded include the amount of data which can be processed by the communications and ground systems, onboard tape recorder storage, and onboard command computer storage.
Although the HST operates largely in a preplanned mode (with schedules fixed about two months in advance of execution), disruptions to the schedule occur for a variety of reasons. The most welcome disruptions are so-called "targets of opportunity", which are rare, important astronomical events requiring immediate attention (e.g. a supernova). Other schedule disruptions result from spacecraft anomalies, loss of communications contacts, and changes in observing programs.
Figure 1 illustrates schematically the range of constraint timescales for HST. The interaction of so many constraints on varying timescales makes it impossible to identify any one dominant scheduling factor. Many of the constraints are periodic with different periods and phases. As a consequence there are generally several opportunities during a year to make a particular observation and a prime goal of HST scheduling is to make an optimal choice among these opportunities for as many observations as possible. This effort is complicated by the fact that the majority of the requested exposures have timing, grouping, repetition, or ordering constraints that couple very strongly with the time-dependent constraints of Figure 1. More extensive discussions of the HST scheduling problem may be found in Miller et al. (1987, 1988) and Johnston (1988a, 1989b, 1990).
FIGURE 1. The range of timescales for HST scheduling constraints, covering more than six orders of magnitude.
It is important that both feasibility and preference information be considered simultaneously during schedule construction. Ignoring feasibility constraints can obviously lead to unimplementable schedules, but disregarding preference constraints (in order to simplify the problem) can lead to unacceptably suboptimal schedules. For this reason the concept of suitability functions (Section 2.1) was developed by merging ideas from two well-studied frameworks, namely constraint satisfaction problems (CSPs) for expressing and manipulating feasibility constraints, and evidential reasoning techniques as a means to combine preference constraints.
Consider scheduling some activity 
, given that other activities 
are already scheduled at times
. A human scheduler would assess the opportunities for scheduling 
at various times by considering the effects of the activities 
on 
via the constraints. Constraints can take a variety of forms, but can be generally be cast into statements of the following type:
are scheduled at times 
, the degree of preference for scheduling activity 
at time
due to constraint
is 
The degrees of preference can be assigned over some numerical range based on a judgment of the importance of the constraint, with larger values of 
corresponding to greater preference. 
can represent both deterministic constraints and intrinsically unpredictable constraints, e.g. 
can also be formulated in terms of (a function of) the probability that some desirable condition will hold.
from all applicable constraints. This combination process is formally similar to that employed in a number of rule-based expert systems which assess evidence for and against various conclusions (e.g. Shortliffe 1976, Hart et al. 1978). While this approach to uncertainty reasoning is known to have its limitations --- In particular, the knowledge base should form a tree so that no evidence is counted twice via alternative paths of reasoning (Pearl 1988) --- it is adequate for many scheduling problems and has the advantage of being computationally tractable.
However, the techniques used in rule-based systems for evaluating evidence for or against discrete conclusions cannot be applied directly to scheduling, since a continuum of scheduling conclusions must be considered (e.g., schedule 
at 
and 
at 
, etc.). What is required instead is a continuum version of uncertainty reasoning, formulated in a way which efficiently expresses the variety of constraints that typically appear in these problems and which retains information about choices that affect schedule optimality. Central to this formulation is a way to combine evidence from two or more independent constraints 
.
Two conditions for the combination of evidence are reasonable: the combination function for 
should be a continuous, monotonically increasing function of its arguments, and it should be associative, i.e. it should not matter in what order the evidence is considered. With these assumptions, the preferences 
together with the combination operator form an Abelian group isomorphic to the additive group of real numbers on 
, a result which has been independently discovered by a number of researchers (e.g., Cox 1946; Good 1960, 1968; Hájek 1985, Cheng and Kashyap 1988). Thus with no loss of generality we take the 
to be real-valued functions that combine simply by addition.
It is common in scheduling problems to have constraints that specify times when an activity is not permitted to be scheduled. These are particularly important since they allow the scheduler to eliminate blocks of time from further consideration. In terms of the preferences, these times should have highly unfavorable values, e.g. 
, where 
is sufficiently large to indicate overwhelming evidence against scheduling activity 
at time 
. We can transform the additive 
into a multiplicative form 
by defining:
Except where 
, the use of the exponential function makes the additive combination of the weights
equivalent to the multiplicative combination of 
. When 
, multiplicative combination provides precisely the desired behavior, i.e. if there is overwhelming evidence against scheduling 
at 
from any source, then no amount of evidence from other sources can counteract this. We have found that the multiplicative formulation is particularly convenient for representing practical constraints defined by scheduling experts. In the HST domain we have further adopted the convention that a value 
represents the absence of evidence either for or against a scheduling decision. In practice, the 
are defined by analysis of the constraints and preferences in consultation with telescope scheduling experts.
It is computationally infeasible to work with the full N-dimensional form of the 
in any practical scheduling problem. The approach adopted in consists of projecting the 
into functions of one time variable only:
where the maximum operator ranges only over times 
where activities 
are permitted to be scheduled (based on the current state of the schedule, i.e. accounting both for times excluded by constraints and for times excluded by decision of the scheduler). 
is zero only when, due solely to the constraint 
, no possible choices for scheduling activity 
will permit 
to be scheduled at time 
; otherwise its value is the best (most preferable) value of 
that can be obtained by scheduling 
at 
, given any other possible schedule of the other activities. The former property of
ensures that no times are excluded prematurely unless provably in violation of a strict constraint. The latter provides an important indicator of optimal scheduling choices to the scheduling agent by always indicating the best that can be achieved, regardless of future scheduling decisions. (It is conceivable that a function other than maximum, e.g. some averaging function or even minimum, could be useful in some scheduling problems.) We call 
the suitability function for activity 
due to constraint 
. The total suitability function for an activity 
is the product of the suitability functions from each of its constraints, multiplied by a restriction operator 
indicating any scheduling decisions made so far in constructing the schedule 
for excluded times, 1 otherwise):
if activity 
is excluded from being scheduled at time 
, either because a strict constraint would be violated or because of prior scheduling decisions. These equations implicitly determine the suitability function for an activity and are solved by an iteration procedure corresponding to the propagation of constraints.
The suitability function concept can be illustrated by a simple example: consider a preference constraint of the form:
as soon as possible after the end of 
, but starting no sooner than 
minutes afterwards and ending no later than 
minutes afterwards."
We can represent this by choosing 
where 
is a function indicating the judgment (objective or subjective) of how much better or worse it is to delay scheduling 
after 
. Given the suitability function 
of 
it is straightforward to construct 
due to this constraint as illustrated in Figure 2. Panel (a) shows what the 
could look like for a plausible choice of 
. Panel (b) shows what the suitability function 
might be at some stage in the scheduling: in this case there are two disjoint candidate intervals where 
could be scheduled. The last panel (c) shows the resulting suitability 
for task 
.
FIGURE 2. Illustration of suitability functions for the case of a binary preference constraint: (a) preference expressing that a task should be scheduled as soon as possible after minutes from the completion of another task (of duration ) and in no case later than minutes; (b) hypothetical suitability of at some stage in the scheduling process; (c) the resulting suitability of . The intervals where each function is non-zero are indicated by bars under the time axes in (b) and (c).
Suitability functions provide a simple but effective framework for capturing metric-time scheduling constraints, both strict and preference. All of the conventional binary temporal interval relationships (before, after, during, etc.: see Allen 1983) are easily represented by appropriate suitability functions, along with a large class of far more general temporal couplings (Shapiro 1980). Like Rit's (1986) formulation of "constrained occurrences" for binary interval constraints, suitability functions can represent and propagate disjunctions; more generally, however, they also handle constraints of higher order than binary, and can incorporate preferences as well. The combination of preferences is analogous to other similar constraint evaluation methods (e.g. Fox and Smith 1984, Smith et al. 1986), but differs in that the combination of evidence for or against a scheduling decision is required to be monotonic and associative. It is also worth noting that, while there is a resemblance between suitabilty functions and the propagated preferences of Sadeh and Fox (1988), the latter method is based on a probabilistic model of start time distributions. Such a probabilistic characterization of the results of scheduling as an input to the scheduling agent differs from the suitability function perspective, which maintains a distinction between the likelihood of different decisions by the scheduler and the characterization of preferences vs. time. However, this does not rule out the use of similar models that attempt to estimate resource demand and contention (e.g. Sadeh 1991): these can play a useful role as suitability components that reflect resource or capacity limits.
is constrained to follow 
with a minimum end-to-start separation of 
, that both activities have unit durations and are restricted to be scheduled in the interval 
. Then the interval 
is excluded for 
, and the interval 
is excluded for 
. To introduce arc-consistency into the network, we restrict activities to fall within the overall scheduling interval 
, and then propagate constraints (Equation 3).
must precede 
which must in turn precede 
: by explicitly representing the constraint "
precedes 
" we can immediately represent the implication of a decision on scheduling 
which would otherwise require a further decision about 
. For simple precedence, the additional constraints inferred by path consistency are just those derived from the transitive closure of the precedence relationship. However, for more general binary constraints which depend on time differences only (e.g. "group 
within 24 hours"), it is possible to generalize this calculation and derive much more informative constraints (Johnston and Adorf 1992).
We have found a substantial benefit in pre-computing and storing for later access the results of node-, arc-, and path-consistency. We have also found that explicit representation of inferred constraints makes the conflict-count repair heuristics (Section 4.2) more effective. However, in other scheduling domains, the significant pre-processing computational cost must be traded against the potential speed-up during search. To help control this, the constraint propagation code used in includes a "time-out" capability which can be used to limit the amount of computation devoted to path-consistency.
where the suitability has a value of 
from 
up to 
, then a value of 
, etc. Suitability values are not restricted to a fixed set. Arbitrary values are allowed and are only required to be constant over appropriate intervals (which can be different for different constraints). In this way, the basic constraint representation mechanism places no arbitrary restriction on the timescale or suitability value that can be represented.The choice of PCFs has other advantages as well. They are closed under all of the common operations required for manipulation of suitability functions such as multiplication or maximum (in contrast to other representations such as piecewise linear functions). The cost of storing and combining PCFs is proportional to the number of intervals with distinct values, not to the size of the scheduling interval.
Although the PCF representation of suitabilities does not require discretization of suitability values, in practice this may be useful as small differences in suitability (e.g. a few percent) may not be significant and "collapsing" these differences in suitability can decrease the storage required for the suitability function and increase the speed of constraint propagation.
incorporates a general "toolkit" for representing and manipulating constraint satisfaction problems, which we will briefly describe in this section. This toolkit is used in the scheduling search algorithm, which will be discussed in Section 4.0.
The state information maintained by CSP and variable instances can be manipulated with an extensive library of methods. These provide capabilities which have proven extremely useful in a practical scheduling environment. Each variable instance maintains constraint conflicts and preferences data for each of its domain values, as well as the variable's current assigned value.
Some of the more important capabilities provided by the CSP toolkit include:
In HST scheduling we generally chose option (b) for the initial implementation and moved toward option (a) for specific constraints as experience was gained with operations. The choice must be determined for each problem type based on the characteristics of the constraints and the difficulty of dealing with the consequences. In some problems there will be a natural time unit in terms of which constraints are defined, so that no sampling error will occur. A further discussion of sampling and discretization is given in Johnston and Adorf (1992).
The heuristics employed in are stochastic, so there is benefit in repeating the three steps above as often as there is time. The general strategy is to select the best of many runs, possibly trying different initial guess and repair heuristics. However, the algorithm has desirable "anytime" characteristics (cf. Zweben et al. 1990): at any point in the processing after the initial guess has been constructed, a feasible schedule can be produced simply by removing any remaining activities with constraint violations, as described further below.
Two additional factors play a major role in 's search process:
Both hill climbing and backtracking repair procedures have been tried, but hill climbing has been shown to be the most cost-effective on problems attempted to date. Typically only a relatively small number of repair steps is allowed, e.g. 
where 
is the number of activities to schedule and 
is usually 2 but is kept in the range 1-5. This helps deal with the problems of "cycles" which can afflict hill-climbing procedures, where the repair process repeatedly attempts to place the same set of activities at mutually inconsistent times. While cycles are sometimes observed and there has been some work done to identify and avoid them, they have turned out not to be a significant problem in practice.
One particularly interesting measure plays a role when the activities to be scheduled have durations 
that vary as a function of time: in this case the total gap time in the schedule serves as one component of a quality measure, since it indicates how much time could potentially be used if there were appropriate activities available. Note that, in this case, the total summed activity duration scheduled can be highly misleading --- it is possible to construct a very inefficient schedule which rates highly by this measure simply by placing activities at times when they are very inefficient (i.e. 
) but tend to fill up the schedule. So the appropriate quality measure is the non-intuitive sum of total minimum activity duration, plus the total gap time.
FIGURE 3. The processing flow for HST scheduling. Proposals are received electronically over the Internet and processed through a proposal database. The "Transformation" system converts the astronomer's observing plan into a set of tasks to schedule. SPIKE does the long-range scheduling, then passes off 1-week segments to SPSS for short-term scheduling and instrument command request generation. The main output product, the Science Mission Specification (SMS) is a detailed time-tagged command list for the HST's onboard computers.
The Phase II proposal contains information on the astronomical objects, individual exposures, instrument parameters, and the relationships (i.e. constraints) among exposures: Table 1 lists the kinds of constraints that proposers may specify, in the syntax that they actually use. Proposals are submitted electronically in an ASCII file, through the Remote Proposal Submission System (RPSS). The RPSS software validates the contents of a proposal file and can detect a wide range of problems, including typographical errors (e.g. a misspelled filter name), values out of range (e.g. a target declination exceeding 90\xa1 ), and missing or inconsistent information (e.g. an exposure referencing an undefined target). A dedicated RPSS computer is available to the astronomical community over the Internet and the Space Physics Astrophysics Network (SPAN). The RPSS software has been distributed to approximately 100 astronomical institutions around the world, and is run by most proposers at their home institutions before they send their proposals to STScI.
STScI designed RPSS and the HST proposal language with the following goals in mind:
Transformation performs several planning tasks, including: determining the order to execute observations (when not explicitly specified by the proposer), breaking exposures into pieces to better match target visibility conditions, grouping observations to minimize overhead operations, choosing specific implementation scenarios, supplying values of instrumental settings which were defaulted by the proposer. Transformation also detects certain errors which may be present in the proposal including: conflicting timing requirements among exposures, loops in precedence constraints, and inconsistencies in instrument parameter settings. Transformation makes use of suitability function framework (Section 2.1) and the temporal constraint mechanism to collect and propagate temporal constraints and to achieve path consistency (Section 2.2).
The input to Transformation is a file generated from the Proposal Entry Processor (PEP) database which is essentially a parsed version of the astronomer's Phase II proposal. Transformation produces output files which specify the structure of the scheduling units and the nature of any constraints that act on them. These files then become the inputs to and SPSS.
Transformation was initially conceived and implemented as a rulebased expert system implemented in OPS5 (Rosenthal et al. 1986) but was re-implemented in Common Lisp when the complexity of the rulebased system grew too great (Gerb 1991a). It remains an expert system in that it models a large body of expertise developed by the astronomers who operate the HST scheduling systems.
Using , SUs can be committed to time intervals either manually or with the automatic (CSP) scheduler (Section 4.0). A graphical user interface (e.g. Figure 4) is available to view and manipulate the schedule, or to run the automatic scheduler. Scheduling decisions (when final) are recorded in a database, then reported to files and transmitted to SPSS. Once SPSS has completed short-term sequencing, software analyzes the calendar to determine what observations were scheduled and what factors could affect the future schedule (e.g. timing, special orientations, or contingent SUs). also analyzes a report from the data archive to verify that the data was received and processed. Observations which are not scheduled by SPSS, which are lost in transmission, or which are marked as poor quality, are considered candidates for rescheduling.
provides a number of tools to support the scheduling process, including high-resolution PostScript plots of observing constraints and interactive X-window tools for analysis of complex spacecraft orientation constraints and for viewing the component exposures and constraints from individual proposals. The latter can be analyzed in detail, which is particularly important when it is necessary to examine the effects of individual constraints on potential scheduling decisions. This facility has also proven to be very useful for uncovering and fixing problems with proposals.
's central position in the HST scheduling process has led us to develop an integrated tracking system called ASSIST to monitor and report the status of all observations in the scheduling pipeline. Prior to the development of ASSIST, users of the various systems (PEP, Transformation, SPSS, etc.) each maintained separate tracking systems. Since proposals consist of many observations which are executed at different times, finding the status of a proposal required substantial work. ASSIST provides a central repository for data from the various stages of scheduling, including proposal preparation, long-range scheduling, short-range scheduling, and archiving.
Certain combinations of HST instruments can operate in tandem, and for some astronomical targets such "parallel" observations can yield very interesting data. 's Parallel Observation Matching System (POMS) analyzes the weekly schedule and finds appropriate matches from a pool of parallel proposals. POMS is an expert system which includes a sophisticated knowledge base and matching strategies for identifying and ranking the quality of matches (Lucks 1992). Multiple ranked candidate parallel matches are sent to SPSS, along with each weekly schedule.
Execution of the observations is monitored by both the STScI and the POCC (by monitoring real-time transmissions or by playback of recorded science and engineering telemetry). The STScI analyzes the data to ensure that scheduled observations were completed successfully. It then calibrates the data and delivers it to the proposer for scientific analysis. Since HST observations are an important astronomical resource, an archive of all HST data is maintained. The proposer is normally granted exclusive access to the data for a proprietary period (usually 1 year), after which the data becomes available to the scientific community at large.
Since 1987 there has been a great deal of evolution in Lisp hardware and software. We have continued to modify to keep pace with these changes. All of the Flavors code has been converted to the Common Lisp Object System (CLOS). Between late 1990 and mid-1992 we transitioned from Explorers to Sun SparcStations as the primary operations and development platform: there are currently a total of 22 SparcStation 2s used for Transformation and . The Lisp used on the SparcStations is Allegro Common Lisp from Franz, Inc., which supports a version of CommonWindows based on X-windows. Thus the user interface continued to operate on the SparcStations as it did on the Explorers (and allowed us to operate for some time with a mix of Explorers and SparcStations). After substantial investigation of alternative window systems, we recently reimplemented the user interface tools using the Common Lisp Interface Manager (CLIM). Updating for new Lisp language features has not been difficult, and there are currently no plans to convert any of the system to C or C++.
A common feature of PEP, Transformation and development was that each system had to be developed in a short time (about 6 months for the initial system, with substantial extensions continuing over several years) and with a small staff (2-3 people initially). It was also impossible to specify in advance a complete set of requirements for these systems since many important factors were unknown. These considerations led to the use of a rapid prototyping software development methodology instead of a more classical "waterfall" approach (requirements definition, design, implementation and test). A tool-oriented approach was also encouraged, i.e. the development of general software routines which could be used for other applications later in development.
The most significant advantage of rapid prototyping to the HST was that it allowed PEP, Transformation and to be implemented in time to support testing and operations --- in an environment with changing requirements there is no choice but to use an adaptive software development methodology. Perhaps the most serious complication of this approach is that once the prototype is used operationally, it becomes increasingly difficult to make large changes to it. (In an ideal rapid prototyping situation, a prototype can be discarded after evaluation). Once operational, it is necessary to ensure that each version of the system is upwardly compatible with the previous version. A corollary to this is that pressure on the users to do operational work can prevent them from further participation in the software development process, e.g. critiquing initial requirements and evaluating prototype software. This can lead to a divergence between the needs of the users and the products of the developers, which must be carefully guarded against. We have found two techniques are useful to keep developers in touch with the needs of users. One is for developers to perform full-scale end-to-end tests with real data to uncover problems and bottlenecks. (This is in advance of any testing which may be performed by an test group affiliated with a software configuration management effort.) The other is to allow developers to apprentice in the user group (typically for a month or so) in order to gain firsthand knowledge of the operational environment and requirements.
The incorporation of realistic test data proved to be quite important. Due to delays in the launch of HST, we had several hundred observing proposals which were constantly used to test prototype systems and to make development decisions. Had such extensive data not been available, the creation of a substantial body of simulated test data would have been required.
It is interesting to note that some of the most useful software tools were developed as quick-response reactions: a user would informally ask for a tool to handle some problem which was previously unrecognized or thought to be of low priority, and one of the software developers would then provide the tool in a very short time. For example, a number of functions used to fine-tune the long-range plan were developed in this way. One such function identified for a particular week candidate activities scheduled in later weeks which could be moved earlier to compensate for activities which had to be removed from the schedule at the last minute. Also, the ability to store and restore scheduling commitments in files was first implemented informally and was subsequently used to track scheduling decisions until 's ASSIST database tracking system was completed. A number of useful graphical displays and plots were also developed in this manner, all of which highlights the importance of good communications between developers and users, and a certain flexibility in the development schedule to permit timely response to user requests.
While following a non-classical development methodology, we nonetheless paid careful attention to such classic risk management factors as configuration control and testing. Developers use code management tools (i.e. Unix rcs) to prevent uncoordinated changes. Building, testing and installing the software is automated with software tools to the greatest extent possible to help detect problems before delivery to the users and to minimize the chance for human errors --- indeed, Transformation even incorporates a separate expert system to perform its own testing (Gerb 1991b). Procedures and tools to deliver software changes on a very short timescale (days to hours) are also essential.
The system was first used to support HST scheduling for Cycle 0. The timeline for SV observations was established by NASA. The STScI used to verify this timeline and to schedule GTO observations during weeks when time was available. Scheduling of these proposals in Cycle 0 used in an interactive mode: planners would display individual proposals on timeline displays and choose times of high suitability for observations. Various automatic scheduling tools were sometimes used in conjunction with making manual commitments. Scheduling of early Cycle 1 proposals has also been largely interactive with little use of the high-level, automated schedulers. The main value of in this mode was the identification of problems with proposals and the assignment of observations to feasible, but not necessarily optimal, weeks.
When used on actual GTO and GO proposals, Transformation and reported large numbers of diagnostic messages. Initially, many problems were due to an incomplete understanding of how to best present complex observations to SPSS. The frequency of problems allowed us to effectively prioritize work in determining requirements and implementing the code. A significant number of problems uncovered by and Transformation were due to an inadvertent specification by the proposer of inconsistent requirements in the proposal. Although the PEP system performs syntactic checking on proposal information, Transformation and are the first systems that can detect problems related to planning and scheduling. (In particular, accurate instrument overhead times and orbital viewing conditions are calculated by Transformation and these can reveal problems with the proposal.) We are currently investigating how to incorporate such checks in PEP and RPSS. Not only will this provide proposers with immediate feedback on certain classes of problems, but it will also reduce the delays in the scheduling process due to late proposal modifications.
We originally anticipated that long term schedules covering 6-12 months duration would be maintained beginning with Cycle 0. However true long-term planning began late in Cycle 1 with schedules of approximately 3 months duration and year-long schedules were first generated operationally beginning with Cycle 2. This was not due to any inherent limitation in the software (test schedules of a year duration had been generated well before launch). It was primarily due to a much larger than anticipated rate of change of proposals. Prior to launch, \xb2 10% of the proposals were expected to change after submission, whereas the actual rate is nearly 100%. Many proposals have been revised several times. A substantial portion of this can be attributed to the spherical aberration of the HST mirror and other unexpected behaviors of the instruments and spacecraft. Another factor is that the HST and major elements of the ground system are designed for fully pre-planned observations with little capability to inject changes late in the scheduling process. A change to a proposal can therefore often require a repeat of the entire scheduling process, wasting much if not all of the earlier work. Tracking multiple revisions of proposals and their scheduling and execution status also requires substantial effort. Our recommendation to developers of future systems with requirements similar to HST would be to build in the expectation of change from the outset and to carefully examine factors in the design which are sensitive to a high rate of change. We realize that such flexibility will increase the initial cost of a system, but it can significantly reduce the lifecycle maintenance and operational costs. A further discussion of the HST experience can be found in Miller and Johnston (1991).
The adaptation of for these problems demonstrates the flexibility of the scheduling framework. As indicated above, was designed so that new tasks and constraints can be defined without changing the basic framework. For ASTRO-D (Isobe et al. 1993) and XTE (Morgan 1992), is operated in a hierarchical manner, with long-term scheduling first allocating observations to weeks much as they are for the HST problem (and with similar types of long-term constraints and preferences). Then each week is scheduled in detail, subject to the detailed minute-by-minute constraints of low earth orbit operation. The major changes required to implement short-term scheduling were:
All of the general constraint combination and propagation mechanisms (Section 2.0), and the CSP toolkit (Section 3.0) and scheduling search techniques (Section 4.0), apply directly to both long-term and short-term scheduling. Figure 4 shows the CLIM user interface displaying an ASTRO-D long-term schedule. Figure 5 shows a portion of the high-resolution PostScript plot output for a short-term schedule for ASTRO-D. Only one day of a 7-day schedule is shown. Note that several observations are broken to fit around earth blockages or radiation belt passages and so are taken in multiple segments.
FIGURE 5. An example of Spike output on short-term scheduling of astronomical observations. Shown is a 24-hour portion of a 7-day schedule. The start-time suitability for each exposure is plotted as the upper graph, with interruptions due to target blockage by the earth and by satellite passage through high-radiation regions. The available exposure intervals are shown below as open bars, which are filled in to indicate the actual scheduled times. Some of the observations can be fit within one orbit; others must be interrupted and thus span several orbits.
Most of the effort required to apply to the new problems was limited to the specific domain modelling necessary, which typically involves computation related to the geometry of the satellite, Sun, target, and Earth. These problems can be expected to differ from one satellite to another, and it is not surprising that different models are required. Some of the modelling includes state constraints, although does not perform explicit planning (cf. Muscettola et al. 1992).
EUVE is unusual in that it makes long (2-3 day) observations, in contrast to HST and ASTRO-D which typically make numerous short (15-40 minute) observations. As a consequence, EUVE is schedulable over year-long intervals without breaking the schedule into hierarchical levels. One of the more interesting results from a comparison of search algorithms for scheduling EUVE was that the repair-based methods gained an extra 20 days of observing time in a year, when compared to the best incremental scheduling approach.