N94-35048 A Criterion Autoscheduler For Long Range Planning

The requestfor suchsoftwareby theplannerscatalyzedthe designandimplementationof the Criterion AutoSchedulerfor Long range planning (CASL) which is the subject of this report. CASL is described in detail in later sections. The resource constraint levels for the LRP larger pool of SUs for micro-scheduling. for the fact that certain SPSS scheduling If, therefore, certain commitments are alternative SUs. 4.3. are set to greater than 100% in order to provide a This oversubscription is intended to compensate constraints are not encoded in SPIKE currently. incorrect, the larger pool provides SPSS with Micro-scheduling The final step in proposal processing, at the STScI, is accomplished by SPSS. The SUs committed to one week time segment in the LRP are communicated to SPSS operators who micro-schedule them very precisely on a calendar (a data structure that represents a time line). Upon completion, this calendar is converted into a sequence of spacecraft commands. 5. The An expert developed. previously Multiple Criterion Network Expert System Engine system technology called the multiple criterion network MCN is based on functional knowledge representation in two other systems (Lucks, 1992 and Lucks, 1990). system (MCN) has been which has been applied Several terms are now defined informally. The MCN score is a numeric value in the set of real numbers ranging from zero to one. Conventionally, a zero score is interpreted as poor and a unit score as good. CASL computes a score that schedules in a specific time zero, then the fit is poor. describes segment. how well an If the score SU is The MCN criterion is domain-specific and deemed an important attribute of the problem being solved by the expert and so is required information concerning the decision making process. For example, in is a criterion. This technology provides CASL, system scheduling builders The ability to store expert knowledge domain-specific and which calculate to 1). ii. The ability to explicitly knowledge mappings and users alike. iii. The ability to define aggregation function. These capabilities support system. an SU with the following as early as possible capabilities: in the form of knowledge functions which are numeric scores (real numbers in the range from 0 declare mappings from raw scores to more refined scores. These clarify the decision making calculations for knowledge engineers the way scores are accumulated support trade-offs between competing The components of MCN are described 61 into a single score criterion in an automated in the following sections. via an decision

5.1. The Knowledge Functions The knowledge function is a program which encodes expert knowledge about the domain. Each function either produces a numeric score or maps one score to another. There are four types of knowledge functions in the MCN model. They are described below. 5.1.1. Measurement Functions The measurement function is the initial source of data in the MCN model. This function is the point where the application information about a specific criterion is accessed directly and converted to a measurement value. This value is not required to be a score and in fact may be quantitative or qualitative. CASL's earliest criterion measurement function maps (for example) to a measurement value of 0.085 (i.e., the temporal offset of a time segment with respect to the entire schedule). Another criterion, preference (i.e., static goodness of fit) might produce a value of 50 (where the maximum is i00). 5.1.2. Intensity Functions The intensity function is defined as a mapping between measurement value and the intensity value which is required to be from zero to one. This mapping is a normalization of criteria to a single scale and may be any arbitrary function. The intensity value conventionally is not interpreted as good or poor. The earliest criterion measurement intensity of 0.915 (the mapping inverse). The preference intensity of 0.085 maps to an is simply the additive for 50 is 0.50. 5.1.3. Compatibility Functions . : ,, . , i . The compatibility function maps from intensity value to compatibility can be any function and must be specified by the knowledge engineer There are two important attributes to this mapping: 1. This compatibility meaning. 2. value conventionally uses the classic value. This mapping with expert guidance. 0.0 poor and 1.0 good The mapping also provides a way to adjust the relative power or importanc e of the criterion. An intensity value may be either tempered or amplified by this mapping to diminish or increase its importance with respect to other criteria. In CASL, a simple weighting scheme is used for this map.ping. The weight is applied as follows. Let w be the weight, m be the maximum intensity value, and v be the intensity value. Computation of compatibility is performed by this formula: m - (w * (m - v)), The earliest criterion maps (by application 0.5) from intensity 0.915 to a compatibility 0.941. The preference value maps (with weight intensity 0.5 to a compatibility value of 0.5. 62 of weight value of 1.0) from

5.1.4. Aggregation Function The aggregation function maps from the compatibility value to the aggregation value which is the final score of the network. In the functional knowledge representation technology, an augmented decision tree (and/or graph) is used to compute the score from the individual criteria. The augmentation includes other functions that may be defined by the engineer. These are described in Lucks, 1992. MCN employs a single function (e.g., multiply) to perform the aggregation. Aggregating all criteria for yields a value of 0.211. One highest score as the winning scheduled. 5.2. Parallel Observations Matching a specific SU/segment pair can select the segment with match where the SU can be System The Space Telescope is capable of executing observations in parallel provided a set of restrictions are satisfied (e.g., the same instrument cannot be used in parallel with itself). Functional knowledge representation has been applied to the problem of matching predefined parallel scheduling units with standard SUs (see Lucks, 1992). A large pool of such parallel SUs must compete for scheduled SUs. This system, the Parallel Observations Matching System (POMS), is in operational use at STScI. 6. CASL Architecture The CASL system employs MCN technology to direct the LRP generation. Specifically, the aggregation decision tree is replaced with a simple combining function (the multiply function, for example). The function of CASL is to create Long Range Plans for HST that: do not violate maximize satisfy constraints the suitability the planning of all commitments goals of the LRP planners The CASL system requires that prepared proposals be loaded into a CSP Scheduling System which provides the workbench upon which the expert system operates. There are two main phases to the application of CASL. They are described below. 6.1. Prioritization Phase The prioritization phase of CASL is responsible for analyzing each scheduling unit using MCN techniques to determine the order by which SUs are placed on the schedule. This ordering does not specify the time ordering on the resulting schedule. A subset of the criteria used are described below: Absolute Time Windows (ABSOLUTE). Characterize an SU based that is available to it based on its absolute constraints. Relative Timing Links (RELATIVE). constraints that are attached to it. Characterize an SU based on the amount on the number of time of relative Proposal Completion (COMPLETION). Consider a proposal and its component SUs. The fraction of SUs that have been scheduled by SPSS is used to compute the completion 63

measurement function. The priority of anSU (with respectto this rule)is proportional to thefractionalcompletion. The orderingis donebasedon theaggregatescorefor eachSU. The SU with the highest score(i.e., hasthehighestpriority) will be placedon theplan first. 6.2. Autoscheduling Phase The next phase of the CASL algorithm is the actual scheduling. An SU is selected from the sorted list and is analyzed with respect to all week-long time segments in the scheduling interval (which can span a year or more). 6.2.1. Some Time of the criteria Min-Conflicts conflicts. Selection used to select a time segment (CONFLICTS): Max-Preference highest Segment This criterion (PREFERENCE): preference for each SU are described will select This criterion for segments will select below: that have for segments few or no that have the value. Earliest-Segment (EARLIEST): schedule if possible. This criterion Minimize-Proposal-Spread (SPREAD): proposal together on the schedule. Level-SU-Duration (DURATION): have less SU Duration resource will tend to place This criterion This criterion consumed. commitments will tend to keep earlier on the SUs from the same will tend to place SUs into segments that Prior-Commit (PRIOR): This criterion attempts to preserve pre-existing commitments. Periodically, the LRP must be regenerated due to feedback from the micro-schedule, changes in spacecraft status, etc. This criterion attempts to preserve old LRP state by biasing for selection of segments previously selected. Group-Instruments (GROUP): This criterion attempts to commit SUs with the same science instrument (SI) into the same segment. It determines an SI frequency distribution of the instrument for the SU and this becomes the score. For example, if the SU under study uses the Faint Object Camera (FOC) and the distribution of FOC in the segment is 0.70 then that is the score (since it is fairly good score the segment will be attractive for commitment). Continuous Viewing Zone (CVZ): The measurement function for this criterion determines whether the SU is a candidate for the CVZ which is a period of time (usually a few days) when the target is not occulted by the earth. Scheduling SUs in the CVZ improves the efficiency of spacecraft operation. z -- " : Random-Choice (RANDOM): This criterion should be used only when the autoscheduler is to be executed several times in order to search for relatively better plans. It injects an element of chance into time segment selection thereby allowing schedules to differ. The associated criterion weight specifies the degree to which randomness is inserted. 64

Table 1. This table provides example data for one SU/segment is displayed. The aggregate score for this set of criteria criteria Criterion pair. Only is: 0.211. a subset Measurement Intensity Weight 0.000 1.000 1.000 1.000 50.000 0.500 1.000 0.500 SU DUR 0.422 0.578 0.600 0.747 EARLIEST 0.085 0.915 0.500 0.941 SPREAD 8.500 0.200 0.500 0.600 CONFLICTS PREFERENCE of the Compatibility In Table 1, the EARLIEST criterion has a measurement value of 0.085 (i.e., the week under analysis has an offset that is 8.5% of the scheduling interval and therefore very early). Normalization by the intensity function produces an intensity value of 0.915 (which is good). The weight of 0.5 reduces the effect of the criterion producing a compatibility value of 0.941. 6.2.2. Commitment The result of the time segment selection process is the selection highest aggregate score. The SU is then committed to this week. following side effects: of the week that has the This action produces the i. Constraint propagation is performed to determine the effect of the commitment SUs that are linked (via timing constraints) to the committed SU. ii. For such a linked SU, conflicts based on constraint propagation. iii. The committed iv. 7. SU consumes accumulate some SUs that are yet to be analyzed resources. CASL portion for any week of available will be affected that has become resource constraints. by the change in conflict on other unsuitable counts and Behavior In the following sections, CASL experimental data are presented and described. An informal Meta-Scheduling Hypothesis for these experiments is as follows. Let schedule quality be defined as average preference for all commitments. Preference takes into account the physical and proposer constraints on the SU. Sufficient flexibiIity exists in the placement of scheduling agenda can be followed without sacrificing schedule units such that a meta-scheduling average preference. The scheduling units, criteria, and weights in these studies operational database currently in use by HST planners. 65 have been obtained from the

7.1. The Cycle 4 Long Range Plan The Cycle 4 Proposal period extends from January 1994 (following the First Servicing Mission) to June 1995. For this report, 994 scheduling units from 281 proposals were automatically scheduled into 78 week-long time segments using CASL. This dataset has the following attributes: It is not randomly generated and therefore cannot benchmark dataset. This dataset may not adequately The dataset contains a 4944 SU to SU timing links which The pool represents a subset of the complete have not been completely prepared. The resource ceilings are very high available time. This is unrealistic be considered a general exercise CASL. make scheduling set of Cycle (approximately but does not 4 SUs because purpose difficult. the proposals 200%) compared to the really effect the outcome actual of the experiments. The descriptions criterion seL 7.2. below Criterion include Unit unit tests on several criteria and tests done on the integrated Tests In each of-the following tests, t-he preference aia t min-co-hfiicts criteria Were in effect and set to a unity weight. The Meta-Scheduling Hypothesis proposes that meta-scheduling criteria (such as earlies0 can be applied without violating the preference requirement. The data format Spread: of the following Let n be the number in a proposal, tables is as follows: of proposals, last-su i be the latest commitment and first-su i be the first commitment date of all SUs date of the same proposal. Spread is This gives an n Z defined as: last-sui-first-sui i l n Spread SD: This is the standard deviation (in weeks) for proposal spread. indication of how each proposal varies from the sample mean spread. Completion: This is the number of SUs committed divided by the total. Offset: For each proposal a mean offset (segment of commitment/total segments) is determined. This value is the mean of all mean offsets and provides a measure of when the proposal was scheduled relative to the entire schedule. This attribute is directly affected by the earliest criterion. SU Dur Mean: all weeks. SU Dur SD: indicate duration This is the mean This is the standard perfectly criterion. amount of available deviation level consumption. SU Duration of the SU Dur Mean. This attribute 66 is directly resource A value affected consumed for of 010 would by the level su

Pref: Let n be the numberof SUsandrc(SUi) bethe percentof maximumpreferencefor n ] the ith SU. Pref is defined as n(SUi) i l n Orbits-Min: This is the number of spacecraft orbits consumed by the schedule minus the theoretical minimum number of orbits. An SU may consume a different number of orbits at different times of the year due to variance in target viewing times. The optimal value for this measure is zero. It should be noted that CASL does not explicitly operate on this attribute and so no attempt is made to minimize changes to it. Preference references this information implicitly along with many other aspects of target viewing. Note that the schedule minimum orbits is equal to 2432 and that an Orbits-Min value of 100 represents 4% difference from the optimal. The proposal spread criterion results are in Table 2. Table 2. This table contains which tends Attribute to keep I was tested data obtained the SUs from a given with weights of 0.0, 0.1., 0.5, from unit tests of the proposal proposal tc ether. and 1.0. spread Wt 0.0 0.1 0.5 1.0 14.4 11.2 8.0 5.7 18.8 16.0 13.3 10.4 Completion 0.71 0.71 0.71 0.71 Offset 0.86 0.87 0.87 0.87 SU Dur Mean 0.46 0.45 0.45 0.45 SU Dur SD 0.25 0.22 0.23 0.23 Pref 0.99 0.99 0.98 0.95 91 99 104 104 Spread Spread SD Orbits-Min There criterion The average Spread was decreased from 14.4 to 5.7 weeks (a 60% change) and the Spread SD decreased by 45% while the Pref value changed by only 4% and the Orbits-Min value change by 14%. These data indicate that this criterion can cause an improvement to a schedule without disrupting the crucial Pref value. A second criterion, Level are recorded in Table 3. SU Duration, was analyzed 67 in the same manner and the results

Table3. Thesedatawereobtainedfrom unit testsof theLevel Attribute Wt 0.0 0.1 SU Duration 0.5 1.0 , Spread criterion. , 14.4 16.2 16.5 17.2 18.8 18.8 19.0 19.4 Completion 0.71 0.71 0.71 0.71 Offset 0.86 0.89 0.88 0.88 Spread SD SU Dur Mean 0.46 0.46 0.46 0.46 SU Dur SD 0.25 0.11 0.09 0.08 Pref 0.99 1.0 0.99 0.98 Orbits-Min 91 102 105 109 The SU Dur SD decreased from 0.25 to 0.08 (a 68% change) while the Pref value changed by only 1% and the Orbits-Min value change by 20%. These data indicate that this criterion can cause measurable changes to a schedule without disrupting the crucial Pref value. The Earliest Criterion The Earliest criterion was tested in a context that contained criteria and the results are illustrated in Figure 1. only the preference and conflicts The behavior of the criterion is apparent in that 100% of the SU Duration resource is consumed in the early segments (,e.g., 94.031) and decreases to 0% in the final segments (e.g., 95.065). The Level SU Duration Criterion The effect of the Level SU Duration criterion on the LRP can be seen in Figure 2 below. In Figure 2, the peaks and valleys for SU Duration are tempered by the criterion,s effect. The minimum and maximum values for the control LRP are 9% and 100%. The minimum and maximum for the criterion are 33% and 80%. It should be noted that if the preference and conflict criteria were inactivated, the bold line in Figure 2 would be fiat. 7.3. Integrated Tests In the integrated tests, a subset (Preference, Conflicts, Earliest, Spread, and Level SU Duration) of the criteria were activated and given the weights used operationally at STScI. Figure 3 illustrates some of the calculations used for time segment selection for one scheduling unit. Since no conflicted commitments are permitted, this criterion is omitted from further discussion. 68

Earliest Segment Figure 1. The bold line represents the LRP when the Earliest Criterion is set to weight of 1.0 compared with the control LRP that is scheduled with only Max Preference and Min Conflicts. An earliest week bias exists in the control LRP because the weeks are analyzed chronolo icall] . Level SU Dur 100% gO% 7O% 60% 50% I 1t IlL I I '\ I I " i !ll .t 1 i h I 1 40% 80% 3O% 2O% " i ;,,. 7, I '( ," ' ',,/',. 10% 0% Segment Figure 2. The control LRP is compared ap

N94-35048 A Criterion Autoscheduler for Long Range Planning Jeffrey L. Sponsler Space Telescope Science Institute 3700 San Martin Drive, Baltimore, MD 21218 USA (410) 338-4565 sponsler@ stsci.edu Abstract A constraint-based scheduling system called SPIKE is used to create long-term schedules for the Hubble Space Telescope.