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.

We determine the implicit assumptions and the structure of the Single and Double Cross Calculi within Euclidean geometry, and use these results to guide the construction of analogous calculi in mereogeometry.  The systems thus obtained have strong semantic and deductive similarities with the Euclidean-based Cross Calculi although they rely on a different geometry. This fact suggests that putting too much emphasis on usual classification of qualitative spaces may hide important commonalities among spaces living in different classes.

Qualitative techniques for spatial reasoning are important in artificial intelligence. We present an extended cardinal direction calculus (XCDC) for spatio-temporal event representation and reasoning. The methods presented in this paper can be used in systems based on natural language processing which are also discussed in this paper.

In this paper, we construct and investigate a hierarchy of spatio-temporal formalisms that result from various combinations of propositional spatial and temporal logics such as the propositional temporal logic PTL, the spatial logics RCC-8, BRCC-8, S4u and their fragments. The obtained results give a clear picture of the trade-off between expressiveness and `computational realisability' within the hierarchy. We demonstrate how different combining principles as well as spatial and temporal primitives can produce NP-, PSPACE-, EXPSPACE-, 2EXPSPACE-complete, and even undecidable spatio-temporal logics out of components that are at most NP- or PSPACE-complete.

Given an N N grid of squares, where each square has a count and an underlying population, our goal is to find the square region with the highest density, and to calculate its significance by randomization. Any density measure D, dependent on the total count and total population of a region, can be used. For example, if each count represents the number of disease cases occurring in that square, we can use Kulldorff's spatial scan statistic D