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

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

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.

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.

Evaluate this representation on a monitoring problem simple enough to enumerate all the hypotheses and track them all simultaneously.

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

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

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

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

- 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: highDuring 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.

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

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

[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