Qualitative Spatial and Temporal Reasoning E-Book

Gérard Ligozat

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 950

Veröffentlichungsjahr: 2013

Beschreibung

Starting with an updated description of Allen's calculus, the book proceeds with a description of the main qualitative calculi which have been developed over the last two decades.  It describes the connection of complexity issues to geometric properties. Models of the formalisms are described using the algebraic notion of weak representations of the associated algebras. The book also includes a presentation of fuzzy extensions of qualitative calculi, and a description of the study of complexity in terms of clones of operations.

Leseprobe

Table of Contents

Introduction. Qualitative Reasoning

Chapter 1. Allen's Calculus

1.1. Introduction

1.2. Allen's interval relations

1.3. Constraint networks

1.4. Constraint propagation

1.5. Consistency tests

Chapter 2. Polynomial Subclasses of Allen's Algebra

2.1. "Show me a tractable relation!"

2.2. Subclasses of Allen's algebra

2.3. Maximal tractable subclasses of Allen's algebra

2.4. Using polynomial subclasses

2.5. Models of Allen's language

2.6. Historical note

Chapter 3. Generalized Intervals

3.1. "When they built the bridge . . . "

3.2. Entities and relations

3.3. The lattice of basic (p, q)-relations

3.4. Regions associated with basic (p, q)-relations

3.5. Inversion and composition

3.6. Subclasses of relations: convex and pre-convex relations

3.7. Constraint networks

3.8. Tractability of strongly pre-convex relations

3.9. Conclusions

3.10. Historical note

Chapter 4. Binary Qualitative Formalisms

4.1. “Night driving"

4.2. Directed points in dimension 1

4.3. Directed intervals

4.4. The OPRA direction calculi

4.5. Dipole calculi

4.6. The Cardinal direction calculus

4.7. The Rectangle calculus

4.8. The n-point calculus

4.9. The n-block calculus

4.10. Cardinal directions between regions

4.11. The INDU calculus

4.12. The 2n-star calculi

4.13. The Cyclic interval calculus

4.14. The RCC-8 formalism

4.15. A discrete RCC theory

Chapter 5. Qualitative Formalisms of Arity Greater than 2

5.1. "The sushi bar"

5.2. Ternary spatial and temporal formalisms

5.3. Alignment relations between regions

5.4. Conclusions

Chapter 6. Quantitative Formalisms, Hybrids, and Granularity

6.1. "Did John meet Fred this morning?"

6.2. TCSP metric networks

6.3. Hybrid networks

6.4. Meiri's formalism

6.5. Disjunctive linear relations (DLR)

6.6. Generalized temporal networks

6.7. Networks with granularity

Chapter 7. Fuzzy Reasoning

7.1. "Picasso's Blue period"

7.2. Fuzzy relations between classical intervals

7.3. Events and fuzzy intervals

7.4. Fuzzy spatial reasoning: a fuzzy RCC

7.5. Historical note

Chapter 8. The Geometrical Approach and Conceptual Spaces

8.1. "What color is the chameleon?"

8.2. Qualitative semantics

8.3. Why introduce topology and geometry?

8.4. Conceptual spaces

8.5. Polynomial relations of INDU

8.6. Historical note

Chapter 9. Weak Representations

9.1. "Find the hidden similarity"

9.2. Weak representations

9.3. Classifying the weak representations of An

9.4. Extension to the calculi based on linear orders

9.5. Weak representations and configurations

9.6. Historical note

Chapter 10. Models of RCC–8

10.1. "Disks in the plane"

10.2. Models of a composition table

10.3. The RCC theory and its models

10.4. Extensional entries of the composition table

10.5. The generalized RCC theory

10.6. A countable connection algebra

10.7. Conclusions

Chapter 11. A Categorical Approach of Qualitative Reasoning

11.1. "Waiting in line”

11.2. A general construction of qualitative formalisms

11.3. Examples of partition schemes

11.4. Algebras associated with qualitative formalisms

11.5. Partition schemes and weak representations

11.6. A general definition of qualitative formalisms

11.7. Interpretating consistency

11.8. The category of weak representations

11.9. Conclusions

Chapter 12. Complexity of Constraint Languages

12.1. "Sudoku puzzles"

12.2. Structure of the chapter

12.3. Constraint languages

12.4. An algebraic approach of complexity

12.5. CSPs and morphisms of relational structures

12.6. Clones of operations

12.7. From local consistency to global consistency

12.8. The infinite case

12.9. Disjunctive constraints and refinements

12.10. Refinements and independence

12.11. Historical note

Chapter 13. Spatial Reasoning and Modal Logic

13.1. "The blind men and the elephant"

13.2. Space and modal logics

13.3. The modal logic S4

13.4. Topological models

13.5. Translating the RCC–8 predicates

13.6. An alternative modal translation of RCC–8

13.7. Generalized frames

13.8. Complexity

13.9. Complements

Chapter 14. Applications and Software Tools

14.1. Applications

14.2. Software tools

Chapter 15. Conclusion and Prospects

15.1. Introduction

15.2. Combining qualitative formalisms

15.3. Spatio-temporal reasoning

15.4. Alternatives to qualitative reasoning

15.5. To conclude — for good

Appendix A. Elements of Topology

A.l. Topological spaces

A.2. Metric spaces

A.3. Connectedness and convexity

Appendix B. Elements of Universal Algebra

B.l. Abstract algebras

B.2. Boolean algebras

B.3. Binary relations and relation algebras

B.4. Basic elements of the language of categories

Appendix C. Disjunctive Linear Relations

C.l. DLRs: definitions and satisfiability

C.2. Linear programming

C.3. Complexity of the satisfiability problem

Bibliography

Index

First published 2012 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd

John Wiley & Sons, Inc.

27-37 St George's Road

111 River Street

London SW19 4EU

Hoboken, NJ 07030

UK

USA

www.iste.co.uk

www.wiley.com

© ISTE Ltd 2012

The rights of Gérard Ligozat to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

Ligozat, Gérard.

 Qualitative spatial and temporal reasoning / Gérard Ligozat.

   p. cm.

Includes bibliographical references and index.

ISBN 978-1-84821-252-7

1. Qualitative reasoning. 2. Spatial analysis (Statistics) 3. Space and time--Mathematical models. 4. Logic, Symbolic and mathematical. I. Title.

   Q339.25.L54 2011

   511.3--dc23

2011029658

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN 978-1-84821-252-7

Introduction

Qualitative Reasoning

Why do we need qualitative reasoning formalisms? Let us consider an example of [LIG 05a], which represents a “spatial” version of what we will call the Point calculus in this book. This example describes a boat race (Figure 1) that is conducted on a river, which we represent as a directed axis giving the direction of the race.

Figure 1. A boat race

An observer positioned on the river bank transmits a telephonic message to his correspondent to inform him about the state of the competition. His initial message would be:

1) A is behind B;

2) C is in front of B;

3) D is behind B;

4) E is at the same level as D.

Let us assume then that a second informant gives the following indication:

5) C is behind E.

The manner in which the observers formulate their messages shows that they have implicitly adopted a “qualitative” view point: they do not try to give indications of distance, but only information that is related to the order of the competitors. A listener who would like to make a graphical representation of the situation could perfectly content himself with representing the river as a directed line, and the boats by points located on it. Using such an abstraction, the message would need only three relations: in front of, behind, and at the same level. The selected level of description makes it clear that there are only three possible relations between two boats (one precedes or follows the other, or they are at the same level), and that these relations are exclusive of each other. We are in the presence of three qualitative relations which constitute what is known as a JEPD set of relations, jointly exhaustive (whose reunion is exhaustive) and pairwise disjoint (pairwise exclusive).

In the context of qualitative reasoning, these three relations are called basic relations.

Let us notice that the relation at the same level, in terms of points on the line, is the equality relation. In the same manner, in front of and behind correspond to the relations greater than and smaller than between points. The two relations in front of and behind are what one calls inverse relations of each other: for each pair (x, y) of elements, x is in front of y if, and only if, y is behind x. Obviously, the relation at the same level is its own inverse.

Using the concept of inverse, the listener has a possibility of reasoning on the information he gets from the informant, where “reasoning” means deriving new pieces of information. For instance, knowing that “C is in front of B” (a piece of information he has been given), he can derive by inversion that “B is behind C” (which is a new piece of information). More interestingly, the listener can use another operation to derive new information: he can compose relations. For instance, from the fact that A is behind B and B is behind C, the listener can deduce that A is behind C. By doing so, the listener implicitly uses the fact that the relation behind is a transitive relation, i.e. that, for each 3-tuple (x, y, z) of elements, x behind y and y behind z imply that x is behind z. This (composing the relation behind with itself) is a typical case of composition of two relations. For this operation, it is clear that the relation at the same level is what is called a neutral element.

The fact is that D is behind B is equivalent to B being in front of D. What can we say about the position of D from the fact that A is behind B and that B is in front of D? Nothing at all, i.e. we can have A behind D, or A at the same level as D, or A in front of D. We can express this fact by saying that the composition of behind and in front of is the relation known as the universal relation, which is the union of the three basic relations.

This last example of composition of relations shows that the composition operation leads us to consider, in addition to the three basic relations, subsets of the set of basic relations. Such subsets will be called disjunctive relations, or, in short, relations.

In our case, it is natural to represent the three relations behind, in front of, and at at the same level by the symbols <, >, and eq respectively. On doing this, we notice that most of the subsets of the set {<, eq, >}, interpreted as disjunctions, have usual “names”: for example, {<, eq} corresponds to the relation denoted by ≤, and {<, >} to the relation denoted by ≠.

At this stage we could rewrite the information about the race provided by the first observer in the following way:

l) A < B;

2) C > B;

3) D < B;

4) E eq D.

The information given by the second informant would then be written as:

5) C < E.

But we will use a different kind of representation, namely a representation in terms of constraint networks. This is a key move which will allow us to establish a connection to the domain of constraint-based reasoning.

The data consisting of the five objects and of the relations between them can be represented by a directed graph having five vertices A,… ,E, and whose arcs are labeled according to the relations provided by the informants. In our case, the content of the message from the first informant is represented by the graph (a) of Figure 2, and that from the two informants brought together by graph (b); these graphs are called the associated constraint networks.

When no indication is provided on the relation between two vertices, the arc in question will not be drawn, but it is clear that one could equivalently use the universal relation as a label. In a similar manner, it is equivalent to label an arc by a relation, or to label the opposite arc by the inverse relation. It is generally assumed that either one of the two arcs has been selected, and that the inverse relation on the opposite arc is implicitly assumed.

Figure 2. Representation in the form of constraint networks of the messages of the two informants: (a) conditions 1) to 4); (b) conditions 1) to 5)

This representation has the advantage of considering the basic operations in terms of path-following on the graph. The inversion operation corresponds to replacing one arc by the opposite arc, and that of composition to combining two successive arcs, first from x to y, and then from y to z, to get a path from x to z.

Let us consider the recipient of the telephone messages. Can he graphically represent the five boats as points on the directed line, based on the information received from the two informants? In order to do so, it is necessary that the provided information be consistent, i.e. represents a possible configuration. However, this is not the case. In fact, from C > B, we can deduce that B < C (by inversion on the arc (B, C)), then by composition of D < B (going from D to B) and B < C (going from from B to C) we deduce that D < C, which cannot be the case, since in addition C < E and D eq E imply that C < D. The information provided by the two informants taken together is thus contradictory, and the network considered is an inconsistent network. That would not have been the case if the message from the second informant (C precedes E) had not been taken into account. The corresponding network would then be that of Figure 2 (b). Perhaps the second informant wanted to say that, actually, it is E which precedes C. In that case, the information would be correct, but redundant: owing to the fact that E eq D, E < C is implied by the constraints 1) to 4). A network is called consistent if there is a configuration compatible with its constraints.

Let us consider what happens if we do not take into account the information provided by the second informant, i.e. leave out constraint 5). The corresponding network is the network (b) of Figure 2, obtained from (a) by removing the constraint < from the arc (C, E) (which amounts to replacing it by the universal constraint). Now this network is consistent. Figure 3 then represents the three possible qualitative configurations.

Figure 3. The three configurations of points satisfying the constraints 1) to 4) of Figure 2 (a)

A fundamental problem in the domain of qualitative reasoning will be to determine whether a given constraint network is consistent. If this is the case, we may, like the recipient of the messages in our example, be interested in describing a configuration, or all possible configurations.

A configuration, conversely, can be represented by a constraint network which has the peculiarity that each one of its arcs is labeled by a basic relation. Such a network is called a scenario or an atomic network. A general question will be to determine whether a given scenario is a consistent network. For example, three consistent scenarios correspond to the three configuration of Figure 3. Rather than representing them in graphic form, we can use a tabular representation as in Table 1.

Table 1. A tabular representation of the first scenario

The example of the boat race had enabled us to introduce some of the basic notions used in qualitative reasoning: one considers constraint networks, whose vertices correspond to spatial or temporal entities (here, points of a directed line), and whose arcs are labeled by relations (unions of basic relations). In particular, a scenario is a network where all the labels are basic relations. The central problem is to determine whether a given network (and in particular a scenario), is consistent, i.e. if it corresponds to a configuration of the entities in question.

We have chosen in this presentation to consider the points of the line as spatial entities (abstractions of the position of a boat). However, the formalism whose definition we have outlined is interpreted in general in a temporal manner: the entities in question are time points on the time axis, the relation A < B is read “time point A precedes time point B”, and the relation eq is the concomitance relation. For this reason, we will, from now onwards, refer to this formalism as to the Point calculus.

The Point calculus thus provides a language which allows us to express qualitative constraints on configurations of points. The constraint propagation operations allow a simple type of inference.

We will see that the problem of determining whether a given network is consistent can be solved by simple algorithms whose time-cost is polynomial with regard to the size of the network.

More generally, in this book, we will be interested in qualitative reasoning on various types of temporal or spatial entities. In our example, these entities could be considered as points of a directed axis. In the temporal case, they can be time points, time intervals, or more complex entities. In the spatial case, the nature of the entities considered can vary widely: points of the plane, regions of the plane, but also points, pairs of points, or regions of a Euclidean space, or even abstract entities such as subspaces of a topological space.

The temporal or spatial entities are elements of a certain universe U, and one is interested in finite sets of relations of a fixed arity r between the entities (arity 2 for binary relations, arity 3 for ternary relations). In the example of the boat race, U can be represented by the real line . The relations considered are three binary relations, hence, from the mathematical point of view, three subsets of :

– the relation denoted by <, i.e. ;

– its inverse, the relation denoted by >, i.e. ;

– the equality relation denoted by eq, i.e. .

This set B of relations, known as the set of basic relations, constitutes a finite partition of all r-ary relations on U (this is the property known as the JEPD property), i.e. these relations are non-empty and any r-tuple of elements of U belongs to one and only one of these basic relations. The reasoning machinery uses the set A of all subsets of B, whose elements are called (disjunctive) relations, as constraints. It makes use of the inversion and composition operations, which are defined on B, and by extension on A, for propagating the constraints.

Structure of the book

Chapter 1 deals with Allen's calculus [ALL 83], which corresponds to a choice of entities more complex than punctual entities: in the temporal domain, they are (closed and bounded) intervals in the real line; such intervals are characterized by their starting and ending points.

The relations considered are the 13 possible qualitative relations between two intervals, i.e. they correspond to all possible orderings of two pairs of distinct points in a linear order.

These relations, known as basic relations, constitute a JEPD (Jointly Exhaustive and Pairwise Disjoint) set of relations. Their algebraic structure is similar to the one we have described for points; in particular, there exists inversion and composition operations on the set B2 of basic relations. The composition of two basic relations takes its values in the set A2 of subsets of B2, which is called the set of Allen's interval relations. The operations of inversion and composition extend to A2 and provide it with an algebraic structure which makes it a relation algebra. Equipped with this structure, A2 is known as Allen's Interval algebra (or IA).

In this chapter we examine the definition and the basic properties of constraint networks on Allen's Interval algebra. Any finite configuration of intervals can be described by such a network (whose labels are then basic relations). The fundamental problem, known as the consistency problem, is to determine, conversely, whether there are configurations of intervals described by a given constraint network. A necessary condition for consistency is that the network should be algebraically closed, a condition which can be checked in polynomial time. However, the general problem is NP-complete, and the existing algorithms have to use backtracking techniques.

Chapter 2 is devoted to the study of polynomial subclasses of Allen's Interval algebra. In fact, in view of the NP-completeness of the general consistency problem, an important part of the research in this domain has been devoted to the determination of subsets of relations known as tractable subsets, i.e. for which the consistency problem can be solved in polynomial time, relative to the size of the network. In this case, the question also arises for determining whether the algebraic closure condition provides a sufficient criterion for consistency.

The techniques used for the determination of tractable classes are related to two types of approach: techniques of a geometrical type and techniques of a syntactic nature. In this chapter, we focus on the first, which exploit the possibility of associating two particular structures to the set of basic relations: a partial order structure, which makes it a distributive lattice, and a geometrical structure which reflects the fact that relations can be regarded as regions of the plane.

Using these two representations, we describe three particular subclasses of relations: convex, pointizable and pre-convex relations. The geometrical techniques enable us to show that the criterion of algebraic closure can be used for pre-convex relations, and that these relations constitute the only maximal tractable subset containing all basic relations.

We also show that the class of pre-convex relations of Allen's algebra coincides with the class of ORD-Horn relations, a class originally characterized by syntactic methods. We end this chapter with a description of all the tractable subclasses of Allen's algebra.

Chapter 3 describes the framework of generalized intervals, which contains and generalizes a wide class of calculi including the Point calculus, Allen's calculus, as well as Vilain's Point-and-interval calculus [VIL 82].

The encoding used for the relations highlights the lattice structure from which they inherit in a natural manner. This lattice plays a significant role in the study of subclasses of relations. In the same way, the interpretation of the relations in terms of regions of a Euclidean space highlights their geometrical and topological properties (concepts of dimension, closure).

Representing relations in terms of lattices and regions of a Euclidean space makes it possible to develop a geometrical approach to the study of complexity based on defining convex, pointizable, and pre-convex relations, and leads to a general result of polynomial complexity for the strongly pre-convex relations. We show that these strongly pre-convex relations are precisely the relations characterized in a syntactic way as ORD-Horn relations, which shows that for generalized intervals the geometrical and syntactic approaches result in two alternative characterizations of the same polynomial subclass.

Chapter 4 continues with the investigation of new binary qualitative formalisms by presenting some of the many works devoted to temporal or spatial qualitative formalisms, which have appeared during the last two decades. Some of these formalisms can be considered as variations on Allen's calculus (for example, the Directed interval calculus, which can also be interpreted in a spatial way, as we have done earlier for the Point calculus). A special role in this category is played by the INDU formalism, which is a refinement of Allen's calculus by the introduction of a concept of relative duration, but whose study shows profound differences with Allen's formalism.

The variation can also relate to the nature of the ambient space: for example, the latter can be circular, which makes it possible to develop a formalism called the Cyclic interval calculus.

With regard to those calculi that clearly relate to spatial entities, we will mainly deal with two families: the first is that of “product” formalisms, which use the fact that the n-dimensional Euclidean space is the product of n ID spaces. This projection-based approach, introduced by Güesgen [GÜS 89], has spawned many variants besides the prototypical “Rectangle calculus", such as the n-point calculi and the n-block calculi.

The 2-point calculus coincides with the standard Cardinal relation calculus, which is concerned with relations between points in the Euclidean plane. Its extension to relations between regions has given rise to a Calculus of cardinal relations between regions which, in addition to the fact that its expressiveness is higher than that of the Rectangle calculus, presents interesting properties. We describe recent results concerning the consistency problem for constraints networks in this formalism.

A second important family of formalisms is concerned with the study of binary topological relations between regions. They are spatial formalisms developed in the context of mereotopological theories. The theory known as RCC (region connection calculus) enables us to define a qualitative calculus called RCC-8 whose composition table coincides with that of the formalism developed by Egenhofer under the name of “9-intersection calculus”. We present the basic elements of this formalism here. We end this chapter by describing a proposal, due to Galton [GAL 99], for a discrete analog of this calculus.

Chapter 5 is dedicated to the study of qualitative formalisms of arity higher than 2: the relations considered are not binary any more, but of arity higher than 1. Indeed, if the formalisms considered up to now concerned relations between pairs of entities, it appears that the restriction to binary relations is no longer justified in many cases: for example, on a circle, the relation “the points x, y, z are met in this order when one traverses the circle in the counterclockwise direction” is the most natural relation of orientation for points on the circle; it is a ternary relation. Similarly, in space, important concepts such as “x is between y and z” correspond to ternary relations. As a last example, consider spatial entities in the plane: if a global frame of reference is not available, describing the orientation of x with respect to y requires the introduction of a third object z as a reference. We describe some well-known qualitative formalisms using ternary relations: Freksa's Double-cross calculus [FRE 92b], and calculi based on the alignment relation between regions, including the so-called 5-intersection calculus.

Chapter 6 presents what we call hybrid formalisms, for which one leaves the strictly qualitative framework to approach aspects of metric type. Indeed, a presentation limited to describing only purely qualitative formalisms would conceal the fact that, right from the early works of the 1980s, an interest in the study of formalisms integrating qualitative knowledge and metric knowledge had emerged. Such an integration is required in many applications, in particular those related to natural language processing. Typical cases in this direction include the works of Kautz and Ladkin [KAU 91] and those of Meiri [MEI 91, MEI 96] at the beginning of the 1990s, which have defined formalisms for reasoning about knowledge that is at the same time qualitative (like, for example, what can be deduced from the assertion “The stay of x precedes that of y”) and metric (as in the assertion “The departure of x precedes that of y by 30 to 35 minutes”). This chapter is dedicated to a presentation of some of the main hybrid formalisms in the literature.

Chapter 7 approaches the domain of fuzzy qualitative reasoning. In fact, the qualitative formalisms that we have considered up to now make it possible to describe incomplete knowledge (for example, “interval x and interval y are disjoint”, therefore one precedes the other, without knowing which one comes first), but they are not adequate to take into account knowledge where this ignorance is weighted (as in the assertion “There is a 90% chance that x precedes y”). Another type of difficulty arises when the entities considered are defined in a fuzzy manner, whether it is in the temporal domain or in the spatial domain: when does the period of the Renaissance start and end? What about Picasso's “Blue period”? Where do the suburbs of a big city end?

A possible approach to treat these questions is provided by fuzzy logic. We have chosen to describe three types of approaches: the use of fuzzy interval relations, Allen's calculus between fuzzy intervals, and an extension of the RCC-8 calculus to relations between fuzzy regions.

A - somewhat sweeping - but striking and encouraging conclusion of the results in this direction is that several complexity results in the “classical” case can be carried over to the fuzzy context.

Chapter 8 revisits the foundations of the geometrical approach to the study of complexity in qualitative formalisms, with a view to determining to what extent this approach can be used for general qualitative formalisms. We show that the geometrical representations can be regarded as particular instances of “theoretical” conceptual spaces, in the sense of Gärdenfors [GÄR 04].

Then we examine the case of the INDU calculus and the problem of determing its polynomial classes. We show that the use of syntactic methods on the one hand, and of geometrical methods on the other hand, enables us to characterize different polynomial classes, contrary to what was the case for generalized intervals.

Chapters 9, 10 and 11 focus on determining the models of a formalism, and on studying the structures satisfying a given constraint network. To this end, we use the concept of a weak representation of the algebra associated with a formalism. This concept corresponds to the intuitive idea of a “weak” interpretation of the composition table, and generalizes the concept of algebraically closed scenario.

As an introduction to the topic of weak representations, let us examine the case of the Point calculus. A weak representation of the Point algebra is basically a linear order. The models of the Point calculus, in this sense, are all linear orders. In addition, a constraint network which is an algebraically closed scenario is a weak representation of the Point algebra, and there is exactly one linear ordering on the set of vertices of the network such that all the constraints are satisfied. In other words, in this case, a consistent scenario describes one, and only one, qualitative configuration. We will see that a similar result holds in the case of Allen's formalism. On the other hand, the situation is much more complex in many other cases.

Chapter 9 is devoted to the study of weak representations and to their relation with the configurations that they can describe.

We begin this study with the case of the weak representations of generalized intervals, which includes in particular the Point calculus, Allen's calculus, and the Point-and-interval calculus. We also study the weak representations of the formalisms presented in the preceding chapter that can be considered as product calculi of generalized calculi. This applies in particular to the Cardinal direction calculus, the n-point calculus, and the n-block calculus.

For all these formalisms, we show that we can define a concept of closure in such a way that any weak representation is embedded in a natural way in a closed weak representation, called its closure, and that a closed weak representation is entirely equivalent to a well-defined configuration. For example, in the case of generalized intervals, a weak representation defines a set of implicit bounding points for each generalized interval it contains, and the ordering of all bounding points is completely determined by the weak representation considered.

To prove these results, Ligozat [LIG 90, LIG 01] uses the language of category theory. A basic component of the proof is a construction which, given a weak representation for a calculus based on complex entities, associates to it a weak representation of the Point algebra. This construction can be interpreted as a functor which is left-adjoint to the natural functor associated with the construction of complex entities from points.

Using the same techniques, we also prove that the relation algebras associated to those calculi share the following property with the Point algebra: there is a unique countable representation of this algebra up to isomorphism. This also implies that the first-order theories associated to the algebras are No categorical.

Chapter 10 deals with the weak representations of RCC-8. It describes in particular recent research which made it possible to clarify the following question: to what extent does a weak representation of RCC-8 correspond to a representation of the algebra, i.e. how far can the composition table be interpreted in an extensional manner (that is, as giving necessary and sufficient conditions)? It turns out that, if natural interpretations of RCC-8 (closed circles of the plane for example) constitute representations, we cannot find an RCC model which has this property. Results of Li et al. [LI 03b] make it possible to characterize for each entry of the composite table its “defect” of extensionality.

The description of the models of RCC was largely facilitated by its reformulation in terms of connection algebras. It has been of great help for determining which among them are associated with topological spaces. Using a generalization of the concept of connection algebra, one can moreover study the construction of finite or countable models.

As already mentioned, a qualitative formalism defines a Boolean algebra with operators, which in many classical cases, including that of Allen's calculus, is a relation algebra. However, the example of the INDU calculus, whose algebra is not associative, shows that more general algebras have to be considered. On the other hand, the relation algebra associated with a calculus has only a loose relationship with the properties of the constraint networks, for which the properties of the interpretation domain have a prime importance. In the case of RCC-8, the entities whose relations one describes can be of very varied nature. In general, with regard to the relations between the various concepts of consistence, the domain of interpretation intervenes in a fundamental way: for example, an algebraically closed scenario on the Point algebra is consistent for an interpretation in terms of integers, but it is not 3-consistent.

Chapter 11 proposes an answer to the general question: what is a qualitative formalism?

The main result is that a qualitative formalism is built on the basis of what we call a partition scheme. For example, the real line, together with the three relations <, >, and eq, define such a partition scheme.

A partition scheme naturally gives rise to a Boolean algebra equipped with operations of inversion and composition (known as weak composition) which make it a non-associative algebra (a concept which generalizes that of relation algebra). The map which, to each basic relation symbol, associates the corresponding relation of the partition scheme, constitutes a weak representation of this algebra. In this way we get a very general definition answering our initial question: a qualitative formalism is defined as non-associative algebra together with a weak representation of it.

Using once more the language of category theory, one sees that the consistency condition for a network corresponds to the existence of a morphism between two objects in the category of weak representations: the network, on the one hand and, on the other hand, the weak representation which defines the formalism.

We end this chapter by a discussion of the various notions of consistency in a qualitative formalism: besides “mere” consistency, definable in terms of the existence of a morphism, we have to consider properties such as k-consistency (possibility of extension to k variables of an instantiation of (k - 1) variables), strong k-consistency, and global consistency.

Chapter 12 presents an alternative approach to the study of the complexity of qualitative constraint-based formalisms. In the preceding chapters we saw how the use of algebraic techniques made it possible to clarify the nature of the formalisms and in certain cases to describe their complexity properties. In this use from the algebraic point of view, the main role is played by the algebra of basic relations of the formalism.

Another aspect of the algebraic study of satisfaction problems was highlighted by the works of Krokhin et al. [KRO 03]: the complexity of a constraint language is directly related to the properties of what is called its associated operation clones. In this context, relational structures are considered, which consist of a relational signature together with an interpretation of this signature. For example, the Point calculus can be considered as associated to the signature containing the eight symbols corresponding to the disjunctions of <, >, and eq, and the usual interpretations of these symbols as binary relations on . The operations in question are the operations on which preserve these relations, and, in an intuitive manner, the complexity is correlated with the existence of certain types of operations. Moreover, these methods make it possible to study the conditions under which k-consistency for a certain k guarantees global consistency.

The consideration of relations of various arities, other than those of the basic relations, can be compared to the use of disjunctive constraints, using constraint families of which the reduced complexity is known in order to combine them into constraints which, under certain assumptions, preserve this reduced complexity. We describe these techniques, as well as their use by the refinement method, which allows us to a certain extent to automate the discovery of polynomial subclasses. These techniques make it possible in particular to give alternative proofs of known results for Allen's Interval algebra, the RCC-8 algebra, and the Point-and-interval algebra.

Chapter 13 is devoted to some aspects of the use of modal languages for spatial reasoning. A key element in proving the consistency of weak representations of RCC-8 is the use of an interpretation of RCC-8 in terms of modal logic. The links between the modal logic S4 and topology have been known and used right from the 1940s, and a fundamental result of McKinsey and Tarski [MCK 44] asserts that S4 is in a very precise way the modal logic of topology. We recall this result, and describe some recent research which uses the connection with the modal logics to explore questions of expressiveness, as well as extension of modal logics incorporating notions such as convexity.

Chapter 14 departs from the domain of theory. It provides a list of applications of the techniques described in the book in various domains. It also contains short descriptions of software libraries which have been developed with the aim of providing researchers with generic tools for qualitative reasoning.

The term of application can be understood, in our opinion, in at least three different ways:

– on the one hand, in terms of transposition of a domain of research in another. For example, the RCC-8 reasoning techniques for the spatial domain can be used in a “space” which is a conceptual space, and the relations considered will be of relations of topological type between concepts. The application, in this case, remains on the same theoretical level;

– on the other hand, we could use the term of modular applications of spatio-temporal reasoning to refer to the integration of “ready-for-use” spatio-temporal modules in various kinds of systems: spatial or temporal database management systems, planning systems;

– finally, a third type of application corresponds to systems in which the reasoning on time and/or space is closely integrated into the system itself. Many examples are provided by systems incorporating natural language processing components, such as components providing event recognition or event sequencing in textual sources.

In this chapter, rather than making a choice of applications which could only be arbitrary, we simply provide the reader with a substantial set of bibliographical references.

As for software libraries, we present three of them: QAT, SparQ, and GQR.

Chapter 15 presents research directions which appear important and promising to us. We retain three of them:

– the first relates to the problem of combining several qualitative calculi on the same domain: an example is the INDU calculus, which can be considered as a combination of Allen's calculus and of the Point calculus. Two general questions arise in this context: first, determining to what extent consistency in the composed calculus can be deduced from consistency in each component; secondly, determining the complexity of the consistency problem for the composed calculus;

– the second is that of the elaboration of spatio-temporal calculi, either as full-fledged calculi (the basic entities are then elements of space-time), or as combinations of spatial and temporal calculi. In this last case, the general problems of combination also arise;

– the third is related the development of efficient methods for solving qualitative constraint satisfaction problems. The question is the following: can one hope to increase efficiency by translating the qualitative problems in terms of formalisms for which one currently has very powerful techniques, such as finite CSPs or the SAT problem?

Appendices

For the convenience of the reader, we give in the appendices short reviews of three domains, so that the reader can refer to them while reading this book:

– appendix A: basic concepts and results of topology;

– appendix B: elements of universal algebra and of category theory;

– appendix C: disjunctive linear relations (DLRs).

A reading grid of the book

It may be useful to view the project represented by this book in the general perspective of the elaboration and the study of formalisms for representation and reasoning.

Such an undertaking typically comprises a certain number of stages which will be addressed in the course of the book:

1) defining the representation language; here, the language considered will be predominantly the language of constraint networks;

2) studying the expressiveness of this language;

3) defining reasoning techniques; in the present case, the main reasoning techniques are based on constraint propagation;

4) characterizing the reasoning complexity: are the main problems decidable, solvable in polynomial time? What are the possible compromises in terms of expressivity versus complexity?

5) elaborating effective algorithms, and studying their theoretical and empirical properties;

6) studying the models of the formalism: having been devised to represent a certain state of affairs (the expected model), can the formalism have other models, and if such is the case, can one give a description of these alternative models?

Acknowledgments

During the AAAI, UCAI, and ECAI conferences of these last decades, we organized with Frank Anger, Rita Rodriguez, and Hans Guesgen, a series of “workshops” dealing with the qualitative reasoning on time and space. I owe to these colleagues, to their support and their friendship, the idea of writing a book which would take stock of the advancement of research on qualitative spatial and temporal reasoning.

The European network “SPACENET”, of which my laboratory, the LIMSI, was a participant, was a great opportunity for promoting research on space cognition and circulating ideas and projects in the European context. Many thanks to Tony Cohn, Christian Ereksa, and to all those who took part in this network.

I would also like to thank the many colleagues with whom I had the chance to have many stimulating exchanges, in particular: Philippe Balbiani, Peter van Beek, Christian Bessière, Brandon Bennett, Maroua Bouzid, Myriam Bras, Christophe Claramunt, Jean-Erançois Condotta, Ivo Düntsch, Geoffrey Edwards, Anthony Galton, Alfonso Gerevini, Amar Isli, Robert Jeansoulin, Lina Khatib, Peter Ladkin, Florence Le Ber, Sanjiang Li, Debasis Mitra, Robert Morris, Till Mossakowski, Bernard Moulin, Amitabha Mukerjee, Bernhard Nebel, Odile Papini, Jochen Renz, Christoph Schlieder, John Stell, Kathleen Stewart Hornsby, Zygmunt Vetulani, Laure Vieu, Stefan Wölfl.

Thanks also to Patrick Paroubek, who gave the initial impulse to write this book, then followed the writing constantly.

The throes of writing a book are undoubtedly a minor nuisance compared with those that the author's entourage must undergo. I must thus particularly thank my family for their support and understanding during that time.

Chapter 1

Allen's Calculus

1.1. Introduction

The story of qualitative temporal and spatial reasoning begins with the publication of Allen's 1983 paper [ALL 83]. In this chapter and the following one, we give an introduction to Allen's calculus, and take stock of the current state of knowledge on the subject. The past 25 years have witnessed a steady development of results and techniques for reasoning about time and space in a qualitative way. For a view of the state of knowledge on this subject by the late 1980s, the reader can refer to [BBS 89b].

1.1.1. The mystery of the dark room

In [ALL 83], Allen introduces his calculus by using the following anecdote:

1)John was not in the room when I touched the switch to turn on the light;

2)But John was in the room later while the light went out.

1.1.1.1. Representation

These two sentences refer to three events, which in turn correspond to three time intervals: Let S (for switch) be a short time interval during which the switch was pressed, an interval L (for light) corresponding to the period when the light was on, and an interval R (for room) during which John was present in the room. Moreover, the two sentences provide qualitative (qualitative, i.e. not involving measurements) information about the relationships between the three time intervals I, L, and J.

What indeed can we deduce from these sentences?

Figure 1.1.When I pressed the switch

According to sentence 1, there is no overlapping of the time intervals S and R. Moreover, our common sense informs us that the light was on in the room at a time soon after I started to press the switch and also not later than the time when I released the pressure on the switch.

If we consider all possible relations between two intervals based only on the relative orderings of their starting and ending points, we get the 13 relations represented in These 13 relations are called Allen's