Personal tools
You are here: Home Tutorials T-3: Qualitative Spatial and Temporal Reasoning

Tutorial 3: Qualitative Spatial and Temporal Reasoning

Qualitative Spatial and Temporal Reasoning:

Formal Aspects and Cognitive Theories

by Marco Ragni,  Albert-Ludwigs-Universität Freiburg, Germany.


Starting with Allen's Interval Calculus 25 years ago the field of qualitative spatial and temporal reasoning (QSTR) has become an important part of knowledge representation and reasoning. Today the number of calculi developed to describe imprecise knowledge about space is growing quickly. This imprecise knowledge is described by qualitative descriptions which are abstractions of similar quantitative states. New research aims at combining existing qualitative calculi for improving the expressiveness, but taking also an increasing complexity into account. Since human-machine interaction is an important application field for QSTR, and therefore naturally cognitive questions play an important role. Here, in contrast to formal investigations, the way how spatial information is represented (in humans) is of importance.

The tutorial presents the most important approaches from a formal point of view to qualitative spatial and temporal reasoning, including satisfiability problems, neighborhood graphs, compositional reasoning, and combinations of calculi. This is complemented by a short introduction of the two main cognitive theories: The theory of mental models (Johnson-Laird, 1983) and the theory of mental logic (Rips, 1994). A comparison between the notion of human and formal difficulty in reasoning concludes the tutorial.



  1. Introduction
    1. A simple calculus (Point Algebra)
    2. Constraint Satisfaction Problems
    3. Neighborhood Graphs
    4. Compositional Reasoning
    5. Complexity
  2. Formal aspects of qualitative calculi
    1. Allen's Interval Calculus: Definition. Neighborhood graph. Compositional reasoning. Complexity. Extension: Block Calculus.
    2. Region Connection Calculus: Definition. Neighborhood graph. Compositional reasoning. Complexity.
    3. Cardinal Direction Calculus: Definition. Neighborhood graph. Compositional reasoning. Complexity.
    4. Other Calculi: Double-Cross Calculus. Combinations of calculi.
  3. Cognitive Theories
    1. Mental Model Theory
    2. Mental Logic Approaches
    3. Empirical Findings
  4. Comparison of cognitive and computational complexity
  5. Conclusion



The tutorial serves as an introductory course for researchers interested in formal aspects of qualitative spatial and temporal reasoning and cognitive theories. The tutorial is intended for the general Spatial Cognition community audience and only basic knowledge in AI is assumed. The objective of the tutorial is to introduce into the field of qualitative spatial and temporal reasoning and main calculi, both from a formal and cognitive point of view. Furthermore, a basis for assessing the suitability of different qualitative calculi for specific research question is provided.

Complementary to this tutorial (presenting the state of the art in QSTR) is a Workshop on Cognitive Models in Human Spatial Reasoning. The focus of the workshop is to enable the discussion on new cognitive models and systems (of human working memory) for spatial reasoning. For the workshop a certain familiarity with cognitive theories (about spatial reasoning) is useful but not necessary.



Marco Ragni is post-doctoral reearcher at the Center of Cognitive Science at the University of Freiburg. He received a diploma in mathematics (Dipl.-Mathematiker) from the University of Freiburg in May 2002. He was a research scientist (from July 2002 to January 2008) in the Research Group on the Foundations of Artificial Intelligence at the University of Freiburg, headed by Bernhard Nebel. From April 2002 to January 2003, he was working for the EU-Project CogViSys. Since January 2003, he has been a member of the Transregional Collaborative Research Center Spatial Cognition working in the project Effects of Background Knowledge on Human Spatial Reasoning. He was also a member of the Laboratory for Human Spatial Reasoning headed by Markus Knauff.




  • A.G. Cohn, S.M. Hazarika: Qualitative Spatial Representation and Reasoning: An Overview. Fundam. Inform. 46(1-2): 1-29 (2001)
  • P.B. Ladkin, R. Maddux. On binary constraint networks. Journal of the ACM , 41:435–469, 1994.

Constraint Satisfaction

  • A.K. Mackworth. Constraint satisfaction. In S. C. Shapiro, editor, Encyclopedia of Artificial Intelligence, pages 205–211. Wiley, Chichester, England, 1987.

Complexity Questions

  • J.F. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM , 26(11):832–843, November 1983.
  • B. Bennett. Spatial Reasoning with propositional logic. Principles of Knowledge Representation and Reasoning: Proceedings of the 4th International Conference (KR-94), 1994, 51-62.
  • A.U. Frank: Qualitative Spatial Reasoning: Cardinal Directions as an Example. International Journal of Geographical Information Science 10(3): 269-290 (1996).
  • A. Gerevini, B. Nebel: Qualitative Spatio-Temporal Reasoning with RCC-8 and Allen's Interval Calculus: Computational Complexity. ECAI 2002 : 312-316, 2002.
  • A. Gerevini, J. Renz: Combining topological and size information for spatial reasoning. Artif. Intell. 137(1-2): 1-42, 2002.
  • G. Ligozat: Reasoning about Cardinal Directions. Journal Visual Language Computing 9(1): 23-44, 1998.
  • B. Nebel, H.-J. Bürckert. Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra. Journal of the ACM , 42(1): 43-66, 1995.
  • D.A. Randell, Z.Cui, A.G. Cohn: A Spatial Logic based on Regions and Connection. Proceedings of the Principles of Knowledge Representation and Reasoning Conference (KR-92): 165-176, 1992.
  • J. Renz, B. Nebel. On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus. Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI’97) , August 1997, 522-527.

Cognitive Theories

  • P.N. Johnson-Laird, R.M.J. Byrne. Deduction. Hillsdale, NJ: Lawrence Erlbaum Associates, 1991.
  • R.M.J. Byrne, P.N. Johnson-Laird. Spatial reasoning. Journal of Memory and Language , 28, 564-575, 1989.
  • L. Rips. The Psychology of Proof. MIT Press, Cambridge, MA, 1994.





Document Actions