Abstract
Following reviews of previous approaches to spatial reasoning, a completely qualitative method for reasoning about cardinal directions, without recourse to analytical procedures, is introduced and a method is presented for a formal comparison with quantitative formulae. We use an algebraic method to formalize the meaning of cardinal directions. The standard directional symbols (N, S, E, W) are extended with a symbol 0 to denote an undecided case, which greatly increases the power of inference. Two examples of systems to determine and reason with cardinal directions are discussed in some detail and results from a prototype are given. The deduction rules for the coordination of directional symbols are formalized as equations; for inclusion in an expert system they can be coded as a look-up table (given in the text). The conclusions offer some direction for future work.
Funding from NSF for the NCGIA under grant SES 88-10917, from Intergraph Corporation and Digital Equipment Corporation is gratefully acknowledged.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. G. Bobrow, S. Mittal and M. J. Stefik. 1986. Expert Systems: Perils and Promise. Communications of the ACM 29 (9): 880–894.
S.-K. Chang, E. Jungert and Y. Li. 1990. “The Design of Pictorial Databases Based Upon the Theory of Symbolic Projection”. In Design and Implementation of Large Spatial Databases. Edited by A. Buchmann, O. Gunther, T. R. Smith and Y.-F. Wang. 303–324. New York NY: Springer Verlag.
S. K. Chang, Q. Y. Shi and C. W. Yan. 1987. Iconic Indexing by 2-D String. IEEE Transactions on Pattern Analysis and Machine Intelligence 9 (3): 413–428.
S. Dutta. 1988. “Approximate Spatial Reasoning”. In First International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems. 126–140. Tullahoma. Tennessee: ACM Press.
S. Dutta. 1990. “Qualitative Spatial Reasoning: A Semi-quantitative Approach Using Fuzzy Logic”. In Design and Implementation of Large Spatial Databases. Edited by A. Buchmann, O. Günther, T. R. Smith and Y.-F. Wang. 345–364. New York NY: Springer Verlag.
A. U. Frank. 1990. “Spatial Concepts, Geometric Data Models and Data Structures”. In GIS Design Models and Functionality. Edited by D. Maguire. Leicester, UK: Midlands Regional Research Laboratory, University of Leicester.
A. U. Frank. 1991. Qualitative Spatial Reasoning about Cardinal Directions. In Autocarto 10. Edited by D. Mark and D. White. 148–167.
A. U. Frank and D. M. Mark. 1991. “Language Issues for Geographical Information Systems”. In Geographic Information Systems: Principles and Applications. Edited by D. Maguire, D. Rhind and M. Goodchild. London: Longman Co. (in press).
J. Freeman. 1975. The modelling of spatial relations. Computer Graphics and Image Processing 4: 156–171.
D. Hernández. 1990. Relative Representation of Spatial Knowledge: The 2-D Case. Report FKI-135–90. Munich FRG: Technische Universität München.
A. Herskovits. 1986. Language and Spatial Cognition — An Interdisciplinary Study of the Propositions in English. Stiudies in Natural Language Processing. Cambridge UK: Cambridge University Press.
R. Jackendoff. 1983. Semantics and Cognition. Cambridge, Mass.: MIT Press.
D. M. Mark and A. U. Frank. 1990. Experiential and Formal Representations of Geographic Space and Spatial Relations. Technical Report (in press).: NCGIA.
D. M. Mark, A. U. Frank, M. J. Egenhofer, S. M. Freundschuh, M. McGranaghan and R. M. White. 1989. Languages of Spatial Relations: Initiative Two Specialist Meeting Report. Technical Report 89–2.: National Center for Geographic Information and Analysis.
D. McDermott and E. Davis. 1984. Planning routes through uncertain territory. Artificial Intelligence 22: 107–156.
NCGIA. 1989. The U.S. National Center for Geographic Information and Analysis: An overview of the agenda for research and education. International Journal of Geographical Information Systems 2 (3): 117–136.
S. Nirenburg and V. Raskin. 1987. “Dealing with Space in Natural Language Processing”. In Spatial Reasoning and Multi-Sensor Fusion. Edited by A. Kak and S.-s. Chen. 361–370. Pleasan Run Resort, St. Charles, IL: Morgan Kaufmann Publishers.
Peuquet and C.-X. Zhan. 1987. An algorithm to determine the directional relationship between arbitrarily-shaped polygons in a plane. Pattern Recognition 20: 65–74.
G. Retz-Schmidt. 1987. “Deitic and Intrinsic Use of Spatial Propositions: A Multidisciplinary Comparison”. In Spatial Reasoning and Multi-Sensor Fusion. Edited by A. Kak and S.-s. Chen. 371–380. Pleasan Run Resort, St. Charles, IL: Morgan Kaufmann Publishers
F. S. Robert. 1973. Tolerance Geometry. Notre Dame Journal of Formal Logic 14 (1): 68–76.
L. A. Zadeh. 1974. “Fuzzy Logic and Its Application to Approximate Reasoning”. In Information Processing.: North-Holland Publishing Company.
C. Zeeman. 1962. “The Topology of the Brain and Visual Perception”. In The Topology of 3-Manifolds. Edited by M. K. Fort. 240–256. Englewood Cliffs, NJ: Prentice Hall.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Frank, A.U. (1991). Qualitative Spatial Reasoning with Cardinal Directions. In: Kaindl, H. (eds) 7. Österreichische Artificial-Intelligence-Tagung / Seventh Austrian Conference on Artificial Intelligence. Informatik-Fachberichte, vol 287. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-46752-3_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-46752-3_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54567-5
Online ISBN: 978-3-642-46752-3
eBook Packages: Springer Book Archive