language: en

[In Proceedings of the Eighth International Workshop on Qualitative Physics about Physical Systems (QR-94) Nara, Japan, 1994.]

Model Decomposition and Simulation

Daniel J. Clancy and Benjamin Kuipers
Department of Computer Sciences University of Texas at Austin
Austin, Texas 78712
clancy@cs.utexas.edu and kuipers@cs.utexas.edu

Abstract Qualitative reasoning uses incomplete knowledge to compute a description of the possible behaviors for dynamic systems. For complex systems containing a large number of variables and constraints, the simulation frequently is intractable or results in a large, incomprehensible behavioral description. Abstraction and aggregation techniques are required during the simulation to eliminate irrelevant details and highlight the important characteristics of the behavior. The total temporal ordering of unrelated events provided by a traditional state-based qualitative representation is one such irrelevant distinction. Model decomposition and simulation addresses this problem. Model decomposition uses a causal analysis of the model to partition the variables into tightly connected components. The components are simulated separately in the order dictated by the causal analysis beginning with causally upstream components. Information from the simulation of causally upstream components is used to constrain the behavior of downstream components. If a feedback loop exists between components or a set of components are acausally related, then a concurrent simulation is performed for these components. A truth maintenance system is used to record and retract assumptions made during this concurrent simulation. Model decomposition provides a general architecture which separates the method of simulation from the model decomposition algorithm. This architecture can be used to introduce alternative abstraction techniques to eliminate other irrelevant distinctions.

1 Introduction