SPATIO-TEMPORAL REASONING USING A MULTI-DIMENSIONAL TESSERAL REPRESENTATION
Frans Coenen, B. Beattie, Trevor J. M. Bench-Capon, Bernard M. Diaz, Michael J. R. Shave · European Conference on Artificial Intelligence · 1998
A versatile and universally applicable quantitative multi - dimensional reasoning mechanism founded on a unique linear tesseral representation of space is described. The reasoning mechanism is based on a constraint satisfaction mechanism supported by a heuris- tically guided constraint selection strategy. The mechani sm has been incorporated into a spatio-temporal reasoning system, the SPARTA (SPAtial Reasoning using Tesseral Addressing) system, which has been applied successfully to a diverse number of spatial applications. In this paper we describe a quantitative spatio-temporal re asoning system founded on a tesseral representation of Euclidean space which is universally applicable to N-dimensional spatial data st ored or pre- sented using a raster style encoding. The universal applica bility of- fered by the reasoning system is a direct consequence of the tesseral representation on which it is founded. This representation may be viewed as either an intermediate representation which link s the rea- soning mechanism with some primary representation (raster and by extension vector), or as a primary representation in its own right. The reasoning mechanism comprises a constraint satisfaction ap- proach to spatial problem solving supported by a heuristica lly guided constraint selection mechanism so as to minimise the search space. The mechanism has been incorporated into a demonstration spatio- temporal reasoning system, the SPARTA (SPAtial Reasoning using Tesseral Addressing) system. Spatial problems are passed to this sys- tem in the form of a script comprising a set of object descript ions and a set of constraints defining the relationships desired to exist between pairs or groups of objects. The system then produces all so- lutions that satisfy the given constraints and outputs thes e solutions in a graphical or textual format as directed by the user. 2 REPRESENTATION N-dimensional space can be conceptualised as comprising a set ( ) of N-dimensional cells where each cell has some unique identifier re- ferred to as an address or reference. Sub-spaces within this space can then be defined in terms of subsets of . Spatial reasoning is con- cerned with the interpretation and manipulation of knowledge con- cerning the attributes of spatial objects. If we wish to mani pulate ob- jects whose attributes are expressed in terms of sets of addr esses it is desirable to adopt an addressing mechanism that supports computa- tionally effective processing of these sets. The most obvio us starting