\chapter{Introduction}
The world nowadays depends more and more on robots. But not only stationary
robots, like those used in assembly lines, improve our lives and make it
possible to excel at industrial and exploratory challenges. Also, mobile robots
could be an integral part of our world in the near future. Not only are they
predestined for dangerous duties which would much certainly cost lives if
humans had to do them, like detecting disarming mines in war zones, they are
also much more specialized to their challenges.

However, in most cases, mobile robots become useless if they don't know anything
about their environment. Especially their location is a basic to know,
and particularly autonomous mobile robots benefit from the knowledge about their
location. This knowledge gives them the ability to create a map of their
environment, to find ways between certain points of interest, and to contact
both human beings as well as other robots.

There are several methods to achieve knowledge about the location of mobile
robots. At first, they can be classified as absolute or relative methods. For
example, absolute positioning methods rely on a fixed, distributed
infrastructure which allows the robot to determine its absolute location inside
a specific region. For example, the \ac{GPS} only works because satellites orbit
around the earth and constantly send a signal. There are also approaches using
navigation beacons or by matching the observed environment to a previously
known map.

All of that positioning methods however depend on the infrastructure, which can
be expensive to deploy and maintain. Also, most of the algorithms used are
fairly complex and need highly specialized hardware or a certain computing
power, and therefore cannot (yet) be used in real time. And sometimes, they are
even more imprecise than relative approaches.~\cite{umbmark}

Relative positioning methods however only yield a position relative to a
defined point, and mostly can be applied with cheap hardware. The best-known
approach in this field is \definition{dead reckoning}, which computes the
position relative to an initial starting point by considering the covered
distance and course the robot has moved. In the case of mobile robots, the
covered distance can be simply computed in real time from the revolution of its
wheels, or by accelerometers the robot may be equipped with.

The advantage of dead reckoning is that it is easy and fast to implement.
However, there is also a drawback. The vehicle's current position is based on
its previous position, and distance and course measurement is mostly imprecise.
the error of the calculated position grows with time. In order to maintain a
certain accuracy, countermeasures need to be taken to keep the error as small as
possible.

In this thesis, the popular Roomba manufactured by the iRobot Corporation is
used as an instance for an mobile robot, since it is cheap, small, and can be
simply controlled over a serial interface. The Roomba is accompanied with a
netbook sitting on top of it, on which runs an application to represent the
autonomous aspect. This application in turn uses the Wiselib library to control
the Roomba.

In the first experiment, the Roomba's movement behaviour will be analyzed. Then,
two different easy approaches for minimizing the positioning error are presented
and tested for their suitability.

\chapter{Related Work}
There are already some results on the problem. Yamauchi proposes to use dead
reckoning with evidence grids to represent the robot's view of the
world.~\cite{yamauchi} Evidence grids are subdivisions of the Cartesian space
into cells, and each cell is assigned a probability value representing the
estimated probability of occupancy by the robot. The robot now explores its
environment, using its sensors to detect moving and fixed obstacles, and finally
tries to find its home location again using dead reckoning. On its way back, it
creates a second evidence grid. Finally, both grids are incorporated by an
algorithm, which estimates the error in orientation and translation.
Experimental results with a real robot showed a maximum translation error of 28\%
and an orientation error of 25\%.

Chong and Kleeman use high-precision odometry to increase the accuracy
of position estimation by dead reckoning.~\cite{chongkleeman} They succeeded in
building a odometry system that is as good as the best reported system, but can
be fabricated at low-cost.

Borenstein and Feng design a benchmark for mobile robots.~\cite{umbmark} They
show how to measure systematic and non-systematic errors, and how to correct
them.
