Tutorial 3: Qualitative Spatial and Temporal Reasoning

Qualitative Spatial and Temporal Reasoning:

Formal Aspects and Cognitive Theories

Abstract

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.

Contents

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

Audience

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.

Instructor

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.

Literature

Overview

• 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.