Kuipers, B. (1986). Qualitative Simulation. Artificial Intelligence, 29(3), 289–338. doi:10.1016/0004-3702(86)90073-1

Summary

Kuipers gives an overview of what qualitative simulation is, how it can be used, and what some its limitations are. He focuses specifically on the QSIM system, which is similar to other qualitative reasoning systems (e.g. from de Kleer, Forbus) but which also has a few differences. Regardless of the specific system, the point of qualitative reasoning is to break down continuous sytems into discrete analogues. Given a set of constraints that the continuous system must follow, along with an initial qualitative state description, qualitative reasoning determines how the system must evolve without necessarily specifying any precise values. For example, qualitative reasoning can be used to infer that if a ball is thrown upwards, it must eventually come down again (but the specific position and velocity of the ball need not be specified).

Kuipers shows that the QSIM method will always produce the true behavior of the system that it describes, but it may additionally produce false behaviors if the proper constraints aren’t given (e.g. conservation of energy).

Methods

n/a

Algorithm

Qualitative behavior

The qualitative description of a continuous and differentiable function $f:[a,b]\rightarrow\mathbb{R}^*$ relies on a set of landmark values, which include 0, $f(a)$, $f(b)$, and $f(t)$ where $t$ is a critical point of the function. A distinguished time point is the corresponding $t$ for a landmark value.

Then, the qualitative state of the function at a particular point in time is $\mathrm{QS}(f,t)=[\mathrm{qval},\mathrm{qdir}]$, where $\mathrm{qval}$ is either a landmark value or the interval between landmark values, and where $\mathrm{qdir}$ is $\mathrm{sgn}(f^\prime(t))$. The qualitative behavior of a function is the sequence $[\mathrm{QS}(f,t_0),\mathrm{QS}(f,t_0,t_1),\mathrm{QS}(f,t_1),\ldots{},\mathrm{QS}(f,t_{n-1},t_n),\mathrm{QS}(f,t_n)]$, where each $t_i$ is a distinguished time point.

A qualitative state transition is either a P-transition, which is the transition from a distinguished time point to an interval between distinguished time points: $\mathrm{QS}(f,t_i)\Rightarrow \mathrm{QS}(f, t_i, t_{i+1})$. Similarly, a I-transition is the other way around: $\mathrm{QS}(f,t_{i-1},t_i)\Rightarrow\mathrm{QS}(f,t_i)$.

Qualitative structure

Constraints can be imposed on either a single function, or on a pair of functions, for example:

  • $\mathrm{ADD}(f, g, h)$ is defined as $f(t)+g(t)=h(t)$
  • $\mathrm{MULT}(f, g, h)$ is defined as $f(t)\cdot{}g(t)=h(t)$
  • $\mathrm{MINUS}(f, g)$ is defined as $f(t)=-g(t)$
  • $\mathrm{DERIV}(f, g)$ is defined as $f^\prime(t)=g(t)$
  • $\mathrm{M}^+(f, g)$ is defined as $f(t)=H(g(t))$ where $H^\prime(x)>0$. This rougly says that $f$ and $g$ are directly proportional
  • $\mathrm{M}^-(f, g)$ is defined as $f(t)=H(g(t))$ where $H^\prime(x)<0$. This roughly says that $f$ and $g$ are inversely proportional.

Note that these constraints only need to hold for $t$ within the domain of $f$ and $g$ (i.e., so you could have $x=\cos\theta$ on $\theta\in(0,\pi)$ and then $\mathrm{M}^-(\theta, x)$ will be true for that specific range of $\theta$).

Qualitative simulation

The qualitative simulation takes as input the functions, constraints, landmark values, upper and lower range limits, an initial time point $t_0$, and initial qualitative values for the functions.

The qualitative simulation returns as output the qualitative behavior descriptions for the given functions, which include: the distinguished time points, landmark values (which may include additional ones not given as input), and qualitative state descriptions for each distinguished time point and interal between time points.

The way that the simulation works for a single state is, roughly:

  1. For each function, determine the P-transitions and I-transitions for the current qualitative state
  2. For each constraint, form combinations of “transition tuples” for each of the functions involved in the constraint, and filter out those which violate the constraint
  3. For each constraint, filter our transition tuples for which there are no transition tuples for adjacent constraints that have the same transition for the shared parameter (e.g. $(I4,I9)$ for $\mathrm{DERIV}(Y,V)$ would be filtered out if there is no corresponding tuple beginning with $I9$ for $\mathrm{DERIV}(V, A)$).
  4. Generate possible global interpretations based on the remaining tuples
  5. Check which interpretations constitute either a state that has been visited before (cylce) or if the function diverges (goes to infinity). These are leaves of the seach tree; others are next possible states.

Takeaways

This was a really nice, detailed explanation of how (one particular version of) qualitative simulation and reasoning works. I think it’s cool that you can show that this type of qualitative reasoning will produce the right answer (even if it might also produce other answers). It seems like the big challenge is—as Kuipers points out in the discussion—is determining what the constraints on the system are in the first place. This is somewhat related to the question of how you set up a physical simulation in the first place (i.e. object positions, velocities), though in this case the choices that need to be made are the functional constraints, rather than specifics about the object. Certaintly in qualitative simulation it seems that it is easier to specify information about the state of the object: the hard part is in determining what information to specify about the function.

Also, this seems to apply specifically to continuous systems than can be described by a differential equation, though, so I’m interested in understanding better how this approach works with things that are not continuous (for example, colliding objects) or situations where there are additional types of constraints, such as inequality or equality constraints. I expect some of the next readings will give me a better sense of this.