A Survey of Qualitative Spatial and Temporal Calculi: Algebraic and Computational Properties
---
paper_title: A survey of qualitative spatial representations

paper_content:

Representation and reasoning with qualitative spatial relations is an important problem in artificial intelligence and has wide applications in the fields of geographic information system, computer vision, autonomous robot navigation, natural language understanding, spatial databases and so on. The reasons for this interest in using qualitative spatial relations include cognitive comprehensibility, efficiency and computational facility. This paper summarizes progress in qualitative spatial representation by describing key calculi representing different types of spatial relationships. The paper concludes with a discussion of current research and glimpse of future work.
---
paper_title: Qualitative Spatial Reasoning with Cardinal Directions

paper_content:

Following reviews of previous approaches to spatial reasoning, a completely qualitative method for reasoning about cardinal directions, without recourse to analytical procedures, is introduced and a method is presented for a formal comparison with quantitative formulae. We use an algebraic method to formalize the meaning of cardinal directions. The standard directional symbols (N, S, E, W) are extended with a symbol 0 to denote an undecided case, which greatly increases the power of inference. Two examples of systems to determine and reason with cardinal directions are discussed in some detail and results from a prototype are given. The deduction rules for the coordination of directional symbols are formalized as equations; for inclusion in an expert system they can be coded as a look-up table (given in the text). The conclusions offer some direction for future work.
---
paper_title: Reasoning about binary topological relations

paper_content:

A new formalism is presented to reason about topological relations. It is applicable as a foundation for an algebra over topological relations. The formalism is based upon the nine intersections of boundaries, interiors, and complements between two objects. Properties of topological relations are determined by analyzing the nine intersections to detect, for instance, symmetric topological relations and pairs of converse topological relations. Based upon the standard rules for the transitivity of set inclusion, the intersections of the composition of two binary topological relations are determined. These intersections are then matched with the intersections of the eight fundamental topological relations, giving an interpretation to the composition of topological relations.
---
paper_title: Modeling Spatial Knowledge

paper_content:

A person's cognitive map, or knowledge of large-scale space, is built up from observations gathered as he travels through the environment. It acts as a problem solver to find routes and relative positions, as well as describing the current location. The TOUR model captures the multiple representations that make up the cognitive map, the problem-solving strategies it uses, and the mechanisms for assimilating new information. The representations have rich collections of states of partial knowledge, which support many of the performance characteristics of common-sense knowledge.
---
paper_title: Qualitative spatial reasoning about distances and directions in geographic space

paper_content:

Abstract Most known methods for spatial reasoning translate a spatial problem into an analytical formulation in order to solve it quantitatively. This paper describes a method for formal, qualitative reasoning about distances and cardinal directions in geographic space. The problem addressed is how to deduce the distance and direction from point A to C, given the distance and direction from A to B and B to C. We use an algebraic approach, discussing the manipulation of distance and direction symbols (e.g. ‘N’, ‘E’, ‘S’ and ‘W’, or ‘Far’ and ‘Close’) and define two operations, composition and inverse , applied to them. After a review of other approaches, the desirable properties of deduction rules for distance and direction values are analyzed. This includes an algebraic specification of the ‘path’ image schema, from which most of the properties of distance and direction manipulation follow. Specific systems for composition of distance are explored. For directions, a formalization of the well-known triangular concept of directions (here called cone-shaped directions) and an alternative projection-based concept are explored. The algebraic approach leads to the completion of distance or direction symbols with an identity element, standing for the direction or distance from a point to itself. The so completed axiom system allows deductions, at least ‘Euclidean-approximate’, for any combination of input values.
---
paper_title: The Psychological Validity of Qualitative Spatial Reasoning in One Dimension

paper_content:

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.
---
paper_title: Current topics in qualitative reasoning

paper_content:

In this editorial introduction to this special issue of AI Magazine on qualitative reasoning, we briefly discuss the main motivations and characteristics of this branch of AI research. We also summarize the contributions in this issue and point out challenges for future research.
---
paper_title: GIS, a computing perspective

paper_content:

INTRODUCTION What is a GIS? GIS Functionality Data and Databases Hardware Support FUNDAMENTAL DATABASE CONCEPTS Introduction to Databases Relational Databases Database Development Object-Orientation FUNDAMENTAL SPATIAL CONCEPTS Euclidean Space Set-Based Geometry of Space Topology of Space Network Spaces Metric Spaces Endnote on Fractal Geometry MODELS OF GEOSPATIAL INFORMATION Modeling and Ontology The Modeling Process Field-Based Models Object-Based Models REPRESENTATION AND ALGORITHMS Computing with Geospatial Data The Discrete Euclidean Plane The Spatial Object Domain Representations of Field-Based Models Fundamental Geometric Algorithms Vectorization and Rasterization Network Representation and Algorithms STRUCTURES AND ACCESS METHODS General Database Structures and Access Methods From One to Two Dimensions Raster Structures Point Object Structures Linear Objects Collections of Objects Spherical Data Structures ARCHITECTURES Hybrid, Integrated, and Composable Architectures Syntactic and Semantic Heterogeneity Distributed Systems Distributed Databases Location-Aware Computing INTERFACES Human-Computer Interaction Cartographic Interfaces Geovisualization Developing GIS Interfaces SPATIAL REASONING AND UNCERTAINTY Formal Aspects of Spatial Reasoning Information and Uncertainty Qualitative Approaches to Uncertainty Quantitative Approaches to Uncertainty Applications of Uncertainty in GIS TIME Introduction: A Brief History of Time Temporal Information Systems Spatiotemporal Information Systems Indexes and Queries Appendices
---
paper_title: Exploiting qualitative spatial reasoning for topological adjustment of spatial data

paper_content:

Formal models of spatial relations such as the 9-Intersection model or RCC-8 have become omnipresent in the spatial information sciences and play an important role to formulate constraints in many applications of spatial data processing. A fundamental problem in such applications is to adapt geometric data to satisfy certain relational constraints while minimizing the changes that need to be made to the data. We address the problem of adjusting geometric objects to meet the spatial relations from a qualitative spatial calculus, forming a bridge between the areas of qualitative spatial representation and reasoning (QSR) and of geometric adjustment using optimization approaches. In particular, we explore how constraint-based QSR techniques can be beneficially employed to improve the optimization process. We discuss three different ways in which QSR can be utilized and then focus on its application to reduce the complexity of the optimization problem in terms of variables and equations needed. We propose two constraint-based problem simplification algorithms and evaluate them experimentally. Our results demonstrate that exploiting QSR techniques indeed leads to a significant performance improvement.
---
paper_title: Qualitative spatial and temporal reasoning with AND/OR linear programming

paper_content:

This paper explores the use of generalized linear programming techniques to tackle two long-standing problems in qualitative spatio-temporal reasoning: Using LP as a unifying basis for reasoning, one can jointly reason about relations from different qualitative calculi. Also, concrete entities (fixed points, regions fixed in shape and/or position, etc.) can be mixed with free variables. Both features are important for applications but cannot be handled by existing techniques. In this paper we discuss properties of encoding constraint problems involving spatial and temporal relations. We advocate the use of AND/OR graphs to facilitate efficient reasoning and we show feasibility of our approach.
---
paper_title: On Redundant Topological Constraints

paper_content:

The Region Connection Calculus (RCC) is a well-known calculus for representing part-whole and topological relations. It plays an important role in qualitative spatial reasoning, geographical information science, and ontology. The computational complexity of reasoning with RCC has been investigated in depth in the literature. Most of these works focus on the consistency of RCC constraint networks. In this paper, we consider the important problem of redundant RCC constraints. For a set Γ of RCC constraints, we say a constraint (x R y) in Γ is redundant if it can be entailed by the rest of Γ. A prime network of Γ is a subset of Γ which contains no redundant constraints but has the same solution set as Γ. It is natural to ask how to compute a prime network, and when it is unique. In this paper, we show that this problem is in general co-NP hard, but becomes tractable if Γ is over a tractable subclass of RCC. If S is a tractable subclass in which weak composition distributes over non-empty intersections, then we can show that Γ has a unique prime network, which is obtained by removing all redundant constraints from Γ. As a byproduct, we identify a sufficient condition for a path-consistent network being minimal.
---
paper_title: On the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints

paper_content:

Spatial and temporal reasoning is a crucial task for certain Artificial Intelligence applications. In this context, and since two decades, various formalisms representing the information through qualitative constraint networks (QCN) have been proposed. Given a QCN, the main two problems that are facing researchers are: deciding whether this QCN is consistent or not, and, the minimal labeling problem. In this paper, we propose an efficient algorithm aiming at solving the minimal labeling problem. This algorithm is based on subclasses of relations for which the property of-consistency implies the minimality of the QCN.
---
paper_title: Towards a declarative spatial reasoning system

paper_content:

We present early results on the development of a declarative spatial reasoning system within the context of the Constraint Logic Programming (CLP) framework. The system is capable of modelling and reasoning about qualitative spatial relations pertaining to multiple spatial domains, i.e., one or more aspects of space such as topology, and intrinsic and extrinsic orientation. It provides a seamless mechanism for combining formal qualitative spatial calculi within one framework, and provides a Prolog-based declarative interface for AI applications to abstract and reason about quantitative, geometric information in a qualitative manner. Based on previous work concerning the formalisation of the framework [2], we present ongoing work to develop the theoretical result into a comprehensive reasoning system (and Prolog-based library) which may be used independently, or as a logic-based module within hybrid intelligent systems.
---
paper_title: Qualitative Spatial Representation and Reasoning with the Region Connection Calculus

paper_content:

This paper surveys the work of the qualitative spatial reasoning group at the University of Leeds. The group has developed a number of logical calculi for representing and reasoning with qualitative spatial relations over regions. We motivate the use of regions as the primary spatial entity and show how a rich language can be built up from surprisingly few primitives. This language can distinguish between convex and a variety of concave shapes and there is also an extension which handles regions with uncertain boundaries. We also present a variety of reasoning techniques, both for static and dynamic situations. A number of possible application areas are briefly mentioned.
---
paper_title: Qualitative Spatial Reasoning about Sketch Maps

paper_content:

Sketch maps are an important spatial representation used in many geospatial-reasoning tasks. This article describes techniques we have developed that enable software to perform humanlike reasoning about sketch maps. We illustrate the utility of these techniques in the context of nuSketch Battlespace, a research system that has been successfully used in a variety of experiments. After an overview of the nuSketch approach and nuSketch Battlespace, we outline the representations of glyphs and sketches and the nuSketch spatial reasoning architecture. We describe the use of qualitative topology and Voronoi diagrams to construct spatial representations, and explain how these facilities are combined with analogical reasoning to provide a simple form of enemy intent hypothesis generation.
---
paper_title: Realizing RCC8 networks using convex regions

paper_content:

RCC8 is a popular fragment of the region connection calculus, in which qualitative spatial relations between regions, such as adjacency, overlap and parthood, can be expressed. While RCC8 is essentially dimensionless, most current applications are confined to reasoning about two-dimensional or three-dimensional physical space. In this paper, however, we are mainly interested in conceptual spaces, which typically are high-dimensional Euclidean spaces in which the meaning of natural language concepts can be represented using convex regions. The aim of this paper is to analyze how the restriction to convex regions constrains the realizability of networks of RCC8 relations. First, we identify all ways in which the set of RCC8 base relations can be restricted to guarantee that consistent networks can be convexly realized in respectively 1D, 2D, 3D, and 4D. Most surprisingly, we find that if the relation 'partially overlaps' is disallowed, all consistent atomic RCC8 networks can be convexly realized in 4D. If instead refinements of the relation 'part of' are disallowed, all consistent atomic RCC8 relations can be convexly realized in 3D. We furthermore show, among others, that any consistent RCC8 network with 2n+1 variables can be realized using convex regions in the n-dimensional Euclidean space.
---
paper_title: Qualitative Spatial Reasoning with Conceptual Neighborhoods for Agent Control

paper_content:

Research on qualitative spatial reasoning has produced a variety of calculi for reasoning about orientation or direction relations. Such qualitative abstractions are very helpful for agent control and communication between robots and humans. Conceptual neighborhood has been introduced as a means of describing possible changes of spatial relations which e.g. allows action planning at a high level of abstraction. We discuss how the concrete neighborhood structure depends on application-specific parameters and derive corresponding neighborhood structures for the $\mathcal{OPRA}_m$ calculus. We demonstrate that conceptual neighborhoods allow resolution of conflicting information by model-based relaxation of spatial constraints. In addition, we address the problem of automatically deriving neighborhood structures and show how this can be achieved if the relations of a calculus can be modeled in another calculus for which the neighborhood structure is known.
---
paper_title: Formal Properties of Constraint Calculi for Qualitative Spatial Reasoning

paper_content:

In the previous two decades, a number of qualitative constraint calculi have been developed, which are used to represent and reason about spatial configurations. A common property of almost all of these calculi is that reasoning in them can be understood as solving a binary constraint satisfaction problem over infinite domains. The main algorithmic method that is used is constraint propagation in the form of the path-consistency method. This approach can be applied to a wide range of different aspects of spatial reasoning. We describe how to make use of this representation and reasoning technique and point out the possible problems one might encounter. 1 Qualitative Spatial Representation and Reasoning Representing spatial information and reasoning about this information is an important subproblem in many applications, such as geographical information systems (GIS), natural language understanding, robot navigation, and document interpretation. Often this information is only available qualitatively, for instance when a GIS query or integrity condition has to be specified (Sharma et al., 1994). Similarly, in document interpretation, the precise size and location of layout objects is not of interest, but the relative position of these objects matters (Walischewski, 1999). A number of approaches to representing qualitative spatial information and reasoning about it are possible. A very early attempt at qualitative spatial representation and reasoning is Kuipers’ (1978) TOUR model, which addresses the navigation problem using qualitative descriptions. Other approaches aim, for instance, to capture spatial notions using first-order logic (Randell and Cohn, 1989;
---
paper_title: What is a Qualitative Calculus ? A General Framework

paper_content:

What is a qualitative calculus? Many qualitative spatial and temporal calculi arise from a set of JEPD (jointly exhaustive and pairwise disjoint) relations: a stock example is Allen's calculus, which is based on thirteen basic relations between intervals on the time line. This paper examines the construction of such a formalism from a general point of view, in order to make apparent the formal algebraic properties of all formalisms of that type. We show that the natural algebraic object governing this kind of calculus is a non-associative algebra (in the sense of Maddux), and that the notion of weak representation is the right notion for describing most basic properties. We discuss the ubiquity of weak representations in various guises, and argue that the fundamental notion of consistency itself can best be understood in terms of consistency of one weak representation with respect to another.
---
paper_title: What is a Qualitative Calculus ? A General Framework

paper_content:

What is a qualitative calculus? Many qualitative spatial and temporal calculi arise from a set of JEPD (jointly exhaustive and pairwise disjoint) relations: a stock example is Allen's calculus, which is based on thirteen basic relations between intervals on the time line. This paper examines the construction of such a formalism from a general point of view, in order to make apparent the formal algebraic properties of all formalisms of that type. We show that the natural algebraic object governing this kind of calculus is a non-associative algebra (in the sense of Maddux), and that the notion of weak representation is the right notion for describing most basic properties. We discuss the ubiquity of weak representations in various guises, and argue that the fundamental notion of consistency itself can best be understood in terms of consistency of one weak representation with respect to another.
---
paper_title: What is a Qualitative Calculus ? A General Framework

paper_content:

What is a qualitative calculus? Many qualitative spatial and temporal calculi arise from a set of JEPD (jointly exhaustive and pairwise disjoint) relations: a stock example is Allen's calculus, which is based on thirteen basic relations between intervals on the time line. This paper examines the construction of such a formalism from a general point of view, in order to make apparent the formal algebraic properties of all formalisms of that type. We show that the natural algebraic object governing this kind of calculus is a non-associative algebra (in the sense of Maddux), and that the notion of weak representation is the right notion for describing most basic properties. We discuss the ubiquity of weak representations in various guises, and argue that the fundamental notion of consistency itself can best be understood in terms of consistency of one weak representation with respect to another.
---
paper_title: The finest of its class: The natural point-based ternary calculus for qualitative spatial reasoning

paper_content:

In this paper, a ternary qualitative calculus ${\mathcal LR}$ for spatial reasoning is presented that distinguishes between left and right. A theory is outlined for ternary point-based calculi in which all the relations are invariant when all points are mapped by rotations, scalings, or translations (RST relations). For this purpose, we develop methods to determine arbitrary transformations and compositions of RST relations. We pose two criteria which we call practical and natural. ‘Practical' means that the relation system should be closed under transformations, compositions and intersections and have a finite base that is jointly exhaustive and pairwise disjoint. This implies that the well-known path consistency algorithm [10] can be used to conclude implicit knowledge. ‘Natural' calculi are close to our natural way of thinking because the base relations and their complements are connected. The main result of the paper is the identification of a maximally refined calculus amongst the practical natural RST calculi, which turns out to be very similar to Ligozat's flip-flop calculus. From that it follows, e.g., that there is no finite refinement of the TPCC calculus by Moratz et al that is closed under transformations, composition, and intersection.
---
paper_title: On the utilization of spatial structures for cognitively plausible and efficient reasoning

paper_content:

The authors present an approach to representing and processing qualitative orientation information which is motivated by cognitive considerations about the knowledge acquisition process. The approach to qualitative spatial reasoning is based on directional orientation information as available through perceptual processes. qualitative orientations in two-dimensional space are given by the relation between a point and a vector. A basic iconic notation for spatial orientation relations which exploits the spatial structure of the domain is presented, and a variety of ways in which these relations can be manipulated and combined for spatial reasoning is explored. >
---
paper_title: Formal Properties of Constraint Calculi for Qualitative Spatial Reasoning

paper_content:

In the previous two decades, a number of qualitative constraint calculi have been developed, which are used to represent and reason about spatial configurations. A common property of almost all of these calculi is that reasoning in them can be understood as solving a binary constraint satisfaction problem over infinite domains. The main algorithmic method that is used is constraint propagation in the form of the path-consistency method. This approach can be applied to a wide range of different aspects of spatial reasoning. We describe how to make use of this representation and reasoning technique and point out the possible problems one might encounter. 1 Qualitative Spatial Representation and Reasoning Representing spatial information and reasoning about this information is an important subproblem in many applications, such as geographical information systems (GIS), natural language understanding, robot navigation, and document interpretation. Often this information is only available qualitatively, for instance when a GIS query or integrity condition has to be specified (Sharma et al., 1994). Similarly, in document interpretation, the precise size and location of layout objects is not of interest, but the relative position of these objects matters (Walischewski, 1999). A number of approaches to representing qualitative spatial information and reasoning about it are possible. A very early attempt at qualitative spatial representation and reasoning is Kuipers’ (1978) TOUR model, which addresses the navigation problem using qualitative descriptions. Other approaches aim, for instance, to capture spatial notions using first-order logic (Randell and Cohn, 1989;
---
paper_title: What is a Qualitative Calculus ? A General Framework

paper_content:

What is a qualitative calculus? Many qualitative spatial and temporal calculi arise from a set of JEPD (jointly exhaustive and pairwise disjoint) relations: a stock example is Allen's calculus, which is based on thirteen basic relations between intervals on the time line. This paper examines the construction of such a formalism from a general point of view, in order to make apparent the formal algebraic properties of all formalisms of that type. We show that the natural algebraic object governing this kind of calculus is a non-associative algebra (in the sense of Maddux), and that the notion of weak representation is the right notion for describing most basic properties. We discuss the ubiquity of weak representations in various guises, and argue that the fundamental notion of consistency itself can best be understood in terms of consistency of one weak representation with respect to another.
---
paper_title: A new approach to cyclic ordering of 2D orientations using ternary relation algebras

paper_content:

Abstract In Tarski's formalisation, the universe of a relation algebra (RA) consists of a set of binary relations. A first contribution of this work is the introduction of RAs whose universe is a set of ternary relations: these support rotation as an operation in addition to those present in Tarski's formalisation. Then we propose two particular RAs: a binary RA, CYC b , whose universe is a set of (binary) relations on 2D orientations; and a ternary RA, CYC t , whose universe is a set of (ternary) relations on 2D orientations. The RA CYC t , more expressive than CYC b , constitutes a new approach to cyclic ordering of 2D orientations. An atom of CYC t expresses for triples of orientations whether each of the three orientations is equal to, to the left of, opposite to, or to the right of each of the other two orientations. CYC t has 24 atoms and the elements of its universe consist of all possible 2 24 subsets of the set of all atoms. Amongst other results, 1. we provide for CYC t a constraint propagation procedure computing the closure of a problem under the different operations, and show that the procedure is polynomial, and complete for a subset including all atoms; 2. we prove that another subset, expressing only information on parallel orientations, is NP-complete; 3. we show that provided that a subset S of CYC t includes two specific elements, deciding consistency for a problem expressed in the closure of S can be polynomially reduced to deciding consistency for a problem expressed in S ; and 4. we derive from the previous result that for both RAs we “jump” from tractability to intractability if we add the universal relation to the set of all atoms. A comparison to the most closely related work in the literature indicates that the approach is promising.
---
paper_title: The finest of its class: The natural point-based ternary calculus for qualitative spatial reasoning

paper_content:

In this paper, a ternary qualitative calculus ${\mathcal LR}$ for spatial reasoning is presented that distinguishes between left and right. A theory is outlined for ternary point-based calculi in which all the relations are invariant when all points are mapped by rotations, scalings, or translations (RST relations). For this purpose, we develop methods to determine arbitrary transformations and compositions of RST relations. We pose two criteria which we call practical and natural. ‘Practical' means that the relation system should be closed under transformations, compositions and intersections and have a finite base that is jointly exhaustive and pairwise disjoint. This implies that the well-known path consistency algorithm [10] can be used to conclude implicit knowledge. ‘Natural' calculi are close to our natural way of thinking because the base relations and their complements are connected. The main result of the paper is the identification of a maximally refined calculus amongst the practical natural RST calculi, which turns out to be very similar to Ligozat's flip-flop calculus. From that it follows, e.g., that there is no finite refinement of the TPCC calculus by Moratz et al that is closed under transformations, composition, and intersection.
---
paper_title: On the consistency of cardinal directions constraints

paper_content:

We present a formal model for qualitative spatial reasoning with cardinal directions utilizing a co-ordinate system. Then, we study the problem of checking the consistency of a set of cardinal direction constraints. We introduce the first algorithm for this problem, prove its correctness and analyze its computational complexity. Utilizing the above algorithm, we prove that the consistency checking of a set of basic (i.e., non-disjunctive) cardinal direction constraints can be performed in O(n^5) time. We also show that the consistency checking of a set of unrestricted (i.e., disjunctive and non-disjunctive) cardinal direction constraints is NP-complete. Finally, we briefly discuss an extension to the basic model and outline an algorithm for the consistency checking problem of this extension.
---
paper_title: Using Orientation Information for Qualitative Spatial Reasoning

paper_content:

A new approach to representing qualitative spatial knowledge and to spatial reasoning is presented. This approach is motivated by cognitive considerations and is based on relative orientation information about spatial environments. The approach aims at exploiting properties of physical space which surface when the spatial knowledge is structured according to conceptual neighborhood of spatial relations. The paper introduces the notion of conceptual neighborhood and its relevance for qualitative temporal reasoning. The extension of the benefits to spatial reasoning is suggested. Several approaches to qualitative spatial reasoning are briefly reviewed. Differences between the temporal and the spatial domain are outlined. A way of transferring a qualitative temporal reasoning method to the spatial domain is proposed. The resulting neighborhood-oriented representation and reasoning approach is presented and illustrated. An example for an application of the approach is discussed.
---
paper_title: On the Scope of Qualitative Constraint Calculi

paper_content:

A central notion in qualitative spatial and temporal reasoning is the concept of qualitative constraint calculus, which captures a particular paradigm of representing and reasoning about spatial and temporal knowledge. The concept, informally used in the research community for a long time, was formally defined by Ligozat and Renz in 2004 as a special kind of relation algebra — thus emphasizing a particular type of reasoning about binary constraints. Although the concept is known to be limited it has prevailed in the community. In this paper we revisit the concept, contrast it with alternative approaches, and analyze general properties. Our results indicate that the concept of qualitative constraint calculus is both too narrow and too general: it disallows different approaches, but its setup already enables arbitrarily hard problems.
---
paper_title: On the utilization of spatial structures for cognitively plausible and efficient reasoning

paper_content:

The authors present an approach to representing and processing qualitative orientation information which is motivated by cognitive considerations about the knowledge acquisition process. The approach to qualitative spatial reasoning is based on directional orientation information as available through perceptual processes. qualitative orientations in two-dimensional space are given by the relation between a point and a vector. A basic iconic notation for spatial orientation relations which exploits the spatial structure of the domain is presented, and a variety of ways in which these relations can be manipulated and combined for spatial reasoning is explored. >
---
paper_title: Categorical methods in qualitative reasoning: the case for weak representations

paper_content:

This paper argues for considering qualitative spatial and temporal reasoning in algebraic and category-theoretic terms. A central notion in this context is that of weak representation (WR) of the algebra governing the calculus. WRs are ubiquitous in qualitative reasoning, appearing both as domains of interpretation and as constraints. Defining the category of WRs allows us to express the basic notion of satisfiability (or consistency) in a simple way, and brings clarity to the study of various variants of consistency. The WRs of many popular calculi are of interest in themselves. Moreover, the classification of WRs leads to non-trivial model-theoretic results. The paper provides a not-too-technical introduction to these topics and illustrates it with simple examples.
---
paper_title: Qualitative Spatial and Temporal Reasoning: Efficient Algorithms for Everyone

paper_content:

In the past years a lot of research effort has been put into finding tractable subsets of spatial and temporal calculi. It has been shown empirically that large tractable subsets of these calculi not only provide efficient algorithms for reasoning problems that can be expressed with relations contained in the tractable subsets, but also surprisingly efficient solutions to the general, NP-hard reasoning problems of the full calculi. An important step in this direction was the refinement algorithm which provides a heuristic for proving tractability of given subsets of relations. In this paper we extend the refinement algorithm and present a procedure which identifies large tractable subsets of spatial and temporal calculi automatically without any manual intervention and without the need for additional NP-hardness proofs. While we can only guarantee tractability of the resulting sets, our experiments show that for RCC8 and the Interval Algebra, our procedure automatically identifies all maximal tractable subsets. Using our procedure, other researchers and practitioners can automatically develop efficient reasoning algorithms for their spatial or temporal calculi without any theoretical knowledge about how to formally analyse these calculi.
---
paper_title: PelletSpatial: A Hybrid RCC-8 and RDF/OWL Reasoning and Query Engine

paper_content:

In this paper, we present PelletSpatial, a qualitative spatial reasoning engine implemented on top of Pellet. PelletSpatial provides consistency checking and query answering over spatial data represented with the Region Connection Calculus (RCC). It supports all RCC-8 relations as well as standard RDF/OWL semantic relations, both represented in RDF/OWL. As such, it can answer mixed SPARQL queries over both relation types. PelletSpatial implements two RCC reasoners: (a) A reasoner based on the semantics preserving translation of RCC relations to OWL-DL class axioms and (b) a reasoner based on the RCC composition table that implements a path-consistency algorithm. We discuss the details of two implementation approaches and focus on some of their respective advantages and disadvantages.
---
paper_title: The RacerPro knowledge representation and reasoning system

paper_content:

RacerPro is a software system for building applications based on ontologies. The backbone of RacerPro is a description logic reasoner. It provides inference services for terminological knowledge as well as for representations of knowledge about individuals. Based on new optimization techniques and techniques that have been developed in the research field of description logics throughout the years, a mature architecture for typical-case reasoning tasks is provided. The system has been used in hundreds of research projects and industrial contexts throughout the last twelve years. W3C standards as well as detailed feedback reports from numerous users have influenced the design of the system architecture in general, and have also shaped the RacerPro knowledge representation and interface languages. With its query and rule languages, RacerPro goes well beyond standard inference services provided by other OWL reasoners.
---
paper_title: SPASS Version 2.0

paper_content:

Spass is an automated theorem prover for full first-order logic with equality. This system description provides an overview of recent developments in Spass 2.0, including among others an implementation of contextual rewriting, refinements of the clause normal form transformation, and enhancements of the inference engine.
---
paper_title: Reasoning about Cardinal Directions between Extended Objects

paper_content:

Direction relations between extended spatial objects are important commonsense knowledge. Recently, Goyal and Egenhofer proposed a relation model, known as the cardinal direction calculus (CDC), for representing direction relations between connected plane regions. The CDC is perhaps the most expressive qualitative calculus for directional information, and has attracted increasing interest from areas such as artificial intelligence, geographical information science, and image retrieval. Given a network of CDC constraints, the consistency problem is deciding if the network is realizable by connected regions in the real plane. This paper provides a cubic algorithm for checking the consistency of complete networks of basic CDC constraints, and proves that reasoning with the CDC is in general an NP-complete problem. For a consistent complete network of basic CDC constraints, our algorithm returns a 'canonical' solution in cubic time. This cubic algorithm is also adapted to check the consistency of complete networks of basic cardinal constraints between possibly disconnected regions.
---
paper_title: Qualitative constraint calculi: Heterogeneous verification of composition tables

paper_content:

In the domain of qualitative constraint reasoning, a subfield of AI which has evolved in the past 25 years, a large number of calculi for efficient reasoning about spatial and temporal entities has been developed. Reasoning techniques developed for these constraint calculi typically rely on so-called composition tables of the calculus at hand, which allow for replacing semantic reasoning by symbolic operations. Often these composition tables are developed in a quite informal, pictorial manner—a method which seems to be error-prone. In view of possible safety critical applications of qualitative calculi, however, it is desirable to formally verify these composition tables. In general, the verification of composition tables is a tedious task, in particular in cases where the semantics of the calculus depends on higher-order constructs such as sets. In this paper we address this problem by presenting a heterogeneous proof method that allows for combining a higherorder proof assistance system (such as Isabelle) with an automatic (first order) reasoner (such as SPASS or VAMPIRE). The benefit of this method is that the number of proof obligations that is to be proven interactively with a semi-automatic reasoner can be minimized to an acceptable level.
---
paper_title: Connecting qualitative spatial and temporal representations by propositional closure

paper_content:

This paper establishes new relationships between existing qualitative spatial and temporal representations. Qualitative spatial and temporal representation (QSTR) is concerned with abstractions of infinite spatial and temporal domains, which represent configurations of objects using a finite vocabulary of relations, also called a qualitative calculus. Classically, reasoning in QSTR is based on constraints. An important task is to identify decision procedures that are able to handle constraints from a single calculus or from several calculi. In particular the latter aspect is a longstanding challenge due to the multitude of calculi proposed. In this paper we consider propositional closures of qualitative constraints which enable progress with respect to the longstanding challenge. Propositional closure allows one to establish several translations between distinct calculi. This enables joint reasoning and provides new insights into computational complexity of individual calculi. We conclude that the study of propositional languages instead of previously considered purely relational languages is a viable research direction for QSTR leading to expressive formalisms and practical algorithms.
---
paper_title: An Algebra of Qualitative Taxonomical Relations for Ontology Alignments

paper_content:

Algebras of relations were shown useful in managing ontology alignments. They make it possible to aggregate alignments disjunctively or conjunctively and to propagate alignments within a network of ontologies. The previously considered algebra of relations contains taxonomical relations between classes. However, compositional inference using this algebra is sound only if we assume that classes which occur in alignments have nonempty extensions. Moreover, this algebra covers relations only between classes. Here we introduce a new algebra of relations, which, first, solves the limitation of the previous one, and second, incorporates all qualitative taxonomical relations that occur between individuals and concepts, including the relations "is a" and "is not". We prove that this algebra is coherent with respect to the simple semantics of alignments.
---
paper_title: Reasoning about temporal relations: a maximal tractable subclass of Allen's interval algebra

paper_content:

We introduce a new subclass of Allen's interval algebra we call "ORD-Horn subclass," which is a strict superset of the "pointisable subclass." We prove that reasoning in the ORD-Horn subclass is a polynomial-time problem and show that the path-consistency method is sufficient for deciding satisfiability. Further, using an extensive machine-generated case analysis, we show that the ORD-Horn subclass is a maximal tractable subclass of the full algebra (assuming P≠NP). In fact, it is the unique greatest tractable subclass amongst the subclasses that contain all basic relations.
---
paper_title: What is a Qualitative Calculus ? A General Framework

paper_content:

What is a qualitative calculus? Many qualitative spatial and temporal calculi arise from a set of JEPD (jointly exhaustive and pairwise disjoint) relations: a stock example is Allen's calculus, which is based on thirteen basic relations between intervals on the time line. This paper examines the construction of such a formalism from a general point of view, in order to make apparent the formal algebraic properties of all formalisms of that type. We show that the natural algebraic object governing this kind of calculus is a non-associative algebra (in the sense of Maddux), and that the notion of weak representation is the right notion for describing most basic properties. We discuss the ubiquity of weak representations in various guises, and argue that the fundamental notion of consistency itself can best be understood in terms of consistency of one weak representation with respect to another.
---
paper_title: Relation Algebras and their Application in Temporal and Spatial Reasoning

paper_content:

Qualitative temporal and spatial reasoning is in many cases based on binary relations such as before, after, starts, contains, contact, part of, and others derived from these by relational operators. The calculus of relation algebras is an equational formalism; it tells us which relations must exist, given several basic operations, such as Boolean operations on relations, relational composition and converse. Each equation in the calculus corresponds to a theorem, and, for a situation where there are only finitely many relations, one can construct a composition table which can serve as a look up table for the relations involved. Since the calculus handles relations, no knowledge about the concrete geometrical objects is necessary. In this sense, relational calculus is "pointless". Relation algebras were introduced into temporal reasoning by Allen (1983, Communications of the ACM 26(1), 832--843) and into spatial reasoning by Egenhofer and Sharma (1992, Fifth International Symposium on Spatial Data Handling, Charleston, SC). The calculus of relation algebras is also well suited to handle binary constraints as demonstrated e.g. by Ladkin and Maddux (1994, Journal of the ACM 41(3), 435--469). In the present paper I will give an introduction to relation algebras, and an overview of their role in qualitative temporal and spatial reasoning.
---
paper_title: A new approach to cyclic ordering of 2D orientations using ternary relation algebras

paper_content:

Abstract In Tarski's formalisation, the universe of a relation algebra (RA) consists of a set of binary relations. A first contribution of this work is the introduction of RAs whose universe is a set of ternary relations: these support rotation as an operation in addition to those present in Tarski's formalisation. Then we propose two particular RAs: a binary RA, CYC b , whose universe is a set of (binary) relations on 2D orientations; and a ternary RA, CYC t , whose universe is a set of (ternary) relations on 2D orientations. The RA CYC t , more expressive than CYC b , constitutes a new approach to cyclic ordering of 2D orientations. An atom of CYC t expresses for triples of orientations whether each of the three orientations is equal to, to the left of, opposite to, or to the right of each of the other two orientations. CYC t has 24 atoms and the elements of its universe consist of all possible 2 24 subsets of the set of all atoms. Amongst other results, 1. we provide for CYC t a constraint propagation procedure computing the closure of a problem under the different operations, and show that the procedure is polynomial, and complete for a subset including all atoms; 2. we prove that another subset, expressing only information on parallel orientations, is NP-complete; 3. we show that provided that a subset S of CYC t includes two specific elements, deciding consistency for a problem expressed in the closure of S can be polynomially reduced to deciding consistency for a problem expressed in S ; and 4. we derive from the previous result that for both RAs we “jump” from tractability to intractability if we add the universal relation to the set of all atoms. A comparison to the most closely related work in the literature indicates that the approach is promising.
---
paper_title: The finest of its class: The natural point-based ternary calculus for qualitative spatial reasoning

paper_content:

In this paper, a ternary qualitative calculus ${\mathcal LR}$ for spatial reasoning is presented that distinguishes between left and right. A theory is outlined for ternary point-based calculi in which all the relations are invariant when all points are mapped by rotations, scalings, or translations (RST relations). For this purpose, we develop methods to determine arbitrary transformations and compositions of RST relations. We pose two criteria which we call practical and natural. ‘Practical' means that the relation system should be closed under transformations, compositions and intersections and have a finite base that is jointly exhaustive and pairwise disjoint. This implies that the well-known path consistency algorithm [10] can be used to conclude implicit knowledge. ‘Natural' calculi are close to our natural way of thinking because the base relations and their complements are connected. The main result of the paper is the identification of a maximally refined calculus amongst the practical natural RST calculi, which turns out to be very similar to Ligozat's flip-flop calculus. From that it follows, e.g., that there is no finite refinement of the TPCC calculus by Moratz et al that is closed under transformations, composition, and intersection.
---
paper_title: What is a Qualitative Calculus ? A General Framework

paper_content:

What is a qualitative calculus? Many qualitative spatial and temporal calculi arise from a set of JEPD (jointly exhaustive and pairwise disjoint) relations: a stock example is Allen's calculus, which is based on thirteen basic relations between intervals on the time line. This paper examines the construction of such a formalism from a general point of view, in order to make apparent the formal algebraic properties of all formalisms of that type. We show that the natural algebraic object governing this kind of calculus is a non-associative algebra (in the sense of Maddux), and that the notion of weak representation is the right notion for describing most basic properties. We discuss the ubiquity of weak representations in various guises, and argue that the fundamental notion of consistency itself can best be understood in terms of consistency of one weak representation with respect to another.
---
paper_title: Relation Algebras and their Application in Temporal and Spatial Reasoning

paper_content:

Qualitative temporal and spatial reasoning is in many cases based on binary relations such as before, after, starts, contains, contact, part of, and others derived from these by relational operators. The calculus of relation algebras is an equational formalism; it tells us which relations must exist, given several basic operations, such as Boolean operations on relations, relational composition and converse. Each equation in the calculus corresponds to a theorem, and, for a situation where there are only finitely many relations, one can construct a composition table which can serve as a look up table for the relations involved. Since the calculus handles relations, no knowledge about the concrete geometrical objects is necessary. In this sense, relational calculus is "pointless". Relation algebras were introduced into temporal reasoning by Allen (1983, Communications of the ACM 26(1), 832--843) and into spatial reasoning by Egenhofer and Sharma (1992, Fifth International Symposium on Spatial Data Handling, Charleston, SC). The calculus of relation algebras is also well suited to handle binary constraints as demonstrated e.g. by Ladkin and Maddux (1994, Journal of the ACM 41(3), 435--469). In the present paper I will give an introduction to relation algebras, and an overview of their role in qualitative temporal and spatial reasoning.
---
paper_title: What is a Qualitative Calculus ? A General Framework

paper_content:

What is a qualitative calculus? Many qualitative spatial and temporal calculi arise from a set of JEPD (jointly exhaustive and pairwise disjoint) relations: a stock example is Allen's calculus, which is based on thirteen basic relations between intervals on the time line. This paper examines the construction of such a formalism from a general point of view, in order to make apparent the formal algebraic properties of all formalisms of that type. We show that the natural algebraic object governing this kind of calculus is a non-associative algebra (in the sense of Maddux), and that the notion of weak representation is the right notion for describing most basic properties. We discuss the ubiquity of weak representations in various guises, and argue that the fundamental notion of consistency itself can best be understood in terms of consistency of one weak representation with respect to another.
---
paper_title: A Condensed Semantics for Qualitative Spatial Reasoning About Oriented Straight Line Segments

paper_content:

More than 15 years ago, a set of qualitative spatial relations between oriented straight line segments (dipoles) was suggested by Schlieder. However, it turned out to be difficult to establish a sound constraint calculus based on these relations. In this paper, we present the results of a new investigation into dipole constraint calculi which uses algebraic methods to derive sound results on the composition of relations of dipole calculi. This new method, which we call condensed semantics, is based on an abstract symbolic model of a specific fragment of our domain. It is based on the fact that qualitative dipole relations are invariant under orientation preserving affine transformations. The dipole calculi allow for a straightforward representation of prototypical reasoning tasks for spatial agents. As an example, we show how to generate survey knowledge from local observations in a street network. The example illustrates the fast constraint-based reasoning capabilities of dipole calculi. We integrate our results into two reasoning tools which are publicly available.
---
paper_title: On the consistency problem for the INDU calculus

paper_content:

In this paper, we further investigate the consistency problem for the qualitative temporal calculus INDU introduced by A. K. Pujari et al. (1999). We prove the intractability of the consistency problem for the subset of preconvex relations. On the other hand, we show the tractability of strongly preconvex relations. Furthermore, we also define another interesting set of relations for which the consistency problem can be decided by a method similar to the usual path-consistency method.
---
paper_title: Relations between spatial calculi about directions and orientations

paper_content:

Qualitative spatial descriptions characterize essential properties of spatial objects or configurations by relying on relative comparisons rather than measuring. Typically, in qualitative approaches only relatively coarse distinctions between configurations are made. Qualitative spatial knowledge can be used to represent incomplete and underdetermined knowledge in a systematic way. This is especially useful if the task is to describe features of classes of configurations rather than individual configurations. ::: ::: Although reasoning with them is generally NP-hard (even ∃IR-complete), relative directions are important because they play a key role in human spatial descriptions and there are several approaches how to represent them using qualitative methods. In these approaches directions between spatial locations can be expressed as constraints over infinite domains, e.g. the Euclidean plane. The theory of relation algebras has been successfully applied to this field. Viewing relation algebras as universal algebras and applying and modifying standard tools from universal algebra in this work, we (re)define notions of qualitative constraint calculus, of homomorphism between calculi, and of quotient of calculi. Based on this method we derive important properties for spatial calculi from corresponding properties of related calculi. From a conceptual point of view these formal mappings between calculi are a means to translate between different granularities.
---
paper_title: Consistency in Networks of Relations

paper_content:

Artificial intelligence tasks which can be formulated as constraint satisfaction problems, with which this paper is for the most part concerned, are usually by solved backtracking the examining the thrashing behavior that nearly always accompanies backtracking, identifying three of its causes and proposing remedies for them we are led to a class of algorithms whoch can profitably be used to eliminate local (node, arc and path) inconsistencies before any attempt is made to construct a complete solution. A more general paradigm for attacking these tasks is the altenation of constraint manipulation and case analysis producing an OR problem graph which may be searched in any of the usual ways. ::: ::: Many authors, particularly Montanari and Waltz, have contributed to the development of these ideas; a secondary aim of this paper is to trace that history. The primary aim is to provide an accessible, unified framework, within which to present the algorithms including a new path consistency algorithm, to discuss their relationships and the may applications, both realized and potential of network consistency algorithms.
---
paper_title: Qualitative spatial and temporal reasoning with AND/OR linear programming

paper_content:

This paper explores the use of generalized linear programming techniques to tackle two long-standing problems in qualitative spatio-temporal reasoning: Using LP as a unifying basis for reasoning, one can jointly reason about relations from different qualitative calculi. Also, concrete entities (fixed points, regions fixed in shape and/or position, etc.) can be mixed with free variables. Both features are important for applications but cannot be handled by existing techniques. In this paper we discuss properties of encoding constraint problems involving spatial and temporal relations. We advocate the use of AND/OR graphs to facilitate efficient reasoning and we show feasibility of our approach.
---
paper_title: Qualitative constraint satisfaction problems: An extended framework with landmarks

paper_content:

Dealing with spatial and temporal knowledge is an indispensable part of almost all aspects of human activity. The qualitative approach to spatial and temporal reasoning, known as Qualitative Spatial and Temporal Reasoning (QSTR), typically represents spatial/temporal knowledge in terms of qualitative relations (e.g., to the east of, after), and reasons with spatial/temporal knowledge by solving qualitative constraints. When formulating qualitative constraint satisfaction problems (CSPs), it is usually assumed that each variable could be ''here, there and everywhere''. Practical applications such as urban planning, however, often require a variable to take its value from a certain finite domain, i.e. it is required to be 'here or there, but not everywhere'. Entities in such a finite domain often act as reference objects and are called ''landmarks'' in this paper. The paper extends the classical framework of qualitative CSPs by allowing variables to take values from finite domains. The computational complexity of the consistency problem in this extended framework is examined for the five most important qualitative calculi, viz. Point Algebra, Interval Algebra, Cardinal Relation Algebra, RCC5, and RCC8. We show that all these consistency problems remain in NP and provide, under practical assumptions, efficient algorithms for solving basic constraints involving landmarks for all these calculi.
---
paper_title: Combining RCC-8 with Qualitative Direction Calculi : Algorithms and Complexity ∗

paper_content:

We investigate the problem of non-covariant behavior of policy gradient reinforcement learning algorithms. The policy gradient approach is amenable to analysis by information geometric methods. This leads us to propose a natural metric on controller parameterization that results from considering the manifold of probability distributions over paths induced by a stochastic controller. Investigation of this approach leads to a covariant gradient ascent rule. Interesting properties of this rule are discussed, including its relation with actor-critic style reinforcement learning algorithms. The algorithms discussed here are computationally quite efficient and on some interesting problems lead to dramatic performance improvement over noncovariant rules.
---
paper_title: Qualitative Spatio-Temporal Reasoning with RCC-8 and Allen's Interval Calculus: Computational Complexity

paper_content:

There exist a number of qualitative constraint calculi that are used to represent and reason about temporal or spatial configurations. However, there are only very few approaches aiming to create a spatio-temporal constraint calculus. Similar to Bennett et al., we start with the spatial calculus RCC-8 and Allen's interval calculus in order to construct a qualitative spatio-temporal calculus. As we will show, the basic calculus is NP-complete, even if we only permit base relations. When adding the restriction that the size of the spatial regions persists over time, or that changes are continuous, the calculus becomes more useful, but the satisfiability problem appears to be much harder. Nevertheless, we are able to show that satisfiability is still in NP.
---
paper_title: Qualitative Representation of Spatial Knowledge

paper_content:

Qualitativeness.- A cognitive perspective on knowledge representation.- Qualitative representation of positions in 2-D.- Reasoning with qualitative representations.- Applications.- Extensions of the basic model.- Relevant related work.- Conclusion.
---
paper_title: Multi-Dimensional Modal Logic as a Framework for Spatio-Temporal Reasoning

paper_content:

In this paper we advocate the use of multi-dimensional modal logics as a framework for knowledge representation and, in particular, for representing spatio-temporal information. We construct a two-dimensional logic capable of describing topological relationships that change over time. This logic, called PSTL (Propositional Spatio-Temporal Logic) is the Cartesian product of the well-known temporal logic PTL and the modal logic S4u, which is the Lewis system S4 augmented with the universal modality. Although it is an open problem whether the full PSTL is decidable, we show that it contains decidable fragments into which various temporal extensions (both point-based and interval based) of the spatial logic RCC-8 can be embedded. We consider known decidability and complexity results that are relevant to computation with multi-dimensional formalisms and discuss possible directions for further research.
---
paper_title: Viewing composition tables as axiomatic systems

paper_content:

Axiomatic systems and composition tables are often seen asalternative ways of specifying the semantic interrelations ofrelations for qualitative reasoning. Axiomatic characterizationsusually specify ontological assumptions concerning the domain ofthe relations and introduce a taxonomic system of relations that,on the one hand, serves to specify the relations and, on the otherhand, supports the communication of the intended meaning.In thisarticle, composition tables are seen as a specific form ofaxiomatic theories that can also be combined with a taxonomicsystem of relations. On this basis, the content of compositiontables can be reformulated in a simplified way. This simplificationsupports the construction of such tables parallel to thedevelopment of the axiomatic specification or on the basis of agiven axiomatic characterization.
---
paper_title: Spatial reasoning in RCC-8 with Boolean region terms

paper_content:

We extend the expressive power of the region connection calculus RCC-8 by allowing applications of the 8 binary relations of RCC-8 not only to atomic regions but also to Boolean combinations of them. It is shown that the statisfiability problem for the extended language in arbitrary topological spaces is still in NP; however, it becomes PSPACE-complete if only the Euclidean spaces ℝn, n > 0, are regarded as possible interpretations. In particular, in contrast to pure RCC-8, the new language is capable of distinguishing between connected and non-connected topological spaces.
---
paper_title: Multidimensional Mereotopology with Betweenness

paper_content:

Qualitative reasoning about commonsense space often involves entities of different dimensions. We present a weak axiomatization of multidimensional qualitative space based on 'relative dimension' and dimension-independent 'containment' which suffice to define basic dimension-dependent mereotopological relations. We show the relationships to other meoreotopologies and to incidence geometry. The extension with betweenness, a primitive of relative position, results in a first-order theory that qualitatively abstracts ordered incidence geometry.
---
paper_title: The Mathematical Morpho-Logical View on Reasoning about Space

paper_content:

Qualitative reasoning about mereotopological relations has been extensively investigated, while more recently geometrical and spatio-temporal reasoning are gaining increasing attention. We propose to consider mathematical morphology operators as the inspiration for a new language and inference mechanism to reason about space. Interestingly, the proposed morpho-logic captures not only traditional mereotopological relations, but also notions of relative size and morphology. The proposed representational framework is a hybrid arrow logic theory for which we define a resolution calculus which is, to the best of our knowledge, the first such calculus for arrow logics.
---
paper_title: An Axiomatic Approach to the Spatial Relations Underlying Left-Right and in Front of-Behind

paper_content:

This paper presents an axiomatic characterization of spatial orderings in the plane and of concepts underlying intrinsic and deictic uses of spatial terms such as in front of, behind, left and right. This characterization differs in several aspects from existing theories that either employ systems of coordinate axes or systems of regions to specify the meaning of such expressions. We argue that the relations given by in front of and behind can be modeled on the basis of linear orders and on the basis of axes, whereas the relations given by left and right can be modeled as planar and on the basis of regions. The explicit characterization of the means necessary to specify the intrinsic and deictic uses thereby sheds light on the structures contributed by different frames of reference and therefore contributes to understanding the deictic/intrinsic-distinction.
---
paper_title: Logical Representations for Automated Reasoning about Spatial Relationships

paper_content:

This thesis investigates logical representations for describing and reasoning about spatial situations. Previously proposed theories of spatial regions are investigated in some detail - especially the 1st-order theory of Randell, Cui and Cohn (1992). The difficulty of achieving effective automated reasoning with these systems is observed. ::: ::: A new approach is presented, based on encoding spatial relations in formulae of 0-order ('propositional') logics. It is proved that entailment, which is valid according to the standard semantics for these logics, is also valid with respect to the spatial interpretation. Consequently, well-known mechanisms for propositional reasoning can be applied to spatial reasoning. Specific encodings of topological relations into both the modal logic S4 and the intuitionistic propositional calculus are given. The complexity of reasoning using the intuitionistic representation is examined and a procedure is presented with is shown to be of O(n3) complexity in the number of relations involved. ::: ::: In order to make this kind of representation sufficiently expressive the concepts of model constraint and entailment constraint are introduced. By means of this distinction a 0-order formula may be used either to assert or to deny that a certain spatial constraint holds of some situation. It is shown how the proof theory of a 0-order logical language can be extended by a simple meta-level generalisation to accommodate a representation involving these two types of formula. ::: ::: A number of other topics are dealt with: a decision procedure based on quantifier elimination is given for a large class of formulae within a 1st-order topological language; reasoning mechanisms based on the composition of spatial relations are studied; the non-topological property of convexity is examined both from the point of view of its 1st-order characterisation and its incorporation into a 0-order spatial logic. It is suggested that 0-order representations could be employed in a similar manner to encode other spatial concepts.
---
paper_title: A Tableau Algorithm for Description Logics with Concrete Domains and General TBoxes

paper_content:

In order to use description logics (DLs) in an application, it is crucial to identify a DL that is sufficiently expressive to represent the relevant notions of the application domain, but for which reasoning is still decidable. Two means of expressivity required by many modern applications of DLs are concrete domains and general TBoxes. The former are used for defining concepts based on concrete qualities of their instances such as the weight, age, duration, and spatial extension. The purpose of the latter is to capture background knowledge by stating that the extension of a concept is included in the extension of another concept. Unfortunately, combining concrete domains with general TBoxes often leads to DLs for which reasoning is undecidable. In this paper, we identify a general property of concrete domains that is sufficient for proving decidability of DLs with both concrete domains and general TBoxes. We exhibit some useful concrete domains, most notably a spatial one based on the RCC-8 relations that have this property. Then, we present a tableau algorithm for reasoning in DLs equipped with concrete domains and general TBoxes.
---
paper_title: PelletSpatial: A Hybrid RCC-8 and RDF/OWL Reasoning and Query Engine

paper_content:

In this paper, we present PelletSpatial, a qualitative spatial reasoning engine implemented on top of Pellet. PelletSpatial provides consistency checking and query answering over spatial data represented with the Region Connection Calculus (RCC). It supports all RCC-8 relations as well as standard RDF/OWL semantic relations, both represented in RDF/OWL. As such, it can answer mixed SPARQL queries over both relation types. PelletSpatial implements two RCC reasoners: (a) A reasoner based on the semantics preserving translation of RCC relations to OWL-DL class axioms and (b) a reasoner based on the RCC composition table that implements a path-consistency algorithm. We discuss the details of two implementation approaches and focus on some of their respective advantages and disadvantages.
---
paper_title: Pellet : A practical OWL-DL reasoner

paper_content:

In this paper, we present a brief overview of Pellet: a complete OWL-DL reasoner with acceptable to very good performance, extensive middleware, and a number of unique features. Pellet is the first sound and complete OWL-DL reasoner with extensive support for reasoning with individuals (including nominal support and conjunctive query), user-defined datatypes, and debugging support for ontologies. It implements several extensions to OWL-DL including a combination formalism for OWL-DL ontologies, a non-monotonic operator, and preliminary support for OWL/Rule hybrid reasoning. Pellet is written in Java and is open source.
---
paper_title: The description logic handbook: theory, implementation, and applications

paper_content:

Description logics are embodied in several knowledge-based systems and are used to develop various real-life applications. Now in paperback, The Description Logic Handbook provides a thorough account of the subject, covering all aspects of research in this field, namely: theory, implementation, and applications. Its appeal will be broad, ranging from more theoretically oriented readers, to those with more practically oriented interests who need a sound and modern understanding of knowledge representation systems based on description logics. As well as general revision throughout the book, this new edition presents a new chapter on ontology languages for the semantic web, an area of great importance for the future development of the web. In sum, the book will serve as a unique resource for the subject, and can also be used for self-study or as a reference for knowledge representation and artificial intelligence courses.
---
paper_title: SOWL: a framework for handling spatio-temporal information in OWL 2.0

paper_content:

We propose SOWL, an ontology for representing and reasoning over spatio-temporal information in OWL. Building upon well established standards of the semantic web (OWL 2.0, SWRL) SOWL enables representation of static as well as of dynamic information based on the 4D-fluents (or, equivalently, on the N-ary) approach. Both RCC- 8 topological and cone-shaped directional relations are integrated in SOWL. Representing both qualitative temporal and spatial information (i.e., information whose temporal or spatial extents are unknown such as "left-of" for spatial and "before" for temporal relations) in addition to quantitative information (i.e., where temporal and spatial information is defined precisely) is a distinctive feature of SOWL. The SOWL reasoner is capable of inferring new relations and checking their consistency, while retaining soundness, completeness, and tractability over the supported sets of relations.
---
paper_title: Logic-based robot control in highly dynamic domains

paper_content:

In this paper, we present the robot programming and planning language Readylog, a Golog dialect, which was developed to support the decision making of robots acting in dynamic real-time domains, such as robotic soccer. The formal framework of Readylog, which is based on the situation calculus, features imperative control structures such as loops and procedures, allows for decision-theoretic planning, and accounts for a continuously changing world. We developed high-level controllers in Readylog for our soccer robots in RoboCup's Middle-size league, but also for service robots and for autonomous agents in interactive computer games. For a successful deployment of Readylog on a real robot it is also important to account for the control problem as a whole, integrating the low-level control of the robot (such as localization, navigation, and object recognition) with the logic-based high-level control. In doing so, our approach can be seen as a step towards bridging the gap between the fields of robotics and knowledge representation.
---
paper_title: Modelling Dynamic Spatial Systems in the Situation Calculus

paper_content:

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 ...
---
paper_title: On-Line Decision-Theoretic Golog for Unpredictable Domains

paper_content:

DTGolog was proposed by Boutilier et al. as an integration of decision-theoretic (DT) planning and the programming language Golog. Advantages include the ability to handle large state spaces and to limit the search space during planning with explicit programming. Soutchanski developed a version of DTGolog, where a program is executed on-line and DT planning can be applied to parts of a program only. One of the limitations is that DT planning generally cannot be applied to programs containing sensing actions. In order to deal with robotic scenarios in unpredictable domains, where certain kinds of sensing like measuring one’s own position are ubiquitous, we propose a strategy where sensing during deliberation is replaced by suitable models like computed trajectories so that DT planning remains applicable. In the paper we discuss the necessary changes to DTGolog entailed by this strategy and an application of our approach in the RoboCup domain.
---
paper_title: Reasoning with Qualitative Positional Information for Domestic Domains in the Situation Calculus

paper_content:

In this paper, we present a thorough integration of qualitative representations and reasoning for positional information for domestic service robotics domains into our high-level robot control. In domestic settings for service robots like in the RoboCup@Home competitions, complex tasks such as “get the cup from the kitchen and bring it to the living room” or “find me this and that object in the apartment” have to be accomplished. At these competitions the robots may only be instructed by natural language. As humans use qualitative concepts such as “near” or “far”, the robot needs to cope with them, too. For our domestic robot, we use the robot programming and plan language Readylog, our variant of Golog. In previous work we extended the action language Golog, which was developed for the high-level control of agents and robots, with fuzzy set-based qualitative concepts. We now extend our framework to positional fuzzy fluents with an associated positional context called frames. With that and our underlying reasoning mechanism we can transform qualitative positional information from one context to another to account for changes in context such as the point of view or the scale. We demonstrate how qualitative positional fluents based on a fuzzy set semantics can be deployed in domestic domains and showcase how reasoning with these qualitative notions can seamlessly be applied to a fetch-and-carry task in a RoboCup@Home scenario.
---
paper_title: Using Maptrees to Characterize Topological Change

paper_content:

This paper further develops the theory of maptrees, introduced in [13]. There exist well-known methods, based upon combinatorial maps, for topologically complete representations of embeddings of connected graphs in closed surfaces. Maptrees extend these methods to provide topologically complete representations of embeddings of possibly disconnected graphs. The focus of this paper is the use of maptrees to admit fine-grained representations of topological change. The ability of maptrees to represent complex spatial processes is demonstrated through case studies involving conceptual neighborhoods and cellular processes.
---
paper_title: Qualitative reasoning with directional relations

paper_content:

Qualitative spatial reasoning (QSR) pursues a symbolic approach to reasoning about a spatial domain. Qualitative calculi are defined to capture domain properties in relation operations, granting a relation algebraic approach to reasoning. QSR has two primary goals: providing a symbolic model for human common-sense level of reasoning and providing efficient means for reasoning. In this paper, we dismantle the hope for efficient reasoning about directional information in infinite spatial domains by showing that it is inherently hard to decide consistency of a set of constraints that represents positions in the plane by specifying directions from reference objects. We assume that these reference objects are not fixed but only constrained through directional relations themselves. Known QSR reasoning methods fail to handle this information.
---
paper_title: The Mathematical Morpho-Logical View on Reasoning about Space

paper_content:

Qualitative reasoning about mereotopological relations has been extensively investigated, while more recently geometrical and spatio-temporal reasoning are gaining increasing attention. We propose to consider mathematical morphology operators as the inspiration for a new language and inference mechanism to reason about space. Interestingly, the proposed morpho-logic captures not only traditional mereotopological relations, but also notions of relative size and morphology. The proposed representational framework is a hybrid arrow logic theory for which we define a resolution calculus which is, to the best of our knowledge, the first such calculus for arrow logics.
---
paper_title: RCC8 Is Polynomial on Networks of Bounded Treewidth

paper_content:

We construct an homogeneous (and ω-categorical) representation of the relation algebra RCC8, which is one of the fundamental formalisms for spatial reasoning. As a consequence we obtain that the network consistency problem for RCC8 can be solved in polynomial time for networks of bounded treewidth.
---
paper_title: A Unifying Approach to Temporal Constraint Reasoning

paper_content:

Abstract We present a formalism, Disjunctive Linear Relations (DLRs), for reasoning about temporal constraints. DLRs subsume most of the formalisms for temporal constraint reasoning proposed in the literature and is therefore computationally expensive. We also present a restricted type of DLRs, Horn DLRs, which have a polynomial-time satisfiability problem. We prove that most approaches to tractable temporal constraint reasoning can be encoded as Horn DLRs, including the ORD-Horn algebra by Nebel and Burckert and the simple temporal constraints by Dechter et al. Thus, DLRs is a suitable unifying formalism for reasoning about temporal constraints.
---
paper_title: Qualitative spatial and temporal reasoning with AND/OR linear programming

paper_content:

This paper explores the use of generalized linear programming techniques to tackle two long-standing problems in qualitative spatio-temporal reasoning: Using LP as a unifying basis for reasoning, one can jointly reason about relations from different qualitative calculi. Also, concrete entities (fixed points, regions fixed in shape and/or position, etc.) can be mixed with free variables. Both features are important for applications but cannot be handled by existing techniques. In this paper we discuss properties of encoding constraint problems involving spatial and temporal relations. We advocate the use of AND/OR graphs to facilitate efficient reasoning and we show feasibility of our approach.
---
paper_title: A much better polynomial time approximation of consistency in the LR calculus

paper_content:

In the area of qualitative spatial reasoning, the LR calculus (a refinement of Ligozat's flip-flop calculus) is a quite simple constraint calculus that forms the core of several orientation calculi like the Dipole calculi and the OPRA1 calculus by introducing the left-right-dichotomy. ::: ::: For many qualitative spatial calculi, algebraic closure is applied as the standard polynomial time “decision” procedure. For a long time it was believed that this can decide the consistency of scenarios of the LR calculus. However, in [8] it was shown that algebraic closure is a bad approximation of consistency for LR scenarios: scenarios in the base relations “Left” and “Right” are always algebraically closed, no matter if those scenarios are consistent or not. So algebraic closure is completely useless here. Furthermore, in [15] it was proved that the consistency problem for any calculus with relative orientation containing the relations “Left” and “Right” is NP-hard. ::: ::: In this paper we propose a new and better polynomial time approximation procedure for this NP-hard problem. It is based on the angles of triangles in the Euclidean plane. LR scenarios are translated to sets of linear inequalities over the real numbers. We evaluate the quality of this procedure by comparing it bot to the old approximation using algebraic closure and to the (exact but exponential time) Buchberger algorithm for Grobner bases (used as a decision method).
---
paper_title: StarVars — Effective Reasoning about Relative Directions ∗

paper_content:

Relative direction information is very commonly used. Observers typically describe their environment by specifying the relative directions in which they see other objects or other people from their point of view. Or they receive navigation instructions with respect to their point of view, for example, turn left at the next intersection. However, it is surprisingly hard to integrate relative direction information obtained from different observers, and to reconstruct a model of the environment or the locations of the observers based on this information. Despite intensive research, there is currently no algorithm that can effectively integrate this information: this problem is NP-hard, but not known to be in NP, even if we only use left and right relations. ::: ::: In this paper we present a novel qualitative representation, StarVars, that can solve these problems. It is an extension of the STAR calculus [Renz and Mitra, 2004]) by a VARiable interpretation of the orientation of observers. We show that reasoning in StarVars is in NP and present the first algorithm that allows us to effectively integrate relative direction information from different observers.
---
paper_title: Generating approximate region boundaries from heterogeneous spatial information: An evolutionary approach

paper_content:

Spatial information takes different forms in different applications, ranging from accurate coordinates in geographic information systems to the qualitative abstractions that are used in artificial intelligence and spatial cognition. As a result, existing spatial information processing techniques tend to be tailored towards one type of spatial information, and cannot readily be extended to cope with the heterogeneity of spatial information that often arises in practice. In applications such as geographic information retrieval, on the other hand, approximate boundaries of spatial regions need to be constructed, using whatever spatial information that can be obtained. Motivated by this observation, we propose a novel methodology for generating spatial scenarios that are compatible with available knowledge. By suitably discretizing space, this task is translated to a combinatorial optimization problem, which is solved using a hybridization of two well-known meta-heuristics: genetic algorithms and ant colony optimization. What results is a flexible method that can cope with both quantitative and qualitative information, and can easily be adapted to the specific needs of specific applications. Experiments with geographic data demonstrate the potential of the approach.
---
paper_title: – Mastering Left and Right – Different Approaches to a Problem That Is Not Straight Forward

paper_content:

Reasoning over spatial descriptions involving relations that can be described as left, right and inline has been studied extensively during the last two decades. While the fundamental nature of these relations makes reasoning about them applicable to a number of interesting problems, it also makes reasoning about them computationally hard. The key question of whether a given description using these relations can be realized is as hard as deciding satisfiability in the existential theory of the reals. In this paper we summarize the semi-decision procedures proposed so far and present the results of a random benchmark illustrating the relative effectiveness and efficiency of these procedures.
---
paper_title: Here, there, but not everywhere: an extended framework for qualitative constraint satisfaction

paper_content:

Dealing with spatial and temporal knowledge is an indispensable part of almost all aspects of human activities. The qualitative approach to spatial and temporal reasoning (QSTR) provides a promising framework for spatial and temporal knowledge representation and reasoning. QSTR typically represents spatial/temporal knowledge in terms of qualitative relations (e.g., to the east of, after), and reasons with the knowledge by solving qualitative constraints. When formulating a qualitative constraint satisfaction problem (CSP), it is usually assumed that each variable could be "here, there and everywhere2." Practical applications e.g. urban planning, however, often require a variable taking values from a certain finite subset of the universe, i.e. require it to be 'here or there'. This paper extends the classic framework of qualitative constraint satisfaction by allowing variables taking values from finite domains. The computational complexity of this extended consistency problem is examined for five most important qualitative calculi, viz. Point Algebra, Interval Algebra, Cardinal Relation Algebra, RCC-5, and RCC-8. We show that the extended consistency problem remains in NP, but when only basic constraints are considered, the extended consistency problem for each calculus except Point Algebra is already NP-hard.
---
paper_title: CLP(QS): a declarative spatial reasoning framework

paper_content:

We propose CLP(QS), a declarative spatial reasoning framework capable of representing and reasoning about high-level, qualitative spatial knowledge about the world. We systematically formalize and implement the semantics of a range of qualitative spatial calculi using a system of non-linear polynomial equations in the context of a classical constraint logic programming framework. Whereas CLP(QS) is a general framework, we demonstrate its applicability for the domain of Computer Aided Architecture Design. With CLP(QS) serving as a prototype, we position declarative spatial reasoning as a general paradigm open to other formalizations, reinterpretations, and extensions. We argue that the accessibility of qualitative spatial representation and reasoning mechanisms via the medium of high-level, logic-based formalizations is crucial for their utility toward solving real-world problems.
---

Title: A Survey of Qualitative Spatial and Temporal Calculi: Algebraic and Computational Properties

Section 1: INTRODUCTION
Description 1: Write about the importance of spatial and temporal knowledge across various knowledge-based systems, the focus on qualitative representations, and provide an overview of what the paper covers.

Section 2: Demarcation of Scope and Contribution
Description 2: Highlight the target audience, the scope of the survey, and the specific focus areas of qualitative calculi and their properties.

Section 3: WHAT IS QUALITATIVE SPATIAL AND TEMPORAL REASONING
Description 3: Explain the reasoning problems that QSTR deals with and provide a characterization of QSTR.

Section 4: A General Definition of QSTR
Description 4: Present a formal definition of QSTR, including the use of relational languages to represent and manipulate spatial and temporal knowledge.

Section 5: Taxonomy of Constraint-Based Reasoning Tasks
Description 5: Provide an overview of different reasoning tasks associated with QSTR, categorizing them using a taxonomy.

Section 6: QUALITATIVE SPATIAL AND TEMPORAL CALCULI FOR DOMAIN REPRESENTATIONS
Description 6: Survey the fundamental construct of qualitative calculi, discussing their minimal requirements and relevance for spatial and temporal representation.

Section 7: Requirements to Qualitative Spatial and Temporal Calculi
Description 7: Define the minimal requirements for qualitative calculi, including notions like partition schemes, identity, and converse.

Section 8: Spatial and Temporal Reasoning
Description 8: Discuss the role of qualitative constraint satisfaction problems (QCSPs) in spatial and temporal reasoning and introduce k-consistency.

Section 9: Tools to Facilitate Qualitative Reasoning
Description 9: List various tools and systems that support qualitative reasoning, including their specific functionalities.

Section 10: Existing Qualitative Spatial and Temporal Calculi
Description 10: Provide an overview of the existing qualitative calculi, referencing important tables and figures that help categorize them.

Section 11: ALGEBRAIC PROPERTIES OF SPATIAL AND TEMPORAL CALCULI
Description 11: Explain the algebraic properties of qualitative calculi, their importance, and how they relate to reasoning optimizations.

Section 12: The Notion of a Relation Algebra
Description 12: Define relation algebras and discuss their axioms relevant to the operations involved in qualitative calculi.

Section 13: Discussion of the Axioms
Description 13: Elaborate on the relevance and implications of the axioms for spatial and temporal representation and reasoning.

Section 14: Prerequisites for Being a Relation Algebra
Description 14: Discuss the necessary properties for a qualitative calculus to function as a relation algebra.

Section 15: Algebraic Properties of Existing Spatial and Temporal Calculi
Description 15: Analyze the algebraic properties of various existing spatial and temporal calculi and present results in a hierarchical structure.

Section 16: Universal Procedure for Algebraic Closure
Description 16: Introduce a universal algorithm for computing algebraic closure that is applicable across all calculi and respects all necessary axioms.

Section 17: COMBINATION AND INTEGRATION
Description 17: Review ways qualitative calculi can be combined with other knowledge representation languages and formalisms for enhanced expressivity.

Section 18: Qualitative Calculi in Constraint-Based Knowledge Representation Languages
Description 18: Discuss the use of qualitative calculi in constraint-based knowledge representation languages and their combinations for modeling complex knowledge.

Section 19: Qualitative Relations and Classical Logics: Spatial Logics
Description 19: Describe how qualitative relations can be combined with classical logics, especially spatial logics, for enriched representation and reasoning.

Section 20: Qualitative Calculi and Description Logics
Description 20: Explain how qualitative calculi can be integrated with description logics to describe spatial and temporal qualities in domains.

Section 21: Qualitative Calculi and Situation Calculus
Description 21: Address the integration of qualitative calculi with the situation calculus, highlighting their relevance for reasoning about actions and changes.

Section 22: ALTERNATIVE APPROACHES
Description 22: Provide an overview of alternative reasoning techniques for spatial and temporal reasoning that are not based solely on qualitative calculi.

Section 23: Algebraic Topology
Description 23: Discuss connections between algebraic topology and qualitative spatial reasoning, including topological invariants.

Section 24: Combinatorial Geometry
Description 24: Mention the importance of combinatorial structures like oriented matroid theory and their contributions to QSTR.

Section 25: Graph Theoretical Approaches
Description 25: Highlight the use of graph-theoretical methods to represent and reason about spatial changes based on qualitative relations.

Section 26: Logic Frameworks
Description 26: Explain the use of logic frameworks such as arrow logic to capture mereotopological relations and their automated reasoning potential.

Section 27: Model-Theoretic and Constraint Reasoning Methods
Description 27: Outline how qualitative CSPs can be reformulated as general CSPs and solved using model-theoretic methods and SAT solving.

Section 28: Quantitative Methods
Description 28: Describe how linear programming and quantitative methods can be utilized to decide constraint problems in spatial and temporal reasoning.

Section 29: CONCLUSION AND FUTURE RESEARCH DIRECTIONS
Description 29: Summarize the survey's findings and discuss potential future research directions in the field of qualitative spatial and temporal reasoning.

Section 30: Beneficiaries of This Survey
Description 30: Identify the primary beneficiaries of this survey and describe how different groups can utilize the information presented.

Section 31: Open Problem Areas in QSTR
Description 31: Highlight open problems and challenges in QSTR, suggesting areas that require further research and development.

Section 32: ELECTRONIC APPENDIX
Description 32: Provide information about the additional materials available in the electronic appendix, including examples, proofs, and experimental results.