A Combined Calculus on Orientation with Composition Based on Geometric Properties

摘要

Qualitative spatial reasoning (QSR) is an established field of research investigating qualitative representations of space that abstract from the details of the physical world together with reasoning techniques that allow predictions about spatial relations, even if precise quantitative information is not available [1]. Qualitative spatial (and temporal) calculi are a sophisticated means to deal with imprecise knowledge. A calculus is comprised of a set of relations, e.g., {front,left,back,right}, and a set of operations. Besides standard set-theoretic operations composition (o) is the most important to perform constraint reasoning. Simplified, if A is left of B and B is left of C, it can be derived that A is left of C (r_(A,B) o r_(B,C) = r_(A,C)). If a calculus needs to be extended by a property or two calculi are combined, the composition operation for the compound calculus must be given in order to perform any constraint reasoning. Previous results, e.g., regarding the INDU Calculus [6], show that reasoning on the basis of the individiual compositions (bipath consistency) does not return the correct result in many cases. Therefore, general approaches to deal with relation dependencies in combined calculi have to be investigated. Wolfl et al. distinguish two different categories: tight and loose combinations [8]. A loose combination is given if the calculi are kept separately and specialized algorithms are developed for solving biconstraint networks. In case of tight combinations a new combined calculus is defined regarding the interdependencies of the calculi when determining the new base relations and the results of the operations, i.e., composition and converse. They evaluate tight combinations to be more expressive than loose combinations. Several examples for tight and loose combinations are given. For example, in [3] a biconstraint algorithm that works for a rather large class of biconstraint networks with topological and qualitative size information is developed. Similar, in [4] loose combinations of RCC-8 and Rectangle Algebra, Cardinal Direction Calculus respectively, are investigated. In case of the INDU Calculus a new composition table was derived by hand [6]. For details on the different calculi mentioned sofar we refer to [1].