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

QSIM in MATLAB

Redesign and reimplement the entire QSIM system (including QPC, CC, QSIM, and SQSIM) as a MATLAB toolkit.

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 elsewhere.
Use existing numerical algorithms to implement NSIM and other aspects of SQSIM. Also use them to integrate Monte Carlo simulation with SQSIM.
Use online data acquisition capabilities to support MIMIC-style monitoring.
Provide access to a symbolic computing language (Lisp or Scheme) to support continued research in qualitative reasoning, particularly in model-building.

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.

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.

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.

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.

Draw on the work of Gordon Novak and his students, showing how to focus on particular abstract models.
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 information.
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.

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.

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.

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 (giorgio@dimi.uniud.it).)

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.
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:
- 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.
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).
Extend the expressiveness of the TeQsim constraint language.
DIFFICULTY: moderate.
- 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) > 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 controllers.
- 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.
  DIFFICULTY: high.
  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 [2].

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

BJK