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