R3-[Q-Shape] - Details

Reasoning about Paths, Shapes, and Configuration

planning a sailing course
SparQ verifying a qualitative constraint calculus
one of our robots inspecting a warehouse


This project investigates qualitative approaches to representation and reasoning with the goal of developing a universal collection of methods for intelligently handling spatial knowledge within autonomous agents.

So far, we have established means of abstracting information from the sensor-level up to abstract representations that retain all relevant information for a given navigational task. Such abstraction yields an approach that is effective and robust. In the third project phase we will focus on how (piecewise) static spatial reasoning can be extended to reasoning about spatial processes and actions in space. We start with conceptual neighborhood structures of qualitative relations and build qualitative representations of spatial change on top of these structures: qualitative changeovers as captured by conceptual neighborhoods are used as base entities of qualitative navigation calculi. This is a significant extension of conceptual neighborhoods as it allows us to go beyond single relation crossovers and to represent qualitative spatio-temporal trajectories. Our approach exhibits three main features: First and foremost, it is tightly integrated with existing qualitative representations of static scenes which already have proven successful. The foundation in qualitative spatial relations sets our approach apart from existing representations of dynamic scenes that define specific calculi purely capable of representing dynamics. Second, we extend qualitative approaches that handle either spatial or temporal domains to integrated spatio-temporal domains. Third, our approach is general in that it can be used with a variety of spatial calculi. Our research on qualitative reasoning about processes and actions in space will enable intelligent agent control to benefit from qualitative methods. As support, we will provide a qualitative agent control framework comprising our representation and reasoning techniques.

We will also complement the tool repository of qualitative methods. Algebraic specification of qualitative relations has shown to provide a solid basis for analyzing qualitative calculi. We will investigate the utility of algebraic techniques for reasoning in calculi for which composition tables do not provide effective means. Algebraic techniques also allow us to compute quantitative valuations from qualitative knowledge bases. We note that the mapping from qualitative to quantitative information has been rarely studied, although there are  several important applications that demand for such a mapping. Foremost we mention the ability to graphically externalize qualitative knowledge in a communication setting. Qualitative reasoning tools developed in this project will be integrated into our reasoning toolbox SparQ (available from http://www.sfbtr8.uni-bremen.de/project/r3/sparq/). To further improve dissemination of qualitative spatial representation and reasoning tools we will also work on linking qualitative representation and reasoning to a description logic framework.