Gérard Ligozat

When logic meets constraints: qualitative spatial and temporal reasoning from a modeller's perspective

Abstract

The main motivation for developing qualitative spatial and temporal formalisms is to represent and reason about qualitative knowledge about space and time, as opposed to metric knowledge. Qualitative knowledge is typically what is conveyed by natural language, and the level of qualitative information is the natural medium of interaction with computerized systems of information such as GIS.

The standard approach to knowledge representation and reasoning (KRR) is through logical systems, either classical, or non standard, such as modal logics, non monotonic logics, or abductive logics. Designing a logical system means first defining its abstract language and a formal reasoning framework, then considering four basic issues: expressiveness, complexity, reasoning procedures (e.g. defining algorithms), and models (measuring how well a formalism relates to its intended, "real world" model).

Qualitative spatial and temporal reasoning (QSTR) arose from a shift of perspective, namely, concentrating on languages where formulas are seen as constraint networks. A landmark is Allen's 1983 paper where Allen's version of interval calculus is defined in terms of temporal constraint networks. This move allows the use of the machinery developed for constrain satisfaction problems (CSP) notably of filtering algorithms.

 The following two decades witnessed the development of a host of constraint-based formalisms, covering various aspects of space such as topology, direction, or qualitative distance. A prominent part of the research activity has been devoted to problems of complexity, using both syntax-based and topologically-based approaches. The first approach is based on restricting the languages, while the second uses the structural properties of space and time to identify specific subsets of constraints. The question of determining the models of the calculi has been another active and fruitful domain of investigation.

As a consequence of the introduction of the constraint-based  perspective, mathematics has entered the field in many forms, including universal algebra (relation algebras and their representations, clones of operations), geometry and topology (characterization of tractable subsets), lattice theory (models of the RCC calculi), mereology and mereotopology, and category theory.

Modelling the processes at work in the use of natural language in relation to space implies integrating aspects of that use which are beyond space and geometry, such as functionality. This emphasizes the need for developing systematic approaches to the combination of formalisms (space and time, space and function, topology and distance, topology and orientation). This is likely to put the consideration of families of formalisms, rather than individual ones, to the foreground of the agenda.