next up previous contents
Next: Envisionment of Motion through Up: A Program for Reasoning Previous: Representing Contact State

Contact State Transitions

All possible sliding motions involve changes of state between the above categories of contact, and this is represented by corresponding changes in the contact list for the moving object, and in those of the obstacles. The change in state which occurs after any given sliding motion depends on the shape of the features involved, and on the direction of the slide.

The shape of features which are neighbours to the current contact site is static information which can be obtained directly from the qualitative scene description. The direction of sliding motion is dynamic information, which must be determined for each change of state. Direction of sliding is conveniently described for a single moving object as being either clockwise or anticlockwise with respect to the boundary of the moving object (for multiple moving objects, direction would have to be stated relative to one of them).

The distinction between the clockwise and anticlockwise sliding directions in motion description must be supported by an annotation of shape description that establishes which neighbours of a feature lie in a clockwise or anticlockwise direction (this can be stated independently relative to the boundary of each object). If this were not done, the reasoning program would not be able to determine the ``handedness'' of the object descriptions, and would not be able to distinguish between mirror copies of objects.

A substantial amount of effort in the implementation of this sliding analysis program involved providing functions for accessing the shape representation in terms of the two directions, and describing both contacts and object boundaries in these terms. A typical problem in doing this was that the list of features which comprised a subpart or object was described as a simple list, whereas the clockwise ordering of neighbouring features had to be circular. The necessity for use of circular lists is mentioned again briefly in the discussion of implementation.

Having established the present state, the neighbouring features to the current contact position, and the direction in which motion toward the neighbouring features is taking place, it is possible to identify the next qualitative change in contact state that will occur.

The list of possible state transitions is much less than the square of the number of states, because very few states can possibly follow each unique contact type in a physically possible object description. In particular, any contact between non-vertex combinations must be followed by a contact that involves vertices. Possible transitions can be categorised in terms of their behaviour around vertices. The program described here distinguishes between three important types of sliding state around a vertex. I describe these as ``aligned'' contact, ``sliding over'' a vertex, and ``falling off'' a vertex.

There are therefore three basic types of aligned to non-aligned transition: the slide-over motion, the slide-to/slide-from motion, and the fall-off motion. These transition categories, when expanded to included the relevant cases from the list of possible contact states, can describe the motion of a single moving object over the boundary of a single obstacle, but they must be extended to describe an object moving around a number of obstacles. This extension is not too complex, because two obstacles in contact (or even near each other) form a new feature that behaves like one of the normal features. The extensions that would be necessary identify the equivalent feature, and allow the concept of ``neighbouring'' features to include features on other objects which are candidates for the next contact.

Transitions between contacts with features on different objects are therefore of the same types as transitions between features on the same object. The main distinction is between the cases of sliding over an aligned boundary between objects, and an overlapping boundary. The simplest case is the aligned boundary, in which there is an intermediate state where the moving object is in contact with both objects.

There are several cases of overlapping obstacle contacts: there are two directions from which to approach an overlap - from the high side, the moving object will ``fall off'' onto the second obstacle. From the low side, the moving object will come into contact with the hanging part of the overlap. In either case, the behaviour also depends on the curvature of neighbouring shape features.

The level of analysis presented so far does not deal with one important case: contact between a concave and convex curve, or even between the areas surrounding a concave and convex vertex. If the angles of the curves or vertices include right angles, or if one is acute and the other obtuse, the resulting contact states can be determined. If both are acute or both obtuse, it is impossible to determine the contact that will occur, because the relative sizes of the angles are unknown.

A second case which is difficult to analyse is sliding across the gap between two obstacles which are not touching each other. This would require direct comparison between the size of the gap between the obstacles, and the size of the moving object. The other state transitions I have described can all be qualitatively analysed without size or angle magnitude comparison, and it was this case which made clear the deficiencies of the ASSF representation with respect to direct comparison of feature sizes. This is discussed further with other implementation issues.

next up previous contents
Next: Envisionment of Motion through Up: A Program for Reasoning Previous: Representing Contact State
Alan Blackwell