Welcome

Overview of R3-[Q-Shape] 'Reasoning about Paths, Shapes, and Configurations'

The R3-[Q-Shape] project is part of the transregional collaborative research center SFB/TR 8 'Spatial Cognition' funded by the Deutsche Forschungsgemeinschaft (DFG). Its goal is the development of qualitative high-level representation and reasoning methods for cognitive agents operating in a spatial environment and communicating about space. The project started in January 2003 and the first phase will be finished in the end of 2006. The project is lead by Prof. Christian Freksa, Ph.D.

For more information see the R3-Factsheet.

Research goals in brief

We pursue the development of techniques to efficiently and robustly solve complex spatial tasks and aim at advancing formal techniques to real-world problems. In particular, we investigate techniques of qualitative spatial representation and reasoning to obtain an adequate level of abstraction and effective means for a task at hand. Three ways to achieve abstractions are fostered: aspectualization, coarsening, and conceptual classification. We address navigation and recognition tasks by designing suitable underlying representations and neighborhood- and constraint-based reasoning methods.

Research goals in detail

R3-[Q-Shape] aims at developing qualitative spatial representation and reasoning methods as required by cognitive agents that operate in a spatial environment and communicate about space with other cognitive agents on the basis of high-level spatial concepts. Solving problems in space requires the agents to deal with large amounts of information from different knowledge sources that can be incomplete, imprecise, and even partially conflicting. To successfully deal with these challenges, humans typically employ means to abstract the available information. Qualitative spatial representations and constraint-based as well as neighborhood-based qualitative spatial reasoning (QSR) techniques constitute a promising approach to deal with these problems. In the first project phase, two important problems were identified and approached:

First, the integration of specialized spatial reasoning calculi and the development of methods to support or automate the construction of task-specific calculi. And second, providing an interface that mediates between perceptual and conceptual spatial knowledge. Results from this work include the following: A theoretical framework for constraint-based reasoning with ternary calculi that extends the traditional constraint reasoning with binary relation algebras has been developed. A qualitative spatial reasoning toolbox called SparQ that is intended to make QSR methods available for applications has been implemented. Several spatial calculi for navigation and reasoning about paths and configurations have been conceived and investigated. Two compact spatial representations (one a shape-based geometric representation and one a route-based topological representation) together with procedures for automatic construction have been devised. In the second phase, the focus will be on principles of abstraction as required to solve challenging spatial problems. Three different ways of abstraction will be investigated: aspectualization, coarsening, and conceptual classification.

Techniques to realize these abstractions will be developed and the resulting compact representations will be evaluated in different scenarios. In particular, we will study their benefits by applying them 180 SFB/TR 8 Spatial Cognition Phase II to the problems of recognizing spatial configurations and of action planning in order to yield feasible solutions. Besides constraint-based reasoning techniques, conceptual neighborhoods will play a central role, in particular to resolve conflicts on the symbolical level by sensibly relaxing constraints. The results of the second phase will be brought together in the form of two exemplary applications: a map merging application and a spatial communication scenario, both contributing to the SFB/TR 8 application scenarios “enabling robots” and “intelligent environments”.

The long-term goal of R3-[Q-Shape] is to advance sound spatial representation and qualitative reasoning techniques. We will extend existing techniques towards real applications that handle a broad range of basic entities and towards task-adaptive calculi. Formal frameworks will be developed for manipulation of information across different levels of granularity and sensible derivation of knowledge in the presence of conflicting information. We will demonstrate that these techniques are well-suited for mastering complex real-world tasks involving navigation and communication about space.

Research goals in detail of Phase I

The goal of the R3-[Q-Shape] project is to develop qualitative representation and reasoning methods as required for a cognitive agent that operates in a spatial environment and communicates about space with other cognitive agents (humans or robots) on the basis of high-level spatial concepts as humans do it. Important abilities to successfully operate in a spatial environment are acquiring a model of the environment (mapping) and purposeful locomotion based on this model (navigation). Both require the agent to deal with incomplete, imprecise and even partially conflicting information. For communication with humans, human conceptualizations and cognitive adequacy of the employed representations has to be taken into account.

Two subproblems of this general goal were identified: First, to integrate specialized spatial reasoning calculi and to develop methods to support or automate the construction of task-specific calculi. And second, to provide an interface that mediates between perceptual and conceptual spatial knowledge that allows qualitative spatial reasoning techniques to be applied in situations in which the information about the environment mostly originates from the agent's own sensors.

In the past, different aspects of space had mainly been modeled independently resulting in reasoning calculi for topological reasoning about regions and positional (orientation and distance) reasoning about point objects. Solving navigational tasks, however, requires to integrate these different research directions, to be able to reason about various spatial entities like paths, shapes of objects, and complex configurations of potentially extended objects. From the theoretical perspective, spatial reasoning for navigation required the adaptation of traditional binary constraint reasoning techniques to algebras of ternary relations needed to express relative position information. In addition, cognitively motivated and application-oriented often only a weak composition can be defined, requiring an alternative framework to traditional relation algebras. Furthermore, deriving composition tables for new or combined calculi is a costly and error-prone process, making methods to derive composition tables automatically desirable.

In many applications spatial reasoning requires the acquisition of a spatial model of the environment from sensor data by integrating local knowledge into global knowledge. In most current mapping systems developed for mobile robots the sensor data was stored rather uninterpreted in the form of occupancy grids or sets of simple geometric elements like points or lines. Robust construction of more abstract, object-centered, and possibly hierarchically organized global representations from real sensor data and the role qualitative spatial reasoning approaches can play to support this construction process were open problems that needed to be solved to make qualitative spatial reasoning feasible for navigation tasks.