Overview
HSTS is a problem solving framework for developing integrated planning and scheduling applications. It synthesizes the representational assumptions of contemporary temporal planning frameworks with the structured resource modeling concepts underlying current scheduling frameworks. contemporary planning and scheduling frameworks. There are three distinguishing characteristics of the HSTS framework:

• A representational framework that decomposes the state of the world into a finite set of "state variables" which vary over time, and describes domain dynamics (e.g., activity pre and post conditions) in terms of temporally "compatible" state variable value configurations. The modeling framework thus integrates the problem/domain structure inherent in scheduling representations with the expressiveness of modern temporal planning frameworks. This enables the specification of scheduling algorithms that exploit problem decomposability and provides the necessary structure for optimizing resource utilization.
• A flexible representation of solutions (i.e., possible executions) as an explicit temporal constraint graph. Within this solution model, the occurrence of events (e.g., activity start times) can be allowed to "float" within the temporal constraints imposed by the problem and the problem solving process. This avoids the problems of over-commitment inherent in "fixed times" scheduling frameworks and contributes directly to increased scheduling efficiency.
• A uniform view of planning and scheduling processes as an iterative constraint posting process. Flexibility is provided to accommodate a range of problem solving strategies (e.g. forward simulation, back chaining, etc.) and to support dynamic interleaving of goal sequencing and goal expansion actions. This allows the incorporation of algorithms that opportunistically exploit problem structure to consistently direct problem solving toward the most critical tradeoffs that need to be made.

Results and Applications
HSTS has been developed and applied principally in the context of space-based observatory scheduling problems, under funding provided by NASA. The original application focus was development of executable, short-term observing schedules for the Hubble Space Telescope (HST). The observation scheduler for HST that was developed was shown to scale to the full problem, producing observation schedules complete with all necessary enabling activities such as instrument reconfiguration, telescope repointing, data communication, etc. in a time frame acceptable for actual application. Complementary results demonstrated the ability of multi-perspective scheduling techniques to produce better quality schedules, in terms of balancing conflicting mission objectives, than a variant of the short-term scheduling algorithm currently being used in HST mission operations. More recently, HSTS has been used to develop of scheduler for application to a second orbiting telescope, the Small Wave SubMillimeter Astronomy Satellite (SWAS), currently due to be launched in June 1995. In collaboration with the SWAS mission team, we are currently evaluating the developed scheduler on full scale reference problems.

Current Status
Ongoing development of the HSTS platform has moved with Nicola Muscettola from CMU to NASA Ames Research Center. Nicola can be reached at mus@ptolemy.arc.nasa.gov. At CMU, we have incorporated HSTS solution representation and management concepts into the design of DITOPS a configurable, mixed-initiative planning and scheduling system.

back to top