Figure 1: Eight (disjoint and exhaustive) topological relations that can hold between two regions.
Introduction
This paper explores the application to GIS of formal representations and reasoning algorithms for manipulating qualitative spatial information. There are two main reasons why non-precise, qualitative information may be needed in a GIS. One is that, in certain cases, only partial information may be available (e.g. we may know that one region is disconnected from another without knowing the precise geometry of the regions). The other is that general constraints holding among geographical objects are often most naturally stated in qualitative terms (e.g. we may wish to specify that a certain terrain-type may only be found a part of some particular type of region).
The domain of qualitative concepts relevant to geographical information is extremely wide, so this paper focuses on topological relations, which are of fundamental importance. I start by considering the representation of these relations in formal logical languages, drawing on AI research in this area. I then survey what is known about the computational complexity of reasoning with these representations. I describe a language capable of representing a significant class of topological relationships and for which the consistency of a set of n relational facts can be computed in order 7/3 time. The second half of the paper is concerned with the exploitation of such a reasoning algorithm within a GIS. I describe a prototype system which operates with both quantitative and qualitative data; and, in answering queries, transparently combines these two kinds of information. Some practical uses for this capability are discussed.
Representation of qualitative spatial information
Randell et al. (1992) have presented an axiomatic theory of spatial relations, known as the Region Connection Calculus (RCC), which is intended to provide a logical framework for the incorporation of spatial reasoning into 'intelligent' computer systems. This lst-order theory based on a primitive connectedness relation C(x,y), is a modification of earlier work by Clarke (1981). Randell et al. (1992) identify the set of eight topological relations shown in Figure 1 as being of particular importance. The same set of relations has independently been identified as significant in the context of Geographical Information Systems (Egenhofer & Franzosa, 1991; Egenhofer, l991; Clementini et al., 1994). In English the relations can be described as: DisConnection, External Connection, Partial Overlap, Tangential Proper Part, Non-Tangential Proper Part and Equality. Formal notations for these relations are given under the diagrams (the part relations, being asymmetric, have inverses denoted, Ri).
Figure 1: Eight (disjoint and exhaustive) topological relations that can hold between two regions.
Computational issues
The lst-order representation of Randell et al. (1992) is very expressive but no algorithm is known that will determine the validity of entailments in this language in finite time. However, exploiting the results of Tarski (1938), Bennett (1994) has shown how a significant class of spatial relations can be encoded in the 0-order intuitionistic logic (which is usually regarded as a 'propositional' logic). Because this logic is decidable, the encoding provides a decision procedure for reasoning about these relations. By analysing the intuitionistic sequents which are needed to reason with Bennett's encoding of spatial relations, Nebel (1995) showed that consistency of certain sets of topological relations can be computed in polynomial time. Recent refinement of the method of Bennett (1994) has resulted in an algorithm whose time complexity is of order n3. (Some other complexity results, such as those of Grigni et al. ( 1995), will also be considered in the full paper).
Applications
The n3 topological reasoning algorithm has been implemented as part of a larger 'spatial AI' system being developed as part of EPSRC project GR/K65041 on 'Logical Theories and Decision Procedures for Reasoning about Physical Systems'. The current system contains a database of geographical information in the form of geometrical polygon data and also contains qualitative data in the form of topological relations between named regions. Some of these named regions are identified directly with polygons in the geometrical database, whereas for others the geometry is not precisely known but only constrained by the qualitative topological relations. The topological relationships determined by the quantitative geometrical data can also be rapidly computed and accessed by the topological reasoning mechanism, allowing queries to be addressed to the combined qualitative and quantitative database. This capability is (as far as I know) not available in any other system. Work is also underway to demonstrate the use of topological reasoning in the control of artificial agents operating in a virtual world constituted by geographical data.
Figure 2 shows a screen-dump of the current prototype system. Most of the code is written in (SICStus) Prolog but a Tcl/Tk sub-process is used to create the GUI. The window at the top left shows a simple cartographical display, whose geometry is determined by a database giving the co-ordinates and terrain-type of a number of triangular regions. This data is shown in the bottom left window. The top right window presents a database of qualitative relations between regions. In the middle on the right is the Prolog top-level query window. All functions of the system can be accessed by typing commands and queries at the Prolog prompt (although common operations are more conveniently accessed via the GUI). In the figure the Prolog interpreter is being used for querying the qualitative database. Such queries are answered by means of Bennett's consistency checking algorithm which will determine whether a relation given as a query is consistent with, inconsistent with, or a necessary consequence of the database. (The bottom right window is one of a number of information screens which can be displayed via the system's 'help' facility.)
Figure 2: The current prototype system
Conclusions
Recent complexity results indicate that the capability of tractable reasoning with qualitative information can be added to GIS systems. Acceptable performance cannot be achieved by general purpose logical proof systems but requires the construction of specialised representations and reasoning algorithms. Identification of useful functionality which can be provided by qualitative reasoning is the subject of ongoing work. It is hoped that experimentation with and development of the current prototype system will lead to practical applications .
Acknowledgements
This work was supported by the EPSRC under grant GR/165041.
References
Bennett, B. 1994. "Spatial reasoning with propositional logics" In Doyle, J, Sandewall, E. and Torasso, P. (eds.) "Principles of Knowledge Representation and Reasoning", Proceedings of the 4th International Conference (KR94). San Francisco: Morgan Kaufmann.
Clarke, B. L. 1981. "A calculus of individuals based on 'connection'", Notre Dame Journal of Formal Logic, 23(3), 204-218.
Clementini, E., Sharma, J. and Egenhofer, M. J. 1994. "Modeling topological spatial relations: strategies for query processing", Computers and Graphics, 18(6), 815-822.
Egenhofer, M. 1991. "Reasoning about binary topological relations" In Gunther, O. and Schek, H.J. (eds.) Proceedings of the Second Symposium on Large Spatial Databases, SSD'91 (Zurich, Switzerland). Lecture Notes in Computer Science 525. 143-160.
Egenhofer, M. and Franzosa, R. 1991. "Point-set topological spatial relations", International Journal of Geographical Information Systems, 5(2), 161-174.
Grigni, M., Papadias, D. and Papadimitriou, C. 1995. "Topological inference" In Mellish, C. (ed.), Proceedings of the fourteenth international joint conference on artificial intelligence (IJCAI-95) - Vol. 1. Morgan Kaufmann. 901-906.
Nebel, B. 1995. "Computational properties of qualitative spatial reasoning: First results", Proceedings of the 19th German AI Conference.
Randell, D. A., Cui, Z. and Cohn, A. G. 1992. "A spatial logic based on regions and connection", Proc. 3rd Int. Conf. on Knowledge Representation and Reasoning. San Mateo: Morgan Kaufmann, , 165-176.
Tarski, A. 1938. "Der aussagenkalkul und die topologie [sentential calculus and topology]", Fundamenta Mathematicae, 31, 103-134. English translation in Tarski, A. 1956, Logic, Semantics, Metamathematics: Oxford: Clarendon Press.