d
d d d Institut fur Informatik derd d d d
d d
d d d
d d d d
d d d Technischen Universit at Munc hen
Experience-Based Control and Coordination
of Autonomous Mobile Systems
in Dynamic Environments
Dissertation
Sebastian Buckd
d d d Institut fur Informatik derd d d d
d d
d d d
d d d d
d d d Technischen Universit at Munc hen
Experience-Based Control and Coordination
of Autonomous Mobile Systems
in Dynamic Environments
Sebastian Buck
Vollst andiger Abdruck der von der Fakult at fur Informatik der Technischen Uni-
versit at Munc hen zur Erlangung des akademischen Grades eines
Doktors der Naturwissenschaften (Dr. rer. nat.)
genehmigten Dissertation.
Vorsitzender: Univ.-Prof. Dr. Alois Knoll
Prufer der Dissertation:
1. Univ.-Prof. Dr. Bernd Radig
2. Univ.-Prof. Dr. Gun ther Palm,
Universit at Ulm
Die Dissertation wurde am 25.03.2003 bei der Technischen Universit at Munc hen
eingereicht und durch die Fakult at fur Informatik am 09.12.2003 angenommen.Abstract
Many real-time machine control skills are too complex and laborious to be coded
by hand. Preferably, such skills are acquired by learning algorithms. Suitable
algorithms should learn automatically and based on experience from interaction
with the machine’s environment. But unfortunately, typical learning methods
for real world machine control tasks have a number of problems: Huge high-
dimensional state spaces complicate inductive learning, and it might be di cult
to get a su cien t amount of appropriate training data for learning either because
it takes too long or because it is extremely di cult to obtain good examples for
learning from exploration. Furthermore, most current learning algorithms rely on
a discrete MDP-model of the continuous state space, su er from the incremental
summation of errors during learning, and neglect the existence of undesirable
states.
The idea behind our approach of experience-based control is to exploit trajecto-
ries of successful explorations to approximate a value-function for the state space.
To overcome the lack of training data we employ a realistic neural simulation of
the machine’s dynamics and introduce adequate exploration techniques, such as
backward exploration, to acquire learning data. The combination of di eren t
exploration techniques allows for the integration of various types of initial know-
ledge and undesirable states can be integrated in the learning model. Since the
majority of machine control tasks in technical applications shows deterministic
behavior { or at least a unimodal probability distribution with a small variance
{ it is possible to use a simple projection-function instead of a complex MDP-
model that was originally designed for discrete states. Our algorithms operate
directly in a continuous state space and perform a number of explorations before
we exploit the data. This is the main reason why our approach is robust against
the incremental summation of noise which is often encountered in conventional
learning algorithms. For the practical and e cien t approximation of continuous
functions we employ neural networks and networks of radial basis functions. Our
methods have successfully been applied to numerous navigation tasks and tasks
of situation dependent algorithm-selection.
iiiZusammenfassung
Viele Maschinensteuerungsaufgaben sind so komplex, dass es zu aufw andig w are,
sie von Hand zu programmieren. Im Idealfall wird hier das gewunsc hte Verhalten
durch Lernalgorithmen erreicht. Geeignete Algorithmen mussen automatisch und
basierend auf Erfahrungen aus der Interaktion mit der Umwelt der Maschine ler-
nen. Leider zeigen viele g angige Lernalgorithmen fur reale Maschinensteuerungs-
aufgaben einige Probleme: Sehr gro e und hochdimensionale Zustandsr aume er-
schweren induktives Lernen, und es kann schwierig sein, eine ausreichende Menge
geeigneter Trainingsdaten zu bekommen. Ursache dafur kann einerseits ein Man-
gel an Zeit sein; andererseits ist es vielleicht schwierig, ub erhaupt gute Beispiele
zum Lernen zu nden. Darub er hinaus basieren die meisten gebr auchlichen Lern-
algorithmen auf einem diskreten MDP-Modell des kontinuierlichen Zustandsrau-
mes, leiden unter der inkrementellen Summierung von Fehlern w ahrend des Ler-
nens und vernachl assigen die Existenz von unerwunsc hten Zust anden.
Die Idee, die dem vorgestellten Ansatz fur erfahrungsbasierte Regelung zugrunde
liegt, basiert auf der Ausnutzung von Trajektorien erfolgreicher Explorationen zur
Approximation einer Bewertungsfunktion fur den Zustandsraum. Um auch mit
wenigen Trainingsdaten zum Erfolg zu gelangen, wird eine realistische neuronale
Simulation der Dynamik der Maschine verwendet. Weiter werden intelligente Ex-
plorationstechniken wie z.B. Ruc kw artsexploration eingesetzt, um an Trainings-
daten zu gelangen. Die Kombination verschiedener Explorationstechniken erlaubt
die Integration verschiedensten initialen Wissens, und unerwunsc hte Zust ande
k onnen vorab spezi ziert werden. Da die Mehrheit der technischen Maschinen-
steuerungsaufgaben deterministisches Verhalten { oder zumindest eine unimodale
Verteilung mit kleiner Varianz { zeigt, ist es m oglich, das komplexe MDP-Modell,
das ohnehin fur diskrete Zust ande entwickelt wurde, durch eine einfache Projek-
tionsfunktion zu ersetzen. Die vorgestellten Algorithmen arbeiten direkt in einem
kontinuierlichen Zustandsraum und fuhren eine Anzahl von Explorationen durch,
bevor die gesammelten Daten zum Lernen eingesetzt werden. Das ist auch der
Hauptgrund, warum der vorgestellte Ansatz gegen die inkrementelle Summierung
von Fehlern robust ist, die in konventionellen Lernalgorithmen weit verbreitet
ist. Zur praktikablen und e zien ten Approximation kontinuierlicher Funktio-
nen werden neuronale Netze und Netze von radialen Basisfunktionen eingesetzt.
iiiiv
Die vorgestellten Methoden wurden erfolgreich in mehreren Navigationsaufgaben
sowie in der situationsabh angigen Algorithmenauswahl eingesetzt.Acknowledgements
First, I would like to thank my advisor, professor Bernd Radig, for his guidance
during the last years and providing all the necessary requirements and support
to write this dissertation. I am grateful to professor Gun ther Palm for becoming
the second supervisor of this dissertation and for providing valuable support.
Very special thanks go to Michael Beetz for many proli c discussions. Without
his ideas and our discussions, this work would not have come to fruition.
I wish to thank my former supervisors at University of Karlsruhe, professor Mar-
tin Riedmiller and Rainer Malaka for introducing me to machine learning and
nurturing me through my graduate career.
Thanks go also to Gerhard Kraetzschmar, the Ulm Sparrows RoboCup Team,
and the CS Freiburg RoboCup Team for motivating and funny RoboCup-related
discussions and interesting training games.
Further thanks to Daniel Kiecza, Freek Stulp, and Andreas Hofhauser for read-
ing drafts of this dissertation and providing valuable criticism. Their tireless
input de nitely improved the scienti c and linguistic quality of this disserta-
tion. Thanks to Robert Hanek for being a most enjoyable room mate and part-
ner in scienti c and non-scienti c discussions. Furthermore I thank all people,
researchers and students, involved in the AGILO-RoboCuppers, and especially
Thorsten Schmitt, for an ongoing pleasant and successful collaboration. Thanks
also go to Matthias Hilbig for helping me to solve the bureaucratic and formal
tasks of this dissertation.
Altogether I want to thank my colleagues and former colleagues at Informatics
IX for providing a supportive and most enjoyable working environment.
Finally, I wish to thank my parents, my wife D orte, and my sons Ilian and Linus
for all their support. This made my dissertation possible.
vvi
This work was supported in part by Deutsche Forschungsgemeinschaft (DFG,
Semiautomatischer Erwerb visuomotorischer kooperativer Pl ane) and in part by
the Siemens Mobile Corporation.