The HSTS System
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 of HSTS
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.
Jump to --> ICL Lab home page
Stephen F. Smith
<sfs@cs.cmu.edu>