Relations Between Spatial Calculi About Directions and Orientations (Extended Abstract)

1 Introduction

In constraint-based reasoning about spatial configurations, typically a partial initial knowledge of a scene is represented in terms of qualitative constraints between spatial objects. Implicit knowledge about spatial relations is then derived by constraint propagation. See [Ligozat, 2011] for an overview and references. In this work, we apply universal algebraic tools to binary qualitative calculi and demonstrate that two calculi expressing related features but on different levels of granularity can often be connected via homomorphisms 1 .

2 Relation Algebras for Spatial Reasoning

Standard methods developed for finite domains generally do not apply to constraint reasoning over infinite domains. The theory of relation algebras [Ladkin and Maddux, 1994; Maddux, 2006] allows for a purely symbolic treatment of constraint satisfaction problems involving relations over infinite domains. The corresponding constraint reasoning techniques were originally introduced by [Montanari, 1974], applied for temporal reasoning [Allen, 1983] and later proved to be valuable for spatial reasoning [Renz and Nebel, 1999; Isli and Cohn, 2000]. The central data for a binary calculus is given by:

1 Full details and proofs can be found in the full version of our paper [Mossakowski and Moratz, 2015].

• a list of (symbolic names for) base-relations, which are interpreted as relations over some domain, having the crucial "JEPD" properties of joint exhaustiveness and pairwise disjointness (a general relation is then simply a union of base-relations).
• a table for the computation of the converses of relations.
• a table for the computation of the compositions of relations.

Then, the path consistency algorithm [Montanari, 1974] and backtracking techniques [van Beek and Manchak, 1996] are the tools used to tackle the problem of consistency of constraint networks and related problems. The mathematical background of composition in table-based reasoning is given by the theory of non-associative algebras [Maddux, 2006; Ligozat and Renz, 2004], where relations algebras are generalised by dropping associativity. These algebras treat spatial relations as abstract entities (independently of any domain) that can be combined by certain operations and governed by certain equations.

When providing examples, it is easier to start with partition schemes [Ligozat and Renz, 2004; Mossakowski et al., 2006]. A partition scheme partitions the set of binary relations over a given set U. It leads to a non-accosivateive algebra, using weak composition, a symbolic approximation of set-theoretic composition.

Example 1. The most prominent temporal calculus is Allen's interval algebra IA [Allen, 1983], which describes possible relations between intervals in linear flows of time 2 . An interval is a pair (s, t) of real numbers such that s < t. This leads to 13 basic relations between such intervals.

Example 2. The CYCb calculus [Isli and Cohn, 2000] is based on the domain CYC = {φ | -π < φ ≤ π} of cyclic orientations. Equivalently, these angles can be represented as oriented straight lines containing the origin of the 2D Euclidian plane associated with a reference system. Using this latter representation, Fig. 1 depicts the four base-relations r, l, o, e (e.g. "right", "left", "opposite", "equal") of CYCb.

Example 3. The OPRAn calculus [Moratz, 2006; ?] is based on the domain OP = {(p, φ) | p ∈ R2 , -π < φ ≤ π}

2 There is also a spatial interpretation of the Allen calculus in which the intervals are interpreted as one-dimensional spatial entities

of oriented points in Euclidean plane. An oriented point consists of a point and an angle serving as its orientation. The full angle is divided using n axes, leading to 4n regions, see Fig. 2. If the points of A and B differ, the relation A m∠ji B

(i, j ∈ Z4m3 ) reads like this: given a granularity m, the relative position of B with respect to A is described by i and the relative position of A with respect to B is described by j. If the points of A and B coincide, the relation A m∠i B expresses that the difference between B's and A's orientations (angles) is in region i.

Example 4. The OPRA∗m calculus [Dylla, 2008] is similar to OPRAm. Here, we concentrate on OPRA∗1 . The important extension is a refinement that is applied to the relations 1∠33 , 1∠13 , 1∠11 , and 1∠31 . These relations are refined by marking themwith letters '+' or '-', 'P' or 'A', according to whether the two orientations of the oriented points are positive, negative, parallel or anti-parallel. Altogether, we obtain a set of 28 base-relations.

Example 5. A dipole is a pair of distinct points in the Euclidean plane. Before explaining dipole-dipole relations, we first study dipole-point relations. We distinguish between whether a point lies to the left, to the right, or at one of five qualitatively different locations on the straight line that passes through the corresponding dipole. Using these seven possible relations between a dipole and a point, the relations between two dipoles may be specified according to the following conjunction of four relationships:

where Ri ∈ {l, r, b, s, i, e, f} with 1 ≤ i ≤ 4. The formal combination gives us 2401 relations, out of which 72 relations are geometrically possible. These constitute the DRAf calculus [Moratz et al., 2000; 2011]. There is a refinement of DRAf , called DRAfp, with additional distinguishing features due to parallelism which are analogous to those for OPRA∗1 .

3Z4m is the residue ring; for simplicity, we set Z4m = {0, . . . , 4m- 1}.

4 Note that e.g. A r sB reads "sB is to the right of A".

3 Granularity and Homomorphisms

The presented calculi offer the possibility to describe scenes on different levels of granularity. The granularity of a description is the context-dependent selection of an adequate level of detail in the description [Hobbs, 1985]. In this paper we deal with granularity in the form of modality changes. In previous work we also dealt with granularity parameters dealing with scale of resolution even enabling the representation of qualitative shape [Dorr et al., 2015; Moratz and Wallgrün, 2014; Dorr and Moratz, 2017]. Granularity plays a key role in human strategies to deal with the complexity of the spatial features of the real world. This is demonstrated nicely by an example from Hobbs (1985). In his example he points out that humans conceptualize streets as one-dimensional entities when they plan a trip, they use a two-dimensional conception when they cross a street. And in contexts where the pavement has to be dug up the street becomes a three-dimensional volume. The key importance of mechanisms to flexibly switch and translate between granularities for successful reasoning about the world is highlighted by the following quote from Hobbs (1985, p. 432):

Our ability to conceptualize the world at different granularities and to switch among these granularities is fundamental to our intelligence and flexibility. It enables us to map the complexities of the world around us into simple theories that are computationally tractable to reason in.

Imagine a scenario involving ships and their relative positions in the open sea (see Fig. 3). Ships can be modelled as elongated, directed entities neglecting their width or any other shape property. The resulting DRAfp representation uses a single dipole for each ship to be represented (see left part of Fig. 3). In the OPRA∗1 representation in addition even the lengths of the ships are neglected (see middle part of Fig. 3). The CYCb representation abstracts away the different locations of the ships and only focuses on their relative orientation (see right part of Fig. 3).

In another example ships are represented with DRAfp in such a way that the start point corresponds to the position of the ship and the end point represents its current speed. More specifically, the end point denotes the future position after one minute travel (if speed and heading were constant). Then longer arrows represent faster ships in a diagram. When we have an alternative representation in OPRA∗1 , in this representation we might only focus on location and heading of the ships and abstract away from the their speed. Then several DRAfp relations in one representation map onto a single OPRA∗1 relation in the alternative representation. For example the three relations {flll, ells, illr} are mapped to 1∠10 (see Fig. 5).

If different spatial calculi can be used to represent a given spatial situation at different levels of granularity, the relation between the calculi can typically be formalized as a quotient abstraction from shape abstraction from location homomorphism. Figure 5 exemplifies the action of a quotient homomorphism. Homomorphisms also arise in other contexts, e.g. as embeddings of a smaller calculus into a larger one (for example, Allen's interval algebra can be embedded into DRAfp ).

Figure 5: In a quotient homomorphism between DRAfp and OPRA∗1 the three relations {flll, ells, illr} are mapped to 1∠10 .

We now study homomorphisms in general. They are a means for the examination of relationships among calculi. Often, conceptual relations between different calculi and their domains can be formalised as homomorphism, and vice versa, if one has found a homomorphism, then often there is also some conceptual relation behind it.

Homomorphisms can also be used to transfer properties (like strength of composition, or algebraic closure deciding consistency) from one calculus to another one, see Propositions 8, 9, 18 and 23 below. Using homomorphisms, it is also possible to find errors in composition tables (we discovered errors in 197 entries of the composition table of OPRA∗1 , see Example 17 below).

Homomorphisms have been studied in [Ligozat and Renz, 2004; Ligozat, 2005; 2011] (mainly under the name of representations). We here introduce a more systematic treatment of homomorphisms. For non-associative algebras, we recall and refine the weaker notion of lax homomorphisms [Moratz et al., 2009; Lücke, 2012], which allow for both the embedding of a calculus into its domain, as well as relating several calculi to each other. Dually to lax homomorphisms, we can define oplax homomorphisms, which enable us to define projections from one calculus to another.

Definition 6 (Lax homomorphism, [Moratz et al., 2009; Lücke, 2012]). Given non-associative algebras A and B, a lax homomorphism is a homomorphism h: A-→B on the underlying Boolean algebras such that:

• h(∆A) ≥∆B
• h(a⌣) = h(a)⌣ for all a ∈ A
• h(a ⋄ b) ≥ h(a) ⋄ h(b) for all a, b ∈ A

A lax homomorphism between complete atomic nonassociative algebras is called semi-strong [Mossakowski et al., 2006] if for atoms a, b

This notion has been inspired by the definition of weak composition and will be used for representation homomorphisms of qualitative calculi.

Definition 7 (Oplax homomorphism, [Moratz et al., 2009; Lücke, 2012]). Given non-associative algebras A and B, an oplax homomorphism is a homomorphism h : A-→B on the underlying Boolean algebras such that:

• h(∆A) ≤∆B
• h(a⌣) = h(a)⌣ for all a ∈ A
• h(a ⋄ b) ≤ h(a) ⋄ h(b) for all a, b ∈ A

A homomorphism is full iff it fully induces the structure on its direct image.

A proper homomorphism (sometimes just called a homomorphism) of non-associative algebras is a homomorphism that is lax and oplax at the same time; the above inequalities then turn into equations. Each proper homomorphism is also full. A proper injective homomorphism is also semi-strong.

An oplax homomorphism of non-associative algebras is said to be a quotient homomorphism if it is full and surjective. We have then the following facts:

Proposition 8. Proper quotient homomorphisms preserve the holding of equations, in particular, associativity.

Proposition 9. Given a quotient homomorphism q : A → B, B's converse and composition tables can be computed from those for A, using q.

A first sample use of homomorphism is the embedding of Allen's interval relations [Allen, 1983] into DRAfp via a homomorphism.

Proposition 10 ([Moratz et al., 2011]). There is a proper homomorphism from Allen's interval algebra to DRAfp.

Another important application of homomorphisms is their use in the definition of a qualitative calculus. [Ligozat and Renz, 2004] define a qualitative calculus in terms of a socalled weak representation [Ligozat, 2005; 2011]: A weak representation ϕ: A → P(U × U) is an identity-preserving and converse-preserving lax homomorphism ϕ from a complete atomic non-associative algebra A into the powersetrelation algebra of a domain U.

Definition 11. Given weak representations ϕ: A → P(U × U) and ψ : B → P(V×V), a ∈ {lax, oplax, full, proper} and b ∈ {lax, oplax, proper}, an (a,b)-homomorphism of weak representations (h, i) : ϕ → ψ is given by

• an a-homomorphism of non-associative algebras h: A→B, and
• a map i : U → V, such that ψ ◦ h = P(i × i) ◦ ϕ if b is proper (or ≤, ≥ instead of = if b is lax, oplax).

Example 12. The homomorphism from Prop. 10 can be extended to a (proper, proper) homomorphism of weak representations by letting i be the embedding of time intervals to dipoles on the x-axis.

A quotient homomorphism of weak representations is a (full,oplax) homomorphism of weak representations that is surjective in both components.

Given a weak representation ϕ: A → P(U × U) and an equivalence relation ∼ on U that is a congruence for _⌣ we obtain a quotient representation ϕ/∼. Under certain conditions, we can show that the quotient algebra indeed is a nonassociative algebra. Under suitable conditions, we obtain a (full, oplax) quotient homomorphism of semi-strong representations.

Example 13. CYCb is a quotient of OPRA∗1 . At the level of domains, it acts as follows: an oriented point (p, φ) is mapped to the orientation φ (the point p is forgotten).

Example 14. DRAf (as a weak representation) is a quotient of DRAfp. It is obtained by forgetting the labels '+', '-', 'P' and 'A'.

Example 15. OPRAn is a quotient of OPRAn·m.

In [Dylla et al., 2013], we show that OPRA1 to OPRA8 are not associative. By Prop. 8 and Ex. 15, this carries over to any OPRAn.

Example 16. OPRA1 is a quotient of OPRA∗1 . It forgets the labels '+', '-', 'P' and 'A'.

Example 17. OPRA∗1 is a quotient of DRAfp, by keeping start point and direction, but forgetting the end point.

By Prop. 9, the construction of OPRA∗1 as a quotient allows us the computation of the converse and composition tables by applying the congruence relations to the tables for DRAfp. Actually, we have compared the result of this procedure with the composition table for OPRA∗1 published by [Dylla, 2008] and provided with the tool SparQ [Wallgrün et al., 2009]. In the course of checking the full oplaxness property of the quotient homomorphism fromDRAfp to OPRA∗1 , we discovered errors in 197 entries of the composition table of OPRA∗1 as it was shipped with the qualitative reasoner SparQ. The table has been corrected accordingly in the meantime. 5

Proposition 18. Quotient homomorphisms of weak representations that are bijective in the second component preserve strength of composition.

Corollary 19 ([Moratz et al., 2009; Lücke, 2012]). Composition in OPRA∗1 is strong.

Corollary 20. Composition in CYCb is strong.

Altogether, we get the diagram of calculi (semi-strong representations) and homomorphisms in Fig. 4.

Finally, important properties of qualitative calculi can be transfered along suitable homomorphisms:

Proposition 21. Given non-associative algebras A and B, an oplax homomorphism h: A -→ B preserves algebraic closure. An injective lax homomorphism reflects algebraic closure.

Proposition 22. (_,oplax) homomorphisms of weak representations preserve solutions for scenarios.

Proposition 23. Atomic (lax,oplax) homomorphisms (h, i) of weak representations with injective h preserve the following property to the image of h:

Algebraic closure decides scenario-consistency.

5 See https://github.com/dwolter/SparQ/ commit/89bebfc60a and https://github.com/ dwolter/SparQ/commit/dad260edd9.