//img.uscri.be/pth/9839fd73b6d232032fa5aac1333b13c75534d13f
La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Game theoretic approaches to motion planning in robot soccer [Elektronische Ressource] / von Marcus Post

153 pages
Game Theoretic Approachesto Motion Planningin Robot Soccervon der Fakultät für Elektrotechnik,Informatik und Mathematikder Universität Paderbornzur Erlangung des akademischen GradesDoktor der Naturwissenschaften(Dr. rer. nat.)genehmigte DissertationvonMarcus PostPaderborn, 2008Referees: Prof. Dr. Oliver JungeProf. Dr. Burkhard MonienCommittee: Prof. Dr. Michael Dellnitz (chairman)Prof. Dr. Peter BürgisserProf. Dr. Oliver JungeProf. Dr. Burkhard MonienDr. Elke WolfDate of PhD Defense: 17.04.2008You can not learn anythinguntil you already almost know it.UnknownTo Berthild, Karl-Friedrich, Sebastian, and PingiiiAcknowledgementsI would like to start by thanking my advisors Prof. Dr. Michael Dellnitz and Prof. Dr.Oliver Junge for their guidance, support, motivation, and for the great freedom which wasgiven to me. Prof. Dellnitz’ group at the University of Paderborn always provided a verygood research environment for me. I also want to thank Prof. Dr. Burkhard Monien forhelpful comments and for reviewing this PhD thesis.Moreover, IamverygratefultoProf.Dr.OliverJunge,Prof.Dr.MichaelDellnitz,Dr.SinaOber-Blöbaum, Dr. Kathrin Padberg, Dr. Oliver Schütze, Stefan Sertl, and Bianca Thierefor interesting discussions and exciting joint work. For fruitful discussions and commentsI would also like to thank Mirko Hessel-von Molo, Oliver Kramer, Prof. Dr. Michael G.Lagoudakis, Tim Laue, Dr. Martin Lauer, Henning Meyerhenke, and Willi Richert.
Voir plus Voir moins

Game Theoretic Approaches
to Motion Planning
in Robot Soccer
von der Fakultät für Elektrotechnik,
Informatik und Mathematik
der Universität Paderborn
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
(Dr. rer. nat.)
genehmigte Dissertation
von
Marcus Post
Paderborn, 2008Referees: Prof. Dr. Oliver Junge
Prof. Dr. Burkhard Monien
Committee: Prof. Dr. Michael Dellnitz (chairman)
Prof. Dr. Peter Bürgisser
Prof. Dr. Oliver Junge
Prof. Dr. Burkhard Monien
Dr. Elke Wolf
Date of PhD Defense: 17.04.2008You can not learn anything
until you already almost know it.
Unknown
To Berthild, Karl-Friedrich, Sebastian, and Ping
iiiAcknowledgements
I would like to start by thanking my advisors Prof. Dr. Michael Dellnitz and Prof. Dr.
Oliver Junge for their guidance, support, motivation, and for the great freedom which was
given to me. Prof. Dellnitz’ group at the University of Paderborn always provided a very
good research environment for me. I also want to thank Prof. Dr. Burkhard Monien for
helpful comments and for reviewing this PhD thesis.
Moreover, IamverygratefultoProf.Dr.OliverJunge,Prof.Dr.MichaelDellnitz,Dr.Sina
Ober-Blöbaum, Dr. Kathrin Padberg, Dr. Oliver Schütze, Stefan Sertl, and Bianca Thiere
for interesting discussions and exciting joint work. For fruitful discussions and comments
I would also like to thank Mirko Hessel-von Molo, Oliver Kramer, Prof. Dr. Michael G.
Lagoudakis, Tim Laue, Dr. Martin Lauer, Henning Meyerhenke, and Willi Richert.
In general, I am indebted to my colleagues in Paderborn including Alessandro Dell’ Aere,
Sebastian Hage-Packhäuser, Mirko Hessel-von Molo, Stefan Klus, Dr. Arvind Krishna-
murthy, Anna-Lena Meier, Dr. Sina Ober-Blöbaum, Dr. Kathrin Padberg, Michael Petry,
Dr. Robert Preis, Dr. Oliver Schütze, Stefan Sertl, Bianca Thiere, Dr. Fang Wang, and
Katrin Witting for discussions, technical support, social events and many other things. I
am further indebted to the collegiates of the PaSCo graduate school.
I am grateful to Laurel Frick-Wright for proofreading my thesis to improve the quality of
my English and to Mirko Hessel-von Molo, Anna-Lena Meier, and Stefan Klus for proof-
reading excerpts.
I always received valuable administrative support from the secretaries Marianne Kalle and
Tanja Bürger, and from Anne Belkner. For enabling my work in a different way, namely
by keeping my office clean, I thank the non-scientific staff of the University of Paderborn.
I would like to thank Alessandro Dell’ Aere for helping me to build a physical soccer envi-
ronment for the AIBO robots and some students for supporting me with the AIBO robots’
technical issues: Johannes Berg, Raphael Golombek, and Nicolai Hähnle are to be men-
tioned here.
Last but not least I am very indebted to my parents Berthild and Karl-Friedrich Post who
supportedmenotonlyduringmystudiesbutduringmywholelifeinallwaysimaginable. I
want to thank my brother Sebastian, Janina, my friends from the University of Paderborn,
especially Ping, the “Mensa-Kreis”, and the musicians I played music with, and, of course,
all other friends of mine.
AFor the development of great software tools I want to especially thank all LT X develop-E
ers and the developers of Dia, Kate, and Kile many of whom work voluntarily, and the
developers of Matlab which is a commercial software tool. All of them made my work
technically possible or at least substantially simpler.
For financial support I am very grateful to the Paderborn Institute for Scientific Compu-
(1)tation (PaSCo) and to the University of Paderborn.
Marcus Post, February 2008
(1)The research is (partly) supported by the DFG Research Training Group GK-693 of the Paderborn
Institute for Scientific Computation (PaSCo).
ivAbstract
Robotics is, from a scientific point of view, a very broad topic with many applications.
While highly specialised robots have been widely used in production lines, the next big
scientific steps are towards autonomy of robots and interaction with other robots and hu-
mans. For achieving these long-term goals catenations of physical and mental abilities
which are interdisciplinary and scientifically challenging have to be carried out. At its cur-
rent state, robot soccer is an appropriate environment for demonstrating and developing
robotic skills as several areas are addressed such as image processing and analysis in the
widest sense (including e.g. object matching and directing the camera), control and opti-
misation of physical movement (walking, ball handling), and the strategic planning which
may be considered as being close to high level reasoning. In this thesis, game theoretic and
reinforcement learning approaches are utilised to contribute to strategic planning in robot
soccer which serves as a motivating example. The aim of strategic planning is to obtain
an optimal strategy which also takes the possibly unknown strategies of other players into
account. Anaturalfurthergoalofthisthesisisthedevelopmentandanalysisofalgorithms
by means of which such optimal strategies can be approximately computed.
More specifically, the following steps are undertaken: first, a game theoretic model of
multi-player robot soccer is developed which is independent from the robot hardware. The
occuring challenge to determine an optimal strategy with respect to this model for as
many robots as possible is met by exact model reduction, i.e. by finding equivalent smaller
models. For this, a theoretical framework of symmetries is developed which bases on
homomorphisms between two-player zero-sum Markov games. It lays a formal foundation
for practitioners who already implicitly used results proven within that framework. A
specialresultwhichisimportantformodelreductionisthatthereductioncanbeperformed
in several separate steps and be combined afterwards which is expressed by a composition
of homomorphisms. Finally, a qualitatively new symmetry which interchanges the two
players of the Markov game, i.e. the two teams in robot soccer, is proven to be part of
the homomorphism framework. Particularly, this means that it can be combined with all
symmetries which occur in Markov decision processes.
The theoretical results about Markov game symmetries are algorithmically exploited for
Dynamic Programming (DP) and Reinforcement Learning (RL) methods which are also
compared. Such comparisons ought to be standard but seem unusual for large parts of the
RLliterature. Unsurprisingly,DPmethodsaremoreefficientandthusthefollowinggeneral
procedure seems recommendable: firstly, to design an approximate model for the task at
hand and solve this by DP methods to an appropriate level of precision and, secondly, to
use the DP solution of the rough model as an initialisation for an RL method to let the RL
method adapt to the unknown real model. In this spirit, the developed soccer model and
the computation of its optimal solution can be seen as the completion of the first of the
above two steps. Ideas of dynamical systems and graph theory are additionally integrated
vto design new efficient DP methods by means of almost invariant sets. All algorithms are
thoroughly studied numerically and the results of optimal strategies are also interpreted
in terms of soccer. Finally, some of the most challenging future tasks to implement these
strategies on real robots are identified.
Key Words
reinforcement learning, robotics, robot soccer, optimal strategy, symmetry, model reduc-
tion, control theory, game theory, graph theory, dynamical system, almost invariant set,
homomorphism
viAbstract (German)
Die Robotik ist aus wissenschaftlicher Sicht ein sehr breites Fachgebiet, das viele An-
wendungen hat. Weitverbreitet sind beispielsweise hochspezialisierte Roboter, die in der
maschinellenFertigungeingesetztwerden.EinigedernächstenMeilensteineinderRobotik
sind in der Autonomie von Robotern und in der Interaktion mit Robotern und Menschen
zu erwarten. Zum Erreichen dieser Meilensteine ist eine Verknüpfung von physischen und
“mentalen” Fähigkeiten notwendig, die interdisziplinär ist und wissenschaftliche Herausfor-
derungen bietet. Roboterfußball stellt zum derzeitigen Stand der Wissenschaft eine geeig-
nete Umgebung dar, um verschiedenartige Fähigkeiten der Roboter zu demonstrieren und
weiterzuentwickeln, denn es beinhaltet bereits eine Vielzahl von Gebieten, beispielsweise
Bildverarbeitung im weitesten Sinne (einschließlich Objekterkennnung und -verfolgung),
Kontrolle und Optimierung physischer Bewegung (Fortbewegung, Ballfertigkeiten) und die
strategische Planung, die auch als höhere kognitive Fähigkeit betrachtet werden kann.
In dieser Doktorarbeit werden Ansätze der Spieltheorie und des Reinforcement-Learnings
genutzt,umBeiträgezurstrategischenBewegungsplanungimRoboterfußball,dasalsmoti-
vierendes Beispiel dient, zu leisten. Ziel der Strategieplanung istes, eine optimale Strategie
zu ermitteln, die auch die möglicherweise unbekannten Strategien anderer Spieler einbe-
zieht. Ein weiterführendes Ziel der Arbeit stellt die Weiterentwicklung und Analyse von
Algorithmen, mit deren Hilfe optimale Strategien approximativ berechnet werden, dar.
Dazu werden die folgenden Schritte unternommen: Zunächst wird ein spieltheoretisches
Modell des Mehrspieler-Roboterfußballs entwickelt, das möglichst hardware-unabhängig
ist. Einer wesentlichen dabei auftauchenden Herausforderung, optimale Strategien für die-
ses Modell mit einer möglichst großen Anzahl von Robotern zu bestimmen, wird durch
exakte Modellreduktion begegnet, d.h. es wird versucht, ein möglichst kleines, dem origi-
nalen Modell äquivalentes Markov-Spiel zu ermitteln. Zu diesem Zweck wird ein theoreti-
schesKonzeptvonSymmetrieneingeführt,dasaufHomomorphismenzwischenZweispieler-
Nullsummenspielenbasiert.DerSymmetriebegriffschafftdabeieineformaleBasisfürschon
zuvorzurpraktischenLösungvonMarkov-SpielenimplizitangewendetenSymmetriereduk-
tionen. Ein nützliches Ergebnis für die Modellreduktion ist, dass diese schrittweise durch-
geführt und anschließend kombiniert werden kann, was sich formal durch die Komposition
von Homomorphismen darstellen lässt. Schließlich ist eine qualitativ neuartige Symmetrie,
die die Spieler eines Markov-Spiels vertauscht, in den Formalismus integriert. Insbesondere
wird gezeigt, dass sich die nicht in Markov-Entscheidungsprozessen vorkommende Symme-
trie mit allen dort anzutreffenden Symmetrien kombinieren lässt.
Die theoretischen Ergebnisse über Symmetrien in Markov-Spielen werden algorithmisch
umgesetzt in Methoden der Dynamischen Programmierung (DP) und des Reinforcement-
Learnings (RL), welche ferner miteinander verglichen werden. Derartige Vergleiche sollten
als Standard gelten, scheinen aber eher die Ausnahme in weiten Teilen der RL Literatur zu
sein. Erwartungsgemäß sind die DP Methoden effizienter, weshalb die folgende allgemeine
viiVorgehensweise vorgeschlagen wird: zunächst ein approximatives Modell zu konstruieren
und mit Hilfe der DP Methoden zu lösen, um dann ein RL Verfahren mit dieser Lösung
als Startwert auszustatten. Dies ermöglicht sowohl den Einsatz der effizienteren DP Me-
thoden, die mit angemessener Präzision das approximative Modell lösen, als auch den der
RL Methoden, deren Adaptivität an das unbekannte reale Modell ausgenutzt wird. In die-
sem Sinne können das entwickelte Roboterfußball-Modell und die Berechnung optimaler
Strategien als Lösung des ersten Teils des allgemeinen Vorgehens angesehen werden. Dazu
finden bei der Entwicklung neuer effizienter Algorithmen unter anderem Ideen aus dem
Gebiet der Dynamischen Systeme und der Graphentheorie zu fast invarianten Mengen An-
wendung. Abschließend werden wichtige praktische Herausforderungen identifiziert, die es
zu lösen gilt, bevor die berechneten optimalen Strategien auf reale Roboter übertragen
werden können.
Schlagworte
Reinforcement-Learning,Robotik,Roboterfußball,optimaleStrategie,Symmetrie,Modell-
reduktion, Kontrolltheorie, Spieltheorie, Graphentheorie, Dynamisches System, fast inva-
riante Menge, Homomorphismus
viiiContents
1 Introduction 1
2 Reinforcement Learning (RL) and Game Theory 7
2.1 Dynamical Systems and Markov Processes . . . . . . . . . . . . . . . . . . . 9
2.1.1 Basics and Problem Definitions . . . . . . . . . . . . . . . . . . . . . 9
2.1.2 Numerical Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.3 Complexity, Algorithmic Issues and Software . . . . . . . . . . . . . 15
2.2 Markov Decision Processes (MDPs) . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Basics and Problem Definitions . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 Numerical Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.3 Complexity, Algorithmic Issues and Software . . . . . . . . . . . . . 22
2.3 Matrix Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.1 Basics and Problem Definitions . . . . . . . . . . . . . . . . . . . . . 23
2.3.2 Numerical Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.3 Complexity, Algorithmic Issues and Software . . . . . . . . . . . . . 29
2.4 Two Player Zero Sum Markov Games (2P-ZS-MGs) . . . . . . . . . . . . . . 29
2.4.1 Basics and Problem Definitions . . . . . . . . . . . . . . . . . . . . . 30
2.4.2 Numerical Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4.3 Complexity, Algorithmic Issues and Software . . . . . . . . . . . . . 32
2.5 General Markov Games, Differential Games, and Advanced Concepts of RL 33
3 Model Reduction and Symmetry 36
3.1 Homomorphisms and Symmetry in MDPs . . . . . . . . . . . . . . . . . . . 37
3.1.1 Equivalence of MDP Homomorphisms and MDP Symmetries . . . . 38
3.1.2 Symmetries by Group Actions on MDPs . . . . . . . . . . . . . . . . 42
3.2 Homomorphisms and Symmetry in 2P-ZS-MGs . . . . . . . . . . . . . . . . 43
3.2.1 2P-ZS-MG Homomorphisms and Symmetry . . . . . . . . . . . . . . 44
3.2.2 Automorphisms for the Exchange of Agents . . . . . . . . . . . . . . 49
4 Supervised Learning (SL), Function Approximation, Generalisation 55
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.1.1 General Approximation Results . . . . . . . . . . . . . . . . . . . . . 57
4.1.2 Generalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.1.3 Function Approximation with Automated Basis Determination . . . 58
4.2 Value Iteration with SL: Convergence Result . . . . . . . . . . . . . . . . . . 59
4.3 Combination of RL and SL: Practical Results from Literature . . . . . . . . 61
4.3.1 MDPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.3.2 2P-ZS-MGs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
ix5 Robot Soccer and Other Applications 63
5.1 Modeling Robot Soccer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.1.1 General Issues of Modeling Robot Soccer. . . . . . . . . . . . . . . . 64
5.1.2 A Simple Multi-Player Robot Soccer Model . . . . . . . . . . . . . . 67
5.1.3 Symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.2 Numerical Results of Grid Soccer . . . . . . . . . . . . . . . . . . . . . . . . 74
5.2.1 Preliminaries for the Following Subsections . . . . . . . . . . . . . . 75
5.2.2 Reasoning for 2P-ZS-MG Modelling: Comparison of MDP and 2P-
ZS-MG strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.2.3 Relating Policies to Humanoid Soccer Characteristics . . . . . . . . . 80
5.2.4 Comparison of DP and RL Techniques . . . . . . . . . . . . . . . . . 81
5.2.5 of Different DP Techniques with Various Parameters . . 84
5.2.6 Comparison of Standard Methods and SL Techniques . . . . . . . . . 91
5.2.7 Towards Multi-Player Robot Soccer: 2v2 Grid Soccer . . . . . . . . . 93
5.3 A New Algorithm: MaG-Clus-VI . . . . . . . . . . . . . . . . . . . . . . . . 95
5.4 From Grid Soccer to Robot Soccer: Practical Issues . . . . . . . . . . . . . . 96
5.4.1 Lower Level behaviours . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.4.2 Image Processing and Localisation . . . . . . . . . . . . . . . . . . . 97
5.5 Other Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6 Conclusion and Outlook 100
A Basics of Group Homomorphisms and Group Actions 103
B Bellman Equations and Iterative Linear Solvers 105
C The Software PackageDRPOST 107
C.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
C.2 Technical Aspects of Symmetry Reduction in 2P-ZS-MGs . . . . . . . . . . 108
D Detailed Tables of Numerical Results 110
D.1 Initial Value Functions V and Discount Factors γ . . . . . . . . . . . . . . . 1100
D.2 Additional Figures and Tables for the Comparative Studies of DP and RL
methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
List of Figures 118
List of Tables 120
Glossary 122
Bibliography 126
Index 141
x