Localization,Exploration, and Navigation Based on Qualitative Angle Information

Abstract

Three of the major problems in building autonomous mobile robots are localization, exploration, and navigation. This paper investigates how well different qualitative methods based on angle information, most of them originally invented for representation of spatial knowledge, are suited for addressing these problems. It combines results from discrete and computational geometry with methods from qualitative spatial reasoning, gaining some new insights on the complexity of robot navigation. It turns out that essentially only with panoramas (special roundviews) the qualitative localization problem can be solved in a satisfactory manner. The exploration problem (qualitative map building), remains difficult for all considered approaches.     

On Embedding a Qualitative Representation in a Two-Dimensional Plane

Abstract

This paper discusses embedding in a two-dimensional plane a symbolic representation for spatial data using the simple objects, points (P), lines (L), circuits (C), and areas (A). We have proposed PLCA as a new framework for a qualitative spatial reasoning. In a PLCA expression, the entire figure is represented in a form in which all the objects are related. We investigate the conditions for two-dimensional realizability of a PLCA expression, and derive the relation that the numbers of objects in a PLCA expression should have. In this process, we use the well-known Euler's formula. We also give an algorithm for drawing the figure of the PLCA expression that satisfies this condition in a two-dimensional plane and prove its correctness. The algorithm generates a quantitative expression from qualitative expression.     

Modelling Dynamic Spatial Systems in the Situation Calculus

Abstract

We propose and systematically formalise a dynamical spatial systems approach for the modelling of changing spatial environments. The formalisation adheres to the semantics of the situation calculus and includes a systematic account of key aspects that are necessary to realize a domain-independent qualitative spatial theory that may be utilised across diverse application domains. The spatial theory is primarily derivable from the all-pervasive generic notion of “qualitative spatial calculi” that are representative of differing aspects of space. In addition, the theory also includes aspects, both ontological and phenomenal in nature, that are considered inherent in dynamic spatial systems. Foundational to the formalisation is a causal theory that adheres to the representational and computational semantics of the situation calculus. This foundational theory provides the necessary (general) mechanism required to represent and reason about changing spatial environments and also includes an account of the key fundamental epistemological issues concerning the frame and the ramification problems that arise whilst modelling change within such domains. The main advantage of the proposed approach is that based on the structure and semantics of the proposed framework, fundamental reasoning tasks such as projection and explanation directly follow. Within the specialised spatial reasoning domain, these translate to spatial planning/re-configuration, causal explanation and spatial simulation. Our approach is based on the hypothesis that alternate formalisations of existing qualitative spatial calculi using high-level tools such as the situation calculus are essential for their utilisation in diverse application domains such as intelligent systems, cognitive robotics and event-based GIS.     

The Influence of Landmarks and Pre-exposure to a Structural Map During the Process of Spatial Knowledge Acquisition: A Study with Children and Adults in a Virtual Environment

ABSTRACT

This study investigated the effects of featural information (landmarks) and geometric information (pre-exposure to a structural map) and their possible interaction during the process of spatial knowledge acquisition of 8- and 11-year-old children and adults in a virtual environment. The study confirmed the well-known result of a developmental achievement in spatial cognition from childhood to adulthood. Although landmarks and the pre-exposure to a structural map did not affect the time to learn a specific route, they influenced the use of behavior in spatial learning and eased the acquisition of spatial knowledge measured by a route reversal and map-drawing tasks. Children and adults are able to integrate featural and geometric information in the spatial knowledge acquisition process in an environmental space, but their integration depends on the spatial processing stages that are investigated. Moreover, it was successfully demonstrated that the use of desktop virtual environments seems to be appropriate to investigate the development of spatial cognition.     

Reasoning about Depth and Motion from an Observer's Viewpoint

ABSTRACT

The goal of this paper is to present a logic-based formalism for representing knowledge about objects in space and their movements, and show how this knowledge could be built up from the viewpoint of an observer immersed in a dynamic world. In this paper space is represented using functions that extract attributes of depth, size and distance from snapshots of the world. These attributes compose a novel spatial reasoning system named Depth Profile Calculus (DPC). Transitions between qualitative relations involving these attributes are represented by an extension of this calculus called Dynamic Depth Profile Calculus (DDPC). We argue that knowledge about objects in the world could be built up via a process of abduction on DDPC relations.     

Analyzing Qualitative Spatio-Temporal Calculi using Algebraic Geometry

Abstract

Qualitative spatial reasoning is based on calculi which comprise relations and operation tables that encode operations like relation composition. Designing a calculus involves determining these tables and analyzing reasoning properties—a demanding task that is susceptible to errors if performed manually. This paper is concerned with automating computation of operation tables and analysis of qualitative calculi over real-valued domains like the plane ². We present an approach to specify qualitative relations using polynomial equations that allows methods from algebraic geometry to be applied. This paper shows how reasoning with qualitative relations can be posed algebraically and demonstrates algebraic reasoning using Gröbner base analysis. We evaluate this approach and describe our implementation, which is freely available as part of the spatial reasoning toolbox SparQ.     

Expert Algorithmic and Imagistic Problem Solving Strategies in Advanced Chemistry

Abstract

Visualization and imagistic reasoning appear central to expert practice in science; however, expert use of these strategies on authentic tasks has not been examined in detail. This study documents how science experts use both algorithms and imagistic reasoning to solve problems. Using protocol analysis, we report expert chemists' preferential use of algorithms for solving spatial problems and imagistic reasoning for deducing spatial transformations. We observed experts employ algorithms to solve the majority of spatial tasks while reserving imagistic strategies to solve a class of tasks that required translating between representations. Strategy used varied widely among experts and tasks.     

Effects of Communication Methods on Communication Patterns and Performance in a Remote Spatial Orientation Task

Abstract

An experiment was conducted to examine the impact of communication methods (text-only, audio-only, and audio-plus-video) on communication patterns and effectiveness in a 2-person remote spatial orientation task. The task required a pair of participants to figure out the cardinal direction of a target object by communicating spatial information and perspectives. Results showed that overall effectiveness in the audio-only condition was better than the text-only and audio-plus-video conditions, and communication patterns were more predictive of errors than individual differences in spatial abilities. Discourse analysis showed that participants in the audio-plus-video condition performed less mental transformation of spatial information when communicating, which led to more interpretation errors by the listener. Participants in the text-only conditions performed less confirmation and made more errors by misreading their own display. Results suggested that speakers in the audio-plus-video condition minimized effort by communicating spatial information based on their own perspective but speakers in the audio-only and text-only conditions would more likely communicate transformed spatial information. Analysis of gestures in the audio-plus-video condition confirmed that iconic gestures tended to co-occur with spatial transformation. Iconic gesture rates were negatively correlated with transformation errors, indicating that iconic gestures more likely co-occurred with successful communication of spatial transformation. Results show that when visual interactive feedback is available, speakers tend to adopt egocentric spatial perspectives to minimize effort in mental transformation and rely on the feedback to ensure that the hearer correctly interprets the information. When visual interactive feedback is not available, speakers will put more effort in transforming spatial information to help the hearer to understand the information. The current result demonstrated that allowing two persons to see and communicate with each other during a remote spatial reasoning task can lead to more errors because of the use of a suboptimal communication strategy.     

Qualitative Spatial Reasoning in Interpreting Text and Narrative

Abstract

Simple natural language texts and narratives often raise problems in commonsense spatial knowledge and reasoning of surprising logical complexity and geometric richness. In this article, I consider a dozen short texts—five taken from literature, the remainder contrived as illustrations—and discuss the spatial reasoning involved in understanding them. I conclude by summarizing their common features, and by tentatively drawing some morals for research in this area.     

Revisiting Perspective-Taking: Can People Maintain Imagined Perspectives?

Abstract

Three experiments were conducted to examine whether people can adopt and maintain imagined perspectives in the absence of target information. The task used entailed providing information about an imagined perspective in advance of target information to examine whether this would facilitate perspective-taking performance and reduce or eliminate alignment effects that are commonly reported in the literature. The three experiments employed different types of spatial environments: an environment learned from navigating a computer screen (Experiment 1), and an immersive environment that was either remote (Experiment 2) or immediate (Experiment 3) at the time of retrieval. Across the three experiments, results showed that information about an imagined perspective can be utilized ahead of target information. Furthermore, they suggested that alignment effects can be reduced as a result of processing information about perspective ahead of target information, but only when reasoning about specific nonimmediate spatial relations (Experiments 1 and 2). Results are discussed in connection with previous findings on spatial updating and the organizational structure of spatial memory.     

Contributing Factors to Temporal and Spatial Associations in Mental Representations of Maps

Abstract

The present work explores an interactive model of spatial and temporal information in map memory. In four experiments, participants learned a map with temporal and spatial information confounded or unconfounded. Attentional and representational levels of information were made apparent through tasks that tap spatial, temporal, or other information. Learning criteria emphasizing sequential order or location imposed differential weighting of the information types in memory. Results indicate that map memory is spatial, but also interacts with the order in which map locations are encountered. Findings show flexibility in allocating attention and information indexing of location and sequential order information in map learning.     

The Space within Fisherman's Folly: Playing with a Puzzle in Mereotopology

Abstract

In this paper we propose a spatial ontology for reasoning about holes, rigid objects and a string, taking a classical puzzle as a motivating example. In this ontology the domain is composed of spatial regions whereby a theory about holes is defined over a mereotopological basis. Within this theory we define a data structure, named chain, that facilitates a clear and efficient representation of the puzzle states and its solution.     

A Neuro-Cognitive Theory of Deductive Relational Reasoning with Mental Models and Visual Images

Abstract

Many neuro-imaging studies have provided evidence that the parietal cortex plays a key role in reasoning based on mental models, which are supposed to be of abstract spatial nature. However, these studies have also shown concurrent activation in vision-related cortical areas which have often been interpreted as evidence for the role of visual mental imagery in reasoning. The aim of the paper is to resolve the inconsistencies in the previous literature on reasoning and imagery and to develop a neurally and cognitively plausible theory of human relational reasoning. The main assumption is that visual brain areas are only involved if the problem information is easy to visualize and when this information must be processed and maintained in visual working memory. A regular reasoning process, however, does not involve visual images but more abstract spatial representations—spatial mental models—held in parietal cortices. Only these spatial representations are crucial for the genuine reasoning processes.     

Space,Language and Ontology: A Response to Davis

Abstract

Ernest Davis' article “Qualititative Spatial Reasoning in Interpreting Text and Narrative” discusses challenges that the interpretation of natural language appears to raise for the formalization of commonsense spatial reasoning. Davis finds these to be of “surprising logical complexity,” but also “erratic” in that they do not show a logical structuring of the problem space that could guide productive research. In this response I argue that much of the apparent lack of structure Davis laments is due to the very style of formal modeling he pursues. By augmenting logical considerations with substantial input from other disciplines and by adopting a heterogeneous and modular approach to formalization, I suggest that the problem space is by no means as ill-structured as Davis presents it.     

The cognitive adequacy of Allen's interval calculus for qualitative spatial representation and reasoning

Qualitative spatial reasoning (QSR) is often claimed to be cognitively more plausible than conventional numerical approaches to spatial reasoning, because it copes with the indeterminacy of spatial data and allows inferences based on incomplete spatial knowledge. The paper reports experimental results concerning the cognitive adequacy of an important approach used in QSR, namely the spatial interpretation of the interval calculus introduced by Allen (1983). Knauff, Rauh and Schlieder (1995) distinguished between the conceptual and inferential cognitive adequacy of Allen's interval calculus. The former refers to the thirteen base relations as a representational system and the latter to the compositions of these relations as a tool for reasoning. The results of two memory experiments on conceptual adequacy show that people use ordinal information similar to the interval relations when representing and remembering spatial arrangements. Furthermore, symmetry transformations on the interval relations were found to be responsible for most of the errors, whereas conceptualneighborhood theory did not appear to correspond to cognitively relevant concepts. Inferential adequacy was investigated by two reasoning experiments and the results show that in inference tasks where the number of possible interval relations for the composition is more than one, subjects ignore numerous possibilities and interindividually prefer the same relations. Reorientations and transpositions operating on the relations seem to be important for reasoning performance as well, whereas conceptual neighborhood did not appear to affect the difficulty of reasoning tasks based on the interval relations.     

Learning Routes from Visualizations for Indoor Wayfinding: Presentation Modes and Individual Differences

Abstract

Participants (N = 78) studied a visualization of a route through a complex building and walked that route in the real building without further assistance. Erroneous turns on the route as well as indicators of uncertainty such as hesitations were assessed. Three types of route visualizations were compared: (1) an allocentric, map-based visualization with the route indicated in floor maps, (2) an ordered sequence of pictures of decision points shown from the egocentric perspective, and (3) an animation showing a virtual walk of the route from the egocentric perspective. In addition to the experimental variation, gender differences, differences in visual-spatial abilities and differences in self-reported wayfinding strategies were considered as predictor variables. Wayfinding performance did not differ between allocentric (map) and egocentric (decision point pictures and animation) visualizations. However, wayfinding performance was better with animated than with static egocentric visualizations. Individual differences in the ability to encode visual-spatial information from the visualization played a critical role for route learning. Self-reported sense of direction related to egocentric wayfinding strategies also predicted wayfinding performance. Gender differences were attributable to differences in visual-spatial abilities and egocentric wayfinding strategies. Interactions between visualizations and individual differences were not found. It is concluded that animations of virtual walks are suitable to convey route information in complex buildings. Successful acquisition of route knowledge from maps is possible but might depend on the comprehensibility of the structure of the building.