% This is a DRAFT document describing QSIM and providing further references. \documentstyle[11pt]{article} \pagestyle{myheadings} \markright{QSIM \hfill } \renewcommand{\baselinestretch}{1} %\setlength{\oddsidemargin}{0in} \setlength{\textwidth}{6in} \setlength{\topmargin}{0in} \setlength{\headheight}{.25in} %\setlength{\textheight}{8.5in} \newcommand{\Astrom}{\AA{}str\"{o}m} \newcommand{\Fouche}{Fouch\'{e}} \title{QSIM: A Tool for Modeling and Simulation \\ with Incomplete Knowledge\thanks{This work has taken place in the Qualitative Reasoning Group at the Artificial Intelligence Laboratory, The University of Texas at Austin. Research of the Qualitative Reasoning Group is supported in part by NSF grants IRI-8904454, IRI-9017047, and IRI-9216584, and by NASA grants NCC 2-760 and NAG 9-665.}} \author{Benjamin Kuipers \\ Department of Computer Sciences \\ University of Texas at Austin \\ Austin, Texas 78712 USA \\ \mbox{\tt kuipers@cs.utexas.edu}} \date{July 27, 1993} \begin{document} \maketitle 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, to appear]. 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 {\em 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. \section*{Details} \begin{itemize} \item The QSIM software is experimental, and is provided to researchers as a professional courtesy, with no warranty of any kind. Any commercial rights are retained. \item Installation instructions, release notes and other documentation is provided in the documentation directory that is created once QSIM is untarred. The release notes provide information regarding the platforms that are supported. \item The distribution includes code for QSIM and a number of its extensions, documented and undocumented. A draft manual is included, but is quite incomplete. The examples illustrate many of the available features. Exploring the code should be worthwhile. \item Once QSIM has been loaded in Lisp, evaluate {\tt (qt)} for a partial menu of examples. \item There is a mailing list \mbox{\tt qsim-users@cs.utexas.edu} for discussing QSIM modeling and simulation issues. There is a mailing list \mbox{\tt qphysics@cs.uwashington.edu} for qualitative reasoning issues generally. \item Please refer any questions or comments to either \mbox{\tt clancy@cs.utexas.edu} or \mbox{\tt kuipers@cs.utexas.edu}. \item To obtain any additional software that is not included in this distribution (such as MIMIC or QPC) or to inquire about other extensions that are being developed that might be relevent to your task please contact us. \end{itemize} \section*{References on QSIM and Related Topics} \begin{enumerate}\small \item D. Berleant \& B. Kuipers. 1992. Combined qualitative and numerical simulation with Q3. In Boi Faltings and Peter Struss (Eds.), {\em Recent Advances in Qualitative Physics}, MIT Press, 1992. \item J. M. Crawford, A. Farquhar, B. J. Kuipers. 1990. QPC: a compiler from physical models into qualitative differential equations. {\it Proceedings of the National Conference on Artificial Intelligence (AAAI-90)}, AAAI/MIT Press, 1990. Revised version in Boi Faltings and Peter Struss (Eds.), {\em Recent Advances in Qualitative Physics}, MIT Press, 1992. \item D. Dvorak and B. Kuipers. 1989. Model-based monitoring of dynamic systems. In {\it Proceedings of the Eleventh International Joint Conference on Artificial Intelligence (IJCAI-89)}. Los Altos, CA: Morgan Kaufman. \item D. Dvorak \& B. Kuipers. 1991. Process monitoring and diagnosis: a model-based approach. {\it IEEE EXPERT} {\bf 6}(3): 67-74, June 1991. \item Pierre \Fouche\ \& Benjamin Kuipers. 1992. Reasoning about energy in qualitative simulation. {\it IEEE Transactions on Systems, Man, and Cybernetics} {\bf 22}(1): 47-63. \item D. W. Franke. 1989. Representing and acquiring teleological descriptions. Model-Based Reasoning Workshop, IJCAI-89, Detroit, Michigan, August 1989. \item D. W. Franke. 1991. Deriving and using descriptions of purpose. {\it IEEE Expert}, April 1991, pp. 41-47. \item D. W. Franke and D. Dvorak. 1989. Component-connection models. Model-Based Reasoning Workshop, IJCAI-89, Detroit, Michigan, August 1989. \item H. Kay \& B. Kuipers. 1993. Numerical behavior envelopes for qualitative simulation. {\it Proceedings of the National Conference on Artificial Intelligence (AAAI-93)}, AAAI/MIT Press, 1993. \item B. J. Kuipers. 1984. Commonsense reasoning about causality: deriving behavior from structure. {\it Artificial Intelligence} {\bf 24}: 169 - 204. \item B. J. Kuipers. 1986. Qualitative simulation. {\it Artificial Intelligence} {\bf 29}: 289 - 338. \item B. Kuipers. 1987. Abstraction by time-scale in qualitative simulation. {\it Proceedings of the National Conference on Artificial Intelligence (AAAI-87)}. Los Altos, CA: Morgan Kaufman. \item B. Kuipers. 1989. Qualitative reasoning: modeling and simulation with incomplete knowledge. {\it Automatica} {\bf 25}: 571-585. \item B. J. Kuipers. Reasoning with qualitative models. 1993. {\em Artificial Intelligence} {\bf 59}: 125-132. \item B. J. Kuipers. Qualitative simulation: then and now. 1993. {\em Artificial Intelligence} {\bf 59}: 133-140. \item B. J. Kuipers and K. \Astrom. The composition and validation of heterogeneous control laws. {\em Automatica}, in press. \item B. Kuipers and D. Berleant. 1988. Using incomplete quantitative knowledge in qualitative reasoning. In {\it Proceedings of the National Conference on Artificial Intelligence (AAAI-88)}. Los Altos, CA: Morgan Kaufman. \item B. Kuipers and C. Chiu. 1987. Taming intractible branching in qualitative simulation. {\it Proceedings of the Tenth International Joint Conference on Artificial Intelligence (IJCAI-87)}. Los Altos, CA: Morgan Kaufman. \item B. J. Kuipers, C. Chiu, D. T. Dalle Molle \& D. R. Throop. 1991. Higher-order derivative constraints in qualitative simulation. {\it Artificial Intelligence} {\bf 51}: 343-379. \item B. J. Kuipers and J. P. Kassirer. 1984. Causal reasoning in medicine: analysis of a protocol. {\it Cognitive Science} {\bf 8}: 363 - 385. \item W. W. Lee \& B. Kuipers. 1993. A qualitative method to construct phase portraits. {\it Proceedings of the National Conference on Artificial Intelligence (AAAI-93)}, AAAI/MIT Press, 1993. \item W. W. Lee \& B. Kuipers. 1988. Non-intersection of trajectories in qualitative phase space: a global constraint for qualitative simulation. In {\it Proceedings of the National Conference on Artificial Intelligence (AAAI-88)}. Los Altos, CA: Morgan Kaufman. \item Charles Perrow. 1984. {\it Normal Accidents: Living With High-Risk Technologies}. New York: Basic Books. \end{enumerate} \end{document}