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.     

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.     

Qualitative Spatial Reasoning for Topological Map Learning

Abstract

In this paper we investigate the application of qualitative spatial reasoning methods for learning the topological map of an unknown environment. We develop a topological mapping framework that achieves robustness against ambiguity in the available information by tracking all possible graph hypotheses simultaneously. We then exploit spatial reasoning to reduce the space of possible hypotheses. The considered constraints are qualitative direction information and the assumption that the map is planar. We investigate the effects of absolute and relative direction information using two different spatial calculi and combine the approach with a real mapping system based on Voronoi graphs.     

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.     

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.     

Influences of Form and Function on the Acceptability of Projective Prepositions in Swedish

Abstract

Projective prepositions express the relation between two objects by referring to a direction in space and have traditionally been regarded as expressing purely geometric relations. Recent studies have shown that the appropriateness of English and Spanish projectives also depends on functional relations between objects. This study investigates if the acceptability of the Swedish projectives över, under, ovanför and nedanför are influenced by functional factors as well, and whether över and under are differentially influenced by function than ovanför and nedanför, as has been shown for their English cognates. It also investigates how the shape and parts of the related objects influence their functional interaction, and thereby the acceptability of the prepositions. This is done with respect to the predictions of the AVS-model, a model of the perceptual processes underlying the apprehension of projectives, which takes both the geometric and the functional relation between objects into account. It was found that acceptability judgments about the prepositions are influenced by function as their corresponding English and Spanish prepositions. The acceptability of över was more sensitive to function than ovanför, whereas under and nedanför were not differentially influenced by function, as has been shown for Spanish. It was further found that the shape and parts of both of the related objects influence acceptability regions associated with the prepositions in predictable ways, as functional interactions between objects largely depend on their parts. The results finally show that the AVS-model needs to be further developed in order to account for the form and function of the located object.     

Interface Familiarity Restores Active Advantage in a Virtual Exploration and Reconstruction Task in Children

Abstract

Active exploration is reportedly better than passive observation of spatial displacements in real environments, for the acquisition of relational spatial information, especially by children. However, a previous study using a virtual environment (VE) showed that children in a passive observation condition performed better than actives when asked to reconstruct in reality the environment explored virtually. Active children were unpractised in using the input device, which may have detracted from any active advantage, since input device operation may be regarded as a concurrent task, increasing cognitive load and spatial working memory demands. To examine this possibility, 7–8-year-old children in the present study were given 5 minutes of training with the joystick input device. When compared with passive participants for spatial learning, active participants gave a better performance than passives, placing objects significantly more accurately. The importance of interface training when using VEs for assessment and training was discussed.     

Evidence for Amodal Representations after Bimodal Learning: Integration of Haptic-Visual Layouts into a Common Spatial Image

Abstract

Participants learned circular layouts of six objects presented haptically or visually, then indicated the direction from a start target to an end target of the same or different modality (intramodal versus intermodal). When objects from the two modalities were learned separately, superior performance for intramodal trials indicated a cost of switching between modalities. When a bimodal layout intermixing modalities was learned, intra- and intermodal trials did not differ reliably. These findings indicate that a spatial image, independent of input modality, can be formed when inputs are spatially and temporally congruent, but not when modalities are temporally segregated in learning.     

Tractable Fragments of Fuzzy Qualitative Algebra

Abstract

In this paper we study the computational complexity of Fuzzy Qualitative Temporal Algebra (QA ^fuz ), a framework that combines qualitative temporal constraints between points and intervals, and allows modelling vagueness and uncertainty. Its tractable fragments can be identified by generalizing the results obtained for crisp Constraint Satisfaction Problems (CSPs) to fuzzy CSPs (FCSPs); to do this, we apply a general methodology based on the notion of α-cut. In particular, the results concerning the tractability of Qualitative Algebra QA, obtained in a recent study by different authors, can be extended to identify the tractable algebras of the fuzzy Qualitative Algebra QA ^fuz in such a way that the obtained set is maximal, namely any maximal tractable fuzzy algebra belongs to this set.     

Space,Language, and Ontology: A Response to Bateman

Abstract

Some of John Bateman's critiques of my article “Qualitative Spatial Reasoning in Interpreting Text and Narrative” are certainly valid. However, the alternative solutions that he proposes do not seem to me to be improvements.     

Taxonomy of Human Wayfinding Tasks: A Knowledge-Based Approach

Abstract

Although the term “Wayfinding” has been defined by several authors, it subsumes a whole set of tasks that involve different cognitive processes, drawing on different cognitive components. Research on wayfinding has been conducted with different paradigms using a variety of wayfinding tasks. This makes it difficult to compare the results and implications of many studies. A systematic classification is needed in order to determine and investigate the cognitive processes and structural components of how humans solve wayfinding problems. Current classifications of wayfinding distinguish tasks on a rather coarse level or do not take the navigator's knowledge, a key factor in wayfinding, into account. We present an extended taxonomy of wayfinding that distinguishes tasks by external constraints as well as by the level of spatial knowledge that is available to the navigator. The taxonomy will help to decrease ambiguity of wayfinding tasks and it will facilitate understanding of the differentiated demands a navigator faces when solving wayfinding problems.     

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.     

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.     

The New Generation of Automatic Landmark Detection Systems: Challenges and Guidelines

Abstract

Landmarks are salient objects in an environment. They play an important role in navigation by serving as orientation aids and marking decision points. Recently, there have been several efforts to design methods to automatically designate certain buildings with salient features as landmarks. All of these methodologies consist of similar steps: (a) establishing a neighborhood, usually around an intersection, (b) performing statistical or data mining analysis to find the building with outlier characteristics, and (c) establishing this salient building as the local landmark. Although these advances are significant, we believe that there are still several key issues that need to be fully addressed in order to realize the new generation of Automatic Landmark Detection Systems (ALDSs). Currently, the main shortcomings in the domain of ALDSs is the lack of a thorough and systematic study of attributes of objects that are analyzed to select landmarks, and deficient experimental verification of the benefits of ALDSs to the end users. Unless, these shortcomings are thoroughly addressed, the viability, applicability, and usefulness of ALDSs are uncertain. On the other hand, automatic landmark detection has the potential to be a dynamic, fascinating, and interdisciplinary research topic with wide applicability. Therefore, the goal of this paper is to discuss the current shortcomings in the domain of landmark detection, propose some preliminary solutions, and provide general guidelines for implementation of the new generation of ALDSs. Specifically, we discuss and promote the importance of: (a) widening the types of attributes analyzed in the landmark detection process, (b) weighting each attribute relative to its significance, (c) extending the types of objects considered as landmark candidates beyond just buildings, (d) identifying landmarks outside the vicinity of intersections, (e) identifying false landmarks along routes, and (f) using virtual environments for experiments with ALDSs. Throughout the paper, we discuss several demonstrative examples and experiments to clarify and support the ideas and concepts that are being promoted.     

Topologically Characterized Movement Patterns: A Cognitive Assessment

Abstract

In this paper, we discuss the role of topology as a predictor for the conceptualization of dynamically changing spatial configurations (referred to as movement patterns). We define meaningful units of movement patterns as paths through a topologically defined conceptual neighborhood graph. Topology plays a central role in formal approaches to human cognition and in predicting cognitive similarity ratings—although primarily for static spatial configurations. Formal specifications of the role of topology for characterizing movement patterns do exist, yet there is paucity of behavioral validation. To bridge this gap, we conducted an experiment based on the grouping paradigm to assess factors that underlie conceptualizations of movement patterns. The experiment was designed such that paths through the conceptual neighborhood graph were distinguished by topologically differentiated ending relations. We believe topology can make an important contribution in explaining movement conceptualizations. One recently formulated topology-based contribution is the endpoint hypothesis, asserting that a cognitive focus is placed on event ending relations. We discuss the results of our experiment in relation to previous experiments targeted toward a framework for modeling the cognitive conceptualization of dynamically changing spatial relations.