Interval-based qualitative spatial reasoning.

Abstract

The role of spatial reasoning in the development of systems in the domain of Artificial Intelligence is increasing. One particular approach, qualitative spatial reasoning, investigates the usage of abstract representation to facilitate the representation of and the reasoning with spatial information.This thesis investigates the usage of intervals along global axes as the under-lying representational and reasoning mechanism for a spatial reasoning system. Aspects that are unique to representing spatial information (flow and multi-dimensionality) are used to provide a method for classifying relations between objects at multiple levels of granularity. The combination of these two mechanisms (intervals and classification) provide the basis for the development of a querying system that allows qualitative queries about object relations in multi-dimensional space to be performed upon the representation.The second issue examined by this thesis is the problem of representing intervals when all the interval relations may not be known precisely. A three part solution is proposed. The first shows how the simplest situation, where all relations are explicit and primitive, can be represented and integrated with the above mentioned querying system. The second situation demonstrates how, for interval relations that are primitive but are not all explicitly known, an effective point based representation may be constructed. Finally, when relations between intervals are disjunctions of possible primitive interval relations, a representation is presented which allows solutions to queries to be constructed from consistent data.Our contribution is two-fold:1. a method of classifying the spatial relations and the means of querying these relations;2. a process of efficiently representing incomplete interval information and the means of efficiently querying this information.The work presented in this thesis demonstrates the utility of a multi-dimensional qualitative spatial reasoning system based upon intervals. It also demonstrates how an interval representation may be constructed for datasets that have variable levels of information about relationships between intervals represented in the dataset.