Nearly 15 years ago, a set of qualitative spatial relations between oriented straight line segments (dipoles) was suggested by Schlieder. This work received substantial interest amongst the qualitative spatial reasoning community. However, it turned out to be difficult to establish a sound constraint calculus based on these relations. In this paper, we present the results of a new investigation into dipole constraint calculi which uses algebraic methods to derive sound results on the composition of relations and other properties of dipole calculi. Our results are based on a condensed semantics of the dipole relations. In contrast to the points that are normally used, dipoles are extended and have an intrinsic direction. Both features are important properties of natural objects. This allows for a straightforward representation of prototypical reasoning tasks for spatial agents. As an example, we show how to generate survey knowledge from local observations in a street network. The example illustrates the fast constraint-based reasoning capabilities of the dipole calculus. We integrate our results into two reasoning tools which are publicly available.

We study an alternative to the prevailing approach to modelling qualitative spatial reasoning (QSR) problems as constraint satisfaction problems. In the standard approach, a relation between objects is a constraint whereas in the alternative approach it is a variable. The relation-variable approach greatly simplifies integration and implementation of QSR. To substantiate this point, we discuss several QSR algorithms from the literature which in the relation-variable approach reduce to the customary constraint propagation algorithm enforcing generalised arc-consistency.

The main theme of this workshop (Dagstuhl seminar 04351) is `Spatial Representation: Continuous vs. Discrete'. Spatial representation has two contrasting but interacting aspects (i) representation of spaces' and (ii) representation by spaces. In this paper, we will examine two aspects that are common to both interpretations of the theme, namely nerve constructions and refinement. Representations change, data changes, spaces change. We will examine the possibility of a `differential geometry' of spatial representations of both types, and in the sequel give an algebra of differential forms that has the potential to handle the dynamical aspect of such a geometry. We will discuss briefly a conjectured class of spaces, generalising the Cantor set which would seem ideal as a test-bed for the set of tools we are developing.

We argue that transfer of spatial and conceptual knowledge between tasks and domains is an essential benchmark for multi-representational architectures aimed at human-level intelligence. The underlying hypothesis is that spatial relationships provide a natural level of abstraction, highlighting the similarities and differences between situations and domains. Therefore, not only will spatial representations improve domain reasoning and learning, they will also facilitate the transfer of knowledge across domains. The simulated environments of real-time strategy (RTS) games provide an excellent test-bed for exploring this hypothesis for two reasons: many different RTS domains have been constructed and RTS requires a wide range of reasoning tasks.

In many spatial problems, it can be difficult to create a state representation that is abstract enough so that irrelevant details are ignored, but also accurate enough so that important states of the problem can be differentiated. This is especially difficult for agents that address a variety of problems. A potential way to resolve this difficulty is by using two representations of the spatial state of the problem: one abstract and one concrete, along with internal (imagery) operations that modify the concrete representation based on the contents of the abstract representation. In this paper, we argue that such a system can allow plans and policies to be expressed that can better solve a wider class of problems than would otherwise be possible. An example of such a plan is described. The theoretical aspects of what imagery is, how it differs from other techniques, and why it provides a benefit are explored.

A sizable fraction of current research into human visuo-spatial knowledge processing explicitly or implicitly suggests a spatial processing of certain knowledge types and a visual processing of others. Similarly, many formal and technical approaches for representing and processing visuo-spatial information in artificial intelligence, in computational cognitive modeling, or in knowledge representation and reasoning explicitly or implicitly treat visual and spatial information as belonging to separate types. While there exists good evidence for some differences in mental processing of different visuo-spatial knowledge types, there is much less reason to maintain the currently ascribed separation between the visual and the spatial. We provide arguments on why strict dichotomies seem unwarranted with regard to descriptions of human mental spatial reasoning and disadvantageous for the formal and technical approaches. We build upon a synopsis of psychological evidence for the existence of multiple knowledge type specific representations in human visuo-spatial reasoning and discuss the notion of scalable representation structures. In absence of proof to the contrary, it seems better practice to assume that (a) many of the type differences attributed to visuo-spatial knowledge processing are gradual rather than qualitative in nature, and that (b) tasks involving visuo-spatial knowledge of several types are often mentally processed through dynamic associations of structures for processing basal knowledge types. The paper calls for more investigations of human reasoning in visuo-spatial tasks in which knowledge types dynamically change during reasoning. It outlines a research framework for systematically investigating different basal visuo-spatial knowledge types and their combinations with regard to cognitive and computational plausibility. Current research is related to the framework, including research on Casimir, our computational cognitive architecture for reasoning with visuo-spatial knowledge. We argue that a more systematic course of research along the lines of the proposed framework will not only lead to more appropriate descriptions of human cognition (regarding visuo-spatial knowledge processing) but may also spawn more integrated and versatile formal and technical approaches for dealing with visuo-spatial information.

Current research on qualitative spatial representation and reasoning mainly focuses on one single aspect of space. In real world applications, however, multiple spatial aspects are often involved simultaneously. This paper investigates problems arising in reasoning with combined topological and directional information. We use the RCC8 algebra and the Rectangle Algebra (RA) for expressing topological and directional information respectively. We give examples to show that the bipath-consistency algorithm BIPATH is incomplete for solving even basic RCC8 and RA constraints. If topological constraints are taken from some maximal tractable subclasses of RCC8, and directional constraints are taken from a subalgebra, termed DIR49, of RA, then we show that BIPATH is able to separate topological constraints from directional ones. This means, given a set of hybrid topological and directional constraints from the above subclasses of RCC8 and RA, we can transfer the joint satisfaction problem in polynomial time to two independent satisfaction problems in RCC8 and RA. For general RA constraints, we give a method to compute solutions that satisfy all topological constraints and approximately satisfy each RA constraint to any prescribed precision.

Competence in interacting with the spatial world, the ability to move around an obstacle, or reach for a desired object, is one of the most immediate needs of any agent existing in such a world. For my thesis work, I am extending a largely-symbolic AI system, the Soar cognitive architecture (Laird, 2008), to better handle spatial problems. A key aspect in the design of Soar is a commitment to generality: the goal of the architecture is to be able to solve the same breadth problems humans are able to solve. In addition, Soar is a psychologically-inspired architecture: a second goal is to solve problems in a manner similar to humans. These goals are reflected in the design of the existing architecture, and must be reflected in the design of any extension to it. Systems for spatial reasoning exist, but they are typically defined for limited domains, and in isolation from a comprehensive intelligent system. My approach to the problem derives from work in diagrammatic reasoning and systems exploring mental imagery. The system augments symbolic working memory in Soar with short-term and long-term memories specialized for spatial information. Reasoning is then a process of manipulating both symbolic and lower-level perceptual data.

In this paper we present an approach to the task of generating and resolving referring expressions (REs) for conversational mobile robots. It is based on a spatial knowledge base encompassing both robot-and human-centric representations. Existing algorithms for the generation of referring expressions (GRE) try to find a description that uniquely identifies the referent with respect to other entities that are in the current context. Mobile robots, however, act in large-scale space, that is environments that are larger than what can be perceived at a glance, e.g. an office building with different floors, each containing several rooms and objects. One challenge when referring to elsewhere is thus to include enough information so that the interlocutors can extend their context appropriately. We address Figure 1: Situated dialogue with a campus service robot this challenge with a method for context construction 2. "the area" that can be used for both generating and resolving 3. "Peter's office at the end of the corridor on the third floor REs - two previously disjoint aspects. Our approach of the Acme Corp. building 7 in the Acme Corp. complex, is embedded in a bidirectional framework 47 Evergreen Terrace, Calisota, Earth, (...)" for natural language processing for robots. Clearly, these REs are valid descriptions of the respective entities in the robot's world representation.

Increasing the expressiveness of qualitative spatial calculi is an essential step towards meeting the requirements of applications. This can be achieved by combining existing calculi in a way that we can express spatial information using relations from both calculi. The great challenge is to develop reasoning algorithms that are correct and complete when reasoning over the combined information. Previous work has mainly studied cases where the interaction between the combined calculi was small, or where one of the two calculi was very simple. In this paper we tackle the important combination of topological and directional information for extended spatial objects. We combine some of the best known calculi in qualitative spatial reasoning (QSR), the RCC8 algebra for representing topological information, and the Rectangle Algebra (RA) and the Cardinal Direction Calculus (CDC) for directional information. Although CDC is more expressive than RA, reasoning with CDC is of the same order as reasoning with RA. We show that reasoning with basic RCC8 and basic RA relations is in P, but reasoning with basic RCC8 and basic CDC relations is NP-Complete.