Fruitful Problems in Qualitative Reasoning
These are problems in qualitative reasoning that I consider to be
particularly fruitful right now, in the sense of being both accessible
and important. A good solution to any of these problems will not only
be valuable in its own right, but will enable substantial further work
by the researcher and by others.
I encourage anyone in the QR community to take these on. I will be
happy to give email advice when I can.
(Newly added problems go onto the end.)
QSIM in MATLAB
Redesign and reimplement the entire QSIM system (including QPC, CC,
QSIM, and SQSIM) as a MATLAB toolkit.
The goal is to provide access to major existing engineering software
packages, and to make QR methods more accessible to the engineering
- Define an input representation based on standard algebraic and
differential equation notations. The constraint representation
currently used in QSIM should be, at most, an internal representation
hidden from the user.
- Use existing algebraic manipulation facilities to simplify the
given model, to simplify the Q2 equations before falling back on
interval propagation, to derive higher-order derivative constraints, and
- Use existing numerical algorithms to implement NSIM and other
aspects of SQSIM. Also use them to integrate Monte Carlo simulation
- Use online data acquisition capabilities to support MIMIC-style
- Provide access to a symbolic computing language (Lisp or Scheme)
to support continued research in qualitative reasoning, particularly
While MATLAB is probably the most widespread engineering package, and
their toolkit interface is a good target for a reimplemented QSIM,
consider the major alternatives that may offer significant advantages
in particular areas: LabView, Maple, Mathematica, and perhaps others.
can be implemented as a collection of modular agents, called trackers,
each of which embodies the hypothesis that the observation stream
corresponds to a particular qualitative model and behavior.
To make the tracker a more effective predictor of the consequences of
its hypothesis and the observation stream, implement it to have three
levels of prediction.
This set of predictions provides a range of trade-offs between
soundness and power. For example, an observation that contradicts the
broad envelopes predicted by SQSIM is a hard contradiction, refuting
the hypothesis and killing the tracker. Contradicting the Monte Carlo
prediction greatly reduces confidence in the tracker, but doesn't
utterly refute it. One never expects to match a single behavior, but
distance from it slowly decreases one's confidence in the hypothesis.
- Broad envelopes derived by SQSIM [Kay, 1996], representing the
sound consequences of the SQDE and the observations.
- Narrow envelopes derived by Monte Carlo simulation [Gazi and
Ungar], using values chosen within interval bounds and functions
chosen within static envelopes around monotonic functions. This
eliminates error due to aliasing within intervals, and adds error due
to the possibility of missed behaviors.
- Single numerical trajectory predicted from the "modal ODE" ---
the most likely ODE model consistent with the SQDE.
Evaluate this representation on a monitoring problem simple enough to
enumerate all the hypotheses and track them all simultaneously.
Managing the Tracking Set
When applying MIMIC to a complex system, the set of trackers must
change dynamically, and we must worry about intractable growth of the
- Analyze the current set of trackers, and determine the best next
observation to do differential diagnosis among their hypotheses.
- If the tracking set is growing, do model-based diagnosis to
focus on the hypotheses that are the most likely explanations.
Compositional Modeling for Physics Problem Solving
Build a solver for textbook physics problems capable of covering the
first-year high-school physics course.
The unique strength of qualitative reasoning here is the ability to
record explicitly every assumption involved in the
model-building process. In case the model fails, the enumerated
assumptions help define a search space for diagnosing the problem and
revising the solution approach.
- Draw on the work of Gordon
Novak and his students, showing how to focus on particular
- It may be helpful to use the Figure
Understander as a way to simplify input and interpretation of
diagrams in the problem statement.
- Use the representations and inference methods in QPC, QSIM, and
SQSIM to express the knowledge base of model-fragments, assemble them
into models, do qualitative simulation, and test them for approximate
consistency with known quantitative bounds and order-of-magnitude
- You might need to use
TeQSIM to select the qualitative behaviors relevant to the
behavior referred to in the problem.
- The Q2 equations [Kuipers, QR book, chapter 9] provide a set of
algebraic variables and equations. whose solution solves the problem.
You may need to use Mathematica or Maple to solve the equations.
There have been quite a number of papers on order-of-magnitude
reasoning, but few that integrate it into qualitative modeling and
simulation, and make it as usable for routine semi-quantitative
reasoning as interval bounds are now.
In both cases, the given order-of-magnitude assertions propagate
across constraints to infer new ones. A contradiction means that the
behavior or model is filtered out. There will be design decisions about
how given information should be expressed.
- Implement order-of-magnitude reasoning as a state or behavior
filter, much the way SQSIM (Q2, Q3, and NSIM) does with interval
bounds. In DEDALE [Dague, et al, AAAI-87], a predicted qualitative
behavior is tested for consistency with a given set of
order-of-magnitude relations and refuted if it fails.
- Integrate order-of-magnitude reasoning with QPC as a filter on
model-fragments and their compositions. See Raiman and Williams
[QR-92; AAAI/IJCAI?], who proposed a "patchwork" model derivation
method that exploits order-of-magnitude relations to apply different
simplifications in different regions of the state space.
Example: Controller Tuning
Consider the problem of tuning a PI or PID controller for a simple
plant. Where are the qualitative distinctions in tuning-parameter
space? How does this vary with the dynamics of the plant? Can these
properties be used to do qualitative system identification of the
plant, or to do qualitative tuning to put an optimizer into the right
region? How does this compare with classical methods for tuning?
Optimization and Qualitative Models
A qualitative behavior represents a class of real-valued behaviors.
An optimization algorithm can select an individual member of that
class to optimize a given criterion. Build this insight into a
general-purpose tool that designers can use. (See the following
Williams [AAAI-94] used qualitative analysis to reduce the
dimensionality of the space an optimizer needs to explore to solve a
Improvements to TeQsim
(These are provided by Giorgio Brajnik (firstname.lastname@example.org).)
 G. Brajnik and D. Clancy, 1998, "Focusing qualitative simulation using
temporal logic: theoretical foundations", Annals of Mathematics and
Artificial Intelligence, 22, 59-88.
- Create a more efficient and cleaner algorithm to check validity of
temporal logic formulae.
DIFFICULTY: easy (the most difficult part is to familiarize with
the TeQsim program)
In  we introduce "progressed formulas" (page 73 and ff.), "present
formula extractor", "future formula extractor", and "extended
The idea is that temporal formulae should be progressively
transformed into equivalent formulae that make explicit a
subformula that is not temporal and that can be evaluated wrt
current state. In this way the checking algorithm does not need to
backtrack and repeat many times the evaluation of a same
- Show that TeQsim can be used to prove stability of
non-linear 2nd/3rd order dynamical systems.
During the many discussions with Bjarne Foss (a control system
person), the most relevant issues in contemporary control theory
are performance and stability of nonlinear controlled
systems. Instability should be injected in simple models by either:
I tried to do the latter, by taking a traditional Qsim model of the
Utube and adding an integral controller on the final outflow.
I played with several variations of this family of models (2nd and
3rd order, with/without energy constraints) trying -- without much
success -- to get a reasonable set of semiquantitative behaviors (I
did not use NSIM).
The idea was then to use TeQsim to specify stability as a TL
formula (something like "decreasing oscillations") and run it to
see if a model satisfies or not that constraint. I haven't been able
to achieve this basically because I wasn't able to get reasonably
good Qsim models.
- using delay operators (and hence infinite dimensional states),
- use discrete time (and potentially dealing with hybrid systems),
- add dynamics to sensors and/or to actuators.
NOTE: to specify complex properties like "decreasing oscillations"
appropriate extensions to the PLTL used by TeQsim are needed (see
- Extend the expressiveness of the TeQsim constraint language.
- New temporal operators: to specify for example "decreasing
oscillations" two new operator could be invented "(COMPARE p q)"
and (DECREASES x) where:
(DECREASES x) is a special proposition (bi-formula)
whose interpretation is
based on a pair of states (s,s') and is true iff qmag(x,s) >
(COMPARE p q) requires that q is a bi-formula and is true for a
behavior iff whenever p holds on a subbehavior (s_0,s_1,...,s_n,..)
then q holds for any (s_0,s_j), with j>0.
Then "decreasing oscillations" could be expressed as:
(COMPARE (STD x) (DECREASES X)).
- Metric temporal logic: introduce temporally-limited
versions of temporal quantifiers UNTIL and RELEASES so that one
could say: (UNTIL p q).
Then one could specify in TeQsim constraints like "within 50
seconds the tank level reaches 50 inches", which are needed if
TeQsim is going to be used to prove performance properties of
- Use TeQsim to specify trajectories for exogenous variables to
be used with NSIM.
- Extend TeQsim to represent not only intervals but also bounding
envelopes (that is add new operators and objects that represent
envelopes and their application). [Bert's suggestion]
- Use TeQsim to describe and specify hybrid systems.
TeQsim can be used to specify discrete changes on exogenous
variables. Together with Qsim abilities to switch between models
(or perhaps QPC/SQPC model generation capabilities) it could be
used to reason about the evolution of hybrid discrete-continuous
systems, like when a discrete controller is applied to a continuous
system. One interesting avenue is the generation, on the fly, of
discrete actions that are guaranteed to satisfy a given constraint.
See initial ideas in .
 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.