\chapter*{Table of Acronyms}
-\begin{acronym}[opcode]
+\begin{acronym}[CDROM]
\acro{8N1}{8 data bits, no parity, 1 start/stop bit}
\acro{CDROM}{Compact Disc Read Only Memory}
\acro{DC}{Direct Current}
-\chapter{Conclusions}
-\todo{. }
+\chapter{Conclusion and Future Work}
+The previous chapters have presented the original motion behavior of the
+Roomba, besides two different approaches to improve dead reckoning. This goal
+could be reached only in parts, for laminated floors using the mean correction
+in Experiment~2. However, there is still many potential to work towards that
+goal.
+
+The set of measured data in this work was relatively small to serve as a
+good representation of the world. Only two types of floors were used, and a
+fixed set of parameters for the movements. One possibility here is to widen the
+data set, probably using not only fixed values but maybe also a stochastic
+approach to determine the input values. Furthermore, only the target distance
+resp. orientation, and the velocity were considered as factors to affect the
+measured value. There are still much other factors to consider, for example the
+voltage and capacity of the Roomba's internal battery. Also, the Roomba can
+move not only in straight lines and turn on the spot, but also drive arcs.
+Additionally, it is not sure how different robots or different Roomba
+models behave when it comes to movement.
+
+As mentioned in Section~\ref{sec:exp2:results}, a quadratic regression could be
+applied to the data, which results in a better fit function and a closer
+approximation to the measured data. This may probably improve the mean
+correction approach from Experiment~2, and also correct errors better when
+driving on carpet floors.
\ No newline at end of file
-\chapter{Experiment 1: Original Movement Behaviour}
+\chapter{Experiment 1: Original Movement Behavior}
\label{sec:exp1}
-In the first experiment, the Roomba's original movement behaviour is
+
+The concepts described in the previous chapter are now used to set up a test
+series with the purpose to measure the error in the Roomba's movement and
+to improve its accuracy.
+
+In the first experiment, the Roomba's original movement behavior was
measured to get an overview of the errors that occur while moving, and to
establish a pool of data for correction approaches to work on later.
There was no error correction involved (apart from any possible error
\caption{Measuring turn angles with laser pointer\label{fig:laserpointer}}
\end{figure}
-The test equipment consisted of a small x86 \index{netbook} netbook which was
+The test equipment consisted of a small x86 netbook\index{netbook} which was
mounted on an iRobot Roomba~530\index{Roomba} robot, as seen in
Figure~\ref{fig:roombasetup}. The netbook controlled the Roomba over a
\acs{USB}-to-serial converter plugged into the \ac{ROI}\index{Roomba
Open Interface} port on the Roomba, and hosted as the environment for
executing the Wiselib \index{Wiselib} code.
-In this experiment, the Roomba started right off with the full velocity the
-movement was executed with; so there was no control to adhere a constant
-acceleration when starting or stopping the movement. As mentioned before, due to
-limitations in the \ac{ROI}\index{Roomba Open Interface} it is only possible to
-explicitly start and stop the Roomba's movements at different times, so the
-Wiselib's implementation of the Roomba control code first starts the Roomba's
-movement, keeps track of the turned angle and dcovered distance, and then stops
-the Roomba if these values exceed the target values.
+In this experiment, the Roomba started and stopped with the full velocity the
+movement was executed with; so there was (ideally speaking) an infinite
+acceleration and deceleration at the start and the end of the movement. As
+mentioned before, due to limitations in the \ac{ROI}\index{Roomba Open
+Interface} it is only possible to explicitly start and stop the Roomba's
+movements at different times, so the Wiselib's implementation of the Roomba
+control code first starts the Roomba's movement, keeps track of the turned angle
+and covered distance, and then stops the Roomba if these values exceed the
+target values.
The tests were done in two atomic drive modes: letting the Roomba walk a
specific straight distance with a specific velocity in its viewing direction and
letting it turn on the spot with a specific velocity about a specific angle.
Each of the two modes was carried out on two different floor types\index{floor
-type}, a laminated floor and a carpet floor, to see if the movement behaviour
+type}, a laminated floor and a carpet floor, to see if the movement behavior
significantly depended on the floor type. The side brush was removed, since the
Roomba tends to turn slightly towards the left when driving straight on a
carpet floor. Without the side brush, this was not the case.
-The actual travelled distance of the straight drive tests were determined using
+The actual traveled distance of the straight drive tests were determined using
a measuring tape with an accuracy of 1~mm. Only the distance in the Roomba's
original viewing direction was considered, as it turned out that the offset
perpendicular to the viewing direction and a possible shift in orientation were
For the straight drive tests, the arrays with predefined values were:\\
\begin{tabular}{@{}ll@{}}
-Distances: & 20, 50, 100, 200, 500, 1000, 2000, and 4000~mm \\
-Velocities: & 20, 50, 70, 100, 150, 200, 300, and 400~mm/s
+Distances: & 20, 50, 100, 200, 500, 1000, 2000 and 4000~mm \\
+Velocities: & 20, 50, 70, 100, 150, 200, 300 and 400~mm/s
\end{tabular}
For the turn tests, the arrays with predefined values were: \\
\begin{tabular}{@{}ll@{}}
-Turn angles: & 5, 15, 30, 45, 90, 120, 180, 360, 530, and 720~degree \\
-Velocities: & 20, 50, 70, 100, 150, 200, 300, and 400~mm/s
+Turn angles: & \phantom{0}5, 15, 30, 45, 90, 120, 180, 360, 530 and 720~degree\\
+Velocities: & 20, 50, 70, 100, 150, 200, 300 and 400~mm/s
\end{tabular}
According to the implementation of the Wiselib Roomba control, the velocities
-were given in mm/sec and referred to the distance the wheels travelled when the
+were given in mm/s and referred to the distance the wheels traveled when the
Roomba turned on the spot, which was a circle of 230~mm in diameter.
\section{Results}
\label{exp1:results}
The following graphs show the difference from the measured value to the input
value for driving or turning with different velocities. Positive values mean
-that the Roomba had turned too much or travelled more than the target value,
-negative values mean that the Roomba had turned or travelled too less. The
+that the Roomba had turned too much or traveled more than the target value,
+negative values mean that the Roomba had turned or traveled less. The
plots show multiple test runs; given are the minimum, the maximum and the
arithmetic mean\index{arithmetic mean} of all results for a data point.
\begin{figure}[p!]
\centering
\includegraphics[width=\textwidth]{images/iz250flur_drive_data.pdf}
- \caption{Original behaviour on laminated floor, straight drive movements
+ \caption{Original behavior on laminated floor, straight drive movements
\label{fig:orig:lam:drive}}
\end{figure}
\begin{figure}[p!]
\centering
\includegraphics[width=\textwidth]{images/iz250flur_turn_data.pdf}
- \caption{Original behaviour on laminated floor, turn movements
+ \caption{Original behavior on laminated floor, turn movements
\label{fig:orig:lam:turn}}
\end{figure}
\begin{figure}[p!]
\centering
\includegraphics[width=\textwidth]{images/seminarraum_drive_data.pdf}
- \caption{Original behaviour on carpet floor, straight drive movements
+ \caption{Original behavior on carpet floor, straight drive movements
\label{fig:orig:carpet:drive}}
\end{figure}
\begin{figure}[p!]
\centering
\includegraphics[width=\textwidth]{images/seminarraum_turn_data.pdf}
- \caption{Original behaviour on carpet floor, turn movements
+ \caption{Original behavior on carpet floor, turn movements
\label{fig:orig:carpet:turn}}
\end{figure}
carpet floor when the distance grows.
On the other hand, rising the velocity always seems to cause the
-error to increase.
+error to increase. This illustrates the effect of accumulating errors which
+represents the crucial drawback of dead reckoning\index{dead reckoning}.
The same effects also apply for turn tests. Additionally, there could be errors
-resulting from false assumptions about the Roomba's wheel base\index{wheel base}
-diameter, resulting in false calculations of the circle the Roomba's wheels
+resulting from false assumptions about the Roomba's wheel base\index{wheel
+base}, resulting in bogus calculations of the circle the Roomba's wheels
describe while turning, and therefore leading to false results.
+
+In the following, two approaches to correct errors and improve the accuracy of
+the movement are presented.
-\chapter{Experiment 2: Movement Behaviour with Mean Correction}
+\chapter{Experiment 2: Movement Behavior with Mean Correction}
\todo{}
\label{sec:exp2}
could originate from imprecise measurement of the Roomba's internal sensors or
in the Wiselib implementation. So a natural approach to correct this sort of
errors would be to average the results for each data point from Experiment 1,
-find a function that fits the mean measured error depending of the
-target velocity and target distance or angle as well as possible, and then
-adapting either one of the target parameters so that the resulting movement
+find a function that fits the mean measured error depending on the
+target velocity and target distance or angle as well as possible, and then to
+adapt either one of the target parameters so that the resulting movement
would most likely be the desired target value. In this experiment however, only
the target distance resp. the target angle was adjusted, while the velocity
remained unadjusted.
then used in the algorithm to calculate the adapted target distance or angle.
\section{Setup}
-The hardware setup was exactly the same as in Experiment 1. However, in this
-experiment the application \prog{mean\_correction\_test} was used to measure
-data. It did exactly the same as the application from Experiment 1, except that
-it adapted the target value according to the method described above.
+The hardware setup was exactly the same as in Experiment~1. However, in this
+experiment the application \prog{mean\_correction\_test} (described in
+Section~\ref{sec:impl:mean} was used to measure data.
\section{Results}
+\label{sec:exp2:results}
\begin{figure}[p!]
\centering
\includegraphics[width=\textwidth]{images/iz250flur_drive-mean_data.pdf}
- \caption{Behaviour with mean correction on laminated floor, straight drive
+ \caption{Behavior with mean correction on laminated floor, straight drive
movements}
\end{figure}
\begin{figure}[p!]
\centering
\includegraphics[width=\textwidth]{images/iz250flur_turn-mean_data.pdf}
- \caption{Behaviour with mean correction on laminated floor, turn movements}
+ \caption{Behavior with mean correction on laminated floor, turn movements}
\end{figure}
\begin{figure}[p!]
\centering
\includegraphics[width=\textwidth]{images/seminarraum_drive-mean_data.pdf}
- \caption{Behaviour with mean correction on carpet floor, straight drive
+ \caption{Behavior with mean correction on carpet floor, straight drive
movements}
\end{figure}
\begin{figure}[p!]
\centering
- \includegraphics[width=\textwidth]{images/seminarraum_drive-mean_data.pdf}
- \caption{Behaviour with mean correction on carpet floor, turn movements}
+ \includegraphics[width=\textwidth]{images/seminarraum_turn-mean_data.pdf}
+ \caption{Behavior with mean correction on carpet floor, turn movements}
\end{figure}
-results better than in experiment 1, very accurate for laminate floor, carpet
-floor more spread but still kind of in the middle and less deviation from ideal
-value.
-\todo{!!!}
\ No newline at end of file
+For laminated floors, the results are actually better than in Experiment~1,
+apart from a huge increase of the absolute error for small input values (50~cm,
+5 and 20 degrees). As the error for this values is far into the negative
+range, it means that the Roomba has even turned to or driven in the wrong
+direction. The reason for that is most probably the fit function, which is below
+zero for these target values. Apart from that, higher target values or
+velocities correlate with a higher (absolute) error, just as already mentioned
+for the original behavior, which is caused by accumulating errors. However,
+when it comes to different velocities, the error is not as far distributed as it
+is for the original behavior. This makes the behavior of the Roomba more
+predictable over different velocities. Apparently, mean correction
+significantly improves the accuracy of the Roomba's general movement in this
+case.
+
+For carpet floors, the data shows not much difference to the original
+behavior, apart from the already mentioned large absolute error for small
+target values. Due to the steep drop of the error for large target values, it
+could maybe help to apply a quadratic regression for the determination of a fit
+function, in order to better represent the measured data. However, this is a
+matter for more detailed research and is not covered in this thesis.
-\chapter{Experiment 3: Movement Behaviour with Constant Start/Stop
+\chapter{Experiment 3: Movement Behavior with Constant Start/Stop
Acceleration}
\label{sec:exp3}
-\todo{}
-\section{Setup}
-algorithm: slowly accelerate at start over a time of 1 second, decelerate at
-stop. no mean correction.
-
-approach: correct slippage on the floor
+The third experiment tried to correct the slippage of the wheels on the floor
+that possibly occurred in Experiment~1 when the Roomba suddenly started or
+stopped. Due to inertia, the Roomba's movements are delayed and the influence
+of that effect could be large enough to be measurable.
-setup same as in experiment 1 and 2, application on netbook was
-\prog{soft\_start\_test}.
+To achieve that, the Roomba's velocity was not changed abruptly, as in
+Experiment~1, but it was increased and decreased at a constant rate over a
+time interval of 1~second. No mean correction was involved as in Experiment~2.
-expectations \& were they fulfilled?
+\section{Setup}
+Again, the hardware setup was the same as already in the other two
+experiments. The application used for measuring data was
+\prog{soft\_start\_test}, which is described in Section~\ref{sec:impl:soft}.
\section{Results}
\begin{figure}
\centering
\includegraphics[width=\textwidth]{images/iz250flur_drive-soft_data.pdf}
- \caption{Behaviour with constant start/stop acceleration, laminated floor,
+ \caption{Behavior with constant start/stop acceleration, laminated floor,
straight drive movements}
\end{figure}
\begin{figure}
\centering
\includegraphics[width=\textwidth]{images/iz250flur_turn-soft_data.pdf}
- \caption{Behaviour with constant start/stop acceleration, laminated floor,
+ \caption{Behavior with constant start/stop acceleration, laminated floor,
turn movements}
\end{figure}
\begin{figure}
\centering
\includegraphics[width=\textwidth]{images/seminarraum_drive-soft_data.pdf}
- \caption{Behaviour with constant start/stop acceleration, carpet floor,
+ \caption{Behavior with constant start/stop acceleration, carpet floor,
straight drive movements}
\end{figure}
\begin{figure}
\centering
\includegraphics[width=\textwidth]{images/seminarraum_turn-soft_data.pdf}
- \caption{Behaviour with constant start/stop acceleration, carpet floor,
+ \caption{Behavior with constant start/stop acceleration, carpet floor,
turn movements}
\end{figure}
-same or even worse deviation as in original behaviour...
-
-\todo{statistical values, stddev?}
+The data shows mostly no difference to the original behavior from
+Experiment~1. Apparently inertia and slippage do not influence the accuracy of
+the movement.
\ No newline at end of file
This chapter describes the implementation that was used for the aforementioned
experiments. It consists of the measuring programs themselves, which use the
Wiselib Roomba Control, and are written in C++. Additionally, there are several
-Bash and Perl scripts to help with the analysis of the measured data.
+Bash and Perl scripts to assist in the analysis of the measured data.
All code used for this thesis resides in the Wiselib source tree\footnote{see
\url{https://github.com/ibr-alg/wiselib/}, or the \acs{CDROM} attached at the
-end of this book} in the directory \filepath{apps/pc\_apps/roomba\_tests}.
+end of this thesis} in the directory \filepath{apps/pc\_apps/roomba\_tests}.
\section{Measuring}
\label{sec:impl:measuring}
All measured data is written to a log file in the current directory whose name
is based on the type of experiment performed. Every line in that log file
describes one measurement made by the user, and consists of pairs of the form
-\code{key=value}, separated of by whitespace. In particular, the data on each
+\code{key=value}, separated by white space. In particular, the data on each
line are (with key name, in the order of appearance on the line):
\begin{enumerate}[noitemsep]
\item\texttt{svn:} the \ac{SVN} or Git revision the program was compiled from
determined by the program in automatic mode)
\item\texttt{measured\_angle:} the actual turned angle of the Roomba in degree
(measured by the user)
- \item\texttt{velocity:} (the velocity in mm/s sent to the Roomba via the
+ \item\texttt{velocity:} the velocity in mm/s sent to the Roomba via the
\ac{ROI} \cmd{Drive} command (given by the user in manual mode, or
determined by the program in automatic mode)
\end{enumerate}
\includegraphics[width=0.9\textwidth]{images/Implementation-Diagram.pdf}
\caption[File structure of the measuring implementation]{Simplified file
structure of the measuring implementation\label{fig:impl:struct}\\
- yellow: common files used for all three experiments; green: files for
- Experiment~1; blue: files for Experiment~2; red: files for Experiment~3.\\
- An arrow from node $x$ to node $y$ means ``$y$ depends from $x$''.}
+ yellow: common files used for all three experiments; \\
+ green: files for Experiment~1; blue: files for Experiment~2; \\red: files
+ for Experiment~3.\\
+ An arrow from node $x$ to node $y$ is to be read as ``$y$ depends from
+ $x$''.}
\end{figure}
Figure~\ref{fig:impl:struct} shows the file layout of the measuring
-implementation. It reuses components whereever possible, and therefore
+implementation. It reuses components where ever possible, and therefore
consists of three parts (green, blue, red) specific for the three performed
experiments (see Sections~\ref{sec:exp1}, \ref{sec:exp2} and~\ref{sec:exp3}), as
well as a common part (yellow), which contains the elements of the
\paragraph{Input dialog for measured orientation values}
\hyphenation{Tar-get-Va-lue-In-put-Dia-log}
+
+\begin{figure}
+ \centering
+ \includegraphics[width=0.4\textwidth]{images/target_value_input_dialog.png}
+ \caption{The \class{TargetValueInputDialog}}
+\end{figure}
+
The class \class{TargetValueInputDialog}, which is an implementation of a simple
dialog box using the Qt widget framework, resides in the files
\file{target\_value\_input\_dialog.cc} and
of test performed and if automatic or manual mode, the ground type, and the
Roomba's ID, or the \code{-{}-help} switch to display a usage message.
-After that, it instanciates and initializes a \class{RoombaModel} instance,
+After that, it instantiates and initializes a \class{RoombaModel} instance,
while also providing for the needed instances of the \concept{Timer} concept
and the \concept{SerialCommunication} concept, which is needed for the serial
communication with the Roomba. Furthermore, an instance of
Due to an implementation detail inside the \class{RoombaModel} class, the sensor
data returned by the class itself may be corrupt if it is read while new sensor
data packets arriving from the Roomba are processed. To prevent this corruption,
-we register a callback function which gets called everytime new sensor data is
+we register a callback function which gets called every time new sensor data is
available (i.~e. the sensor data packets have been fully processed, which is
every 15~ms as we are using the \cmd{Stream} command), and let the callback
function perform a deep copy of the sensor values we are interested in.
Section~\ref{sec:exp1:setup}, and slightly scrambled to ensure independence of
the measurements. Furthermore, the file name for the log file to record the
measured values is determined from the operation mode, the type of experiment
-performed, and the Unix timestamp\footnote{The Unix timestamp is a signed
+performed, and the Unix time stamp\footnote{The Unix time stamp is a signed
integer which is defined as the seconds elapsed since January 1st, 1970, 0:00
\ac{UTC}}. To ease measurement of angles, if the type of experiments are turn
movements, the user is prompted once to input the current orientation of the
\item \textbf{In manual mode:} Prompt the user for a new pair of velocity and
input value \\
\textbf{In automatic mode:} For each pair of velocity and input value
- specified in the previously definied arrays, do the following:
+ specified in the previously defined arrays, do the following:
\item Carry out the specified movement using the \class{ControlledMotion}
instance
\item Prompt the user for the measured value using the
\subsection{Implementation for Experiment~2:
Application \prog{mean\_correction\_test}}
+\label{sec:impl:mean}
Additionally, the program \prog{mean\_correction\_test} for Experiment~2 uses
the class \class{CorrectedMeanMotion} from \file{corrected\_mean\_motion.h}.
This class adapts the input value according to the fit function determined from
\subsection{Implementation for Experiment~3: Application
\prog{soft\_start\_test}}
+\label{sec:impl:soft}
As the implementation for Experiment~2, the application \prog{soft\_start\_test}
which is built from the file \file{soft\_start.cc} has the same basic layout as
\file{main.cc} from Experiment~1. As previously, it defines a custom movement in
\paragraph{\prog{graph.sh}}
This wrapper script uses Gnuplot to create interactive 3-dimensional plots of
-the original behaviour from Experiment~1, and also includes the fit function as
+the original behavior from Experiment~1, and also includes the fit function as
determined by \ac{GNU} through linear regression. For each pair of ground type
(carpet floor, laminate floor) and experiment type (straight movement, turn on
spot), it opens a Gnuplot window containing a graph with the target value on the
\chapter{Introduction}
-\todo{motivation, importance of dead reckoning, what was done?}
+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.
-\chapter{Related work}
-Borenstein, Feng \cite{umbmark}: Benchmark for mobile robots
+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.
-Yamauchi \cite{yamauchi}: Dead-reckoning with Evidence Grids
+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.
-Chong, Kleeman \cite{chongkleeman}: High-precision odometry
+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}
-\todo{!!!}
\ No newline at end of file
+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.
\newcommand{\ignoreoutput}[1]{\setbox\trashbox\vbox{#1}}
\author{Roland Hieber}
-\title{Error modeling of an autonomous, mobile robot}
+\title{Error Modeling of an Autonomous, Mobile Robot}
% \date{July 9, 2011}
\makeatletter
{\large by}\\[.5em]
{\large \@author}\\[7em]
{\large \bf Thesis Advisors:}\\[.5em]
- {\large Prof.~Dr.~S\'andor Fekete}\\
+ {\large Prof.~Dr.~S\'andor P\@. Fekete}\\
{\large Dr.~Alexander Kröeller}\\
{\large Dipl-Inf.~Tobias Baumgartner}\\
\par
\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.
+In the following, basic concepts used in this thesis are described. In
+particular, there is a description of the iRobot Roomba, its hardware
+and software, and an overview of the Wiselib algorithm library that is used to
+control the Roomba.
\input{roomba}
\input{wiselib}
-
-Now that the prerequisites have been explained, it is time to assemble them all
-together and \todo{and what}
\ No newline at end of file
\section{iRobot Roomba}
Originally, the \definition{Roomba} is an autonomous vacuum cleaning robot,
-manufactured by the US-based company \definition{iRobot}. The 500 series
+manufactured by the US-American 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.
The top side features several buttons which vary between the different models,
most notably the ``Clean'' and ``Spot'' buttons for manual control of the
cleaning routine, and the ``Dock'' button to send the Roomba to its home base.
-The cover on the top side can be removed, and covers the connector for
+The cover on the top side can be removed to reveal the connector for
the \ac{ROI} which is discussed in Section~\ref{sec:roi}.
On the side, a socket for a coaxial \acs{DC} power connector can be found, which
\paragraph{Wheels}
The Roomba has two rubberized main wheels which are positioned slightly behind
-the centerline, so the Roomba leans forward due to gravity, and a small caster
+the center line, so the Roomba tilts forward due to gravity, and a small caster
on the front to prevent it from sliding on the floor. The space between the
-cmainenter of the main wheels (the \definition{wheel base}) is 230~mm. The main
+center of the main wheels (the \definition{wheel base}) is 230~mm. 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
\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
+the Roomba consists of a crescent-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
+photo-electrical interrupters. 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.
+of them allows the Roomba to recognize objects in a maximum 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
+unbalances it. This leads to the effect that 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.
+floor. It 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 \ac{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
+find its home base and charge itself when it has finished cleaning or is about
+to run out
+of energy. Therefore, it uses a special infrared sensor mounted on top of the
+Roomba, which 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{Original Behaviour}
+\subsection{Behavior}
+\paragraph{Original Behavior}
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
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
+comes to cleaning rooms, but cleaning time is not necessarily the constraining
factor, and the robot still saves the human some time.
\paragraph{Roomba Open Interface}
speaks a specified protocol, called the \acused{ROI}\definition{Roomba Open
Interface} (\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.
+and cleaning behavior.
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:
+his movement and cleaning behavior. However, the user is able to read the
+internal sensors in this mode. 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
0x83 // Safe command
\end{verbatim}
Then, additional commands can be sent over the \ac{ROI}, like actuator commands
-for controlling the Roomba's driving behaviour.
+for controlling the Roomba's driving behavior.
\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 this 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
+two bytes specify the velocity with which the Roomba's center point should travel
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
+Roomba's center point 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
+500~mm/s, with negative values implying backwards movement -- it is to be noted
+however that velocities between -10~mm/sec and 10~mm/sec are ignored, since the
+wheel motors cannot operate with that small velocities. 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
+Roomba turn towards the right, whereas positive values make it turn towards the
left. There are also four special values for the radius: \magicvalue{1} makes
the Roomba turn on the spot in counter-clockwise direction, \magicvalue{-1}
makes the Roomba turn on the spot in clockwise direction, and
0x80, 0x00 // parameter radius: special value "straight"
\end{verbatim}
-A little disadvantage of the \ac{ROI} \cmd{Drive} command is that the robot is
+A slight disadvantage of the \ac{ROI} \cmd{Drive} command is that the robot is
modeled without a time awareness. 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
sensors.
\paragraph{Input commands}
-The Roomba~500 series features a total of 49 different sensor values. Among the
+The Roomba~500 series features a total of 49 different sensor values. Beyond 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. Anyway, 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
+possibility to query the traveled 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.
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
+behavior, 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
+sensor values in packets using the byte format\\
+\verb|0x13|, $\mathtt{n, p_1, v(p_1), p_2, v(p_2), \ldots, p_n, v(p_n),
+c}$, where:
+\begin{itemize}\setlength{\itemsep}{0pt}
+ \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}
+\end{itemize}
Example: The following byte sequence requests data from the left cliff
-signal (packet~ID \magicvalue{0x1d}) and virtual wall sensor (packet~ID
+signal (sensor packet~ID \magicvalue{0x1d}) and virtual wall sensor (packet~ID
\magicvalue{0x0d}):~\cite{irobot-oi}
\begin{verbatim}
0x94, // Stream command
0x1d, 0x0d // parameter: request packets 0x1d and 0x0d
\end{verbatim}
The Roomba then would return a packet with the following format every
-15~ms:\label{sec:roi-stream-packet}~\cite{irobot-oi}
+15~ms:\label{sec:roi-stream-packet}
\begin{verbatim}
0x13, // Header byte
0x05, // 5 bytes following, except checksum
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 = 0x100
+0xb6 // Checksum: 0x5+0x1d+0x2+0x19+0xd+0x0+0xb6 = 0x100
\end{verbatim}
\paragraph{Latency}
the motion. At 19,200 baud, mode \ac{8N1}, the transfer of a 5-byte \cmd{Drive}
command needs $(5 \times 9) \div 19200 = 2.3$~ms. The time the Roomba
logic needs to process the command is not mentioned in the \ac{ROI}
-Specification, and there was no way to measure it sufficiently. It is however
-short enough that a human would describe it as ``instant''.
+Specification, and there was no way to measure it precisely. %It is however
+%short enough that a human would describe it as ``instant''.
The same latency of course also exists in the opposite directions when the
Roomba is sending sensor data to the user. However, the sensor data are sent by
the Roomba every 15~ms (which is the internal speed at which the data is
updated from the sensors) and according to the wheel's maximum velocity of
-500~mm/s (which means that a sensor data packet is received every $0.03$~mm when
-driving at this speed), this is acceptible for real-time evaluation of the data.
-
+500~mm/s (which means that a sensor data packet is received every $7.5$~mm when
+driving at this speed), this is acceptable for real-time evaluation of the data.
+\paragraph{Usage}
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
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.
+platforms are diverse sensor node platforms, like iSense\footnote{see
+\url{http://www.coalesenses.com/index.php?page=isense-hardware}},
+Contiki\footnote{\url{http://www.sics.se/contiki/about-contiki.html}}, and
+TinyOS\footnote{\url{http://www.tinyos.net/}}, but there is as well support for
+the diverse x86-compatible Personal Computer platforms, and the Shawn sensor
+network simulator\footnote{\url{http://shawn.sourceforge.net}}.
\subsection{Architecture}
\label{sec:wiselib:arch}
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. Furthermore, this also allows usage on
-platforms which do not have support for C++, as the bytecode generated by the
+platforms which do not support C++, as the byte code generated by the
compiler does not include C++ specific extensions (no virtual function tables,
and templates are resolved at compile time) and can be linked against any
Standard C Library.
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
+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.
+that their radio model also implements the same radio concept used by the
+routing algorithm.
\begin{figure}
\centering
\paragraph{External Interface}
The \definition{External Interface} provides access to the underlying \ac{OS},
-like iSense, Contiki, Shawn\ldots and defines concepts like a Radio or a Timer.
+like iSense, Contiki, Shawn, etc. and defines concepts like a radio or a timer.
Thus, the concepts are as generic as possible to match all supported operating
systems and provide a light-weight abstraction to the underlying \ac{OS}. These
-concepts sometimes extend the generic concepts, for example there is a TxRadio
+concepts sometimes extend the generic concepts. As an example there is a
+concept \concept{TxRadio}
which has the ability to set the transmission power on the radio. The models
-(for example an iSenseRadioModel or a ShawnTimerModel) implement these concepts
+(for example an \class{iSenseRadioModel} or a \class{ShawnTimerModel}) implement
+these concepts
on the specific operating system, and can be passed around as template
parameters.
\paragraph{Internal Interface}
The \definition{Internal Interface} defines concepts and models for data
-structures that can be used in algorithms. This allows to specialize for
-restricted platforms; for instance a wireless sensor node without dynamic memory
+structures that can be used in algorithms. This allows the specialization for
+platforms with more restricted resources; for instance a wireless sensor node
+without dynamic memory
management can use a static implementation of lists and other containers,
-whereas a full-grown desktop can use the dynamic implementation provided by the
+whereas a full-grown desktop machine can use the dynamic implementation provided
+by the
C++ \ac{STL}. For this purpose, the Wiselib also contains the
\acused{pSTL}\definition{pico Standard Template Library} (\acs{pSTL}) which
implements a subset of the \ac{STL} without the use of dynamic memory
\end{description}
\paragraph{ControlledMotion model}
-On top of the \concept{TurnWalkMotion} and \concept{Odometer} concepts builds
-the \class{ControlledMotion} model. It takes implementations of each of these
+The \class{ControlledMotion} model builds on top of the \concept{TurnWalkMotion}
+and \concept{Odometer} concepts. It takes implementations of each of these
concepts as template parameters and extends the simple turn-and-walk paradigm by
-a temporal dimension, which let the robot stop after a specific time interval.
+a temporal dimension, which makes the robot stop after a specific time interval.
In particular, it provides the following methods:
\begin{description}\item
\begin{description} % to match with the indentation level above
The class first registers a callback function at the given Odometer instance,
and then uses its distance and angle values to control the robot over the
-TurnWalkMotion instance. Everytime the state of the robot changes (i.~e. new
-data from its sensors are received), it compares the new actual values with the
+TurnWalkMotion instance. Every time the state of the robot changes (i.~e. new
+data from its sensors is received), it compares the new actual values with the
target values given by the user through the functions above, and if the actual
values exceed the target values, the robot is stopped.
particular, it manages the serial communication with the Roomba and translates
the function calls \fnfont{turn()}, \fnfont{move()} and \fnfont{stop()} of the
TurnWalkMotion concept to the according parameters for the \ac{ROI} \cmd{Drive}
-command, reads a subset of the Roomba's sensors and presents the sensor data to
-the user, and, while implementing the Odometer concept, calculates the covered
-distance and angle from the Roomba's right and left wheel rotations.
+command. It also reads a subset of the Roomba's sensors and presents the sensor
+data to the user. Finally, while implementing the Odometer concept, it
+calculates the covered distance and angle from the Roomba's right and left wheel
+rotations.
The sensor data is read from the Roomba using the \cmd{Stream} command on the
\ac{ROI}, which results in a sensor data packet (see Section
3 header/checksum bytes. There has currently been no success yet in
communicating at the higher speed of 115,200 baud.
-Also there has been research to use the distance and angle values that the
+Also research has been done to use the distance and angle values that the
Roomba itself provides (sensor packet~IDs \magicvalue{0x13} and
\magicvalue{0x14}). However, according to the \ac{ROI} Specification these
values are integer values, and the value is reset to zero every time it is read.
By using the \cmd{Stream} command on the \ac{ROI} and therefore reading these
values every 15~ms, the Roomba cannot move fast enough to increment these values
-to \magicvalue{1}, so everytime \magicvalue{0} is read. It is obvious that
+to \magicvalue{1}, so every time \magicvalue{0} is read. It is obvious that
these sensor values are not suited for such rapid evaluations, and can only be
used for larger distances and angles. Nevertheless, since the Wiselib Roomba
control needs to keep track of the Roomba's current position and orientation as
working with the Roomba's wheel encoder counts (sensor packet~IDs
\magicvalue{0x2b} and \magicvalue{0x2c}) has proven itself quite acceptable.
After a few test runs, the number of encoder counts per~mm for straight
-walks turned out as $2.27$, and for turning on the spot, $2.27 \times 115 =
+walks turned out to be $2.27$, and for turning on the spot, $2.27 \times 115 =
261.05$ encoder counts per radian, which is the number of encoder counts per~mm
-multiplicated with half the Roomba's wheelbase. So when new sensor data is read
+multiplied by half the Roomba's wheelbase. So when new sensor data is read
each 15~ms, the RoombaModel implementation calculates the \concept{Odometer}
distance and angle from these values.
projects / bachelor-thesis / written-stuff.git / commitdiff