Faculty of Information Systems and Applied Computer Sciences

Smart Environments

Tutorial on Qualitative Spatial Representation and Reasoning

The aim of this tutorial is to present a complete overview of all qualitative representations of space and time developed so far and to provide and introduction to their underlying formalism, their rea- soning algorithms, and applications. We address practitioners who wish to learn about symbolic representation and reasoning techniques available as well as researchers who wish to catch up with the latest advancements in the field.

Qualitative spatial and temporal representations constitute a class of symbolic approaches to capture aspects of spatial or temporal knowledge important for a task at hand, typically choosing a common sense level of abstraction. On the temporal side, existing representations include interval relations such as during or after, on the spatial side examples include topological relations among regions like overlap or direction relations like north of. Nearly every knowledge-based system addressing real-world problems comprises means for representation of, and possibly reasoning about, spatial or temporal knowledge – expertise in the area of qualitative spatial and temporal representations can thus be useful in a wide range of application areas.

This tutorial addresses all researchers and practitioners working with knowledge about space or time who wish to employ reasoning on a symbolic level. We will present an introduction to the field and give a generalized account of its formal basics and discuss properties of individual representa- tions, often called qualitative calculi. These properties are relevant to any symbolic language employing similar spatial or temporal primitives. We will present a thorough overview of all qualitative calculi developed so far, many of which have emerged from concrete application scenarios. There exist about 40 families of calculi, addressing a broad range of spatial and temporal aspects. Attendees of the tutorial will acquire a concise view on the state-of-the-art in reasoning algorithms tailored to qualitative representations, and learn about tools which make the algorithms readily available. They will also learn about open research questions in the field and future directions. Additionally, we will establish connections to other fields of symbolic reasoning related to the field.