Qualitative Spatial Reasoning Scenarios

This section summarises two tasks which are typical robot reasoning problems, and which a useful qualitative spatial reasoning system should be able to perform. The system described later has successfully performed both of these tasks.

The first task deals with sliding motion in two dimensions:

Given a scene consisting of a collection of objects, and one object designated as the moving object, what contacts can be established between the moving object and the others, under the constraint that during all motion, the moving object must remain in contact with at least one other (i.e. it is sliding around the other objects).

The problem here is to produce what is called an ``envisionment'' in qualitative physics - a set of possible future states for a system which is in a known initial state. The major difference between a ``robot'' problem such as this, and a qualitative physics problem, is that the actions of a system analysed in qualitative physics normally result from instability in the initial state, whereas here the robot has to physically act on the system to produce a change of state.

Finding a solution to this problem requires firstly that the object boundaries and position be represented in such a way that possible sliding directions can be found, and secondly that the results of any motion can be described in this representation, so that further motions can be planned. The three reasoning stages in finding a problem solution are therefore:

1.

Propose a possible slide from the current position.

2.

Determine the possible contact positions at the first change of ``state'' after this slide.

3.

Compile a history of states that would be achieved after a series of such sliding motions.

The second task is a simple two dimensional case of the ``Mover's Problem'' or the ``Findpath'' problem, which can be stated as:

Given an initial scene arrangement consisting of an object to be moved, and N obstacles to the motion; find a path for the object through the obstacles, such that it will not collide with any of them.

Note that the mover's problem is considerably more complex in three dimensions than it is in two. I have discussed in chapter 4 my reasons for limiting my approach to the two dimensional case. A two-dimensional scene is shown in figure 1.1.

 

Figure 1.1: Scene Example for the ``Mover's Problem''

The problem for the robot is to find a path for the moving object which will move it from amongst the surrounding obstacles, so that it can be either removed from the scene, or manipulated in open space.

In solving this problem, the reasoning system must ask the following questions:

• What obstacles prevent the moving object from moving into free space?
• Are there any gaps between those obstacles which might provide a path?
• Are any of the gaps large enough for the object to fit through?
• What direction should the object be moved in, if it is to approach a suitable gap?
• Are there any other obstacles along the path to that gap?
• If there are other obstacles, how should the path be modified in order to avoid them?

This thesis describes a qualitative representation for physical objects and scenes. The representation has been used to describe workspaces for the two tasks presented above. Algorithms for carrying out the tasks have been implemented, and both the algorithms and their implementations will be discussed.