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