005 : 00000000000000000000
       006 : 00000000000000000000
       007 : 00000000000000000000
       008 : 00000000000000000000
       009 : 00000000000000000000
             |    .    |    .    |
       010 : 00000000000000000000
       011 : 00000000000000000000
       012 : 00000000001111110000
       013 : 00000000011111110000
       014 : 00000000011111110000
       015 : 00000000011111110000
       016 : 00000000011111111000
       017 : 00000000011111111000

     e and f equal ? 1

     contour of composition
              TRANS
             00        10        20
             |    .    |    .    |
       000 : 00000000010000001000
     R 001 : 00000000001000111000
     O 002 : 00000000001111000000
     T 003 : 00000000000000000000
       004 : 00000000000000000000
       005 : 00000000000000000000
       006 : 00000000000000000000
       007 : 00000000000000000000
       008 : 00000000000000000000
       009 : 00000000000000000000
             |    .    |    .    |
       010 : 00000000000000000000
       011 : 00000000000000000000
       012 : 00000000001111110000
       013 : 00000000010000010000
       014 : 00000000010000010000
       015 : 00000000010000010000
       016 : 00000000010000001000
       017 : 00000000010000001000

###  4 Comparison

A comparison and classification of important calculi presented in this thesis
is done in this section. This is done to help to choose the proper approach
for spatial problems. It should also show, that the Fine-grained Qualitative
Spatial Reasoning about Point Positions calculus developed in this thesis has
unique properties which are useful in some context.

####  1 TPCC vs Fspp

TPCC, which is presented in Section 3, has a predetermined set of atomic
relations. It differentiates two relative distances and eight orientations.
Additionally four linear directions that are derived from the cardinal
direction calculus (see Section 3) can be represented (straight front and
back, left and right neutral) which give the calculus nice algebraic
properties. For robotic applications these linear relations are less important
because objects will almost certainly not be located directly on the straight
line. The constant number of relatively few atomic relations enables a fast
composition using table lookup. TCPP has already been used for robotic
applications [Berndt et al., 2003]. During the test series it became apparent,
that, although it is often possible to achieve good results with TPCC, the
calculus is too coarse for robust robotic applications.

The advantages of Fspp over TPCC are quite straight forward - it supports more
orientation distinctions and more distance distinctions than TPCC. In both
calculi the relative orientation is defined over three points. Fspps absolute
distance system is favorably for robotic representations while the relative
distance in TPCC is better suited for interaction with humans.

In applications such as described in [Berndt et al., 2003] Fspp is expected to
perform significantly better if a high granularity is chosen. Due to it’s
finer grain far less ambiguous situations are expected, that are situations in
which more than one real life object is located in the acceptance areas of the
relation. In situations where no real life object is found the Fspp, the
relation can be expanded by the conceptual neighbors of the atomic relations.
This would not be possible with TPCC because it instantly would lead to very
ambiguous results.

####  2 DOI vs Fspp

The  presented in Section 4 is a very mathematical calculus. The fact that is
does not have atomic relations shows that it is not a qualitative approach.
DOIs are successfully used in the robotic context, for example in maps using
Voronoi graphs, as mentioned in Section 4.

The Fspp uses the  to calculate the composition. It is apparent that the
composition algorithm of the Fspp has a bad complexity, especially compared to
the DOI calculus who just needs one (DOI) calculation for it. But in this
paper measures have been described to keep even high resolution Fspps usable
for robotic applications. The main advantage of Fspp over the DOI approach is,
that it is, to some extent, a qualitative calculus. Thus the fine properties
described in Section 1 are still available for Fspp.

####  3 Gppc vs Fspp

Gppc (see Section 5) is quite similar to Fspp. A minor difference is, that
Gppc has fixed levels of granularity whereas the number of orientation and
distance differentiations in Fspp can be chosen freely. Gppc thus limits the
number of different resolution modes which might make it more user friendly.
The granularity of Fspp on the other hand can easily be adjusted to the users
needs, for example with many distances but few orientations.

The most important difference between the both is clearly, that Gppc uses
relative distances while Fspp has an absolute distance system. The relative
distance system of Gppc yields to quite accurate results of the unary
operations while it causes more ambiguous composition relations. The situation
for the Fspp is reverse. It has good composition results but the results of
the unary operations are quite inexact. The composition is surely the more
important operation, but I think that the disadvantages cancel each other out
since both unary and binary operations are needed during constraint based
reasoning. The relative distance system of Gppc is better suited for
interactions with humans while the absolute distances used in Fspp have
advantages for maps.

####  4 Classification of the calculi

Only few calculi are absolutely qualitative. Many have more or less
quantitative features. The transition from qualitative to quantitative
representations is gradual. Figure 4 shows a classification of different
calculi on a line. More qualitative calculi are inserted on the left while the
quantitative DOI calculus is on the right. The topological RCC is entirely
qualitative, while TPCC can be seen as more number cumbering as the cardinal
algebra because of the relatively higher number of basic relations.

This classification also corresponds to the amount of positional information
the calculi can represent (except of RCC which represents topological
knowledge). Approaches to the left are more coarse than those on the right.
Gppc and even more Fspp don’t have a fixed position on this line because of
the different levels of granularity they offer.

Quantitative vs Qualitative calculi

An extreme version of Fspp with just four orientations and one distance is
more coarse than TPCC. It thus would have to be inserted at the X1 mark in the
figure. A slightly finer Fspp with, for example, eight orientations and three
distances would be located at the X2 mark while even higher resolutions can be
at the X3 mark. DOIs will always be more accurate than Fspp with even the
highest level of granularity because they use real numbers for the orientation
and the range. Therefore X4 indicates the rightmost mark possible for Fspp. In
this classification Gppc can be located in similar regions as the Fspp.

##  Chapter 4 Conclusion

###  1 Summary

In this diploma thesis a new calculus for reasoning about qualitative
positional information with the name "Fine-grained Qualitative Spatial
Reasoning about Point Positions" (Fspp) has been developed. The basic terms
and definition have been defined in Section 1. Representation and reasoning
techniques as well as the properties of qualitative spatial reasoning are
presented there. State of the art approaches have been outlined in Section 2.
The Ternary Point Configuration Calculus (TPCC) is of special interest because
not only the Fspp calculus is derived from it. The  is important because it is
needed for the reasoning process of Fspp. The Granular Point Position Calculus
is a recently developed approach that has many similarities with the one
developed in this thesis.

The representation of the Fspp has been developed in Section 3. The absolute
distance system and the relative orientation are outlined and merged into the
ternary position representation. Unary and binary operations are needed for
the reasoning process. The algorithms for both operations are presented. The
composition makes use of the  while the unary inversion (Inv) operation makes
use of the composition. The algorithm for the unary short cut (Sc) operation
is presented so that the other operations can be calculated using Inv and Sc.
The conceptual neighborhood concept can be applied to Fspp, too.

An important improvement for the calculation of the composition is the use of
a contour trancing algorithm beforehand. The terms that have their origin in
computer graphics have been introduced and the application of the contour
tracing algorithm of Theo Pavlidis to Fspp has been explained. The
implementation of the Fspp calculus was shown to confirm the usability of this
approach. The advantages and disadvantages of the Fspp compared to other
important calculi have been pointed out and a classification was developed
over them.

###  2 Discussion and Outlook

This thesis was written with the aim to develop a new calculus for qualitative
spatial reasoning in the robotic context. An arbitrary level of granularity
for representing positional knowledge was intended. I think that the Fspp
approach at hand satisfies these expectations. It is defined over three points
and offers a free number of distance and orientation distinctions. The
relative orientation and absolute distance offer a good representation of
positional knowledge. The necessary unary operations are defined. Because of
the the absolute distance they are quite ambiguous. This is especially the
case for those operations that are defined indirectly over the Inv and Sc
operations. Future research could be done to define the unary Sci, Hm and Hmi
operations directly to get better results during the reasoning process.

In Fspp the composition is done using the DOI composition of the atomic
relations. This leads to a huge number of DOI operations for very fine-grained
representations. An effective way of reducing this number is presented by only
using the border relations during the composition. During the extensive tests
that have been done with the implementation of the Fspp it was shown that this
border-composition is as exact as a composition with all basic relations. This
is however not proved and thus a topic for future research. Related to this
topic is the question, if 8-connectivity is really sufficient for the border-
composition or if there are special cases in which 4-connectivity is required.

Another interesting topic for future research is the question, which level of
granularity and what distance systems for the Fspp representation are
advisable for typical application scenarios. Especially the distance system is
interesting and cognitive research and test series could be done to find
representations that are optimal for interaction with humans as well as for
usage in maps and other applications.

The comparison with other state of the art calculi revealed that Fspp has
unique properties which are useful in the robotic context. It also became
apparent that the recently developed Gppc has many similarities with the Fspp.
It could be interesting to find algorithms that allow to transform knowledge
represented with those calculi forth and back. That way the advantages of both
approaches could be used.

##  Chapter 5 TPCC definition

The formal definition of the TPCC relations are described by geometric
configurations on the basis of a cartesian coordinate system represented by
$R^{2}$.

Special Cases for $A=(x_{A},y_{A}),B=(x_{B},y_{B}),C=(x_{c},y_{c})$ :
$A,B\mbox{ dou }C:=x_{A}=x_{B}\neq x_{C}\wedge y_{A}=y_{B}\neq y_{C}$
$A,B\mbox{ tri }C:=x_{A}=x_{B}=x_{C}\wedge y_{A}=y_{B}=y_{C}$

For cases with $A\neq B$ a relative radius $r_{A,B,C}$ and a relative angle
$\phi_{A,B,C}$ are defined:

$r_{A,B,C}:=\frac{\sqrt{\left(x_{C}-x_{B}\right)^{2}+\left(y_{C}-y_{B}\right)^{2}}}{\sqrt{\left(x_{B}-x_{A}\right)^{2}+\left(y_{B}-y_{A}\right)^{2}}}$

$\phi_{A,B,C}:=\tan^{-1}\frac{y_{C}-y_{B}}{x_{C}-x_{B}}-\tan^{-1}\frac{y_{B}-y_{A}}{x_{B}-x_{A}}$

Spatial relations:

$\displaystyle A,B\mbox{ sam }C$ $\displaystyle:=$ $\displaystyle r_{A,B,C}=0$
$\displaystyle A,B\mbox{ csb }C$ $\displaystyle:=$ $\displaystyle
0<r_{A,B,C}<1\wedge\phi_{A,B,C}=0$ $\displaystyle A,B\mbox{ dsb }C$
$\displaystyle:=$ $\displaystyle 1\leq r_{A,B,C}\wedge\phi_{A,B,C}=0$
$\displaystyle A,B\mbox{ clb }C$ $\displaystyle:=$ $\displaystyle
0<r_{A,B,C}<1\wedge 0<\phi_{A,B,C}\leq\pi/4$ $\displaystyle A,B\mbox{ dlb }C$
$\displaystyle:=$ $\displaystyle 1\leq r_{A,B,C}\wedge
0<\phi_{A,B,C}\leq\pi/4$ $\displaystyle A,B\mbox{ cbl }C$ $\displaystyle:=$
$\displaystyle 0<r_{A,B,C}<1\wedge\pi/4<\phi_{A,B,C}<\pi/2$ $\displaystyle
A,B\mbox{ dbl }C$ $\displaystyle:=$ $\displaystyle 1\leq
r_{A,B,C}\wedge\pi/4<\phi_{A,B,C}<\pi/2$ $\displaystyle A,B\mbox{ csl }C$
$\displaystyle:=$ $\displaystyle 0<r_{A,B,C}<1\wedge\phi_{A,B,C}=\pi/2$
$\displaystyle A,B\mbox{ dsl }C$ $\displaystyle:=$ $\displaystyle 1\leq
r_{A,B,C}\wedge\phi_{A,B,C}=\pi/2$ $\displaystyle A,B\mbox{ cfl }C$
$\displaystyle:=$ $\displaystyle 0<r_{A,B,C}<1\wedge\pi/2<\phi_{A,B,C}<3/4\pi$
$\displaystyle A,B\mbox{ dfl }C$ $\displaystyle:=$ $\displaystyle 1\leq
r_{A,B,C}\wedge\pi/2<\phi_{A,B,C}<3/4\pi$ $\displaystyle A,B\mbox{ clf }C$
$\displaystyle:=$ $\displaystyle 0<r_{A,B,C}<1\wedge
3/4\pi\leq\phi_{A,B,C}<\pi$ $\displaystyle A,B\mbox{ dlf }C$ $\displaystyle:=$
$\displaystyle 1\leq r_{A,B,C}\wedge 3/4\pi\leq\phi_{A,B,C}<\pi$
$\displaystyle A,B\mbox{ csf }C$ $\displaystyle:=$ $\displaystyle
0<r_{A,B,C}<1\wedge\phi_{A,B,C}=\pi$ $\displaystyle A,B\mbox{ dsf }C$
$\displaystyle:=$ $\displaystyle 1\leq r_{A,B,C}\wedge\phi_{A,B,C}=\pi$
$\displaystyle A,B\mbox{ crf }C$ $\displaystyle:=$ $\displaystyle
0<r_{A,B,C}<1\wedge\pi<\phi_{A,B,C}\leq 5/4\pi$ $\displaystyle A,B\mbox{ drf
}C$ $\displaystyle:=$ $\displaystyle 1\leq r_{A,B,C}\wedge\pi<\phi_{A,B,C}\leq
5/4\pi$ $\displaystyle A,B\mbox{ cfr }C$ $\displaystyle:=$ $\displaystyle
0<r_{A,B,C}<1\wedge 5/4\pi<\phi_{A,B,C}<3/2\pi$ $\displaystyle A,B\mbox{ dfr
}C$ $\displaystyle:=$ $\displaystyle 1\leq r_{A,B,C}\wedge
5/4\pi<\phi_{A,B,C}<3/2\pi$ $\displaystyle A,B\mbox{ csr }C$ $\displaystyle:=$
$\displaystyle 0<r_{A,B,C}<1\wedge\phi_{A,B,C}=3/2\pi$ $\displaystyle
A,B\mbox{ dsr }C$ $\displaystyle:=$ $\displaystyle 1\leq
r_{A,B,C}\wedge\phi_{A,B,C}=3/2\pi$ $\displaystyle A,B\mbox{ cbr }C$
$\displaystyle:=$ $\displaystyle 0<r_{A,B,C}<1\wedge
3/2\pi<\phi_{A,B,C}<7/4\pi$ $\displaystyle A,B\mbox{ dbr }C$ $\displaystyle:=$
$\displaystyle 1\leq r_{A,B,C}\wedge 3/2\pi<\phi_{A,B,C}<7/4\pi$
$\displaystyle A,B\mbox{ crb }C$ $\displaystyle:=$ $\displaystyle
0<r_{A,B,C}<1\wedge 7/4\pi\leq\phi_{A,B,C}<2\pi$ $\displaystyle A,B\mbox{ drb
}C$ $\displaystyle:=$ $\displaystyle 1\leq r_{A,B,C}\wedge
7/4\pi\leq\phi_{A,B,C}<2\pi$

##  Chapter 6 DOI composition formula

The resulting DOI $d_{3}$ of a composition of the DOIs $d_{1}$ and $d_{2}$ has
its minimum and maximum radius and angle to be computed:

$min_{r_{1}^{i},r_{2}^{k},\phi_{1}^{j},\phi_{2}^{l}}r_{\sum}\left(r_{1}^{i},r_{2}^{k},\phi_{1}^{j},\phi_{2}^{l}\right)$
$max_{r_{1}^{i},r_{2}^{k},\phi_{1}^{j},\phi_{2}^{l}}r_{\sum}\left(r_{1}^{i},r_{2}^{k},\phi_{1}^{j},\phi_{2}^{l}\right)$
$min_{r_{1}^{i},r_{2}^{k},\phi_{1}^{j},\phi_{2}^{l}}\phi_{\sum}\left(r_{1}^{i},r_{2}^{k},\phi_{1}^{j},\phi_{2}^{l}\right)$
$max_{r_{1}^{i},r_{2}^{k},\phi_{1}^{j},\phi_{2}^{l}}\phi_{\sum}\left(r_{1}^{i},r_{2}^{k},\phi_{1}^{j},\phi_{2}^{l}\right)$

For
$min_{r_{1}^{i},r_{2}^{k},\phi_{1}^{j},\phi_{2}^{l}}r_{\sum}\left(r_{1}^{i},r_{2}^{k},\phi_{1}^{j},\phi_{2}^{l}\right)$
12 geometric cases have to be considered $r_{3}^{1},\ldots,r_{3}^{12}$. The
$min_{r_{1}^{i},r_{2}^{k},\phi_{1}^{j},\phi_{2}^{l}}r_{\sum}\left(r_{1}^{i},r_{2}^{k},\phi_{1}^{j},\phi_{2}^{l}\right)=min\left(r_{3}^{1},\ldots,r_{3}^{12}\right)$

$\displaystyle r_{3}^{1}$ $\displaystyle=$ $\displaystyle
r_{\sum}\left(r_{1}^{min},r_{2}^{min},0,\phi_{2}^{min}\right)$ $\displaystyle
r_{3}^{2}$ $\displaystyle=$ $\displaystyle
r_{\sum}\left(r_{1}^{min},r_{2}^{min},0,\phi_{2}^{max}\right)$ $\displaystyle
r_{3}^{3}$ $\displaystyle=$ $\displaystyle
r_{\sum}\left(r_{1}^{min},r_{2}^{max},0,\phi_{2}^{min}\right)$ $\displaystyle
r_{3}^{4}$ $\displaystyle=$ $\displaystyle
r_{\sum}\left(r_{1}^{min},r_{2}^{max},0,\phi_{2}^{max}\right)$ $\displaystyle
r_{3}^{5}$ $\displaystyle=$ $\displaystyle
r_{\sum}\left(r_{1}^{max},r_{2}^{min},0,\phi_{2}^{min}\right)$ $\displaystyle
r_{3}^{6}$ $\displaystyle=$ $\displaystyle
r_{\sum}\left(r_{1}^{max},r_{2}^{min},0,\phi_{2}^{max}\right)$ $\displaystyle
r_{3}^{7}$ $\displaystyle=$ $\displaystyle
r_{1}^{min}-r_{2}^{max}\Leftarrow\left(\phi_{2}{min}\leq-\pi\leq\phi_{2}{max}\wedge
r_{1}^{min}>r_{2}^{max}\right)$ $\displaystyle r_{3}^{8}$ $\displaystyle=$
$\displaystyle
r_{2}^{min}-r_{1}^{max}\Leftarrow\left(\phi_{2}{min}\leq-\pi\leq\phi_{2}{max}\wedge
r_{2}^{min}>r_{1}^{max}\right)$ $\displaystyle r_{3}^{9}$ $\displaystyle=$
$\displaystyle
r_{\sum}\left(r_{1}^{min},r_{1}^{min}\cos\left(\pi-\phi_{2}^{max}\right),0,\phi_{2}^{max}\right)\Leftarrow$
$\displaystyle\left(\phi_{2}{max}>\frac{\pi}{2}\wedge
r_{2}^{min}<r_{1}^{min}\cos\left(\pi-\phi_{2}^{max}\right)<r_{2}^{max}\right)$
$\displaystyle r_{3}^{10}$ $\displaystyle=$ $\displaystyle
r_{\sum}\left(r_{1}^{min},r_{1}^{min}\cos\left(\pi+\phi_{2}^{min}\right),0,\phi_{2}^{min}\right)\Leftarrow$
$\displaystyle\left(\phi_{2}{min}<-\frac{\pi}{2}\wedge
r_{2}^{min}<r_{1}^{min}\cos\left(\pi+\phi_{2}^{min}\right)<r_{2}^{max}\right)$
$\displaystyle r_{3}^{11}$ $\displaystyle=$ $\displaystyle
r_{\sum}\left(-\cos\phi_{2}^{max}r_{2}^{min},r_{2}^{min},0,\phi_{2}^{max}\right)\Leftarrow\cos\phi_{2}{max}r_{2}^{min}+r_{1}^{min}<0<\cos\phi_{2}^{max}r_{2}^{min}+r_{1}^{max}$
$\displaystyle r_{3}^{12}$ $\displaystyle=$ $\displaystyle
r_{\sum}\left(-\cos\phi_{2}^{min}r_{2}^{min},r_{2}^{min},0,\phi_{2}^{min}\right)\Leftarrow\cos\phi_{2}{min}r_{2}^{min}+r_{1}^{min}<0<\cos\phi_{2}^{min}r_{2}^{min}+r_{1}^{max}$

For
$max_{r_{1}^{i},r_{2}^{k},\phi_{1}^{j},\phi_{2}^{l}}r_{\sum}\left(r_{1}^{i},r_{2}^{k},\phi_{1}^{j},\phi_{2}^{l}\right)$
the geometric analysis shows seven distinct cases over which the maximum
$max\left(r_{3}^{13},\ldots,r_{3}^{19}\right)$ has to be computed:

$\displaystyle r_{3}^{13}$ $\displaystyle=$ $\displaystyle
r_{\sum}\left(r_{1}^{max},r_{2}^{min},0,\phi_{2}^{min}\right)$ $\displaystyle
r_{3}^{14}$ $\displaystyle=$ $\displaystyle
r_{\sum}\left(r_{1}^{max},r_{2}^{min},0,\phi_{2}^{max}\right)$ $\displaystyle
r_{3}^{15}$ $\displaystyle=$ $\displaystyle
r_{\sum}\left(r_{1}^{max},r_{2}^{max},0,\phi_{2}^{min}\right)$ $\displaystyle
r_{3}^{16}$ $\displaystyle=$ $\displaystyle
r_{\sum}\left(r_{1}^{max},r_{2}^{max},0,\phi_{2}^{max}\right)$ $\displaystyle
r_{3}^{17}$ $\displaystyle=$ $\displaystyle
r_{\sum}\left(r_{1}^{min},r_{2}^{max},0,\phi_{2}^{min}\right)$ $\displaystyle
r_{3}^{18}$ $\displaystyle=$ $\displaystyle
r_{\sum}\left(r_{1}^{min},r_{2}^{max},0,\phi_{2}^{max}\right)$ $\displaystyle
r_{3}^{19}$ $\displaystyle=$ $\displaystyle
r_{\sum}\left(r_{1}^{min},r_{2}^{max},0,0\right)\Leftarrow\phi_{2}^{min}<0<\phi_{2}^{max}$

The algorithm for
$min_{r_{1}^{i},r_{2}^{k},\phi_{1}^{j},\phi_{2}^{l}}\phi_{\sum}\left(r_{1}^{i},r_{2}^{k},\phi_{1}^{j},\phi_{2}^{l}\right)$
and
$max_{r_{1}^{i},r_{2}^{k},\phi_{1}^{j},\phi_{2}^{l}}\phi_{\sum}\left(r_{1}^{i},r_{2}^{k},\phi_{1}^{j},\phi_{2}^{l}\right)$
have been debugged. First the cases are calculated:

$\displaystyle\phi_{3}^{1}$ $\displaystyle=$
$\displaystyle\phi_{\sum}\left(r_{1}^{min},r_{2}^{min},\phi_{1}^{min},\phi_{2}^{min}\right)$
$\displaystyle\phi_{3}^{2}$ $\displaystyle=$
$\displaystyle\phi_{\sum}\left(r_{1}^{min},r_{2}^{max},\phi_{1}^{min},\phi_{2}^{min}\right)$
$\displaystyle\phi_{3}^{3}$ $\displaystyle=$
$\displaystyle\phi_{\sum}\left(r_{1}^{max},r_{2}^{min},\phi_{1}^{min},\phi_{2}^{min}\right)$
$\displaystyle\phi_{3}^{4}$ $\displaystyle=$
$\displaystyle\phi_{\sum}\left(r_{1}^{max},r_{2}^{max},\phi_{1}^{min},\phi_{2}^{min}\right)$
$\displaystyle\phi_{3}^{5}$ $\displaystyle=$
$\displaystyle\phi_{\sum}\left(r_{1}^{min},r_{2}^{max},\phi_{1}^{min},\phi_{2}^{max}\right)$
$\displaystyle\phi_{3}^{6}$ $\displaystyle=$
$\displaystyle\phi_{\sum}\left(r_{1}^{min},r_{2}^{max},\phi_{1}^{min},-\frac{\pi}{2}-\sin^{-1}\frac{r_{2}^{max}}{r_{1}^{min}}\right)\Leftarrow\phi_{2}^{min}<-\frac{\pi}{2}-\sin^{-1}\frac{r_{2}^{m}ax}{r_{1}^{min}}<\phi_{2}^{max}$
$\displaystyle\phi_{3}^{7}$ $\displaystyle=$
$\displaystyle\phi_{\sum}\left(r_{1}^{min},r_{2}^{min},\phi_{1}^{max},\phi_{2}^{max}\right)$
$\displaystyle\phi_{3}^{8}$ $\displaystyle=$
$\displaystyle\phi_{\sum}\left(r_{1}^{min},r_{2}^{max},\phi_{1}^{max},\phi_{2}^{max}\right)$
$\displaystyle\phi_{3}^{9}$ $\displaystyle=$
$\displaystyle\phi_{\sum}\left(r_{1}^{max},r_{2}^{min},\phi_{1}^{max},\phi_{2}^{max}\right)$
$\displaystyle\phi_{3}^{10}$ $\displaystyle=$
$\displaystyle\phi_{\sum}\left(r_{1}^{max},r_{2}^{max},\phi_{1}^{max},\phi_{2}^{max}\right)$
$\displaystyle\phi_{3}^{11}$ $\displaystyle=$
$\displaystyle\phi_{\sum}\left(r_{1}^{min},r_{2}^{max},\phi_{1}^{max},\phi_{2}^{min}\right)$
$\displaystyle\phi_{3}^{12}$ $\displaystyle=$
$\displaystyle\phi_{\sum}\left(r_{1}^{min},r_{2}^{max},\phi_{1}^{max},\frac{\pi}{2}+\sin^{-1}\frac{r_{2}^{max}}{r_{1}^{min}}\right)\Leftarrow\phi_{2}^{min}<\frac{\pi}{2}+\sin^{-1}\frac{r_{2}^{max}}{r_{1}^{min}}<\phi_{2}^{max}$
$\displaystyle\phi_{3}^{13}$ $\displaystyle=$
$\displaystyle\phi_{\sum}\left(r_{1}^{max},r_{2}^{min},\phi_{1}^{max},\phi_{2}^{min}\right)$
$\displaystyle\phi_{3}^{14}$ $\displaystyle=$
$\displaystyle\phi_{\sum}\left(r_{1}^{max},r_{2}^{min},\phi_{1}^{min},\phi_{2}^{max}\right)$

The values of $\phi_{3}^{1-14}$ are modified to be in the range of
$-2\pi\leq\phi_{3}^{n}\leq 0$. After that $\phi_{3}^{1-14}$ are sorted by
their value. The difference between the neighboring cases are calculated, with
the biggest and the smallest value being neighbors, too, since the values are
angles on a circle! The values that have the biggest difference between each
other are taken into account now - they are the new $\phi_{3}^{min}$ and
$\phi_{3}^{max}$ \- with the smaller value being min and the bigger being max.

If the difference between the newly calculated $\phi_{3}^{min}$ and
$\phi_{3}^{max}$ is greater than 180° the special case with $\phi^{max}=\pi$,
$\phi^{min}=-\pi$ and $r^{min}=0$ is set because the goal location can be at
the reference point now! The same holds if the following conditions are met:
$\phi_{2}^{min}\leq-\pi\leq\phi_{2}^{max}$ or $r_{1}^{min}\leq r_{2}^{min}\leq
r_{1}^{max}$ or $r_{1}^{min}\leq r_{2}^{min}\leq r_{1}^{max}$.

##  Chapter 7 Topology definition

Definition: topology, topological space: Let $U$ be a non-empty set, the
universe. A topology on $U$ is a family $T$ of subsets of $U$ that satisfies
the following axioms:

  1. 1.

$U$ and $\emptyset$ belong to $T$,

  2. 2.

the union of any number of sets in $T$ belongs to $T$,

  3. 3.

the intersection of any two sets of $T$ belongs to $T$.

A topological space is a pair $\left[U,T\right]$. The members of $T$ are
called open sets.

In a topological space $\left[U,T\right]$, a subset $X$ of $U$ is called a
closed set if its complement $X^{c}$ is an open set, i.e. if $X^{c}$ belongs
to $T$. By applying the DeMorgan laws, we obtain the properties of closed
sets:

  1. 1.

$U$ and $\emptyset$ are closed sets,

  2. 2.

the intersection of any number of closed sets is a closed set,

  3. 3.

the union of any two closed sets is a closed set.

If the particular topology $T$ on a set $U$ is clear or not important, the $U$
can be referred to as the topological space. Closely related to the concept of
an open set is that of a neighborhood.

Definition: neighborhood, neighborhood system. Let $U$ be a topological space
and $p\in U$ be a point in $U$.

  * •

$N\subset U$ is said to be a neighborhood of $p$ if there is an open subset
$O\subset U$ such that $p\in O\subset N$.

  * •

The family of all neighborhoods of $p$ is called the neighborhood system of
$p$, denoted as $N_{p}$.

A neighborhood system $N_{p}$ has the property that every finite intersection
of members of $N_{p}$ belongs to $N_{p}$. Based on the notion of neighborhood
it is possible to define certain points and areas of a region.

Def interior, exterior, boundary, closure. Let $u$ be a topological space,
$X\subset U$ be a subset of $U$ and $p\in U$ be a point in U.

  * •

$p$ is said to be an interior point of $X$ if there is a neighborhood $N$ of
$p$ contained in $X$. The set of all interior points of $X$ is called the
interior of $X$, denoted $i(X)$.

  * •

$p$ is said to be an exterior point of $X$ of there is a neighborhood $N$ of
$p$ that contains no point of $X$. The set of all exterior points of $X$ is
called the exterior of $X$, denoted $e(X)$.

  * •

$p$ is said to be a boundary point of $X$ if every neighborhood $N$ of $p$
contains at least one point in $X$ and one point is not in $X$. The set of all
boundary points of $X$ is called the boundary of $X$, denoted $b(X)$.

  * •

The closure of $X$, denoted $c(X)$, is the smallest closed set which contains
$X$.

The closure of a set is equivalent to the union of its interior and its
boundary. Every open set is equivalent to its interior, every closed set is
equivalent to its closure.

Def regular open, regular closed. Let $x$ be a subset of a topological space
$U$.

  * •

$X$ is said to be regular open if $X$ is equivalent to the interior of its
closure, i.e. $X=i\left(c\left(X\right)\right)$.

  * •

$X$ is said to be regular closed if $X$ is equivalent to the closure of its
interior, i.e. $X=c\left(i\left(X\right)\right)$.

Two sets of a topological space are called separated if the closure of one set
is disjoint from the other set, and vice-versa. A subset of a topological
space is internally connected if it cannot be written as a union of two
separated sets.

Topological spaces can be categorized according to how points or closed sets
can be separated by open sets. Different possibilities are given by the
separation axioms $T_{i}$. A topological space $U$ that satisfies axiom
$T_{i}$ is called a $T_{i}$ space. Three of these separation axioms which are
important for this work are the following:

$T_{1}$ : Given any two distinct points $p,q\in U$, each point belongs to an
open set which does not contain the other point. $T_{2}$ : Given any two
distinct points $p,q\in U$, there exist disjoint open sets
$O_{p},O_{q}\subseteq U$ containing $p$ and $q$ respectively. $T_{3}$ If $X$
is a closed subset of $U$ and $p$ is a point not in $X$, there exist disjoint
open sets $O_{X},O_{p}\subseteq U$ containing $X$ and $p$ respectively.

A connected space is a topological space which cannot be partitioned into two
disjoint open sets, a topological space is regular, if it satisfies axioms
$T_{2}$ and $T_{3}$.

## References

  * [Allen, 1983] Allen, J. F. (1983).  Maintaining knowledge about temporal intervals.  Commun. ACM, 26(11):832–843.
  * [Arkin, 2000] Arkin, C. (2000).  Behavior-based robotics.  In Intelligent Robots and Autonomous Agents, Cambridge, Mass. MIT Press.
  * [Bennett, 1996] Bennett, B. (1996).  Modal logics for qualitative spatial reasoning.  In Bulletin of the IGPL, page 4(1):23.
  * [Berndt et al., 2003] Berndt, T., Büschenfeld, P., Kay, M., Liberman, D., Meyer, A., Moratz, R., Plagge, J., Schwertfeger, S., Vierhuff, T., and Winterber, A. (2003).  Natürlichsprachliche steuerung von räumlich agierenden robotern.  Technical report, University Bremen.
  * [Braitenberg, 1984] Braitenberg, V. (1984).  Vehicles: Experiments in Synthetic Psychology.  MIT Press.
  * [Brauer et al., 1997] Brauer, W., Eisenkolb, A., Hernández, D., Krieg-Brückner, B., Musto, A., Nebel, B., Renz, J., Schill, K., Schlieder, C., Schmid, U., Wiebrock, S., and Wysotzki, F. (1997).  Qualitative and quantitative approaches to spatial inference and the analysis of movements.  Technical report.
  * [Clementini et al., 1997] Clementini, E., Felice, P. D., and Hernandez, D. (1997).  Qualitative representation of positional information.  Artif. Intell., 95(2):317–356.
  * [Cohn and Hazarika, 2001] Cohn, A. G. and Hazarika, S. M. (2001).  Qualitative spatial representation and reasoning: An overview.  In Fundamenta Informaticae, volume 46, pages 2–32. IOS Press.
  * [Dylla and Moratz, 2004] Dylla, F. and Moratz, R. (2004).  Empirical complexity issues of practical qualitative spatial reasoning about relative position.  In Workshop on Spatial and Temporal Reasoning at ECAI.
  * [Egenhofer and Mark, 1995] Egenhofer, M. J. and Mark, D. M. (1995).  Naive geography.  In Frank, A. U. and Kuhn, W., editors, Spatial Information Theory - A Theoretical Basis for GIS (COSIT’95), pages 1–15. Springer, Berlin, Heidelberg.
  * [Frank, 1991] Frank, A. U. (1991).  Qualitative spatial reasoning about cardinal directions.  In Proceedings of the 7th Austrian Conference on Artificial Intelligence, pages 157–167.
  * [Freksa, 1991] Freksa, C. (1991).  Qualitative spatial reasoning.  In Mark and Frank, editors, Cognitive and Linguistic Aspects of Geographic Space, pages 361–372, Dordrecht. Kluwer Academic Publishers.
  * [Freksa, 1992a] Freksa, C. (1992a).  Temporal reasoning based on semi-intervals.  Artificial Intelligence, 54:199 – 227.
  * [Freksa, 1992b] Freksa, C. (1992b).  Using orientation information for qualitative spatial reasoning.  In A. U. Frank, I. Campari, U. F., editor, Theories and Methods of Spatial-Temporal Reasoning in Geographic Space, pages 162 – 178, Berlin. Springer.
  * [Freksa et al., 2000] Freksa, C., Moratz, R., and Barkowsky, T. (2000).  Schematic maps for robot navigation.  In Spatial Cognition II, Integrating Abstract Theories, Empirical Studies, Formal Methods, and Practical Applications, pages 100–114, London, UK. Springer-Verlag.
  * [Guesgen, 1989] Guesgen, H.-W. (1989).  Spatial reasoning based on allen’s temporal logic.  Tr-89-049, ICSI, Berkeley.
  * [Hernández, 1994] Hernández, D. (1994).  Qualitative Representation of Spatial Knowledge.  Springer-Verlag New York, Inc.
  * [Hernández, 1995] Hernández, D. (1995).  Qualitative distances.  In COSIT. Springer.
  * [Isli, 1999] Isli, A. (1999).  Qualitative spatial representation and reasoning: Algebraic models for relative position.  Fbi-hh-m-284/99, Universität Hamburg, FB Informatik, Hamburg.
  * [Isli and Moratz, 1999] Isli, A. and Moratz, R. (1999).  Constraint propagation of positional information.  Technical report, Contribution to the Colloquium on Spatial Inference, Freiburg.
  * [Jungert, 1993] Jungert, E. (1993).  Symbolic spatial reasoning on object shapes for qualitative matching.  In Frank, A. and Campari, I., editors, Spatial Information Theory: A theoretical basis for GIS, Proc. COSIT’93, pages 444–462. Springer-Verlag.
  * [Ligozat, 1993] Ligozat, G. (1993).  Qualitative triangulation for spatial reasoning.  In Cosit, Berlin. Springer.
  * [Ligozat, 1998] Ligozat, G. (1998).  Reasoning about cardinal directions.  In Journal of Visual Languages and Computing.
  * [Liu and Daneshmend, 2004] Liu, J. and Daneshmend, L. K. (2004).  Spatial Reasoning and Planning.  Advanced Information Processing. Springer, Berlin.
  * [Moratz, 2003] Moratz, e. a. (2003).  Qualitative spatial reasoning about relative position.  In C. Freksa, W. Brauer, C. H. and Wender, K., editors, Lecture Notes in Artifcial Intelligence 2685: Spatial Cognition III, pages 385–400, Berlin/ Heidelberg. Springer Verlag.
  * [Moratz, 2005] Moratz, R. (2005).  A granular point position calculus.  Technical report, Report Series of the Transregional Collaborative Research Center SFB/TR 8 Spatial Cognition, Universität Bremen / Universität Freiburg.
  * [Moratz et al., 2000] Moratz, R., Renz, J., and Wolter, D. (2000).  Qualitative spatial reasoning about line segments.  In Horn, W., editor, Proceedings of the 14th European Conference on Artificial Intelligence, Amsterdam. IOS Press.
  * [Moratz and Wallgrün, 2003a] Moratz, R. and Wallgrün, J. O. (2003a).  Propagation of distance and orientation intervals.  In Proceedings of 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 3245–3250.
  * [Moratz and Wallgrün, 2003b] Moratz, R. and Wallgrün, J. O. (2003b).  Spatial reasoning about relative orientation and distance for robot exploration.  In Kuhn, W., Worboys, M., and Timpf, S., editors, Spatial Information Theory: Foundations of Geographic Information Science. Conference on Spatial Information Theory (COSIT), Lecture Notes in Computer Science, pages 61–74. Springer-Verlag; D-69121 Heidelberg, Germany; http://www.springer.de.
  * [Musto et al., 1999] Musto, A., Stein, K., Eisenkolb, A., and Röfer., T. (1999).  Qualitative and quantitative representations of locomotion and their application in robot navigation.  In IJCAI-99, pages 1067 – 1072.
  * [Pavlidis, 1982] Pavlidis, T. (1982).  Algorithms for Graphics and Image Processing.  Computer Science Press.
  * [Randell et al., 1992] Randell, D. A., Cui, Z., and Cohn, A. G. (1992).  A spatial logic based on regions and connection.  In B. Nebel, W. Swartout, C. R., editor, Principles of Knowledge Representation and Reasoning: Proceedings of the 3rd International Conference, pages 165–176, Cambridge.
  * [Renz, 2002] Renz, J. (2002).  Qualitative Spatial Reasoning with Topological Information.  Springer.
  * [Röfer, 1999] Röfer, T. (1999).  Route navigation using motion analysis.  In Freksa, C. and Mark, D., editors, COSIT 1999, pages 21 – 36, Berlin. Springer.
  * [Vorweg et al., 1997] Vorweg, C., Socher, G., Fuhr, T., Sagerer, G., and Rickheit, G. (1997).  Projective relations for 3d space: Computational model, application and psychological evaluation.  In AAAI, pages 159 – 164.
  * [Wallgrün, 2002] Wallgrün, J. O. (2002).  Exploration und pfadplanung für mobile roboter basierend auf generalisierten voronoi-graphen.  Diploma thesis, Universität Hamburg.
  * [Walter, 1950] Walter, W. G. (1950).  An imitation of life.  In Scientific American, volume 182, pages 42 – 45.
  * [Werner et al., 2000] Werner, S., Krieg-Brückner, B., and Herrmann, T. (2000).  Modelling navigational knowledge by route graphs.  In Spatial Cognition II, Integrating Abstract Theories, Empirical Studies, Formal Methods, and Practical Applications, pages 295–316, London, UK. Springer-Verlag.
  * [Zimmermann and Freksa, 1996] Zimmermann, K. and Freksa, C. (1996).  Qualitative spatial reasoning using orientation, distance, and path knowledge.  Applied Intelligence, 6(1):49–58.