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.)

Ben Kuipers


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 audience.

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.

Semi-Quantitative Trackers

MIMIC 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.

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 tracking set.

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.

Order-of-Magnitude Reasoning

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.

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 problem.)

Williams [AAAI-94] used qualitative analysis to reduce the dimensionality of the space an optimizer needs to explore to solve a given problem.

Improvements to TeQsim

(These are provided by Giorgio Brajnik (

  1. 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 [1] we introduce "progressed formulas" (page 73 and ff.), "present formula extractor", "future formula extractor", and "extended propositional interpretation". 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 subformula.

  2. Show that TeQsim can be used to prove stability of non-linear 2nd/3rd order dynamical systems.
    DIFFICULTY: high

    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.
    NOTE: to specify complex properties like "decreasing oscillations" appropriate extensions to the PLTL used by TeQsim are needed (see below).

  3. Extend the expressiveness of the TeQsim constraint language.
    DIFFICULTY: moderate.

[1] G. Brajnik and D. Clancy, 1998, "Focusing qualitative simulation using temporal logic: theoretical foundations", Annals of Mathematics and Artificial Intelligence, 22, 59-88.

[2] 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.