Reasoning about vague topological information

ABSTRACT

Topological information plays a fundamental role in the human perception of spatial configurations and is thereby one of the most prominent geographical features in natural language. As vagueness abounds in geography, flexible formalisms with the ability to capture vague topological information are often needed in practice. While such formalisms have already been introduced by various authors, complete reasoning procedures are usually not discussed. In this paper, we show how many interesting reasoning tasks, such as consistency checking and entailment checking, can be supported in a generalization of the well-known RCC-8 calculus. In particular, we present decision procedures based on linear programming, solving all reasoning tasks of interest. We furthermore show how deciding the consistency of vague topological information can be reduced to the consistency problem of the original RCC-8.

REFERENCES

• 1: E. Clementini and P. Di Felice. Approximate topological relations. International Journal of Approximate Reasoning, 16(2):173--204, 1997.
• 2: A. Cohn, J. Gooday, and B. Bennett. A comparison of structures in spatial and temporal logics. In Proceedings of the 16th International Wittgenstein Symposium, 1994.
• 3: A. Cohn and N. Gotts. The 'egg-yolk' representation of regions with indeterminate boundaries. In Geographic Objects with Indeterminate Boundaries (P.A. Burrough and A.U. Frank, eds.), pages 171--187. Taylor and Francis Ltd., 1996.
• 4: Soumitra Dutta, Approximate spatial reasoning: integrating qualitative and quantitative constraints, International Journal of Approximate Reasoning, v.5 n.3, p.307-331, May 1991 [doi>10.1016/0888-613X(91)90015-E]
• 5: M. Egenhofer and R. Franzosa. Point-set topological spatial relations. International Journal of Geographical Information Systems, 5(2):161--174, 1991.
• 6: A. Esterline, G. Dozier, and A. Homaifar. Fuzzy spatial reasoning. In Proceedings of the 1997 International Fuzzy Systems Association Conference, pages 162--167, 1997.
• 7: Peter Fisher, Sorites paradox and vague geographies, Fuzzy Sets and Systems, v.113 n.1, p.7-18, July 2000 [doi>10.1016/S0165-0114(99)00009-3]
• 8: A. Gerevini and J. Renz. Combining topological and size information for spatial reasoning.
• 9: F. Gey, R. Larson, M. Sanderson, K. Bischoff, T. Mandl, C. Womser-Hacker, D. Santos, and P. Rocha. GeoCLEF 2006: the CLEF 2006 cross-language geographic information retrieval track overview. In Working Notes for the CLEF 2006 Workshop, 2006.
• 10: M. Grigni, D. Papadias, and C. Papadimitriou. Topological inference. In Proceedings of the 14th International Joint Conference on Artificial Intelligence, pages 901--906, 1995.
• 11: Hans W. Guesgen , Jochen Albrecht, Imprecise reasoning in geographic information systems, Fuzzy Sets and Systems, v.113 n.1, p.121-131, July 2000 [doi>10.1016/S0165-0114(99)00016-0]
• 12: P. Jonsson and C. Bäckström. A linear-programming approach to temporal reasoning. In Proceedings of the 13th National Conference on Artificial Intelligence, pages 1235--1240, 1996.
• 13: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 14: Sanjiang Li, On Topological Consistency and Realization, Constraints, v.11 n.1, p.31-51, January 2006 [doi>10.1007/s10601-006-6847-9]
• 15: S. Li. Combining topological and directional information for spatial reasoning. In Proceedings of the 20th International Joint Conference on Artificial Intelligence, pages 435--440, 2007.
• 16: Y. Li and S. Li. A fuzzy sets theoretic approach to approximate spatial reasoning. IEEE Transactions on Fuzzy Systems, 12(6):745--754, 2004.
• 17: Y. Li and S. Li. Computing the fuzzy topological relations of spatial objects based on induced fuzzy topology. International Journal of Geographical Information Science, 20(8):857--883, 2006.
• 18: Bernhard Nebel, Computational Properties of Qualitative Spatial Reasoning: First Results, Proceedings of the 19th Annual German Conference on Artificial Intelligence: Advances in Artificial Intelligence, p.233-244, September 11-13, 1995
• 19: D. Randell, Z. Cui, and A. Cohn. A spatial logic based on regions and connection. In Proceedings of the 3rd International Conference on Knowledge Representation and Reasoning, pages 165--176, 1992.
• 20: Jochen Renz, Maximal Tractable Fragments of the Region Connection Calculus: A Complete Analysis, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.448-455, July 31-August 06, 1999
• 21: J. Renz. A canonical model of the Region Connection Calculus. Journal of Applied Non-Classical Logics, 12(3-4):469--494, 2002.
• 22: Jochen Renz , Bernhard Nebel, On the complexity of qualitative spatial reasoning: a maximal tractable fragment of the region connection calculus, Artificial Intelligence, v.108 n.1-2, p.69-123, March 1999 [doi>10.1016/S0004-3702(99)00002-8]
• 23: J. Renz and B. Nebel. Efficient methods for qualitative spatial reasoning. Journal of Artificial Intelligence Research, 15:289--318, 2001.
• 24: V. B. Robinson, Individual and multipersonal fuzzy spatial relations acquired using human-machine interaction, Fuzzy Sets and Systems, v.113 n.1, p.133-145, July 2000 [doi>10.1016/S0165-0114(99)00017-2]
• 25: A. Roy and J. Stell. Spatial relations between indeterminate regions. International Journal of Approximate Reasoning, 27(3):205--234, 2001.
• 26: Markus Schneider, A Design of Topological Predicates for Complex Crisp and Fuzzy Regions, Proceedings of the 20th International Conference on Conceptual Modeling: Conceptual Modeling, p.103-116, November 27-30, 2001
• 27: S. Schockaert, C. Cornelis, M. De Cock, and E. Kerre. Fuzzy spatial relations between vague regions. In Proceedings of the 3rd IEEE Conference on Intelligent Systems, pages 221--226, 2006.
• 28: U. Straccia. Reasoning within fuzzy description logics. Journal of Artificial Intelligence Research, 4:137--166, 2001.
• 29: X. Tang and W. Kainz. Analysis of topological relations between fuzzy regions in a general fuzzy topological space. In Proceedings of the Symposium on Geospatial Theory, Processing and Applications, 2002.
• 30: L. Zadeh. Fuzzy sets. Information and Control, 8(3):338--353, 1965.
• 31: F. Zhan. Approximate analysis of binary topological relations between geographic regions with indeterminate boundaries. Soft Computing, 2(2):28--34, 1998.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Uncertainty, "fuzzy," and probabilistic reasoning

General Terms:
Algorithms, Theory