Papers on Qualitative Reasoning
Overviews
The following encyclopedia article provides a compact introduction
to the current state of qualitative simulation.
-
Benjamin Kuipers. 2001. Qualitative simulation.
In R. A. Meyers (Ed.),
Encyclopedia of Physical Science and Technology, Third Edition,
NY: Academic Press.
The QR book is the definitive presentation of the QSIM
approach to qualitative reasoning as of about 1994. Some of the
papers below are superceded by the book; others provide more detail;
and others treat topics the book could not cover. And of course, some
report work that was done since 1994.
These two retrospectives are from a special issue of the AIJ, honoring
the 25 most-cited papers in the first 50 issues (including my 1984 and
1986 papers).
Advances Beyond the QR Book
Out of the many papers reflecting the QSIM approach to qualitative
reasoning, here is a selection that will provide excellent coverage.
There are plenty more ideas in the full list of papers, of course.
Advances in Qualitative and Semi-Quantitative Simulation
Clancy's dissertation provides abstraction, problem-decomposition, and
focusing methods reduce the problem of intractable branching to the
intrinsic complexity of the model, not limitations of the simulation
method. Berleant's work (based on his 1991 dissertation) presents Q3,
and Kay's dissertation presents NSIM and SQUID, which do
semi-quantitative reasoning on the foundation provided by the
qualitative behavior.
Using Qualitative and Semi-Quantitative Simulation
Dvorak's dissertation presents MIMIC, a method for using qualitative
and semi-quantitative models for continuous system monitoring.
Kuipers \& \Astrom show how to use qualitative simulation to prove
properties of complex, non-linear, heterogeneous controllers.
Shults \& Kuipers show how to use model-checking of temporal logic
statements against the behavior tree generated by QSIM to prove
properties of continuous systems.
Qualitative Simulation
The Basic Idea
- B. J. Kuipers. 1984.
Commonsense reasoning about causality: deriving behavior from structure.
Artificial Intelligence 24: 169-203, 1984.
Reprinted in D. G. Bobrow (Ed.), Qualitative Reasoning about Physical
Systems. New York: North-Holland, 1984. Paperback publication by MIT
Press, Cambridge, MA, 1985.
- B. J. Kuipers. 1986.
Qualitative simulation.
Artificial Intelligence 29: 289-338, 1986.
Reprinted in D. S. Weld & J. de Kleer (Eds.), Readings in Qualitative
Reasoning about Physical Systems, Los Altos, CA: Morgan Kaufmann, 1990.
Each of these papers was among the top 25 most-cited papers in the first
50 volumes of the Artificial Intelligence Journal, hence the two
AIJ 1993 retrospectives.
Protocol Analysis
- B. J. Kuipers and J. P. Kassirer. 1984.
Causal reasoning in medicine: analysis of a protocol.
Cognitive Science 8: 363-385, 1984.
- Reprinted in A. Kidd (Ed.), Knowledge Acquisition for Expert Systems,
New York: Plenum, 1987.
- B. J. Kuipers, A. J. Moskowitz, and J. P. Kassirer. 1988.
Critical
decisions under uncertainty: representation and structure.
Cognitive Science 12: 177-210, 1988.
[.pdf]
- Reprinted in G. Shafer and J. Pearl (Eds.), Readings in Uncertain
Reasoning, San Mateo, CA: Morgan Kaufmann Publishers, 1990.
Methods for Tractable Simulation
- Daniel J. Clancy and Benjamin J. Kuipers. 1998.
Qualitative simulation as a temporally-extended constraint
satisfaction problem. Proceedings of the 15th National
Conference on Artificial Intelligence (AAAI-98), AAAI/MIT
Press, 1998.
[.pdf]
- Daniel J. Clancy. 1997.
Solving complexity and ambiguity problems within qualitative
simulation. Doctoral dissertation, Department of Computer
Sciences, The University of Texas at Austin, December 1997.
[.pdf]
- D. J. Clancy and B. J. Kuipers, 1997. Model
decomposition and simulation: A component based qualitative simulation
algorithm. Proceedings from the 14th National Conference on Artificial
Intelligence (AAAI-97), August 1997.
[Abstract]
- D. J. Clancy and B. J. Kuipers, 1997. Static
and dynamic abstraction solves the problem of chatter in qualitative simulation.
Proceedings from the 14th National Conference on Artificial Intelligence
(AAAI-97), August 1997.
[Abstract]
- D. J. Clancy and B. J. Kuipers, 1997. Dynamic
chatter abstraction: a scalable technique for avoiding irrelevant distinctions
during qualitative simulation. Proceedings from the 11th International
Workshop on Qualitative Reasoning about Physical Systems (QR-97) ,
June 1997.
[Abstract]
- B. J. Kuipers, C. Chiu, D. T. Dalle Molle & D. R. Throop. 1991.
Higher-order
derivative constraints in qualitative simulation. Artificial
Intelligence 51: 343-379.
[Superceded by QR
book, chapter 10.]
- Clancy, Daniel J. and Kuipers, Benjamin J. Behavior
abstraction for tractable simulation. Proceedings from the Seventh
International Workshop on Qualitative Reasoning, May 1993.
Describes two techniques for reducing intractable branching in qualitative
simulations. Chatter box abstraction eliminates chatter by performing a
focused envisionment while Behavior Aggregation eliminations event occurrence
branching.
- D. Clancy and B. Kuipers. 1994. Model
decomposition and simulation. In Working Papers of the Eighth
International Workshop on Qualitative Reasoning about Physical Systems
(QR-94), Nara, Japan.
Describes a simulation technique that uses a cross between a state-based
representation and a history-based representation. Models are decomposed
into components and then each component is simulated separately. Temporal
correlations between variables within different components is eliminated
thus reducing many irrelevant distinctions within the behavioral description.
- Richard S. Mallory, Bruce W. Porter, and Benjamin J. Kuipers. 1996.
Comprehending
complex behavior graphs through abstraction. In Working Papers
of the Tenth International Workshop on Qualitative Reasoning (QR-96),
Fallen Leaf Lake, California.
- Lance Tokuda. 1996. Managing
occurrence branching in qualitative simulation. In Proceedings
of the National Conference on Artificial Intelligence (AAAI-96), AAAI/MIT
Press, 1996.
Trajectory Constraints for QSIM
- Pierre Fouche & Benjamin Kuipers. 1992.
Reasoning about energy in qualitative simulation.
IEEE Transactions on Systems, Man, and Cybernetics 22(1): 47-63.
[Superceded by QR
book, chapter 11.]
TeQSIM Papers
TeQSIM restricts the simulation to behaviors that
model a set of trajectory constraints specified via
temporal logic and discontinuous change expressions.
(contact clancy@cs.utexas.edu or giorgio@dimi.uniud.it
if you have any questions)
Note: The QR96 paper is the most comprehensive reference describing
the use of TeQSIM to address specific tasks. The manuscript "Focusing
qualitative simulation using temporal logic" is an extension of the
paper published in TIME-96. This paper provides a detailed description
of the syntax and semantics of the temporal logic along with a formal description
of the model checking algorithm with soundness and completeness theorms.
- Giorgio Brajnik and Daniel J. Clancy. 1997.
Focusing qualitative simulation using temporal logic: theoretical foundations.
Annals of Mathematics and Artificial Intelligence 22: 59-86, 1998.
[Abstract]
- Giorgio Brajnik and Daniel J. Clancy. 1997.
Control of hybrid systems using qualitative simulation.
Working notes from the 11th International Workshop on Qualitative Reasoning about Physical
Systems (QR-97) , June 1997.
[Abstract]
- Giorgio Brajnik and Daniel J. Clancy. 1996.
Trajectory constraints in qualitative simulation.
In Proceedings of the National Conference on Artificial Intelligence (AAAI-96), AAAI/MIT
Press, 1996.
[Abstract]
- Giorgio Brajnik and Daniel J. Clancy. 1996.
Temporal constraints on trajectories in qualitative simulation.
In Working Papers of the Tenth International Workshop on Qualitative Reasoning (QR-96),
Fallen Leaf Lake, California.
[Abstract]
- Giorgio Brajnik and Daniel J. Clancy. 1996.
Guiding and refining simulation using temporal logic.
Third International Workshop on Temporal Representation and Reasoning (TIME'96), 1996.
[Abstract]
Time-Scale Abstraction
- B. J. Kuipers. 1987. Abstraction
by time-scale in qualitative simulation. In Proceedings of the
National Conference on Artificial Intelligence (AAAI-87). Los Altos,
CA: Morgan Kaufman.
(The ftp copy is missing two figures.)
Reprinted in D. S. Weld & J. de Kleer (Eds.), Readings in Qualitative
Reasoning about Physical Systems, Los Altos, CA: Morgan Kaufmann, 1990.
[Superceded by QR
book, chapter 12.]
- Jeff Rickel and Bruce Porter. 1994. Automated
modeling for answering prediction questions: selecting the time scale and
system boundary. In Proceedings of the National Conference on
Artificial Intelligence (AAAI-94), AAAI/MIT Press, 1994.
- Jeff W. Rickel. 1995. Automated
modeling of complex systems to answer prediction questions. Doctoral
dissertation, Department of Computer Sciences, The University of Texas
at Austin.
Qualitative Phase Space
- W. W. Lee & B. J. Kuipers. 1988. Non-intersection
of trajectories in qualitative phase space: a global constraint for qualitative
simulation. In Proceedings of the National Conference on Artificial
Intelligence (AAAI-88). Los Altos, CA: Morgan Kaufmann, 1988.
Reprinted in D. S. Weld & J. de Kleer (Eds.), Readings in Qualitative
Reasoning about Physical Systems, Los Altos, CA: Morgan Kaufmann, 1990.
[Superceded by QR
book, chapter 11.]
- W. W. Lee & B. Kuipers. 1993.
A qualitative method to construct phase portraits.
Proceedings of the National Conference on Artificial Intelligence
(AAAI-93), AAAI/MIT Press, 1993.
[.pdf]
[Superceded by QR
book, chapter 11.]
(
Figure 1, Figure
2a, and Figure
2b were not incorporated into the PostScript file for this paper, so
they appear in auxiliary files.)
- Wood Wai Lee. 1993.
A Qualitative simulation based method to construct phase portraits
Doctoral dissertation, Department of Computer Sciences,
The University of Texas at Austin.
[Abstract]
Comparative Analysis
Semi-Quantitative Reasoning
Q2
Q3
NSIM, SQSIM, and SQUID
- H. Kay & B. Kuipers. 1993. Numerical
behavior envelopes for qualitative simulation. Proceedings of
the National Conference on Artificial Intelligence (AAAI-93), AAAI/MIT
Press, 1993.
- H. Kay & L. H. Ungar. 1993. Deriving
monotonic function envelopes from observations. In Working Papers
of the Seventh International Workshop on Qualitative Reasoning about Physical
Systems (QR'93), Orcas Island, Washington.
- Herbert Kay. 1996. SQsim:
a simulator for imprecise ODE models. University of Texas Artificial
Intelligence Laboratory TR AI96-247, March 1996.
[Abstract]
- Herbert Kay. 1996. Refining
imprecise models and their behaviors. Doctoral dissertation, Department
of Computer Sciences, The University of Texas at Austin, December 1996.
[Abstract]
- Herbert Kay. 1997.
Robust identification using semiquantitative methods.
IFAC Symposium on Fault Detection, Supervision and Safety
for Technical Processes (SAFEPROCESS'97), Hull, UK, 26-28 August 1997.
Describes SQUID, a new system identification method that uses
refutation rather than search to identify a model of a physical
system. By ruling out implausible models rather than searching for
the best model that fits the data, SQUID is more robust in the face
of uninformative data and structural model uncertainty than are
traditional identification methods.
- Herbert Kay. 1998.
SQSIM: a simulator for imprecise ODE models.
Computers and Chemical Engineering 23(1): 27-46, November 1998.
[manuscript .pdf (546K)]
[reprint .pdf (3825K)]
This is the definitive journal article describing SQSIM.
- Herbert Kay, Bernhard Rinner and Benjamin Kuipers. 2000.
Semi-quantitative system identification.
Artificial Intelligence 119: 103-140, 2000.
This is the definitive journal article describing SQUID.
- Herbert Kay and Lyle H. Ungar. 2000.
Estimating monotonic functions and their bounds.
American Institute of Chemical Engineering (AIChE) Journal
46(12): 2426-2434.
This is the definitive journal article describing MSQUID.
QSIM and Temporal Logic Model-Checking
This body of work treats the behavior graph output by QSIM as a
temporal model, and applies a model-checking algorithm to query the
results and prove statements in temporal logic.
The TeQSIM simulation algorithm also uses
temporal logic expressions, however, they are applied during the
simulation to restrict the simulation to behaviors that model the
expressions.
Building Qualitative Models
CC
- David W. Franke and Daniel Dvorak. 1989. Component-connection models.
Model-Based Reasoning Workshop, IJCAI-89, Detroit, Michigan, August 1989.
[Superceded by QR
book, chapter 13.]
QPC
- J. M. Crawford, A. Farquhar and B. J. Kuipers. 1990.
QPC: a compiler from physical models into qualitative differential equations.
National Conference on Artificial Intelligence (AAAI-90),
Revised version in Boi Faltings and Peter Struss (Eds.), Recent Advances
in Qualitative Physics, MIT Press, 1992.
[Superceded by QR
book, chapter 14.]
- Adam Farquhar. 1993. Automated
modeling of physical systems in the presence of incomplete knowledge.
University of Texas at Austin, Artificial Intelligence Laboratory, Technical
Report AI 93-207. (Doctoral dissertation, Department of Computer Sciences.)
- Adam Farquhar. 1994. A
qualitative physics compiler. In Proceedings of the National
Conference on Artificial Intelligence (AAAI-94), AAAI/MIT Press, 1994.
- Adam Farquhar and Giorgio Brajnik. 1994. A
semi-quantitative physics compiler. In Working Papers of the
International Workshop on Qualitative Reasoning (QR-94), 1994.
- B. Falkenhainer, A. Farquhar, D. Bobrow, R. Fikes, K. Forbus, T. Gruber,
Y. Iwasaki, and B. Kuipers. 1994. CML:
a compositional modeling language. Stanford University, Technical
Report KSL-94-16.
- Jeff Rickel and Bruce Porter. 1994. Automated
modeling for answering prediction questions: selecting the time scale and
system boundary. In Proceedings of the National Conference on
Artificial Intelligence (AAAI-94), AAAI/MIT Press, 1994.
- Jeff W. Rickel. 1995. Automated
modeling of complex systems to answer prediction questions. Doctoral
dissertation, Department of Computer Sciences, The University of Texas
at Austin. (Available as technical report AI95-234.)
MISQ
Model Revision
Applying Qualitative Reasoning
Monitoring Continuous Systems
- Charles Perrow. 1984. Normal Accidents: Living With High-Risk Technologies.
New York: Basic Books. (This book motivates the MIMIC approach to system
monitoring.)
- Daniel L. Dvorak. 1987. Expert
systems for monitoring and control. University of Texas at Austin,
Artificial Intelligence Laboratory, Technical Report AI 87-55. (Literature
review.)
- D. Dvorak & B. J. Kuipers. 1989.
Model-based monitoring of dynamic systems.
International Joint Conference on Artificial Intelligence (IJCAI-89).
- Daniel Dvorak & Benjamin Kuipers. 1991. Process
monitoring and diagnosis: a model-based approach. IEEE EXPERT
6(3): 67-74, June 1991.
[.pdf]
- Herbert Kay. 1991. Monitoring
and diagnosis of multitank flows using qualitative reasoning. (Master's
thesis, Department of Computer Sciences, The University of Texas at Austin.)
- Daniel L. Dvorak. 1992. Monitoring
and diagnosis of continuous dynamic systems using semiquantitative simulation.
University of Texas at Austin, Artificial Intelligence Laboratory, Technical
Report AI 92-170. (Doctoral dissertation, Department of Computer Sciences.)
This report provides the definitive description of the MIMIC monitoring
system.
- Bernhard Rinner & Benjamin Kuipers. 1999.
Monitoring piecewise continuous behaviors by refining semi-quantitative
trackers. In Proceedings of the Sixteenth
International Joint Conference on Artificial Intelligence (IJCAI-99).
Stockholm, Sweden.
This paper describes a reformulation and extension of the MIMIC approach
to dynamical systems that exhibit both discrete and continuous behaviors.
Each hypothesis being monitored is embodied as a tracker, which uses the
observation stream to refine its behavioral prediction, its underlying model,
and the time uncertainty of any discontinuous change.
Diagnosis of Continuous Systems
- David Throop. 1991. Model-based
diagnosis of complex, continuous mechanisms. Doctoral dissertation,
Department of Computer Sciences, University of Texas at Austin, Austin,
Texas. August 1991.
- Hwee Tou Ng. 1991. Model-based,
multiple fault diagnosis of time-varying, continuous physical devices.
IEEE Expert 6(6): 38-43, December 1991.
- Siddarth Subramanian and Raymond J. Mooney. 1994. Multiple-fault
diagnosis using general qualitative models with fault modes. In
Working Papers of the Fifth International Workshop on Principles of
Diagnosis, 1994.
- Siddarth Subramanian and Raymond J. Mooney. 1996. Qualitative
multiple-fault diagnosis of continuous dynamic systems using behavioral
modes. In Proceedings of the National Conference on Artificial
Intelligence (AAAI-96), AAAI/MIT Press, 1996.
The Space Shuttle Reaction Control System (RCS)
The following models are steps toward building qualitative models of
large-scale, realistic, mechanisms.
Design, Purpose, and Teleological Reasoning
- David W. Franke. 1989. Representing and acquiring teleological descriptions.
Model-Based Reasoning Workshop, IJCAI-89, Detroit, Michigan, August 1989.
- David W. Franke. 1991.
Deriving and using descriptions of purpose.
IEEE Expert, April 1991, pp. 41-47.
-
David W. Franke. 1992.
A theory of teleology.
Doctoral dissertation, Computer Science Department,
University of Texas at Austin, May 1992. (Available as TR AI93-201.)
Integrating Spatial and Dynamic Reasoning
Qualitative Spatial Representation
- Rajagopalan, R. 1993. A
model of spatial position based on extremal points. Proceedings
ACM Workshop on Advances in Geographic Information Systems, Arlington,
VA, November 1993.
Discussion of representation for spatial reasoning.
- Rajagopalan, R. 1994. On
shape abstractions for qualitative spatial reasoning. Working
notes of the AAAI Workshop on Spatial and Temporal Reasoning, AAAI-94,
Seattle, WA, 1994.
Further descriptions of spatial representation. Emphasis on comparison
with other methods.
Figure Understander
- Rajagopalan, R. and B. Kuipers. 1994. The
Figure Understander: a system for integrating text and diagram input to
a knowledge base. Proceedings Seventh International Conference
on Industrial and Engineering Applications of Artificial Intelligence and
Expert Systems (IEA/AIE-94), Austin, TX, May 1994.
Details of implemented system for integrating graphical and text input
to a knowledge base.
- Rajagopalan, R. 1994. Integrating
text and graphical input to a knowledge base. Working note of
the AAAI Workshop on Integration of Natural Language and Vision Processing,
AAAI-94, Seattle, WA, 1994.
Further extensions of work on integrating diagrammatic and text input to
a knowledge base.
- Raman Rajagopalan. 1995. Picture
semantics for integrating text and diagram input. Artificial
Intelligence Review 10(3-4). Special issue on Integration of
Natural Language and Vision Processing, Recent Advances Volume.
Heterogeneous Control
- Benjamin Kuipers & Karl Astrom. 1991.
The composition of heterogeneous control laws.
In Proceedings of the American Control Conference, 1991, p.630-636.
- Reprinted in A. Kandel & G. Langholz (Eds.), Fuzzy Control
Systems, CRC Press, 1993, pp. 243-261.
- Reprinted in R. R. Yager & L. A. Zadeh (Eds.), Fuzzy Sets, Neural
Networks and Soft Computing, Van Nostrand Reinhold, New York, 1994,
pp. 45-62.
- B. J. Kuipers and K. Astrom. 1994.
The composition and validation of heterogeneous control laws.
Automatica 30(2): 233-249, 1994.
- Reprinted in R. Murray-Smith and T. A. Johansen (Eds.),
Multiple Model Approaches to Nonlinear Modeling and Control,
Taylor & Francis, London, 1997, pages 231-255.
-
B. Kuipers and S. Ramamoorthy. 2002.
Qualitative modeling and heterogeneous control of global system
behavior.
In C. J. Tomlin and M. R. Greenstreet (Eds.), Hybrid
Systems: Computation and Control, Lecture Notes in Computer
Science, Springer Verlag, 2002.
- S. Ramamoorthy and B. Kuipers. 2003.
Qualitative heterogeneous control of higher order systems.
In O. Maler and A. Pnueli (Eds.), Hybrid
Systems: Computation and Control, Lecture Notes in Computer
Science, Springer Verlag, 2003.
- S. Ramamoorthy and B. Kuipers. 2004.
Controller synthesis using qualitative models and simulation.
In J. de Kleer and K. Forbus (Eds.), International Workshop
on Qualitative Reasoning (QR-2004).
BJK