algebra follow trivially. Furthermore, we have tested the associativity of the
composition. For $\mathcal{DRA}_{f}$, we have $373248$ triples of relations to
consider of which $71424$ are not associative. So the composition of $19.14\%$
of all possible triples of relations is not associative202020In the master
thesis of one of our students, a detailed analysis of a specific non-
associative dipole configuration is presented [57], e.g.

$\displaystyle(\textnormal{\rm rrrl};\textnormal{\rm rrrl});\textnormal{\rm
llrl}$ $\displaystyle\neq$ $\displaystyle\textnormal{\rm
rrrl};(\textnormal{\rm rrrl};\textnormal{\rm llrl}).$

For $\mathcal{DRA}_{\mathit{fp}}$ all $512000$ triples of base-relations are
associative w.r.t. composition. With this result, we obtain that
$\mathcal{DRA}_{\mathit{fp}}$ is a relation algebra in a strict sense.

###  3.8 $\mathcal{DRA}_{f}$ composition is weak

The failure of $\mathcal{DRA}_{f}$ to be associative may imply that its
composition is also weak. We will investigate this in this section. First,
recall the definition of strong composition. Furthermore, the composition of
$\mathcal{OPRA}_{1}$ is known to be weak [49], but by Ex. 19 and Prop. 20,
then $\mathcal{DRA}_{f}$ also has a weak composition.

######  Definition 49.

A Qualitative Composition is called _strong_ if, for any arbitrary pair of
objects $A$, $C$ in the domain in relation $Ar_{ac}C$, there is for every
entry in the composition table that contains $Ar_{ac}C$ on the right hand
side, an object $B$ such that $Ar_{ab}B$ and $Br_{bc}C$ reconstruct this
entry.

We will show now that the defining property of strong composition (see Sect.
2.3) is violated for $\mathcal{DRA}_{f}$.

######  Proposition 50.

The composition of $\mathcal{DRA}_{f}$ is weak.

Proof.  Consider the $\mathcal{DRA}_{f}$ composition $A\;\textnormal{\rm
BFII}\;B;B\;\textnormal{\rm LLLB}\;C\mapsto A\;\textnormal{\rm LLLL}\;C$. We
show that there are dipoles $A$ and $B$ such that there is no dipole $B$ which
reflects the composition. Consider dipoles $A$ and $B$ as shown in Fig. 25.

Figure 25: $\mathcal{DRA}_{f}$ weak composition

We observe that they are in the $\mathcal{DRA}_{\mathit{fp}}$ relation LLLL-
with the dipole $C$ pointing towards the line dipole $A$ lies on. Because of
$A\;\textnormal{\rm BFII}\;B$, dipole $B$ has to lie on the same line as $A$.
But, since $C$ is a straight line and lines $A$ and $B$ lie in front of $C$,
the endpoint of $B$ cannot lie behind $C$. ∎

As expected, the composition of $\mathcal{DRA}_{f}$ turns out to be weak. Let
us have a closer look at the composition of $\mathcal{DRA}_{\mathit{fp}}$ in
the next section.

###  3.9 Strong Composition

We are now going to prove that $\mathcal{DRA}_{\mathit{fp}}$ has a strong
composition. The following lemma will be crucial; note that it does _not_ hold
for $\mathcal{DRA}_{f}$.

######  Lemma 51.

Let $R$ be a $\mathcal{DRA}_{\mathit{fp}}$ base relation. For
$\mathcal{DRA}_{\mathit{fp}}$ base relations $R$ not involving parallelism or
anti-parallelism, betweenness and equality among $\\{{\bf s}_{A},{\bf
e}_{A},S_{A,B}\\}$212121Please remember that ${\bf s}_{A}=st(dp_{A})$ and
${\bf e}_{A}=ed(dp_{A})$. for given dipoles $A\,R\,B$ are independent of the
choice of $A$ and $B$, hence uniquely determined by $R$ alone.

Proof.  Let $R=r_{1}r_{2}r_{3}r_{4}r_{5}$, where $r_{5}\in\\{+,-\\}$ even if
$r_{5}$ this is omitted in the standard notation. Note that the assumption
$r_{5}\in\\{+,-\\}$ implies that $S_{A,B}$ is defined. If
$r_{3}\in\\{b,s,i,e,f\\}$, ${\bf e}_{A}\not={\bf s}_{A}=S_{A,B}$, hence there
is no betweenness. Analogously, ${\bf s}_{A}\not={\bf e}_{A}=S_{A,B}$ if
$r_{4}\in\\{b,s,i,e,f\\}$. The remaining possibilities for $r_{3}r_{4}r_{5}$
are:

  1. 1.

ll+, rr-: in these cases, ${\bf e}_{A}$ is between ${\bf s}_{A}$ and
$S_{A,B}$;

  2. 2.

ll-, rr+: in these cases, ${\bf s}_{A}$ is between ${\bf e}_{A}$ and
$S_{A,B}$;

  3. 3.

rl-, lr+: in these cases, $S_{A,B}$ is between ${\bf s}_{A}$ and ${\bf
e}_{A}$.

Note that cases 1 and 2 cannot be distinguished in $\mathcal{DRA}_{f}$.

∎

######  Corollary 52.

Let $R$ be a $\mathcal{DRA}_{\mathit{fp}}$ base relation not involving
parallelism or anti-parallelism. Let $A\,R\,B$ and
$A^{\prime}\,R\,B^{\prime}$. Then, the map $\\{{\bf s}_{A}\mapsto{\bf
s}_{A^{\prime}};{\bf e}_{A}\mapsto{\bf e}_{A^{\prime}};S_{A,B}\mapsto
S_{A^{\prime},B^{\prime}}\\}$ preserves betweenness and equality.

######  Lemma 53.

Let $R$ be a $\mathcal{DRA}_{\mathit{fp}}$ base relation not involving
parallelism or anti-parallelism. Given dipoles $A\,R\,C$ and
$A^{\prime}\,R\,C^{\prime}$ and points $p_{A}$, $p_{A^{\prime}}$, $p_{C}$ and
$p_{C^{\prime}}$ on the lines carrying $A$, $A^{\prime}$, $C$ and $C^{\prime}$
respectively, if the maps $\\{{\bf s}_{A}\mapsto{\bf s}_{A^{\prime}},{\bf
e}_{A}\mapsto{\bf e}_{A^{\prime}},S_{A,C}\mapsto
S_{A^{\prime},C^{\prime}},p_{A}\mapsto p_{A^{\prime}}\\}$ and $\\{{\rm
s}_{C}\mapsto{\bf s}_{C^{\prime}},{\bf e}_{C}\mapsto{\bf
e}_{C^{\prime}},S_{A,C}\mapsto S_{A^{\prime},C^{\prime}},p_{C}\mapsto
p_{C^{\prime}}\\}$ preserve betweenness and equality, then the angles
$\angle(\overrightarrow{S_{A,C}\leavevmode\nobreak\
p_{A}},\overrightarrow{S_{A,C}\leavevmode\nobreak\ p_{C}})$ and
$\angle(\overrightarrow{S_{A,C}\leavevmode\nobreak\
p_{A}},\overrightarrow{S_{A,C}\leavevmode\nobreak\ p_{C}})$ have the same
sign.

Proof.  Since $A\,R\,C$ and $A^{\prime}\,R\,C^{\prime}$, the angles
$\angle(\overrightarrow{{\bf s}_{A}\leavevmode\nobreak\ {\bf
e}_{A}},\overrightarrow{{\rm s}_{C}\leavevmode\nobreak\ {\bf e}_{C}})$ and
$\angle(\overrightarrow{{\bf s}_{A^{\prime}}\leavevmode\nobreak\ {\bf
e}_{A^{\prime}}},\overrightarrow{{\bf s}_{C^{\prime}}\leavevmode\nobreak\ {\bf
e}_{C^{\prime}}})$ have the same sign. By the assumption of the preservation
of betweenness and equality, this carries over to angles
$\angle(\overrightarrow{S_{A,C}\leavevmode\nobreak\
p_{A}},\overrightarrow{S_{A,C}\leavevmode\nobreak\ p_{C}})$ and
$\angle(\overrightarrow{S_{A,C}\leavevmode\nobreak\
p_{A}},\overrightarrow{S_{A,C}\leavevmode\nobreak\ p_{C}})$. ∎

######  Theorem 54.

Composition in $\mathcal{DRA}_{\mathit{fp}}$ is strong.

Proof.  Let $r_{ac}\in r_{ab}\circ r_{bc}$ be an entry in the composition
table, with $r_{ac}$, $r_{ab}$ and $r_{bc}$ base relations. Given dipoles $A$
and $C$ with $Ar_{ac}C$, we need to show the existence of a dipole $B$ with
$Ar_{ab}B$ and $Br_{bc}C$.

Since $r_{ac}\in r_{ab}\circ r_{bc}$, we know that there are dipoles
$A^{\prime}$, $B^{\prime}$ and $C^{\prime}$ with $A^{\prime}r_{ab}B^{\prime}$,
$B^{\prime}r_{bc}C^{\prime}$ and $A^{\prime}r_{ac}C^{\prime}$. Given dipoles
$X$ and $Y$, let $S_{X,Y}$ denote the point of intersection of the lines
carrying $X$ and $Y$; it is only defined if $X$ and $Y$ are not parallel.
Consider now the three lines carrying $A^{\prime}$, $B^{\prime}$ and
$C^{\prime}$, respectively. According to the results of Section 3.1, for the
configuration of these three lines, there are fifteen qualitatively different
cases 1, 2, 3a, 3b, 3c, 4a, 4b, 4c, 5a, 5b, 5c, 6a, 6b, 6c and 7:

  1. 1.

The three points of intersection $S_{A^{\prime},B^{\prime}}$,
$S_{B^{\prime},C^{\prime}}$ and $S_{A^{\prime},C^{\prime}}$ exist and are
different. Since $Ar_{ac}C$ and $A^{\prime}r_{ac}C^{\prime}$, by Corollary 51,
the point sets $\\{{\bf s}_{A},{\bf e}_{A},S_{A,C}\\}$ and $\\{{\bf
s}_{A^{\prime}},{\bf e}_{A^{\prime}},S_{A^{\prime},C^{\prime}}\\}$ are ordered
in corresponding ways on their lines. Hence, it is possible to choose
$S_{A,B}$ in such a way that the point sets $\\{{\bf s}_{A},{\bf
e}_{A},S_{A,C},S_{A,B}\\}$ and $\\{{\bf s}_{A^{\prime}},{\bf
e}_{A^{\prime}},S_{A^{\prime},C^{\prime}},S_{A^{\prime},B^{\prime}}\\}$ are
ordered in corresponding ways on their lines. In a similar way (interchanging
$A$ and $C$), $S_{B,C}$ can be chosen.

Since both $\\{S_{A,B},S_{A,C},S_{B,C}\\}$ and
$\\{S_{A^{\prime},B^{\prime}},S_{A^{\prime},C^{\prime}},S_{B^{\prime},C^{\prime}}\\}$
are affine bases, there is a unique affine bijection
$h\colon\mathbb{R}^{2}\\!\longrightarrow\\!\mathbb{R}^{2}$ with
$h(S_{A^{\prime},B^{\prime}})=S_{A,B}$, $h(S_{A^{\prime},C^{\prime}})=S_{A,C}$
and $h(S_{B^{\prime},C^{\prime}})=S_{B,C}$. By Lemma 53, $h$ preserves
orientation, and thus by Thm. 28 also the $\mathcal{DRA}_{\mathit{fp}}$
relations. Hence, by choosing $B=h(B^{\prime})$, we get $h(A^{\prime})r_{ab}B$
and $Br_{bc}h(C^{\prime})$. Since the sets $\\{{\bf s}_{A},{\bf
e}_{A},S_{A,C},S_{A,B}\\}$ and $\\{h({\bf s}_{A^{\prime}}),h({\bf
e}_{A^{\prime}}),S_{A,C},S_{A,B}\\}$ are on the same line and have
corresponding qualitative (betweenness) relations, and the same holds for the
sets $\\{{\bf s}_{C},{\bf e}_{C},S_{A,C},S_{B,C}\\}$ and $\\{h({\bf
s}_{C^{\prime}}),h({\bf e}_{C^{\prime}}),S_{A,C},S_{B,C}\\}$, we also have
$Ar_{ab}B$ and $Br_{bc}C$ (even though $h(A^{\prime})=A$ and $h(C^{\prime})=C$
do not necessarily hold).

  2. 2.

The three intersection points $S_{A^{\prime},B^{\prime}}$,
$S_{B^{\prime},C^{\prime}}$ and $S_{A^{\prime},C^{\prime}}$ exist and
coincide, i.e.
$S_{A^{\prime},B^{\prime}}=S_{B^{\prime},C^{\prime}}=S_{A^{\prime},C^{\prime}}=:S^{\prime}$.
Let $S=S_{A,C}$. Let $x_{A}$ be ${\bf s}_{A}$ and $x_{A^{\prime}}$ be ${\bf
s}_{A^{\prime}}$ if ${\bf s}_{A}\not=S$ (and therefore ${\bf
s}_{A^{\prime}}\not=S^{\prime}$), otherwise, let $x_{A}$ be ${\bf e}_{A}$ and
$x_{A^{\prime}}$ be ${\bf e}_{A^{\prime}}$. $x_{C}$ and $x_{C^{\prime}}$ are
chosen in a similar way. Since both $\\{S,x_{A},x_{C}\\}$ and
$\\{S^{\prime},x_{A^{\prime}},x_{C^{\prime}}\\}$ are affine bases, there is a
unique affine bijection
$h\colon\mathbb{R}^{2}\\!\longrightarrow\\!\mathbb{R}^{2}$ with
$h(S^{\prime})=S$, $h(x_{A^{\prime}})=x_{A}$ and $h(x_{C^{\prime}})=x_{C}$.
The rest of the argument is similar to case (1).

  3. 3.

(Two lines are parallel and intersect with the third one.) In the sequel, we
will just specify how two affine bases are chosen; the rest of the argument
(as well as the choice of points on the unprimed side in such a way that
qualitative relations are preserved) is then similar to the previous cases.
Subcases (3a), (3b): The lines carrying $A$ and $C$ intersect. Choose $x_{A}$
and $x_{A^{\prime}}$ as in case (2), and chose an appropriate point $S_{B,C}$.
Then use the affine bases $\\{x_{A},S_{A,C},S_{B,C}\\}$ and
$\\{x_{A^{\prime}},S_{A^{\prime},C^{\prime}},S_{B^{\prime},C^{\prime}}\\}$.
Subcase (3c): The lines carrying $A$ and $C$ are parallel. Choose appropriate
points $S_{A,B}$ and $S_{B,C}$ and use the affine bases $\\{{\bf
s}_{A},S_{A,B},S_{B,C}\\}$ and $\\{{\bf
s}_{A^{\prime}},S_{A^{\prime},B^{\prime}},S_{B^{\prime},C^{\prime}}\\}$.

  4. 4.

(Two lines are identical and intersect with the third one.)
Subcases (4a) and (4b): The lines carrying $A$ and $C$ intersect. Choose
$x_{A}$, $x_{A^{\prime}}$, $x_{C}$ and $x_{C^{\prime}}$ as in case (2) and use
the affine bases $\\{S_{A,C},x_{A},x_{C}\\}$ and
$\\{S_{A^{\prime},C^{\prime}},x_{A^{\prime}},x_{C^{\prime}}\\}$.
Subcase (4c): The lines carrying $A$ and $C$ are identical. This means that
$S_{A^{\prime},B^{\prime}}=S_{A^{\prime},C^{\prime}}=:S^{\prime}$. Choose an
appropriate point $S$ and $x_{A}$, $x_{A^{\prime}}$ as in case (2). Moreover,
in a similar way, choose $x_{B^{\prime}}\not=S^{\prime}$, and then some
corresponding $x_{B}$ being in the same $\mathcal{LR}$-relation to $A$ as
$x_{B^{\prime}}$ has to $A^{\prime}$. Then use the affine bases
$\\{S,x_{A},x_{B}\\}$ and $\\{S,x_{A^{\prime}},x_{B^{\prime}}\\}$.

  5. 5.

(All three lines are distinct and parallel.) Subcases (5a), (5b) and (5c) can
all be treated in the same way: Use the affine bases $\\{{\bf s}_{A},{\bf
e}_{A},{\bf s}_{C}\\}$ and $\\{{\bf s}_{A^{\prime}},{\bf e}_{A^{\prime}},{\bf
s}_{C^{\prime}}\\}$. Note that the distance ratio does not matter here.

  6. 6.

(Two lines are identical and are parallel to the third one.)
Subcases (6a) and (6b): The lines carrying $A$ and $C$ are parallel. Proceed
as in case (5).
Subcase (6c): The lines carrying $A$ and $C$ are identical. Choose some ${\bf
s}_{B}$ in the same $\mathcal{LR}$-relation to $A$ as ${\bf s}_{B^{\prime}}$
is to $A^{\prime}$. Then use the affine bases $\\{{\bf s}_{A},{\bf e}_{A},{\bf
s}_{B}\\}$ and $\\{{\bf s}_{A^{\prime}},{\bf e}_{A^{\prime}},{\bf
s}_{B^{\prime}}\\}$.

  7. 7.

(All three lines are identical.) For this case, the result follows from the
fact that Allen’s interval algebra has strong composition (refer to [26]).

∎

######  Corollary 55.

Composition in $\mathcal{DRA}_{\mathit{opp}}$ is strong as well.

Proof.  By Example 19 and Prop. 20. ∎

##  4 Constraint Reasoning with the Dipole Calculus

###  4.1 Consistency

We now consider the question of whether algebraic closure decides consistency.
We call the set of constraints between all dipoles at hand a _constraint
network_. If no constraint between two dipoles is given, we agree that they
are in the universal relation. By _scenario_ , we denote a constraint network
in which all constraints are base-relations222222In this case, a base-relation
between every pair of distinct dipoles has to be provided. We construct
constraint-networks which are geometrically unrealizable but still
algebraically closed. We do this by constructing constraint networks that are
consistent and algebraically closed, and then we will change a relation in
them in such a way that they remain algebraically closed but become
inconsistent. We follow the approach of [58] in using a simple geometric shape
for which scenarios exist, where algebraic closure fails to decide
consistency. In our case, the basic shape is a convex hexagon, similar to a
screw head.

Consider a convex hexagon consisting of the dipoles $A$, $B$, $C$, $D$, $E$
and $F$. Such an object is described as

$(A\;\textnormal{\rm errs}\;B)(B\;\textnormal{\rm errs}\;C)(C\;\textnormal{\rm
errs}\;D)(D\;\textnormal{\rm errs}\;E)(E\;\textnormal{\rm
errs}\;F)(F\;\textnormal{\rm errs}\;A)$

where the components $r$ of the relations ensure convexity, since they enforce
an angle between $0$ and $\pi$ between the respective first and second dipole,
i.e., the endpoint of consecutive dipoles always lies to the right of the
preceding dipole. Such an object is given in Fig. 26

Figure 26: Convex hexagon

To this scenario we add a seventh dipole $G$ with the relations

$(G\;\textnormal{\rm rrll}\;A)(G\;\textnormal{\rm lrll}\;F)(G\;\textnormal{\rm
llrr}\;D)(G\;\textnormal{\rm rlrr}\;C)$

We have the overall constraint network:

$\begin{array}[]{l}(A\;\textnormal{\rm errs}\;B)(B\;\textnormal{\rm
errs}\;C)(C\;\textnormal{\rm errs}\;D)(D\;\textnormal{\rm
errs}\;E)(E\;\textnormal{\rm errs}\;F)(F\;\textnormal{\rm errs}\;A)\\\
(G\;\textnormal{\rm rrll}\;A)(G\;\textnormal{\rm lrll}\;F)(G\;\textnormal{\rm
llrr}\;D)(G\;\textnormal{\rm rlrr}\;C)\end{array}$

Because of the relations $(G\;\textnormal{\rm lrll}\;F)$ and
$(G\;\textnormal{\rm rlrr}\;C)$, line $l_{G}$ intersects line $l_{F}$ as well
as line $l_{C}$. Because of the first two components of the relations, dipoles
$F$ and $C$ are oriented into qualitatively antipodal directions. This network
is consistent and is of course algebraically closed.

To construct an inconsistent network, we change the relation
$(G\;\textnormal{\rm rlrr}\;C)$ to $(G\;\textnormal{\rm rlll}\;C)$ and obtain
the constraint network:

$\begin{array}[]{l}(A\;\textnormal{\rm errs}\;B)(B\;\textnormal{\rm
errs}\;C)(C\;\textnormal{\rm errs}\;D)(D\;\textnormal{\rm
errs}\;E)(E\;\textnormal{\rm errs}\;F)(F\;\textnormal{\rm errs}\;A)\\\
(G\;\textnormal{\rm rrll}\;A)(G\;\textnormal{\rm lrll}\;F)(G\;\textnormal{\rm
llrr}\;D)(G\;\textnormal{\rm rlll}\;C)\end{array}$

The relations $(G\;\textnormal{\rm rlll}\;C)$ and $(G\;\textnormal{\rm
lrll}\;F)$ enforce that $G$ must lie in between $F$ and $C$ as shown in Fig.
27.

Figure 27: Position of $G$

In this case, the all convex hexagons $A$, $B$, $C$, $D$, $E$, $F$ have the
endpoints of consecutive dipoles lying to the left of the preceding one, they
are of the form:

$(A\;\textnormal{\rm ells}\;B)(B\;\textnormal{\rm ells}\;C)(C\;\textnormal{\rm
ells}\;D)(D\;\textnormal{\rm ells}\;E)(E\;\textnormal{\rm
ells}\;F)(F\;\textnormal{\rm ells}\;A)$

which is a contradiction of the required form of hexagon in the scenario. In
fact there is no affine transformation which preserves the relative
orientations between dipoles $A$, $B$, $C$, $D$, $E$, $F$, and maps a hexagon
of Fig. 26 to any that can be constructed along dipoles $C$ and $F$ in Fig. 27
in such a way that the edges $C$ and $F$ of both hexagons coincide. Still
algebraic closure with $\mathcal{DRA}_{f}$ yields the refinement:

$\begin{array}[]{l}(F\;\textnormal{\rm lllr}\;G)(E\,\,(\textnormal{\rm
flll},\textnormal{\rm llll},\textnormal{\rm rfll},\textnormal{\rm
rlll},\textnormal{\rm rrll})\,\,G)(D\;\textnormal{\rm
errs}\;E)(D\;\textnormal{\rm rrll}\;G)\\\ (D\,\,(\textnormal{\rm
rbrr},\textnormal{\rm rllr},\textnormal{\rm rlrr},\textnormal{\rm
rrrr})\,\,F)(C\;\textnormal{\rm llrl}\;G)(C\,\,(\textnormal{\rm
lrrl},\textnormal{\rm rllr})\,\,F)(E\;\textnormal{\rm errs}\;F)\\\
(C\,\,(\textnormal{\rm rllr},\textnormal{\rm rrfr},\textnormal{\rm
rrlr},\textnormal{\rm rrrr})\,\,E)(C\,\,\;\textnormal{\rm
errs}\;\,\,D)(B\,\,(\textnormal{\rm llrr},\textnormal{\rm rrrr})\,\,G)\\\
(B\,\,(\textnormal{\rm blrr},\textnormal{\rm llll},\textnormal{\rm
llrf},\textnormal{\rm llrl},\textnormal{\rm llrr},\textnormal{\rm
rfll},\textnormal{\rm rlll},\textnormal{\rm rlrr, rrbl},\textnormal{\rm
rrll},\textnormal{\rm rrrl},\textnormal{\rm rrrr})\,\,E)\\\
(B\,\,(\textnormal{\rm rbrr},\textnormal{\rm rlrr},\textnormal{\rm
rrfr},\textnormal{\rm rrlr},\textnormal{\rm rrrr})\,\,D)(B\;\textnormal{\rm
errs}\;C)(A\;\textnormal{\rm llrr}\;G)(A\;\textnormal{\rm rser}\;F)\\\
(A\,\,(\textnormal{\rm frrr},\textnormal{\rm lrrr},\textnormal{\rm
rrrb},\textnormal{\rm rrrl},\textnormal{\rm
rrrr)\,\,E)(A\,\,(rllr},\textnormal{\rm rlrr},\textnormal{\rm rrrr})\,\,C)\\\
(A\,\,(\textnormal{\rm lfrr},\textnormal{\rm llbr},\textnormal{\rm
llll},\textnormal{\rm lllr},\textnormal{\rm llrr},\textnormal{\rm
lrll},\textnormal{\rm lrrr},\textnormal{\rm rrlf},\textnormal{\rm
rrll},\textnormal{\rm rrlr},\textnormal{\rm rrrr})\,\,D)\\\
(B\,\,(\textnormal{\rm frrr},\textnormal{\rm lrrl},\textnormal{\rm
lrrr},\textnormal{\rm rrrr})\,\,F)(A\;\textnormal{\rm errs}\;B)\end{array}$

A scenario,

$\begin{array}[]{l}(F\;\textnormal{\rm lllr}\;G)(E\;\textnormal{\rm
flll}\;G)(E\;\textnormal{\rm errs}\;F)(D\;\textnormal{\rm
rrll}\;G)(D\;\textnormal{\rm rrrr}\;F)(D\;\textnormal{\rm errs}\;E)\\\
(C\;\textnormal{\rm llrl}\;G)(C\;\textnormal{\rm rllr}\;F)(C\;\textnormal{\rm
rrlr}\;E)(C\;\textnormal{\rm errs}\;D)(B\;\textnormal{\rm
llrr}\;G)(B\;\textnormal{\rm lrrl}\;F)\\\ (B\;\textnormal{\rm
llrl}\;E)(B\;\textnormal{\rm rlrr}\;D)(B\;\textnormal{\rm
errs}\;C)(A\;\textnormal{\rm llrr}\;G)(A\;\textnormal{\rm
rser}\;F)(A\;\textnormal{\rm rrrr}\;E)\\\ (A\;\textnormal{\rm
lrrr}\;D)(A\;\textnormal{\rm rllr}\;C)(A\;\textnormal{\rm
errs}\;B)\end{array}$

can be derived from this algebraically closed network. It is still deemed
algebraically closed, even though it is not consistent with the same argument
given above. Hence algebraic closure does not decide consistency for
$\mathcal{DRA}_{f}$-scenarios. On the other hand, algebraic closure with
$\mathcal{DRA}_{\mathit{fp}}$ detects all possible extensions of this network
to that calculus as being inconsistent. Extending the consistent case with the
relation $(G\;\textnormal{\rm rlrr}\;C)$ yields three possible extensions for
$\mathcal{DRA}_{\mathit{fp}}$ scenarios, of which all are consistent. In fact,
we get the three following consistent refinements.

$\begin{array}[]{c|c|c|c}DRA_{f}\textnormal{-relation}&\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\textnormal{refinement}1\nobreak\leavevmode\nobreak\leavevmode\nobreak\leavevmode&\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\textnormal{refinement}2\nobreak\leavevmode\nobreak\leavevmode\nobreak\leavevmode&\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\textnormal{refinement}3\nobreak\leavevmode\nobreak\leavevmode\nobreak\leavevmode\\\
\hline\cr(G\;\textnormal{\rm rrll}\;A)&(G\;\textnormal{\rm
rrll-}\;A)&(G\;\textnormal{\rm rrll-}\;A)&(G\;\textnormal{\rm rrll-}\;A)\\\
\hline\cr(G\;\textnormal{\rm llrr}\;D)&(G\;\textnormal{\rm
llrr-}\;D)&(G\;\textnormal{\rm llrr+}\;D)&(G\;\textnormal{\rm
llrrP}\;D)\end{array}$

We have found an example that shows that algebraic closure for
$\mathcal{DRA}_{\mathit{fp}}$ finds inconsistencies in constraint networks
where it fails for $\mathcal{DRA}_{f}$. Does algebraic closure for
$\mathcal{DRA}_{\mathit{fp}}$ decide consistency? We can also give a negative
result for this. To construct a counterexample, we begin with a configuration
as in Fig. 28

Figure 28: Construction of the counterexample

We ensure with the constraints

$(A\;\textnormal{\rm errs}\;B)(B\;\textnormal{\rm errs}\;C)(C\;\textnormal{\rm
errs}\;D)(D\;\textnormal{\rm errs}\;E)(E\;\textnormal{\rm
errs}\;F)(F\;\textnormal{\rm errs}\;A)$

that the dipoles $A$, $B$, $C$, $D$, $E$ and $F$ form a convex hexagon.
Furthermore, we ensure that the dipoles $I$, $H$ and $G$ form a continuous
line by

$(I\;\textnormal{\rm efbs}\;H)(H\;\textnormal{\rm efbs}\;G).$

The constraints

$(F\;\textnormal{\rm rrrl}\;I)(C\;\textnormal{\rm rrlr}\;G)$

state that the line has to lie inside the hexagon, since its start point and
end point lie inside. To construct the counterexample, we just claim that the
end point of $H$ lies outside the hexagon by $(A\;\textnormal{\rm rllr}\;H)$,
i.e. the lines $A$ and $H$ intersect, this is a contradiction of the convexity
of the hexagon. This network can be refined to a scenario

$\displaystyle\mathtt{SCEN}$ $\displaystyle:=$
$\displaystyle(H\;\textnormal{\rm efbs}\;G)(I\;\textnormal{\rm
ffbb}\;G)(I\;\textnormal{\rm efbs}\;H)(F\;\textnormal{\rm
rrrl}\;G)(F\;\textnormal{\rm rrrl}\;H)$ $\displaystyle(F\;\textnormal{\rm
rrrl}\;I)(E\;\textnormal{\rm rrrr-}\;G)(E\;\textnormal{\rm
rrrr-}\;H)(E\;\textnormal{\rm rrrr-}\;I)$ $\displaystyle(E\;\textnormal{\rm
errs}\;F)(D\;\textnormal{\rm rrrrA}\;G)(D\;\textnormal{\rm
rrrrA}\;H)(D\;\textnormal{\rm rrrrA}\;I)$ $\displaystyle(D\;\textnormal{\rm
rrrr-}\;F)(D\;\textnormal{\rm errs}\;E)(C\;\textnormal{\rm
rrlr}\;G)(C\;\textnormal{\rm rrlr}\;H)$ $\displaystyle(C\;\textnormal{\rm
rrlr}\;I)(C\;\textnormal{\rm rrlr}\;F)(C\;\textnormal{\rm
rrrr+}\;E)(C\;\textnormal{\rm errs}\;D)$ $\displaystyle(B\;\textnormal{\rm
rrrl}\;G)(B\;\textnormal{\rm rrrl}\;H)(B\;\textnormal{\rm
rrrl}\;I)(B\;\textnormal{\rm lrrl}\;F)$ $\displaystyle(B\;\textnormal{\rm
llrr-}\;E)(B\;\textnormal{\rm rlrr}\;D)(B\;\textnormal{\rm
errs}\;C)(A\;\textnormal{\rm lllr}\;G)$ $\displaystyle(A\;\textnormal{\rm
rllr}\;H)(A\;\textnormal{\rm rrlr}\;I)(F\;\textnormal{\rm
errs}\;A)(A\;\textnormal{\rm rrrrA}\;E)$ $\displaystyle(A\;\textnormal{\rm
lrrr}\;D)(A\;\textnormal{\rm rlrr}\;C)(A\;\textnormal{\rm errs}\;B).$

which is still algebraically closed w.r.t. $\mathcal{DRA}_{\mathit{fp}}$, even
though it is not consistent. We see that algebraic-closure does not decide
consistency even for $\mathcal{DRA}_{\mathit{fp}}$-scenarios.

We have run several tests to get some quantitative information on how much
better the $\mathcal{DRA}_{\mathit{fp}}$ calculus performs with respect to the
$\mathcal{DRA}_{f}$ calculus. We have generated several scenarios of size
$\leq n$ with $n\in\left\\{30,40,50,60,70\right\\}$ randomly to obtain this
information. It turns out that a number of $10^{\frac{n}{10}+1}$ scenarios
yield usable data. In fact, we have generated $\mathcal{DRA}_{\mathit{fp}}$
scenarios and checked them with an algebraic reasoner, then we have projected
them to $\mathcal{DRA}_{f}$ and checked these with the same reasoner. In the
end, we compared the per-scenario results. The results are as follows:

Scenarios | $10000$ | $100000$ | $1000000$ | $10000000$ | $100000000$
---|---|---|---|---|---
Maximum Size | $30$ | $40$ | $50$ | $60$ | $70$
Algebraically Closed | $691$ | $5295$ | $40820$ | $346164$ | $3048063$
A-closed w.r.t. $\mathcal{DRA}_{f}$ only | $11$ | $149$ | $1061$ | $8839$ | $78792$
A-closed w.r.t. $\mathcal{DRA}_{\mathit{fp}}$ only | $0$ | $0$ | $0$ | $0$ | $0$

Roughly $2.5\%$ of the scenarios that are algebraically closed w.r.t. to
$\mathcal{DRA}_{f}$ are not algebraically closed w.r.t.
$\mathcal{DRA}_{\mathit{fp}}$. Still, for the smallest checked maximum
scenario size $30$ the factor is only $1.5\%$.

We also investigate the question if algebraic closure decides consistency for
$\mathcal{DRA}_{\mathit{op}}$ and $\mathcal{DRA}_{\mathit{opp}}$.

Figure 29:  $\mathcal{DRA}_{\mathit{opp}}$ scenario

######  Proposition 56.

For $\mathcal{DRA}_{\mathit{opp}}$ algebraic closure does not decide
consistency.

Proof.  This proof is inspired by the one that shows that algebraic closure
does not decide consistency for $\mathcal{OPRA}$ (ref. to [49]). Consider a
$\mathcal{DRA}_{\mathit{opp}}$ constraint network in three points $A$, $B$ and
$C$ as shown in Fig. 29. Both $A$ and $B$ point at $C$. These three points are
in the relations:

$A\;\textnormal{\rm LEFTright-}\;B\quad\quad A\;\textnormal{\rm
FRONTleft}\;C\quad\quad B\;\textnormal{\rm FRONTleft}\;C.$

We add a point $D$ to our constraint satisfaction problem with
$C\;\textnormal{\rm RIGHTleftP}\;D$. We claim that $D$ also lies in front of
$A$ and $B$ by introducing the constraints $A\;\textnormal{\rm FRONTleft}\;D$
and $B\;\textnormal{\rm FRONTleft}\;D$. By inspecting the composition table of
$\mathcal{DRA}_{\mathit{opp}}$, we can see that it is consistent. Since by the
constraint $A\;\textnormal{\rm LEFTright-}\;B$ the points $A$ and $B$ are not
collinear, $D$ has to lie on the intersection point of the rays $l_{A}$ and
$l_{B}$, but by $A\;\textnormal{\rm FRONTleft}\;C$ and $B\;\textnormal{\rm
FRONTleft}\;C$, $C$ also has to lie on that intersection point. Hence, $C$ and
$D$ have to have the same position, what is a contradiction to the constraint
$C\;\textnormal{\rm RIGHTleftP}\;D$. Hence this scenario is algebraically
closed, but inconsistent. ∎

######  Proposition 57.

For $\mathcal{DRA}_{\mathit{op}}$ algebraic closure does not decide
consistency.

Proof.  This proof is analogous to the one of Prop. 56, with substituting
LEFTright- by LEFTright and RIGHTleftP by RIGHTleft. ∎

##  5 A Sample Application of the Dipole Calculus

Figure 30:  A street network and two local observations

In this section, we want to demonstrate with an example how spatial knowledge
expressed in $\mathcal{DRA}_{\mathit{fp}}$ can be used for deductive reasoning
based on constraint propagation (algebraic closure), resulting in the
generation of useful indirect knowledge from partial observations in a spatial
scenario. In our sample application, a spatial agent (a simulated robot,
cognitive simulation of a biological system etc.) explores a spatial scenario.
The agent collects local observations and wants to generate survey knowledge.

Fig. 30 shows our spatial environment. It consists of a street network in
which some streets continue straight after a crossing and some streets run
parallel. These features are typical of real-world street networks. Spatial
reasoning in our example uses constraint propagation (e.g. algebraic closure
computation) to derive indirect constraints between the relative location of
streets which are further apart from local observations between neighboring
streets. The resulting survey knowledge can be used for several tasks
including navigation tasks.

The environment is represented as streets $s_{i}$ and crossings $C_{j}$. The
streets and crossings have unique names (e.g. $s_{1}$, … , $s_{12}$, and
$C_{1}$, …, $C_{9}$ in one concrete example). The local observations are
modeled in the following way, based on specific visibility rules (we want to
simulate prototypical features of visual perception): Both at each crossing
and at each straight street segment we have an observation. At each crossing
the agent observes the neighboring crossings. At the middle of each straight
street segment the agent can observe the direction of the outgoing streets at
the adjacent crossings (but not at their other ends). Two specific examples of
observations are marked in Fig. 30. The observation ”s1 errs s7” is marked
green at crossing C1. The observation ”s8 rrllP s9” is marked red at street
s4.

These observations relate spatially neighboring streets to each other in a
pairwise manner, using $\mathcal{DRA}_{\mathit{fp}}$ base relations. The agent
has no additional knowledge about the specific environment. The spatial world
knowledge of the agent is expressed in the converse and composition tables of
$\mathcal{DRA}_{\mathit{fp}}$ .

The following sequence of partial observations could be the result of a tour
made by the spatial agent, exploring the street network of our example (see
Fig. 30):

Figure 31: All observation and resulting uncertainty

---
Observations at crossings
C1: |  (s7 errs s1)
C2: |  (s1 efbs s2) (s8 errs s2) (s1 rele s8)
C3: |  (s2 rele s9)
C4: |  (s10 efbs s7) (s10 errs s3) (s7 srsl s3)
C5: |  (s3 efbs s4) (s11 efbs s8) (s11 errs s4) (s3 ells s8)
|  (s3 rele s11) (s8 srsl s4)
C6: |  (s12 efbs s9) (s4 ells s9) (s4 rele s12)
C7: |  (s10 srsl s5)
C8: |  (s5 efbs s6) (s5 ells s11) (s11 srsl s6)
C9: |  (s6 ells s12)
Observations at streets
s1: |  (s7 rrllP s8)
s2: |  (s8 rrllP s9)
s3: |  (s10 rrllP s11)
s4: |  (s11 rrllP s12)
s8: |  (s3 llrr- s1)
s9: |  (s4 llrr- s2)
s10: |  (s3 rrll- s5)
s11: |  (s4 rrll- s6)

The result of the algebraic closure computation/constraint propagation is a
refined network with the same solution set (the results are computed with the
publicly available SparQ reasoning tool supplied with our newly computed
$\mathcal{DRA}_{\mathit{fp}}$ composition table [50]). We have listed the
results in the appendix. Three different models are the only remaining
consistent interpretations (see the appendix for a list of all the resulting
data). The three different models agree on all but four relations. The
solution set can be explained with the help of the diagram in Fig. 31. The
input crossing observations are marked with green arrows, the input street
observations are marked with red arrows. The result shows that for all street
pairs which could not be observed directly, the algebraic closure algorithm
deduces a strong constraint/precise information. Typically, the resulting
spatial relation between street pairs comprises just one
$\mathcal{DRA}_{\mathit{fp}}$ base relation. The exception consists of four
relations between streets in which the three models differ (marked with dashed
blue arrows in Fig. 31). For these four relations each model from the solution
set agrees on the same $\mathcal{DRA}_{f}$ base relation for a given relation,
but the three consistent models differ on the finer granularity level of
$\mathcal{DRA}_{\mathit{fp}}$ base relations. Since the refinement of one of
these four underspecified relations on a single interpretation
($\mathcal{DRA}_{\mathit{fp}}$ base relation) as a logical consequence also
assigns a single base relation to the other three relations, only three
interpretations are valid models. The uncertainty/indeterminacy is the result
of the specific street configuration in our example. The streets in a North-
South direction are parallel, but the streets in an East-West direction are
not parallel resulting in fewer constraint composition results. However, the
small solution set of consistent models agrees on most of the relative
position relations between street pairs and the differences between models are
small. In our judgement, this means that the system has generated the relevant
survey knowledge about the whole street network from local observations alone.

##  6 Summary and Conclusion

We have presented different variants of qualitative spatial reasoning calculi
about oriented straight line segments which we call dipoles. We have derived
calculi for oriented points from dipole calculi, which turned out to be
isomorphic to some versions of the $\mathcal{OPRA}$ calculi. These spatial
calculi provide a basis for representing and reasoning about qualitative
position information in intrinsic reference systems.

We have computed the composition table for dipole calculi by a new method
based on the algebraic semantics of the dipole relations. We have used a so-
called condensed semantics which uses the orbits of the affine group
$\mathbf{GA}(\mathbb{R}^{2})$ to provide an abstract symbolic notion of
qualitative composition configuration. This can be used to compute the
composition table in a computer-assisted way. The correctness of this
computation is ensured by letting the computer program directly operate with
qualitative composition configurations.

This has been the first computation of the composition table for
$\mathcal{DRA}_{\mathit{fp}}$. So far, only composition tables for
$\mathcal{DRA}_{c}$ and $\mathcal{DRA}_{f}$ exist, which contain many errors
[59]. We have analysed the algebraic features of the various dipole calculi.
We have proved the result that $\mathcal{DRA}_{\mathit{fp}}$ has strong
composition. This is an interesting result, because in this case an
application-motivated calculus extension has been found to also have a certain
mathematical elegance. Moreover, the strength of composition carries over to
$\mathcal{DRA}_{\mathit{opp}}$, the $\mathcal{OPRA}$ variant introduced in
this paper. This transfer of properties from one calculus to another calculus
is an important new general result on quotients of qualitative calculi. To our
knowledge, also the notion of quotient of a qualitative calculus (defined
using methods from universal algebra) appears for the first time in this
paper.

We have demonstrated a prototypical application of reasoning about qualitative
position information in relative reference systems. In this scenario about
cognitive spatial agents and qualitative map building, coarse locally
perceived street configuration information has to be integrated by constraint
propagation in order to get survey knowledge. The well-known path-consistency
method which is implemented with standard QSR tools can make use of our new
dipole calculus composition table and compute the desired result in polynomial
time. Such concrete but generalizable application scenarios for relative
position calculi are the more important since a recent result by Wolter and
Lee [27] showed that relative position calculi are intractable even in base
relations. For this reason, it is necessary to gain experience in which
application contexts the unavoidable approximate reasoning is effective and
produces relevant inference results. With our street network example, we have
a test case which puts emphasis on deriving implicit knowledge as the output
of qualitative spatial reasoning based on observed data. This is a
prototypical application scenario which in the future can also be applied to
other relative position calculi.

Since the observed data in the case of error-free perception leads to
consistent input constraints, the general consistency problem can be avoided –
we instead rely on logical consequence. Now both problems are intractable and
need to be approximated using algebraic closure; however, in our setting,
approximate losses are less harmful, since we do not risk working with
inconsistent scenarios.

Our future work will address the question of how in general the quality of
approximations for relative position reasoning can also be assessed with
quantitative measures. Another part of our future QSR research will apply our
new condensed semantics method to other calculi.

## Acknowledgment

The authors would like to thank Diedrich Wolter, Jochen Renz, Frank Dylla,
Christian Freksa, Franz Kalhoff, Stefan Wölfl, Lutz Schröder, and Brandon
Bennett for interesting and helpful discussions related to the topic of the
paper. Our work was supported by the DFG Transregional Collaborative Research
Center SFB/TR 8 “Spatial Cognition”.

## References

  * [1] A. G. Cohn, Qualitative spatial representation and reasoning techniques, in: G. Brewka, C. Habel, B. Nebel (Eds.), Proc. of KI-97, Lecture Notes in Artificial Intelligence, Springer-Verlag, 1997, pp. 1–30.
  * [2] C. Freksa, Using Orientation Information for Qualitative Spatial Reasoning, in: A. U. Frank, I. Campari, U. Formentini (Eds.), Theories and Methods of Spatial-Temporal Reasoning in Geographic Space, Springer, 1992, pp. 162–178.
  * [3] D. A. Randell, A. G. Cohn, Modelling topological and metrical properties of physical processes, in: R. J. Brachman, H. J. Levesque, R. Reiter (Eds.), Proc. of KR-89, Morgan Kaufmann, 1989, pp. 357–368.
  * [4] D. A. Randell, Z. Cui, A. G. Cohn, A spatial logic based on regions and connection, in: B. Nebel, C. Rich, W. Swartout (Eds.), Proc. of KR-92, Morgan Kaufmann, 1992, pp. 165–176.
  * [5] M. Egenhofer, R. Franzosa, Point-Set Topological Spatial Relations, International Journal of Geographical Information Systems 5 (2) (1991) 161–174.
  * [6] J. Renz, B. Nebel, On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus, Artificial Intelligence 108 (1-2) (1999) 69–123.
  * [7] M. F. Worboys, E. Clementini, Integration of Imperfect Spatial Information, Journal of Visual Languages and Computing 12 (2001) 61–80.
  * [8] C. Freksa, Using orientation information for qualitative spatial reasoning, in: A. U. Frank, I. Campari, U. Formentini (Eds.), Theories and methods of spatio-temporal reasoning in geographic space, Vol. 639 of Lecture Notes in Comput. Sci., Springer, 1992, pp. 162–178.
  * [9] A. Frank, Qualitative Spatial Reasoning with Cardinal Directions, in: Proc. of 7th Österreichische Artificial-Intelligence-Tagung, Springer, 1991, pp. 157–167.
  * [10] G. Ligozat, Reasoning about Cardinal Directions, Journal of Visual Languages and Computing 9 (1998) 23–44.
  * [11] E. Clementini, P. D. Felice, D. Hernandez, Qualitative Represenation of Positional Information, Artificial Intelligence 95 (1997) 317–356.
  * [12] K. Zimmermann, C. Freksa, Qualitative Spatial Reasoning Using Orientation, Distance, Path Knowledge, Applied Intelligence 6 (1996) 49–58.
  * [13] A. Isli, R. Moratz, Qualitative Spatial Representation and Reasoning: Algebraic Models for Relative Position, Tech. rep., Universität Hamburg, FB Informatik, Hamburg (1999).
  * [14] R. Moratz, M. Ragni, Qualitative Spatial Reasoning about Relative Point Position, Journal of Visual Languages and Computing.
  * [15] R. Moratz, T. Tenbrink, Spatial reference in linguistic human-robot interaction: Iterative, empirically supported development of a model of projective relations, Spatial Cognition and Computation 6 (1) (2006) 63–107.
  * [16] S. C. Levinson, Frames of Reference and Molyneux’s Question: Crosslinguistic Evidence, in: P. Bloom, M. Peterson, L. Nadel, M. Garrett (Eds.), Language and Space, MIT Press, 1996, pp. 109–169.
  * [17] R. Moratz, Representing Relative Direction as a Binary Relation of Oriented Points, in: Proc. of ECAI-06, 2006, pp. 407–411.
  * [18] K. Zimmermann, C. Freksa, Qualitative spatial reasoning using orientation, distance, and path knowledge, Applied Intelligence 6 (1996) 49–58.
  * [19] A. Isli, A. G. Cohn, A new approach to cyclic ordering of 2D orientations using ternary relation algebras, Artificial Intelligence 122 (1-2) (2000) 137–187.
  * [20] G. Ligozat, Reasoning about Cardinal Directions, Journal of Visual Languages and Computing 9 (1998) 23–44.
  * [21] J. Renz, D. Mitra, Qualitative Direction Calculi with Arbitrary Granularity, in: Proc. of PRICAI-04, 2004, pp. 65–74.
  * [22] C. Freksa, Conceptual neighborhood and its role in temporal and spatial reasoning, in: M. G. Singh, L. Travé-Massuyès (Eds.), Proc. of the IMACS Workshop on Decision Support Systems and Qualitative Reasoning, 1991, pp. 181–187.
  * [23] C. Freksa, Spatial Cognition - An AI Perspective, in: Proc. of ECAI-04, 2004, pp. 1122–1128.
  * [24] C. Schlieder, Reasoning about Ordering, in: A. Frank, W. Kuhn (Eds.), Spatial Information Theory: a theoretical basis for GIS, no. 988 in Lecture Notes in Comput. Sci., Berlin, 1995, pp. 341–349.
  * [25] F. Dylla, L. Frommberger, J. O. Wallgrün, D. Wolter, S. Wölfl, B. Nebel, SailAway: Formalizing Navigation Rules, in: Proc. of the AISB’07 Artificial and Ambient Intelligence Symposium on Spatial Reasoning and Communication, 2007.
  * [26] J. Renz, G. Ligozat, Weak Composition for Qualitative Spatial and Temporal Reasoning, in: Proc. of CP-05, 2005, pp. 534–548.
  * [27] D. Wolter, J. H. Lee, On Qualitative Reasoning about Relative Point Position, unpublished.
  * [28] R. Moratz, J. Renz, D. Wolter, Qualitative Spatial Reasoning about Line Segments, in: Proc. of ECAI 2000, 2000, pp. 234–238.
  * [29] E. G. Hoel, H. Samet, Efficient processing of spatial queries in line segment databases, in: Proc. of the 2nd Symp. on Large Spatial Databases (SSD’91), Zürich, 1991, pp. 237–255.
  * [30] A. Musto, K. Stein, A. Eisenkolb, T. Röfer, Qualitative and quantitative representations of locomotion and their application in robot navigation, in: Proc. of IJCAI-99, 1999, pp. 1067–1072.
  * [31] D. Wolter, L. J. Latecki, Shape Matching for Robot Mapping, in: C. Zhang, H. W. Guesgen, W. K. Yeap (Eds.), Proc. of 8th Pacific Rim International Conference on Artificial Intelligence, 2004, pp. 693–702.
  * [32] J. F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM (1983) 832–843.
  * [33] G. Ligozat, Qualitative triangulation for spatial reasoning, in: Proc. International Conference on Spatial Information Theory., 1993, pp. 54–68.
  * [34] A. Scivos, B. Nebel, The finest of its class: The natural point-based ternary calculus for qualitative spatial reasoning, in: Spatial Cognition, 2004, pp. 283–303.
  * [35] J. R. Hobbs, Granularity, in: Proc. of IJCAI-85, Morgan Kaufmann, 1985, pp. 432–435.
  * [36] J. Renz, F. Schmid, Customizing Qualitative Spatial and Temporal Calculi, in: Proc. of Australian Conference on Artificial Intelligence, 2007, pp. 293–304.
  * [37] F. Dylla, R. Moratz, Exploiting Qualitative Spatial Neighborhoods in the Situation Calculus, in: Proc. of Spatial Cognition 2004, 2005, pp. 304–322.
  * [38] F. Dylla, An Agent Control Perspective on Qualitative Spatial Reasoning — Towards More Intuitive Spatial Agent Development, Akademische Verlagsgesellschaft Aka GmbH, 2008.
  * [39] P. Ladkin, R. Maddux, On Binary Constraint Problems, J. ACM 41 (3) (1994) 435–469.
  * [40] R. Maddux, Relation Algebras, Stud. Logic Found. Math., Elsevier Science, 2006.
  * [41] U. Montanari, Networks of constraints: Fundamental properties and applications to picture processing, Inf. Sci. 7 (1974) 95–132.
  * [42] P. van Beek, D. W. Manchak, The design and experimental analysis of algorithms for temporal reasoning, J. Artif. Intell. Res. 4 (1996) 1–18.
  * [43] Z. Gantner, M. Westphal, S. Wölfl, GQR - A Fast Reasoner for Binary Qualitative Constraint Calculi, in: Proc. of the AAAI-08 Workshop on Spatial and Temporal Reasoning, 2008.
  * [44] J. O. Wallgrün, L. Frommberger, D. Wolter, F. Dylla, C. Freksa, Qualitative Spatial Representation and Reasoning in the SparQ-Toolbox, in: T. Barkowsky, M. Knauff, G. Ligozat, D. R. Montello (Eds.), Proc. of Spatial Cognition-06, 2006, pp. 39–58.
  * [45] J. Renz, B. Nebel, Qualitative Spatial Reasoning Using Constraint Calculi, in: M. Aiello, I. Pratt-Hartmann, J. van Benthem (Eds.), Handbook of Spatial Logics, Springer, 2007, pp. 161–215.
  * [46] G. Ligozat, J. Renz, What Is a Qualitative Calculus? A General Framework., in: Proc. of PRICAI-04, 2004, pp. 53–64.
  * [47] G. Ligozat, Categorical Methods in Qualitative Reasoning: The Case for Weak Representations, in: COSIT, 2005, pp. 265–282.
  * [48] G. Gratzer, Universal Algebra, 2nd Edition, Springer-Verlag, New York, NY, 1979\.
  * [49] L. Frommberger, J. H. Lee, J. O. Wallgrün, F. Dylla, Composition in $\mathcal{OPRA}_{m}$, Tech. Rep. 013-02/2007, University of Bremen, SFB/TR 8 Spatial Cognition (2007).
  * [50] J. O. Wallgrün, L. Frommberger, F. Dylla, D. Wolter, SparQ User Manual V0.7, User manual, University of Bremen (Jan. 2009).
  * [51] A. K. Mackworth, Consistency in networks of relations, Artificial Intelligence 8 (1977) 99–118.
  * [52] T. Nipkow, M. Paulson, L. C.and Wenzel, Isabelle/HOL — A Proof Assistant for Higher-Order Logic, Springer Verlag, 2002.
  * [53] J. Harrison, HOL Light: An Overview, in: S. Berghofer, T. Nipkow, C. Urban, M. Wenzel (Eds.), Proc. of TPHOLs-09, 2009, pp. 60–66.
  * [54] T. Mossakowski, S. Wölfl, An algebraic charaterisation of qualitative spatial and temporal calculi, draft manuscript.
  * [55] J. H. Gallier, Curves and surfaces in geometric modeling: theory and algorithms, Morgan Kaufmann, 2000.
  * [56] M. Cristani, Reasoning about Qualitative Relations between Straight Lines, Tech. rep., University of Verona (2003).
  * [57] F. Mossakowski, Algebraische Eigenschaften qualitativer Constraint-Kalküle, Master’s thesis, Universität Bremen (2007).
  * [58] R. Röhrig, Representation and processing of qualitative orientation knowledge, in: Proc. of KI-97, Lecture Notes in Comput. Sci., Springer, 1997, pp. 219–230.
  * [59] T. Soller, Spezifikation und Integration von qualitativem Orientierungswissen, Master’s thesis, Universität Bremen (2005).

## Appendix: Computation for the street network application with the SparQ
tool

In this appendix, we demonstrate how to use the publicly available SparQ QSR
toolbox [50] to compute the algebraic closure by constraint propagation for
the street network example from Section 5. For successful relative position
reasoning, the SparQ tool has to be supplied with our newly computed
$\mathcal{DRA}_{\mathit{fp}}$ composition table [50].

The local street configuration observations by the spatial agent are listed in
Section 5. The direct translation of these logical propositions into a SparQ
spatial reasoning command looks as follows232323For technical details of SparQ
we refer the reader to the SparQ manual [50]:

sparq constraint-reasoning dra-fp path-consistency "( (s7 errs s1) (s1 efbs
s2) (s8 errs s2) (s1 rele s8) (s2 rele s9) (s10 efbs s7) (s10 errs s3) (s7
srsl s3) (s3 efbs s4) (s11 efbs s8) (s11 errs s4) (s3 ells s8) (s3 rele s11)
(s8 srsl s4) (s12 efbs s9) (s4 ells s9) (s4 rele s12) (s10 srsl s5) (s5 efbs
s6) (s5 ells s11) (s11 srsl s6) (s6 ells s12) (s7 rrllP s8) (s8 rrllP s9) (s10
rrllP s11) (s11 rrllP s12) (s3 llrr- s1) (s4 llrr- s2) (s3 rrll- s5) (s4 rrll-
s6) )"

242424SparQ refers to $\mathcal{DRA}_{\mathit{fp}}$ with the symbol dra-80.
SparQ does not accept line breaks which we have inserted here for better
readability. All the data for this sample application including the new
composition table can be obtained from the URL http://www.informatik.uni-
bremen.de/~till/Oslsa.tar.gz (which also provides the composition table and
other data for the GQR reasoning tool https://sfbtr8.informatik.uni-
freiburg.de/R4LogoSpace/Resources/).

The result of this reasoning command is a refined network with the same
solution set derived by the application of the algebraic closure/constraint
propagation algorithm (see Section 2.3).

Modified network.
((S5 (EFBS) S6)(S12 (LSEL) S6)(S12 (LLFL) S5)(S11 (SRSL) S6)(S11 (LSEL)
S5)(S11 (RRLLP) S12) (S4 (RRLL-) S6)(S4 (RRLL-) S5)(S4 (RELE) S12)(S4 (RSER)
S11)(S3 (RRLL-) S6)(S3 (RRLL-) S5) (S3 (RFLL) S12)(S3 (RELE) S11)(S3 (EFBS)
S4)(S10 (RRBL) S6)(S10 (SRSL) S5)(S10 (RRLLP) S12) (S10 (RRLLP) S11)(S10
(RRRB) S4)(S10 (ERRS) S3)(S9 (LBLL) S6)(S9 (LLLL-) S5)(S9 (BSEF) S12) (S9
(LLRRP) S11)(S9 (LSEL) S4)(S9 (LLFL) S3)(S9 (LLRRP) S10)(S8 (BRLL) S6)(S8
(LBLL) S5) (S8 (RRLLP) S12)(S8 (BSEF) S11)(S8 (SRSL) S4)(S8 (LSEL) S3)(S8
(LLRRP) S10)(S8 (RRLLP) S9) (S2 (RRLL+ RRLL- RRLLP) S6)(S2 (RRLL+ RRLL- RRLLP)
S5)(S2 (RRLF) S12)(S2 (RRFR) S11)(S2 (RRLL+) S4) (S2 (RRLL+) S3)(S2 (RRRR+)
S10)(S2 (RELE) S9)(S2 (RSER) S8)(S1 (RRLL+ RRLL- RRLLP) S6) (S1 (RRLL+ RRLL-
RRLLP) S5)(S1 (RRLL+) S12)(S1 (RRLF) S11)(S1 (RRLL+) S4)(S1 (RRLL+) S3) (S1
(RRFR) S10)(S1 (RFLL) S9)(S1 (RELE) S8)(S1 (EFBS) S2)(S7 (RRLL-) S6)(S7 (BRLL)
S5) (S7 (RRLLP) S12)(S7 (RRLLP) S11)(S7 (RRBL) S4)(S7 (SRSL) S3)(S7 (BSEF)
S10)(S7 (RRLLP) S9) (S7 (RRLLP) S8)(S7 (RRRB) S2)(S7 (ERRS) S1))

SparQ can output all path-consistent scenarios (i.e. constraint networks in
base relations) via the command:

sparq constraint-reasoning dra-fp scenario-consistency all "( (s7 errs s1) (s1
efbs s2) (s8 errs s2) (s1 rele s8) (s2 rele s9) (s10 efbs s7) (s10 errs s3)
(s7 srsl s3) (s3 efbs s4) (s11 efbs s8) (s11 errs s4) (s3 ells s8) (s3 rele
s11) (s8 srsl s4) (s12 efbs s9) (s4 ells s9) (s4 rele s12) (s10 srsl s5) (s5
efbs s6) (s5 ells s11) (s11 srsl s6) (s6 ells s12) (s7 rrllP s8) (s8 rrllP s9)
(s10 rrllP s11) (s11 rrllP s12) (s3 llrr- s1) (s4 llrr- s2) (s3 rrll- s5) (s4
rrll- s6) )"

For this CSP, only three slightly different path consistent scenarios exist:

((S5 (EFBS) S6)(S12 (LSEL) S6)(S12 (LLFL) S5)(S11 (SRSL) S6)(S11 (LSEL)
S5)(S11 (RRLLP) S12) (S4 (RRLL-) S6)(S4 (RRLL-) S5)(S4 (RELE) S12)(S4 (RSER)
S11)(S3 (RRLL-) S6)(S3 (RRLL-) S5) (S3 (RFLL) S12)(S3 (RELE) S11)(S3 (EFBS)
S4)(S10 (RRBL) S6)(S10 (SRSL) S5)(S10 (RRLLP) S12) (S10 (RRLLP) S11)(S10
(RRRB) S4)(S10 (ERRS) S3)(S9 (LBLL) S6)(S9 (LLLL-) S5)(S9 (BSEF) S12) (S9
(LLRRP) S11)(S9 (LSEL) S4)(S9 (LLFL) S3)(S9 (LLRRP) S10)(S8 (BRLL) S6)(S8
(LBLL) S5) (S8 (RRLLP) S12)(S8 (BSEF) S11)(S8 (SRSL) S4)(S8 (LSEL) S3)(S8
(LLRRP) S10)(S8 (RRLLP) S9) (S2 (RRLLP) S6)(S2 (RRLLP) S5)(S2 (RRLF) S12)(S2
(RRFR) S11)(S2 (RRLL+) S4)(S2 (RRLL+) S3) (S2 (RRRR+) S10)(S2 (RELE) S9)(S2
(RSER) S8)(S1 (RRLLP) S6)(S1 (RRLLP) S5)(S1 (RRLL+) S12) (S1 (RRLF) S11)(S1
(RRLL+) S4)(S1 (RRLL+) S3)(S1 (RRFR) S10)(S1 (RFLL) S9)(S1 (RELE) S8) (S1
(EFBS) S2)(S7 (RRLL-) S6)(S7 (BRLL) S5)(S7 (RRLLP) S12)(S7 (RRLLP) S11)(S7
(RRBL) S4) (S7 (SRSL) S3)(S7 (BSEF) S10)(S7 (RRLLP) S9)(S7 (RRLLP) S8)(S7
(RRRB) S2)(S7 (ERRS) S1))

((S5 (EFBS) S6)(S12 (LSEL) S6)(S12 (LLFL) S5)(S11 (SRSL) S6)(S11 (LSEL)
S5)(S11 (RRLLP) S12) (S4 (RRLL-) S6)(S4 (RRLL-) S5)(S4 (RELE) S12)(S4 (RSER)
S11)(S3 (RRLL-) S6)(S3 (RRLL-) S5) (S3 (RFLL) S12)(S3 (RELE) S11)(S3 (EFBS)
S4)(S10 (RRBL) S6)(S10 (SRSL) S5)(S10 (RRLLP) S12) (S10 (RRLLP) S11)(S10
(RRRB) S4)(S10 (ERRS) S3)(S9 (LBLL) S6)(S9 (LLLL-) S5)(S9 (BSEF) S12) (S9
(LLRRP) S11)(S9 (LSEL) S4)(S9 (LLFL) S3)(S9 (LLRRP) S10)(S8 (BRLL) S6)(S8
(LBLL) S5) (S8 (RRLLP) S12)(S8 (BSEF) S11)(S8 (SRSL) S4)(S8 (LSEL) S3)(S8
(LLRRP) S10)(S8 (RRLLP) S9) (S2 (RRLL-) S6)(S2 (RRLL-) S5)(S2 (RRLF) S12)(S2
(RRFR) S11)(S2 (RRLL+) S4)(S2 (RRLL+) S3) (S2 (RRRR+) S10)(S2 (RELE) S9)(S2
(RSER) S8)(S1 (RRLL-) S6)(S1 (RRLL-) S5)(S1 (RRLL+) S12) (S1 (RRLF) S11)(S1
(RRLL+) S4)(S1 (RRLL+) S3)(S1 (RRFR) S10)(S1 (RFLL) S9)(S1 (RELE) S8) (S1
(EFBS) S2)(S7 (RRLL-) S6)(S7 (BRLL) S5)(S7 (RRLLP) S12)(S7 (RRLLP) S11)(S7
(RRBL) S4) (S7 (SRSL) S3)(S7 (BSEF) S10)(S7 (RRLLP) S9)(S7 (RRLLP) S8)(S7
(RRRB) S2)(S7 (ERRS) S1))

((S5 (EFBS) S6)(S12 (LSEL) S6)(S12 (LLFL) S5)(S11 (SRSL) S6)(S11 (LSEL)
S5)(S11 (RRLLP) S12) (S4 (RRLL-) S6)(S4 (RRLL-) S5)(S4 (RELE) S12)(S4 (RSER)
S11)(S3 (RRLL-) S6)(S3 (RRLL-) S5) (S3 (RFLL) S12)(S3 (RELE) S11)(S3 (EFBS)
S4)(S10 (RRBL) S6)(S10 (SRSL) S5)(S10 (RRLLP) S12) (S10 (RRLLP) S11)(S10
(RRRB) S4)(S10 (ERRS) S3)(S9 (LBLL) S6)(S9 (LLLL-) S5)(S9 (BSEF) S12) (S9
(LLRRP) S11)(S9 (LSEL) S4)(S9 (LLFL) S3)(S9 (LLRRP) S10)(S8 (BRLL) S6)(S8
(LBLL) S5) (S8 (RRLLP) S12)(S8 (BSEF) S11)(S8 (SRSL) S4)(S8 (LSEL) S3)(S8
(LLRRP) S10)(S8 (RRLLP) S9) (S2 (RRLL+) S6)(S2 (RRLL+) S5)(S2 (RRLF) S12)(S2
(RRFR) S11)(S2 (RRLL+) S4)(S2 (RRLL+) S3) (S2 (RRRR+) S10)(S2 (RELE) S9)(S2
(RSER) S8)(S1 (RRLL+) S6)(S1 (RRLL+) S5)(S1 (RRLL+) S12) (S1 (RRLF) S11)(S1
(RRLL+) S4)(S1 (RRLL+) S3)(S1 (RRFR) S10)(S1 (RFLL) S9)(S1 (RELE) S8) (S1
(EFBS) S2)(S7 (RRLL-) S6)(S7 (BRLL) S5)(S7 (RRLLP) S12)(S7 (RRLLP) S11)(S7
(RRBL) S4) (S7 (SRSL) S3)(S7 (BSEF) S10)(S7 (RRLLP) S9)(S7 (RRLLP) S8)(S7
(RRRB) S2)(S7 (ERRS) S1))
3 scenarios found, no further scenarios exist.

This result can be visualized with a diagram and can be interpreted with
respect to the goals of the reasoning task (see Section 5).