R3-[Q-Shape] - Research: Qualitative Spatial Reasoning

Ternary Point Configuration Calculus (TPCC)

Positional calculi are influenced by results of psycholinguistic research in the field of reference systems. These findings point to three different options to give qualitative descriptions of spatial arrangements of objects. The three options are labeled by Levinson [Lev96] as intrinsic, relative, and absolute

In intrinsic reference systems, the relative position of two entities to each other (the referent and the relatum) is described by referring to one of the objects' intrinsic properties such as front or back. Humans employing relative reference systems use the position of a third entity as an anchor point (origin) instead of referring to built in features of one of the two entities (referent and relatum). Thus, a stone (= referent) may be situated to the left of a house (= relatum) from the speaker's, the hearer's, or a further entity's point of view (= origin). In absolute reference systems, neither a third entity nor intrinsic features are used for reference. Instead, the earth's cardinal directions such as north and south serve as reference directions.

Definition of TPCC relations

The TPCC calculus deals with point-like objects in the 2D-plane. It is a application based variant of the Double Cross calculus [Fre92]. It allows finer distinctions of positional information than the calculi presented before. The partition of the calculus is shown in the figure below.

The reference system used by the TPCC calculus

The letters f, b, l, r, s, d, c stand for front, back, left, right, straight, distant, close, respectively. The terms front, back, etc. are given for mnemonic purposes only. The use of the TPCC relations in natural language applications is shown in an article by Moratz, Tenbrink, Fischer and Bateman [MTFB03]. In this application the TPCC relations are used for natural human robot interaction. The resulting valid configurations are: csb, dsb, clb, dlb, cbl, dbl, csl, dsl, cfl, dfl, clf, dlf, csf, dsf, crf, drf, cfr, dfr, csr, dsr, cbr, dbr, crb, and drb. The configuration in which the referent is at the same position as the relatum is called sam (for "same location"). The two special configurations in which origin and relatum have the same location dou, tri are also base relations of this calculus. This results in 27 base relation for TPCC. For a precise, formal definition of all relations we refer to [MNF03, DM04]. 

Operations on TPCC

Unary operations (transformations) use relations about three points to deduce a relation which holds for a permuted sequence of the same points. Binary operations (compositions) deduce information from two relations which have two points in common (the set consists of four points). The result then is a relation about one of the common points and the two other points. 

Permutations

For an intuitive and compact representation a scheme for an iconic representation is given below ->. The segments corresponding to a relation are presented as filled segments. Unions of relation then simply have several segments filled.

Iconic Representation for TPCC-Relations

Now we present the transformation table for the TPCC calculus ->. Some of the transformations contain proper subsets of the base relations, therefore the calculus is not closed. 

Permutation Table for TPCC-Relations

In order to reduce the size of the table trivial cases for dou and tri are omitted. Symmetric cases can be derived using a reflection operation (reflection on an axis). The results of SC(dsf) and SCI(dsf) also include dou as a result. 

Composition

The TPCC calculus is not closed under strong composition. For that reason we can not directly enforce 4-consistency and we can only use weak composition. The table for weak composition of TPCC relations is shown underneath ->. The first operand determines the row, the second operand the column. Again the table omits entries which can be found by reflection in order to reduce the size of the table. And the trivial cases for dou and tri are omitted. 

Composition of TPCC-Relations

Bibliography

[DM04]: Frank Dylla and Reinhard Moratz. Empirical complexity issues of practical qualitative spatial reasoning about relative position. In Workshop on Spatial and Temporal Reasoning at ECAI 2004, 2004.

[Fre92]: C. Freksa. Using Orientation Information for Qualitative Spatial Reasoning . In A. U. Frank, I. Campari, and U. Formentini, editors, Theories and Methods of Spatial-Temporal Reasoning in Geographic Space, pages 162-178. Springer, Berlin, 1992.

[Lev96]:  S. C. Levinson. Frames of Reference and Molyneux's Question: Crosslinguistic Evidence . In P. Bloom, M. Peterson, L. Nadel, and M. Garrett, editors, Language and Space, pages 109-169. MIT Press, Cambridge, MA, 1996.

[MNF03]: Reinhard Moratz, Bernhard Nebel, and Christian Freksa. Qualitative spatial reasoning about relative position: The tradeoff between strong formal properties and successful reasoning about route graphs. In C. Freksa, W. Brauer, C. Habel, and K.F. Wender, editors, Lecture Notes in Artificial Intelligence 2685: Spatial Cognition III, pages 385-400. Springer Verlag, Berlin/Heidelberg, 2003.

[MTFB03]: R. Moratz, T. Tenbrink, F. Fischer, and J. Bateman. Spatial knowledge representation for human-robot interaction. In C. Freksa, W. Brauer, C. Habel, and K.F. Wender, editors, Lecture Notes in Artificial Intelligence 2685: Spatial Cognition III. Springer Verlag, Berlin/Heidelberg, 2003.