Coenen et al

Spatial Reasoning for Geographic Information Systems

F.Coenen, B. Beattie, T.J.M.Bench-Capon, B.M.Diaz and M.J.R.Shave
Department of Computer Science, University of Liverpool, Chadwick Building, P. O. Box 147, Liverpool L69 3BX, United Kingdom

Introduction
Geographic Information Systems (GIS) are well established and used in many areas of application. However, they do not readily support spatio-temporal reasoning with respect to the data objects that they model. This is due to incompatibilities between the (raster/ vector) representations used by current GIS and that supported by existing spatio-temporal reasoning mechanisms. In this paper we describe a mechanism whereby a multi-dimensional reasoning capability can be provided for GIS. More specifically a generic representation is described that is fully compatible with the functionality of current GIS while at the same time supporting a spatio-temporal reasoning mechanism based on a constraint satisfaction paradigm. The representation has been incorporated into a demonstration spatio-temporal reasoning system which has been applied to a number of GIS related application areas, especially in the provision of support for the production of Environmental Impact Assessment (EIA) reports.

Representation
One of the principal advantages of the approach advocated here is that in does not rest on a particular representation. The approach is applicable to any representation that provides for the following features:

Sub-division of space into isomorphic sub-spaces down to some application/machine dependent resolution.
Linearisation through the allocation of unique labels to individual sub-spaces following some intuitive and predictable pattern.
An arithmetic that will allow computationally efficient manipulation of objects, through translation and rotation processes, to support the description of spatial objects and the relationships that may exist between those objects.
Applicable to any number of dimensions.
Effective data storage of spatial information.

A number of example representations that acknowledge the above have been developed. These have tended to be based on either (a) quad-tesseral or (b) complex number theory. Current versions of the system are based on the latter approach because it supports highly efficient translation through simple integer addition.

Object definition
One of the most significant requirements for the representation is that it can be used to succinctly model spatial objects of any form. With respect to GIS spatial objects are considered to posses two principal attributes: location and shape. These attributes can be instantiated to produce four distinct categories of object:

Fixed Objects: Static objects that have both a fixed shape and location.
Free Objects: Objects that have a fixed shape but only a general location (a location space) in which they can be said to exist.
Shapeless Objects: Objects that have an unknown shape and a location space.
Partially Shaped Objects: Objects that have only a partially defined shape and a location space; for example we may be aware of features such as minimum size and/or that the shape is contiguous.

Whatever the case location and shape data associated with spatial objects are defined in terms of sets of addresses.

Spatial relationships/constraints
Spatial relations are concerned with the relative nature of the locations of objects. Given that we express locations in terms of sets of addresses we express such relationships in terms of a number of set operations. To this end we identify two categories of operation:

Filters: Operations that test whether a particular relationship exists between two locations.
Mappings: Operations that force a particular relation to exist between two locations.

Current versions of the system support five filter operations available, isSubsetOf, isNotSubsetOf, isEqualTo, isNotEqualTo and intersectsWith; and two mapping operations, isIntersectionOf and isComplementOf. Using the above filters and mappings only qualitative relationships can be expressed. To quantify such relations, for example to require that an object be located to the north-west of some other object we must first define this area. This is achieved by applying offsets to the locations associated with one or both objects referred to in relation.

Operation
Using the above, spatial problems can be described in terms of a sets of facts (classes and instances of classes) and constraints (relationships). This description is referred to as the start state. The constraints are then used to continually adjust the state until all constraints have been satisfied and an end state is arrived at. Thus the reasoning mechanism comprises a constraint satisfaction technique and a constraint selection strategy, both designed to minimise the amount of computation needed to arrive at the end state. The reasoning mechanism can of course be disassociated from any particular site description technique - it is more generally applicable to all constraint satisfaction problems and not necessarily spatial ones.

The current implementation of the representation technique described here stores all partial solutions and end solutions in a solution tree structure, each node of which represents a solution state after one or more constraints have been satisfied. Branches in the tree indicate nodes where, on satisfaction of a constraint, more than one solution has been produced. This tree is constructed dynamically as the problem solution process progresses. A set of heuristics is used to ensure that fruitless branches in the tree are identified early on in the solution process so that the growth of the tree is minimised.

Conclusions
A mechanism whereby spatial reasoning can be applied to GIS data has been described. Although the approach is currently still undergoing further development the research team have been greatly encouraged by the degree of sophistication demonstrated by current versions of the system and the diversity of the applications to which it is applicable.