UTCS Artificial Intelligence
courses
talks/events
demos
people
projects
publications
software/data
labs
areas
admin
QSIM
The world is infinite, continuous, and continually changing over time. Human knowledge and human inference abilities are finite, apparently symbolic, and therefore incomplete. Nonetheless, people normally reason quite effectively about the physical world. Models of particular systems or mechanisms play an important role in this capability. In service of a task such as diagnosis or design, simulation predicts the behaviors that follow from a particular model. In diagnosis or explanation, these predictions include testable consequences of a diagnostic hypothesis. In design, these predictions make explicit the consequences of a set of design choices. A qualitative differential equation (QDE) model is a symbolic description expressing a state of incomplete knowledge of the continuous world, and is thus an abstraction of an infinite set of ordinary differential equations models. Qualitative simulation predicts the set of possible behaviors consistent with a QDE model and an initial state. We have developed a substantial foundation of tools for model-based reasoning with incomplete knowledge: QSIM and its extensions for qualitative simulation; Q2, Q3 and their successors for quantitative reasoning on a qualitative framework; and the CC and QPC model compilers for building QSIM QDE models starting from different ontological assumptions. The QSIM representation for qualitative differential equations (QDEs) and qualitative behaviors was originally motivated by protocol analysis studies of expert explanations. A QDE represents a set of ODEs consistent with natural states of human incomplete knowledge of a physical mechanism. Qualitative simulation can be guaranteed to produce a set of qualitative behavior descriptions covering all possible behaviors of all ODEs covered by the QDE [Kuipers, 1986]. The subsequent evolution of QSIM has been dominated by the mathematical problems of retaining this guarantee while producing a tractable set of predictions. A variety of methods now exist for applying a deeper analysis, changing the level of description, or appealing to carefully chosen additional assumptions, to obtain tractable predictions from a wide range of useful models. Quantitative information can be used to annotate qualitative behaviors, preserving the coverage guarantee while providing stronger predictions. Quantitative information may be expressed as bounds on landmarks and other symbolic elements of the qualitative description [Kuipers & Berleant, 1988], by adaptively inserting new time-points to improve the resolution of the description and converge to a numerical function [Berleant & Kuipers, 1992], and by deriving envelopes bounding the possible trajectories of the system [Kay & Kuipers, 1993]. Observations are interpreted by unifying quantitative measurements against the qualitative behavior prediction, yielding either a stronger prediction or a contradiction. As quantitative uncertainty in the QDE and initial state decrease to zero, the resulting behavioral description converges to the true quantitative behavior, though computational costs can still be high with current methods. We have developed two model-compilers for QDE models: CC, which takes the component-connection view of a mechanism [Franke, 1989], and QPC, which implements an extended version of Qualitative Process Theory [Crawford, Farquhar & Kuipers, 1990]. Other model-compilers for QDEs, e.g. using bond graphs or compartmental models, have been developed elsewhere. We hope to use these model-building tools to support deeper investigation of modeling assumptions and view selection. There are several inference schemes built on the set of all possible behaviors that are particularly well-suited to reliable model-based reasoning for diagnosis and design. For design, desirable and undesirable behaviors can be identified, and additional constraints inferred to guarantee or prevent those behaviors [Franke, 1991; Kuipers & Astrom, 1994]. For monitoring and diagnosis, plausible hypotheses are unified against observations to strengthen or refute the predicted behaviors. In MIMIC [Dvorak & Kuipers, 1989], multiple hypothesized models of the system are tracked in parallel in order to reduce the ``missing model'' problem [Perrow, 1985]. Each model begins as a qualitative model, and is unified with a priori quantitative knowledge and with the stream of incoming observational data. When the model/data unification yields a contradiction, the model is refuted. When there is no contradiction, the predictions of the model are progressively strengthened, for use in procedure planning and differential diagnosis. Only under a qualitative level of description can a finite set of models guarantee the complete coverage necessary for this performance.
Download:
ZIP