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.     

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.     

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.     

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.     

The Psychological Validity of Qualitative Spatial Reasoning in One Dimension

One of the central questions of spatial reasoning research is whether the underlying processes are inherently visual, spatial, or logical. We applied the dual task interference paradigm to spatial reasoning problems in one dimension, using Allen's interval calculus, in order to make progress towards resolving this argument. Our results indicate that spatial reasoning with interval relations is largely based on the construction and inspection of qualitative spatial representations, or mental models, while no evidence for logical proofs of derivations or the involvement of visual representations and processes was found.     

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.     

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.     

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.     

Implicit spatial reference systems using proximity and aligment knowledge

In this paper, we explore the situation where no cardinal directions or globally available orientations are available and no metric estimates are given. This corresponds to the way many people perceive their environment and carry out spatial reasoning tasks. We consider three kinds of locally available information – proximity (nearest neighbor), relevance (different sets of neighbors) and distribution (alignments) – and we limit our interest to a universe of point objects. We show how the theory of manifolds and sheaves can be applied to the problem of combining locally available information of a qualitative nature into a global model of an environmental space. We then explore the limitations of the resulting global model if information capture is incomplete or uncertain. Finally, we note that some indeterminacy in the global model does not entail difficulties for a user, provided the reasoning task is appropriately constrained or appropriate additional information is used, such as an external reference.     

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 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.     

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.     

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.     

基于三维地形匹配的月球软着陆导航方法研究

针对月球探测器定点着陆任务的需要,研究了基于三维地形匹配的导航方法。对三维地形匹配问题,将高程方差图局部极值点作为三维地形特征,在构建地形特征之间的相对位置与角度不变量的基础上,提出了基于投票的三维地形匹配策略。针对测量噪声统计特性的不确定性,将Sage\|Husa噪声估计算子与迭代卡尔曼滤波相结合,通过对测量噪声进行在线估计有效避免滤波精度下降甚至滤波发散的出现。数字仿真结果表明所研究的导航方法能够有效地实现探测器相对位置和姿态的精确估计。     

Spatial Reorientation: Effects of Verbal and Spatial Shadowing

ABSTRACT

Spatially disoriented adults flexibly conjoin geometric information (macroscopic shape) and nongeometric information (e.g., the color of a wall) to re-establish their bearings. It has been proposed that non-geometric information is incorporated into a geometric frame of reference through the use of spatial language. Support for this assumption comes from dual-task studies in which participants failed to use non-geometric features when they shadowed a verbal message concurrent to the reorientation task. These studies were performed in small rectangular spaces. In contrast, our study was performed in a large square room. Experiment 1 showed that verbal shadowing did not disrupt non-geometric feature use in this environment. In Experiment 2, we found that a spatial shadowing task that required the encoding of frequently changing spatial directions impaired reorientation behavior. Our study shows that nongeometric information can be used for reorientation without recourse to linguistic processes, and suggests that the use of non-geometric features is dependent upon a spatial coding process.     

Spatial understanding and temporal correlation for a mobile robot

In this article we discuss a network model, which simulates functionallysome of the features intrinsic to human navigation and the merits ofincorporating such features on a behavior-based robot. Specifically thepaper deals with implementing a memory based reasoning strategy duringreal-time navigation of a mobile robot. For the purpose ofimplementation, memory has been identified with an ability to cognizethe local environment or scenario, classify such scenarios in terms ofpreviously learned primitives or landmarks, remember and recollect suchprimitives at later instants and correlate over time similar experiencesof scenarios. Such memory based reasoning enhances the robot'snavigation capabilities through intelligent decisions due to spatialunderstanding, scene recollection abilities by remembrance and detectinglocal minimum traps through place recognition. A double layeredspatio-temporal classification scheme consisting of a fuzzy rule-basedspatial classifier and a temporal classifier based on self-organizingmap and ART networks are adopted for this purpose. The classifiernetwork reduces the robot's experience of its environment consisting ofa stream of sensor patterns into weight vectors that signify aparticular landmark. An extension of the network architecture is alsointroduced to cognize the presence of dynamic obstacles amidststationary ones.     

TDD: A Comprehensive Model for Qualitative Spatial Similarity Assessment

Similarity plays a fundamental role in the human cognition process. It serves as a principle of categorization, inductive reasoning, and analogical inference. Spatial similarity assessment plays the same role in the retrieval, integration, and data mining of spatial information. In this paper, we introduce the basic components of a similarity assessment model. The model makes a contribution in the following aspects. First, it applies the order of priority topology --> direction --> distance into spatial similarity assessment. Second, instead of measuring the distance between stimuli, which neglects the effect of common features, we adopt Tversky's feature contrast model, which considers both commonality and difference in similarity assessment. Third, our model applies spatial alignment, which was considered as an assumption in previous research. Fourth, it relaxes the rule used in previous research, which considered identical the transformation costs of each edge belonging to a conceptual neighborhood network. In order to address this fourth point, we group the topological relationships and introduce the concepts of inter- and intra-group transformation costs. The inter-group transformation cost has a higher value than the intra-group transformation cost. We call the model TDD for Topology-Direction-Distance.     

Spatio-Temporal Ontologies and Attention

ABSTRACT

This paper presents a new proposal for the design of spatio-temporal ontologies which has its origin in cognitively motivated spatial semantics. It is shown that selective attention not only plays a central role in the characterization of spatial relations but that the representation of attentional aspects also leads to the possibility of defining an ontological upper structure which systematically covers both the spatial and the temporal domain.     

空间目标光谱特征快速提取

本文利用完备正交函数系计算图象强度函数的数字投影特征序列，此投影特征既能反映目标的外形特点，又能反映目标的光谱特征，利用它不但能区分不同外形的空间目标，还能区分外形相同而光谱特性不同的真假目标。本文还介绍了空间目标光谱特征快速提取系统中需要解决的关键问题和方法。提出了一种空间目标边缘检测梯度算法和一种运动坐标系建立方法。用不同类型卫星图象做了大量实验，验证了所提方法的合理性和可行性。