[bachelor-thesis/written-stuff.git] / Ausarbeitung / preliminaries.tex

\chapter{Preliminaries}
This chapter describes the preliminary topics. \todo .

\section{Dead reckoning}
The process of \definition{dead reckoning} describes an inexpensive method for
relative positioning by computing a vehicle's position from an initial
starting position and the covered distance and course it 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. However, since the vehicle's current position is based on its previous
position, and the distance measurement may be imprecise, dead reckoning has the
disadvantage that errors in position calculation can cumulate and the error
of the calculated position grows with time.

Another approach to determine a vehicle's position is absolute positioning, for
example satellite-based, over navigation beacons or by map matching. Still,
these techniques are rather expensive to deploy, cannot (yet) be used in real
time, or are even impreciser than relative approaches\cite{umbmark}, so dead
reckoning can still be useful for the time being.

In the following, the iRobot Roomba serves as an example of an autonomous,
mobile agent, which can be used to implement dead reckoning for lack of either
built-in absolute positioning and other relative approaches.

\section{iRobot Roomba 500}
Originally, the \definition{Roomba} is an autonomous vacuum cleaning robot,
manufactured by the US-based company \definition{iRobot}. The 500 series
currently represents the third generation of iRobot's cleaning robots, and the
first generation of robots controllable over an external interface.

\subsection{Hardware design}
\todo{diagram?}
\paragraph{Wheels}
The Roomba lives in a cylindrical case with diameter of about 34~cm and height
of about 7~cm. It has two main wheels which are positioned slightly behind the
centerline, so the Roomba leans forward due to gravity, and a small caster on
the front to prevent it from sliding on the floor. The main wheels can be
controlled over two independent motors, each one allowing to turn the connected
wheel with a minimum of 10~mm/s and a maximum of 500~mm/s in each direction.
One of the main wheel motors consumes about 300~mA in their slowest rotation
speed, and about 1000~mA when driving with normal speed. Each wheel is also
equipped with a drop sensor that tells if the respective wheel has dropped into
a hole or similar, and does not reach the ground anymore. These sensors are
realized with a spring pushing the wheel towards the ground, with the spring
force adjusted to the Roomba's weight, and a micro switch which triggers if the
wheel drops below a specified level. Furthermore, both wheels feature rotating,
toothed discs, which in conjunction with an LED and a photo-electric resistor
act as an optical interrupter. This system can be used to measure the wheel's
current speed by counting the optical interruptions the wheel causes while
moving.

\paragraph{Brushes}
In addition to the wheel motors, the Roomba has a motor which operates the
vacuum brush, and a small motor on the front connected to a side brush, to allow
cleaning of room corners.

\paragraph{Bumper shield}
Since the main movement direction in normal operation is forward, the front of
the Roomba consists of a crecent-shaped bumper shield which contains several
sensors. This bumper\index{Roomba!bumper} is spring-loaded and on the one
hand absorbs shock to reduce damage, on the other hand, it allows the Roomba to
detect obstacles in front of it, both via infrared sensors as well as by
mechanical means. There are two sensors for mechanical bump detection, located
30° to the left and to the right of the bumper's center, each implemented as
photo-electrical interruptors. Additionally, six infrared sensors are unevenly
distributed over the bumper, facing away from it in a star-like manner. Each one
of them allows the Roomba to recognize objects in a maxmimum distance of 10~cm.
Finally, the bumper shield contains four infrared sensors facing downwards,
acting as cliff sensors \index{Roomba!cliff sensor} to recognize steps or
similar chasms which could be dangerous for the Roomba to drive towards.

The back part of the Roomba contains the main vacuum brush\index{Roomba!vacuum
brush}, and the reservoir for holding dirt. Both of them can be removed, though
the removal of the main brush reduces the Roomba's weight and slightly
unbalances the Roomba so the springs used for the wheel drop sensors are not in
balance anymore and push the Roomba upwards, so it tilts more to the front when
accelerating forwards. There is also a sensor on the underside
\index{Roomba!dirt sensor} for detecting particularly dirty regions of the
floor, which is implemented as a capacitive touch sensor.

\paragraph{Battery}
The battery\index{Roomba!battery} is placed in the front part behind the bumper,
it is a rechargeable NiMH battery and holds a capacity of 3300~mAh which lasts
for about 90 to 120 minutes under normal operation. The Roomba can also find its
home base and charge itself when it has finished cleaning or runs out of energy
by using a special infrared sensor mounted on top of the Roomba. This sensor can
see in all directions and is able to detect the home base by looking for a
special infrared signal the home base\index{Roomba!home base} emits. The same
principle is used for so-called "`virtual walls"'\index{virtual wall} which can
be placed by the user in regions the Roomba should not move into.

\subsection{Behaviour}
\paragraph{Intended Behaviour}
The Roomba normally follows its own, non-customizable algorithm to detect dirt
and clean rooms. It is kind of a random walk\index{random walk}, controlled by
the internal logic, which tries to keep the Roomba away from dangers like
stairs and walls (by evaluating the cliff and bump sensors), and direct it to
the more dusty regions of the room (by using the dirt sensor). The random walk
concept allows a more or less complete coverage of the room, given the time for
cleaning is large enough, while at the same only needing very little information
about the environment. Of course, that concept is not very efficient when it
comes to cleaning rooms, but cleaning time is not neccessarily the constraining
factor, and the robot still saves the human some time.

\paragraph{Roomba Open Interface}
However, robots of the Roomba 500 series are also easily controllable over a
serial port, which provides a two-way communication at 5~V TTL levels over a
Mini-DIN connector, with a speed of either 19,200 or 115,200 Baud. Over this
serial port, the Roomba speaks a specified protocol, called the
\ignoreoutput{\ac{ROI}}\definition{\acl{ROI}} (\acs{ROI})~\cite{irobot-oi},
which allows the user to interact with the robot's internal logic, reading its
sensor values, and control its movements and cleaning behaviour.

After starting the communication with the Roomba by sending the \cmd{Start}
command, the robot is in a state called \definition{Passive mode}. In this mode,
the user cannot control the robot by himself, but the internal logic defines
icants behaviour. However, the user is able to read the internal sensors. The
\ac{ROI} then allows the user to set the Roomba into two different modes:
\begin{itemize}
  \item In \definition{Safe mode}, the Roomba monitors the wheel drop, cliff
    and internal charger sensors, and reverts into Passive mode if safety
    conditions occur, so the Roomba is not harmed.
  \item In \definition{Full mode}, the user has full control over the Roomba,
    and has to take care not to harm the Roomba by evaluating the wheel drop,
    cliff and internal charger sensors by himself.
\end{itemize}

In particular, every command is assigned an \ac{opcode} of one byte length,
followed by a fixed amount of bytes as parameters which depend on the opcode.
For example, to start the communication with the Roomba, the \cmd{Start}
command has to be sent, which has the \opcode{0x80} and takes no parameters. The
\cmd{Safe} command to put the Roomba into safe mode has \opcode{0x83}, and like
the \cmd{Full} command with \opcode{0x84}, it takes no parameters.

For example, to start the communication with the Roomba and set it into Safe
mode, one would send the following bytes over the serial interface:
\begin{verbatim}
0x80,             // Start command
0x83              // Safe command
\end{verbatim}
The, additional commands can be sent over the \ac{ROI}, like actuator commands
for controlling the Roomba's driving behaviour.

\paragraph{Actuator commands}
The \ac{ROI} specifies various actuator commands to control the Roomba's wheels,
brushes and \ac{LED} displays, and let the Roomba play tunes. However, the
central command needed for the experiments in thie thesis is the \cmd{Drive}
command, \opcode{0x89}, which takes 4 additional bytes as parameter: the first
two bytes specify the velocity that the Roomba's centerpoint should travel with
while driving, and the third and fourth bytes specify the radius of the arc the
Roomba's centerpoint should describe. The Roomba then calculates the required
right and left wheel velocities internally without further interference of the
user.

The velocity is interpreted in mm/s, the value can range from -500~mm/s to
500~mm/s, with negative values implying backwards movement. The radius is
interpreted in mm, ranging from -2000~mm to 2000~mm. Negative values make the
Roomba turn toward the right, whereas positive values make it turn toward the
left. There are also four special values for the radius: \magicnumber{1} makes
the Roomba turn on the spot in counter-clockwise direction, \magicnumber{-1}
makes the Roomba turn on the spot in clockwise direction, and
\magicnumber{0x7fff} and \magicnumber{0x8000} make him drive straight.

For example, to drive straight with a velocity of 1000~mm, one would send the
following bytes over the serial interface:
\begin{verbatim}
0x89,             // Drive command
0x03, 0xe8        // parameter velocity: 0x03e8 == 1000
0x80, 0x00        // parameter radius: special value "straight"
\end{verbatim}

A little disadvantage of the \ac{ROI} \cmd{Drive} command is that the robot is
modeled as a state machine. In the previous example, the Roomba would keep on
driving until it runs out of energy, or a safety condition occurs which causes
the Roomba to revert into Passive mode, or a new \cmd{Drive} command with the
velocity parameter set to zero is sent. Thus, if the user wants to drive a
specific distance, he has to calculate the time the robot needs to travel that
distance, measure the time, and stop the robot after that time interval has
passed. When using incorrect clocks, or when using inaccurate timers, this can
lead to errors in movement. Because of that, it is appropriate to monitor the
Roomba's movement, for example with its internal sensors.

\paragraph{Input commands}
The Roomba~500 series features a total of 49 different sensor values. Among the
sensors mentioned above, there are also some internal values concerning battery
charge, capacity, and temperature, motor currents, and even some more (or less)
useful variables like the characters read from the infrared remote control, the
current \ac{ROI} mode or the currently playing song. Nevertheless, there is
also the possibility to query the travelled distance, the turned angle and the
internal encoder counts ("`ticks"') for the left and right wheel. Each sensor
value is 1 or 2 bytes long and is assigned a specific \definition{packet ID}.
Some packet IDs also describe groups of multiple sensor values sent together.

Sensor values can be retrieved either by explicit polling or by enabling a
stream of values that is sent every 15~ms. Explicit polling works through the
\cmd{Sensors} command (\opcode{0x8e}), which takes the packet ID of a single
sensor as parameter, or through the \cmd{Query List} (\opcode{0x95}) command,
which takes multiple packet IDs headed by the total number of requested packets
as parameter. Both of these functions send back the requested values directly.

By using the \cmd{Stream} command (\opcode{0x94}), it is possible to receive
the requested sensor values every 15~ms. This is very convenient for real-time
behaviour, when the sensor values have to be evaluated very often. As the
\cmd{Query List} command, the \cmd{Stream} command takes the total number of
packet IDs followed by the requested packet IDs as parameter. It sends back the
sensor values in packets using the following format:\\
\verb|0x13|, $n, p_1, v(p_1), p_2, v(p_2), \ldots, p_n, v(p_n), c$\\
where:
\begin{description}
  \item[$n$] is the number of bytes sent back, excluding $n$ and $c$,
  \item[$p_i$] is a requested packet ID, $i = 1, \ldots, n$
  \item[$v(p_i)$] is the value of the packet with the packet ID $p_i$
  \item[$c$] is a checksum, with
    $\sum_{i=1}^n\left(p_1 + v(p_1)\right) + c + n \equiv 0 \mod 256$
\end{description}

Example: The following byte sequence requests data from the left cliff
signal (packet~ID \magicnumber{0x1d}) and virtual wall sensor (packet~ID
\magicnumber{0x0d}):
\begin{verbatim}
0x94,         // Stream command
0x02,         // parameter: 2 packets following
0x1d, 0x0d    // parameter: request packets 0x1d and 0x0d
\end{verbatim}

The Roomba then returns the following bytes every 15~ms:
\begin{verbatim}
0x13,         // Header byte
0x05,         // 5 bytes following, except checksum
0x1d,         // Packet ID 0x1d following
0x02, 0x19,   // Data for Packet ID 0x1d (2 byte)
0x0d,         // Packet ID 0x1d following
0x00,         // Data for Packet ID 0x0d (1 byte)
0xb6          // checksum: 0x5 + 0x1d + 0x2 + 0x19 + 0xd + 0x0 + 0xb6 = 256
\end{verbatim}

In our setup, an iRobot Roomba~530 is used as an instance of an autonomous,
mobile robot to conduct the experiments described afterwards. For that, the
Roomba's movements are controlled over a netbook mounted on top of the Roomba
(cf.~Figure~\ref{fig:roombasetup}), which is running Wiselib code. The Wiselib
code in turn uses the \ac{ROI} and especially the \cmd{Stream} and
\cmd{Drive} command to control the Roomba.

\section{Wiselib}
The \definition{Wiselib}\cite{wiselib} is a C++\index{C++} algorithm library for
sensor
networks, containing for example algorithms for routing, localization and time
synchronization, and is strongly focused on portability and cross-platform
development. In particular, it allows the user to develop applications that run
on different hardware platforms without the need to change the code, and it
strongly uses C++ templates to achieve that feature. Amongst the supported
platforms are diverse sensor node platforms, like iSense, Contiki and TinyOS,
but there are as well implementations for the diverse x86-compatible Personal
Computer platforms, and the Shawn sensor network simulator.

\subsection{Architecture}
\paragraph{Concepts and Models}
Wiselib makes strong uses of \definition{concepts} and \definition{models} as
central design objects. Concepts serve as an informal description of interfaces,
only existent in documentation, defining expected parameters and types. Models
however implement these interfaces in C++ code while fulfilling their
specification. The Wiselib algorithms can in turn rely on the concepts as a
generic specification, and take models as template parameters to use their
functionality, so a function call will be immediately resolved to a specific
model at compile time without the need for an additional function call as it is
the case with virtual inheritance.

This makes cross-platform development easily possible. For example, to implement
a routing algorithm, one can rely on the concept of a Radio to send and receive
data packets, without needing to implement code specific to the used radio
hardware. The users of that routing algorithm can now choose which radio model
they want to use, according to their needs and the underlying hardware, provided
that their radio model also implements the same Radio concept that the routing
algorithm uses.

\begin{figure}
  \centering
  \includegraphics[width=.8\textwidth]{images/Wiselib-Arch.pdf}
  \caption{Wiselib architecture\label{fig:wiselib-arch}}
\end{figure}
Besides algorithms, the Wiselib also consists of two other main parts: the
internal interface and the external interface (see Figure
\ref{fig:wiselib-arch}).

\paragraph{}

\subsection{Roomba}
Moreover, the Wiselib includes code to control the iRobot
Roomba\index{Roomba} over a
serial interface, and getting access to its internal sensor data, using the
iRobot Roomba Open Interface mentioned earlier.

\todo{cite Wisebed book chapter on Roomba code}
\todo{which roomba sensors were used?}