The main achievement of the research described in this thesis has been the development of a representation to support qualitative spatial reasoning. The three key elements of this representation are the qualitative extended polygon boundary for shape description, the proximity transform for describing relative position, and the partial distance ordering for relating boundary size and proximity information.
The extended polygon boundary is a simple and effective qualitative description of shape, at a level which is easily constructed or interpreted by humans. An EPB shape description can include multiple levels of detail for individual portions of an object boundary, or for complete objects. The basic elements of the EPB description could be provided directly from a sensory system.
The proximity transform can extract useful qualitative information directly from two dimensional data describing a scene at a sensory (pixel or edge detection) level. It provides a basis for a quantity space which can describe two dimensional relative position and orientation. The distinction between ``internal'' and ``external'' proximity provides a consistent way of comparing shape to position.
The partial ordering is a well established technique for use in qualitative reasoning systems (although the quantity space is more often used in qualitative physics). The application of a partial ordering to distance information, allowing the comparison of proximity information to object size, results in the partial distance ordering. This ordering has many important benefits for robust reasoning. The consistent treatment of feature size, distance between objects, and ``synthetic'' quantities resulting from geometric constructions, simplifies the implementation of qualitative geometric reasoning functions.
A qualitative proximity description of a scene constitutes a qualitative description of a unique state - a combination of objects in known relative positions. This state description can be used for envisionment purposes, without requiring any division of space into discrete regions. Envisionment of future states resulting from motion can be used for spatial reasoning problems such as path planning.
As a planning system, qualitative methods based on the PDO/EPB representation can carry out some tasks that are required in robot reasoning. The robust nature of the qualitative geometric reasoning provides the advantages for robotics of an ability to reason with incomplete information, and graceful degradation of the overall reasoning system. The human-like level at which this spatial reasoning is carried out gives it natural advantages for applications where humans interact with robot reasoning systems (such as task-level robot programming).
The PDO/EPB representation is a non-numeric technique for describing and reasoning about shape, space, position and motion at a simple geometric level. It has been developed together with qualitative spatial reasoning programs that can solve simple, but useful problems in spatial reasoning. It is an alternative approach to major reasoning tasks in qualitative mechanical physics and in robotics.