next up previous contents
Next: Representing Contact State Up: Implementations of Two Qualitative Previous: Implementations of Two Qualitative

A Program for Reasoning About Sliding

I proposed the ``sliding problem'' as an initial case study to test the power of the ASSF shape representation. The two dimensional scene in which the task is carried out includes a number of stationary obstacles, and one moving object. The task for the program is to list the contacts that might occur if the moving object were sliding around the obstacles (the only constraint on motion in sliding is that the moving object must stay in contact with at least one of the obstacles at all times).

The possible contacts which the program must find are qualitatively described in terms of the pair of features which are in contact: one on the moving object, and one on an obstacle. The moving object might be in contact with more than one obstacle at one time, so one entry in the set of possible contacts might include several of these feature pairs.

The sliding problem is not an especially difficult one when compared to human performance in spatial reasoning, or even when compared to some robot reasoning systems. It is, however, a problem which would not be trivial to solve using computational methods based on numerical geometry. The main point of interest as a problem in qualitative reasoning is that the solution must be expressed in terms of qualitative state; the definition of a ``contact'' implies a particular qualitative state, whereas a numeric system could provide only a range of coordinate values over which the position constraints of the problem are met.

The overall method described below for solving this problem could be implemented equally well using any qualitative shape description that includes a description of boundary features. The last part of this section discusses some technical details of my implementation using the ASSF representation, but a number of these points would apply to any representation.

The main challenge in this problem lies in the need to qualitatively describe the process of sliding, and the state of contact. Both involve interaction between objects that takes place on the boundaries of those objects. The two are closely related by the formulation of the problem, which defines the constraint on sliding motion in terms of contact, and asks for a set of contacts which can occur through sliding. It is therefore natural to conversely describe the process of sliding as a change in contact state over time.

In order to solve the problem, a program must therefore be capable of remembering more than one state of the system under analysis, and it must be capable of ordering these states with respect to the times at which they occur. It must also be capable of representing and analysing state transition. The following sections discuss the representation of contact state, the analysis of state transition, and finally the overall reasoning strategy followed by the program.



 
next up previous contents
Next: Representing Contact State Up: Implementations of Two Qualitative Previous: Implementations of Two Qualitative
Alan Blackwell
2000-11-17