CSAIL Publications and Digital Archive header
bullet Research Abstracts Home bullet CSAIL Digital Archive bullet Research Activities bullet CSAIL Home bullet

link to publications.csail.mit.edu link to www.csail.mit.edu horizontal line


Research Abstracts - 2007
horizontal line

horizontal line

vertical line
vertical line

Tractable Approach to Model-based Temporal Planning for Engineering Operations

Seung H. Chung & Brian C. Williams

As the operational complexity of NASA's increasingly ambitious missions increases, the capabilities of our current operations processes and tools are becoming increasingly strained. The tremendously successful Mars Exploration Rover (MER) mission points to ground-based planning of engineering operations as a potentially time-consuming and error-prone process.

The conventional approaches to systems and software engineering inadvertently create a fundamental gap between the requirements on software specified by systems engineers and the implementation of these requirements by software engineers. Software engineers must perform the translation of requirements into software code, hoping to accurately capture the systems engineer's understanding of the system behavior, which is not always explicitly specified. This gap opens up the possibility for misinterpretation of the systems engineer's intent, potentially leading to software errors.

Operational efficiency is also a driving concern for ground-based embedded systems. For example, the Deep Space Network (DSN) is under constant pressure to reduce its operations budget, while continuing to provide high quality-of-service telecommunications support to an increasing number of spacecraft. This dilemma can be at least partially addressed by increasing the level of automation of its Monitor and Control (M&C) functions, thus enabling operators to work more efficiently, taking on supervisory responsibility for multiple concurrent spacecraft tracking activities.


This research addresses the problem of autonomously planning and sequencing for engineering operation of spacecraft and ground-based systems using the model-based approach [5].

The main objective of this research is to develop a model-based temporal planner that automatically generates an executable sequence for discrete, stochastic, hidden state systems, based on behavior specifications of the components of a system and the specification of the operator's mission objectives and intent. The model used by this planner must be capable of expressing the stochasticity, uncontrollable actions, and temporal constraints. Furthermore, since many systems today include software, the model must be also capable of representing the specification of processes. The goal must specify the intent of the operator and mission objectives. This may include declaring invariants, desired trajectory of partial states, temporal constraints among partial states, etc. Finally, the temporal planner must be able to plan from those models and goals in an efficient manner.


Existing approach to sequencing engineering operations of spacecraft and ground-based assets will be improved through explicit use of verifiable models, i.e. model-based, and state-of-the-art goal-directed planning algorithms. To accomplish this task, the following approaches to modeling, specifying goals, and planning are proposed (see Figure 1):

  1. Specify the model of system behavior as timed, probabilistic, constraint automata (TPHCA) [4] that provide the expressiveness necessary to model the nominal and faulty behavior of the system components, including operational modes with uncertain durations, and state transition uncertainty. (Figure 1a)
  2. Describe the mission objective as a qualitative state plan [3] that expresses the desired temporal evolution of goal states, thus explicitly capturing the intent of the operators, rather than implicitly capturing it in a sequence of commands and procedures that achieve the desired goals. (Figure 1c)
  3. Apply an offline reasoning algorithm to synthesize a set of modular, reusable, and compact partial plans for achieving goal states, thus only requiring a simple composition of partial plans at plan time (Figure 1b), minimizing the amount of computationally expensive online search (Figure 1c). This will be accomplished by using a novel, automated problem decomposition method that unifies existing constraint graph decomposition[2] and causal graph decomposition algorithms [1],
Decomposed temporal planning process.
Figure 1: Decomposed temporal planning process.

Though the objective of this research is to solve autonomous engineering operations problem, an onboard autonomous planning problem is similar. If realtime performance can be guaranteed, the new approach should also be applicable to the onboard autonomous planning problem.

The new approach is novel in several ways:

  1. The decomposition approach that leverages the structure of the component interactions to simplify the planning problem ensures the tractability of planning, even during time-critical situations. This approach is innovative in that it combines the existing decomposition techniques used in constraint satisfaction problem and reactive planning.
  2. The planner incorporates the ability to generate modular, reusable, and compact partial plans that can be automatically verified for correct execution under both nominal and off-nominal situations. This extends the existing model-based reactive planning capability to sequence generation.
  3. Our goal-directed and model-based planning approach ensures that the executable plan is traceable to the mission intent and system specification, increasing the reliability and reviewability of the automatically generated plan.

Unlike other planning and sequencing systems, the new approach will directly exploit engineering models of system component behaviors to compose the plan, validate its robustness under both nominal and failure situations, and, when required, synthesize novel procedures from first principles.

The goal-directed and model-based temporal planning capability has the potential for significant impact on the operations of future space missions and related ground infrastructure (e.g., Deep Space Network), in the form of improved efficiency for ground-based operations in the near term, and in the form of greater onboard autonomy in the longer term. It will particularly benefit highly complex missions, where the experience on Mars Exploration Rover (MER) points to ground-based planning of engineering operations as a potentially time-consuming and error-prone process. The ability to leverage systems engineering models for direct use in automated sequencing will improve the efficiency of mission operations and reduce the risk of errors in translating the understanding of system behavior into operational sequences.


[1] S. H. Chung. A decomposed symbolic approach to reactive planning. Master's thesis, Massachusetts Institute of Technology, June 2003.

[2] R. Dechter and J. Pearl. Tree clustering for constraint networks. Artificial Intelligence, volume 38, no. 3, pp. 353--366, April 1989.

[3] A. Hofmann, Robust Execution of Bipedal Walking Tasks from Biomechanical Principles. Ph.D. Thesis, Massachusetts Institute of Technology, January 2006.

[4] M. D. Ingham. Timed Model-based Programming: Executable Specifications for Robust Mission-Critical Sequences. PhD thesis, Massachusetts Institute of Technology, May 2003.

[5] B. C. Williams, M. D. Ingham, S. H. Chung, and P. H. Elliott. Model-based programming of intelligent embedded systems and robotic space explorers. In Proceedings of the IEEE: : Special Issue on Modeling and Design of Embedded Software, volume 9, no. 1, pp. 212--237, January 2003.


vertical line
vertical line
horizontal line

MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
The Stata Center, Building 32 - 32 Vassar Street - Cambridge, MA 02139 - USA
tel:+1-617-253-0073 - publications@csail.mit.edu