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