CSAIL Research Abstracts - 2005 link to http://publications.csail.mit.edu/abstracts/abstracts05/index.html link to http://www.csail.mit.edu
bullet Introduction bullet Architecture, Systems
& Networks
bullet Language, Learning,
Vision & Graphics
bullet Physical, Biological
& Social Systems
bullet Theory bullet

horizontal line

Model-based Temporal Planner for Engineering Operation

Seung H. Chung & Brian C. Williams

NASA's vision of complex human-robotic missions and the limitations in the state-of-the-art engineering operation capability point to the need for a tool that can quickly generate a correct and robust command sequence that fulfills the desired mission objectives. As such, we are developing a model-based temporal planner (MTP) that will address this need. MTP will autonomously generate a command sequence and assure the robustness of the sequence by reasoning about the model (i.e. the specification) of the system behavior, as human operators would.


Under NASA's vision of sustainable human-robotic missions, the number and the types of space systems will grow substantially, and under the traditional operations approach, the corresponding number of ground operators will grow insurmountably large. This operations problem will be exacerbated by the need to monitor and aid astronauts 24/7 and to coordinate complex missions concurrently. Traditionally, ground operators generate and validate engineering operations procedures (sequences) manually through a painstaking process. Frequently these procedures can be generated by piecing together existing procedures from a library. However, due to subtle interactions, these composed procedures can be brittle or even unsafe, and thus must be carefully validated. The extensive time necessary to generate safe procedures is problematic, especially during time-critical and life-threatening situations, such as the Apollo 13 accident. Because of the large space of possible single and multiple points of failure, most recovery procedures can not be generated a priori, but must instead be generated during the crisis. Furthermore, due to the unique nature of these failures, many of these procedures will be novel.


The engineering operations involve three main challenges. First, the sequence must be generated quickly, for it to be uploaded and executed in time to achieve the mission objectives. Minimizing the sequence generation time will, consequently, permit the scientists and the mission manager to spend more time, making tactical decisions of the desired mission objectives. Second, the sequence must be generated quickly even for novel situations. In fact, in practice, the engineering operations become most challenging when generating a sequence for an unforeseen situation or an objective that has never been achieved before. Finally, the sequence must be correct and robust to failures and uncertainties. Under current approach to sequence generation, much of the time is spent verifying the correctness and the safety of the sequence.


We are addressing these challenges by developing a novel model-based temporal planner (MTP) that enables rapid, autonomous generation of highly robust sequences. MTP will exploit engineering models (i.e. system specification) to compose and validate the robustness of the sequence under nominal and failure situations, and to synthesize novel procedures, when required, from first principles.

Model-based temporal planner architecture Model-based temporal plan preprocessing

Figure 1.  Model-based temporal planner architecture.

Figure 2.  Model-based temporal plan preprocessing.

As illustrated in Figure 1, MTP will generate a sequence, given the model of the system (e.g. rover or spacecraft) and the desired evolution of the mission objectives. The model of the system is specified and represented as timed, probabilistic, hierarchical constraint automata (TPHCA). TPHCA extends the expressiveness of probabilistic, hierarchical constraint automata (PHCA) [2] and timed, concurrent, constraint automata (TCCA) [3] to allow the expressiveness necessary to model the behavior of the hardware and the software of engineering systems. Using TPHCA, we are able to represent the nominal and faulty behavior of concurrently operating components, component modes with durative time and temporal uncertainty, mode transition uncertainty, mode abstraction, and more.

Traditionally, mission objectives are described as an activity plan that specifies the duration of the desired activity and the proper sequence of the activities. In model-based approach [1], the mission objective is described as a desired evolution of goal states. As a result, we can capture the intension of the mission objectives explicitly, rather than, implicitly as a sequence of procedures that achieve the desired goals. We represent the desired evolution of goal states using the Temporal Plan Network (TPN) [4].

Given the system specification, modeled as TPHCA, and the mission objectives, represented in TPN, MTP must rapidly generate a robust sequence that achieves the mission objectives. To quickly generate a plan, for all situation, we synthesize a set of modular, reusable, and compact goal-directed temporal plans (GDTPs) offline, thus requiring only a simple composition of GDTPs, with minimal search, during online plan time. The modularity, reusability, and compactness of GDTPs are achieved through a divide-and-conquer approach as illustrated in Figure 2. The divide-and-conquer approach uses a decomposition technique, similar to [5], that takes advantage of the structural property of the system component dependency. The robustness of the sequence is guaranteed by incorporating a mode estimation technique [1] that guides the planner in generating a sequence that is most likely to succeed. For added robustness, contingent sequences are generated for segments of the sequence that are most likely to fail.


[1] Brian C. Williams, Michel Ingham, Seung H. Chung, and Paul 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, vol. 9, no. 1, pp. 212-237, January 2003.

[2] Brian C. Williams, Seung Chung, Vineet Gupta. "Mode Estimation of Model-based Programs: Monitoring Systems with Complex Behavior." In Proceedings of the International Joint Conference on Artificial Intelligence, Seattle, WA, 2001.

[3] Michel D. Ingham and Brian C. Williams. "Timed Model-based Programming: Executable Specifications for Robust Mission-Critical Sequences." In Proceedings of the Third International Workshop on Self-Adaptive Software, Washington D.C., 2003.

[4] Phil Kim, Brian C. Williams and Mark Abramson. "Executing Reactive, Model-based Programs through Graph-based Temporal Planning." Proceedings of the International Joint Conference on Artificial Intelligence, Seattle, WA, 2001.

[5] Seung H. Chung and Brian C. Williams. "A Decomposed Symbolic Approach to Reactive Planning." In Proceedings of the Third International Workshop on Self-Adaptive Software, Washington D.C., 2003.

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
(Note: On July 1, 2003, the AI Lab and LCS merged to form CSAIL.)