Next: Elements of Qualitative Reasoning Up: Techniques in Qualitative Reasoning Previous: Techniques in Qualitative Reasoning

## Classification of Qualitative Reasoning Tasks

The problems which have been used as test cases for qualitative reasoning systems can be classified in several ways. They can be classified by the general domain in which they occur (medicine or engineering, for example), by complexity, by the quantity of information involved, and so on. They can also be classified by the problem formulation, and the general reasoning strategy that must be taken to find the problem solution. The following list describes types of problem formulation that require different reasoning strategies.

• Explanatory tasks start from the structure of a system, and produce an explanation of behaviour in terms of that structure. Behaviour includes the response of the system when it is perturbed in a given way. De Kleer and Brown's work has emphasised this type of task; the hydraulic pressure regulator circuit is an example of deriving function from structure.
• Predictive tasks start from a description of a system which is in an unstable state. From the structure of the system, and the initial state, they produce a prediction of either a sequence of future states, or a final stable state. De Kleer's roller coaster problem, and Forbus' bouncing ball are both example of predictive tasks.
• Diagnostic tasks start from a state or behaviour that is inconsistent with the presumed structure of the system. The system specifies what element of the structure could, in changing, produce the observed behaviour. A typical domain for diagnostic tasks is electronics, where the system must identify a faulty component. Davis [Dav84b] describes one such system.
• Planning tasks start from a description of a system that is in a given state, together with a goal state for the system. The system must describe a perturbation of the system which will cause it to reach the goal state.
• Design tasks start from a description of desired behaviour for a system, and produce the structure of a system which will have the desired behaviour.

Planning and design tasks are particularly appropriate for the application of qualitative techniques, but they are not usually attempted, perhaps because they are less constrained than the other three types of task. The problem solving system described later in this thesis does carry out a planning task.

A further classification of qualitative reasoning methods can be based on whether the problem domains in which they operate are discrete or continuous. A typical discrete system can be described as a set of separate components, each of which has one or more ``ports'' by which it can be connected to other components. The state of a discrete system is the sum of the states of all components in the system at a given time, where a component state is described in terms of the values at each of its ports. Typical discrete problem domains are those of electronic circuits, and fluid circuits, where state is expressed in terms of voltage and current, or pressure and flow, at each port of a device. The connections between ports are regarded as ``conduits'', which guarantee equal values on each side of the connection [dKB84].

A continuous domain, unlike these discrete domains, cannot be completely described by topology. The ``conduit'' in discrete domains is actually a descriptive device which explicitly discounts the spatial aspects of connections between nodes, allowing physical devices to be represented as abstract networks. Using these techniques for spatial reasoning problems would result in a loss of much spatial information. The normal approach to qualitative reasoning in continuous domains however, involves exactly this type of method. The domain is made to look more discrete, by dividing the continuous space into qualitatively distinct regions. Motion can then be described as a series of transitions between discrete states - each region is represented as a possible state.

The roller coaster problem is an example of this approach, where a linear space (the length of the roller coaster) is divided into distinct regions according to slope. An object travelling the roller coaster can, from any state, make a transition into one of two other states, giving it one degree of freedom. The bouncing ball is an example where there are two dimensions in which qualitative division takes place, and hence two degrees of freedom for state transitions (up/down and left/right).

The significance of this ``discretising'' of continuous spatial domains will be considered further in later sections, but I will first describe the common elements of qualitative reasoning programs that operate on the function and structure of topologically described discrete systems.

Next: Elements of Qualitative Reasoning Up: Techniques in Qualitative Reasoning Previous: Techniques in Qualitative Reasoning
Alan Blackwell
2000-11-17