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.     

Buffering Fuzzy Maps in GIS

In this paper, we show how standard GIS operations like the complement, union, intersection, and buffering of maps can be made more flexible by using fuzzy set theory. In particular, we present a variety of algorithms for operations on fuzzy raster maps, focusing on buffer operations for such maps. Furthermore, we show how widely-available special-purpose hardware (in particular, z-buffering in graphics hardware) can be used for supporting buffer operations in fuzzy geographic information systems (GIS).     

Lagrangian coherent structures in various map representations for application to multi-body gravitational regimes

The Finite-Time Lyapunov Exponent (FTLE) has been demonstrated as an effective metric for revealing distinct, bounded regions within a flow. The dynamical differential equations derived in multi-body gravitational environments model a flow that governs the motion of a spacecraft. Specific features emerge in an FTLE map, denoted Lagrangian Coherent Structures (LCS), that define the extent of regions that bound qualitatively different types of behavior. Consequently, LCS supply effective barriers to transport in a generic system, similar to the notion of invariant manifolds in autonomous systems. Unlike traditional invariant manifolds associated with solutions in an autonomous system, LCS evolve with the flow in time-dependent systems while continuing to bound distinct regions of behavior. Moreover, in general, FTLE values supply information describing the relative sensitivity in the neighborhood of a trajectory. Here, different models and variable representations are used to generate maps of FTLE, and the resulting structures are applied to design and analysis within an astrodynamical context. Application of FTLE and LCS to transfers from LEO to the L₁ region in the Earth–Moon system are presented and discussed. In an additional example, an FTLE analysis is offered of a few stationkeeping maneuvers from the Earth–Moon mission ARTEMIS (Acceleration, Reconnection, Turbulence and Electrodynamics of the Moon's Interaction with the Sun).     

Route generation and description using the notions of object's influence area and spatial conceptual map

In the GRAAD Project we aimed at creatinga system which could generate route directions thatare comparable to route directions created by humanparticipants. With this goal in mind, we started froma linguistic and cognitive study of route directionsproduced by people and the study of cognitive modelsof mental maps. We proposed a new qualitative spatialmodel that can support the spatial properties of humanroute directions. This model is based on the notion ofobject's influence area which is used to modelneighborhood, orientation and distance. The proposedapproach relies on the manipulation of spatialentities in a spatial conceptual map (SCM) which isthe computarized analog of a mental map used bypeople. We developped the GRAAD System, software thatgenerates routes in a SCM and describes them innatural language. Finally, we conducted an experimentin order to compare GRAAD's route directions androutes described by human participants in similarexperimental conditions. GRAAD's output was notdistinguishable from route directions created by humanparticipants. In this paper we present the mainresults obtained during all phases of the GRAADProject.     

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.     

Where's Downtown?: Behavioral Methods for Determining Referents of Vague Spatial Queries

Humans think and talk about regions and spatial relations imprecisely, in terms of vague concepts that are fuzzy or probabilistic (e.g., downtown, near). The functionality of geographic information systems will be increased if they can interpret vague queries. We discuss traditional and newer approaches to defining and modeling spatial queries. Most of the research on vague concepts in information systems has focussed on mathematical and computational implementation. To complement this, we discuss behavioral-science methods for determining the referents of vague spatial terms, particularly vague regions. We present a study of the empirical determination of downtown Santa Barbara. We conclude with a discussion of prospects and problems for integrating vague concepts into geographic information systems.     

Heading south with a north-up map: A choice processing analysis of map alignment effects

This study employed an information accumulation model of choice reaction times to investigate alignment effects in mental representations of maps. University students studied a map from a single orientation (with north at the top). In a subsequent two-choice reaction time task, the students’ spatial knowledge of the map was assessed employing spatial left/right judgments, which were made from imagined perspectives that were either north-aligned or south-aligned. Data showed a standard alignment effect, favoring north- over south-aligned trials. To examine the locus of this effect, data were fit using the Linear Ballistic Accumulator (LBA) model of speeded decisions (Brown & Heathcote, 2008). Of interest were three model parameters: drift rate, the speed at which evidence accumulates toward a response; response threshold, the amount of evidence demanded from the decision maker before selecting a response; and non-decision time, the time consumed by pre- and postdecisional processes. The best-fitting model suggested that non-decision time accounted for the alignment effect. The difference in non-decision time between north and south-aligned judgments suggests a mental alignment stage on south-aligned trials, accounting for the longer reaction times for judgements misaligned with the presented north orientation of the map.     

The effects of maps and textual information on navigation in a desktop virtual environment

This study presents an experimentthat investigates how individuals perform anavigation test in a desktop virtualenvironment. The participants were randomlyassigned to one of the five test conditions:(C1) a map as information material during theentire test, (C2) the map only visible beforethe test, (C3) textual information during theentire test, (C4) textual information onlybefore the test and (C5) no additionalnavigational cues. The results were thatadditional information during the entire testwas more effective than short periods ofstudying the map or textual information onlybefore the test. However, participants weremore accurate in finding their route when anykind of navigational cues were used than whenno navigational cues were used. The results ofan additional questionnaire indicate thatbetween the test groups there were nodifferences in estimating the travelleddistances. The performance to draw the coveredpath into a sketch map of the landscape did notdiffer significantly between the test groupswith additional navigational cues. Theseresults indicate that in certain environmentstextual information may provide an effectivealternative to navigation training with a map.     

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.     

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.     

Virtual to Real Transfer of Spatial Learning in a Complex Environment: The Role of Path Network and Additional Features

The effects of the amount and type of spatial information on the orientation accuracy and metric properties of mental representations of a large-scale built environment were evaluated in a virtual-real transfer study. Four groups of participants explored different virtual versions of a campus before being tested in the real environment. Learning with or without additional features and with or without a network of pathways led to different patterns of data. Although direction measures and straight-line and route distance estimates were least accurate in the absence of either type of information, the combination of both types of information did not produce more accurate knowledge than either did alone. In particular, the presence of additional features had a facilitating effect only on the direction estimates. The results highlight the respective importance of amount and type of spatial information in the acquisition and use of mental spatial representations.     

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.     

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.     

Earth–Moon libration point orbit stationkeeping: Theory,modeling, and operations

Collinear Earth–Moon libration points have emerged as locations with immediate applications. These libration point orbits are inherently unstable and must be maintained regularly which constrains operations and maneuver locations. Stationkeeping is challenging due to relatively short time scales for divergence, effects of large orbital eccentricity of the secondary body, and third-body perturbations. Using the Acceleration Reconnection and Turbulence and Electrodynamics of the Moon's Interaction with the Sun (ARTEMIS) mission orbit as a platform, the fundamental behavior of the trajectories is explored using Poincaré maps in the circular restricted three-body problem. Operational stationkeeping results obtained using the Optimal Continuation Strategy are presented and compared to orbit stability information generated from mode analysis based in dynamical systems theory.