Reinforcement Learning in der Modellfahrzeugnavigationubicomp/projekte/master2009... ·...

Reinforcement Learning in der Modellfahrzeugnavigation

vonvon

Manuel Trittel

Informatik

HAW Hamburg

Vortrag im Rahmen der Veranstaltung AW2 im Masterstudiengang, 02.07.2009

Einführung

Gliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FA

Einführung• Thema• Problemstellung

Relevante Reinforcement Learning Verfahren • Dynamische Programmierung• Temporal Difference Learning• Generalisierung und Funktionsapproximation • Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

• Generalisierung und Funktionsapproximation

Anwendungsfälle der Verfahren

Praktische Herausforderungen• Beschleunigung der Lernverfahren• Diskretisierung kont. Zustands- und Aktionsräume

Zusammenfassung

Bedeutung für eigene Arbeitsziele

Thema

Reinforcement Learningin der Modellfahrzeugnavigation

Konkreter Anwendungsfall:

Einführung

Gliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FAKonkreter Anwendungsfall:

Ø Geschwindigkeitsregelung

Ø Geschwindigkeitsmaximierung= Zeitminimierung

Ø Einhaltung einer maximalen Zentripetalkraft

• Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

Einführung

ProblemstellungGliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FA• Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

Relevante Reinforcement Learning Verfahren

Ø Dynamische Programmierung

Ø Temporal Difference Learning

Ø Generalisierung und Funktionsapproximation

Gliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FA• Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

Relevante Reinforcement Learning Verfahren

Dynamische Programmierung

Ø aus den 1950er Jahren von Richard E. Bellman

Ø basiert auf vollständigem Markov Modell

Ø Bestimmung einer optimalen Zustandstrajektorie durchØ value iterationØ policy iteration

Gliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FAØ policy iteration

-7 -6 -5 -6 -7

0 -5 -4 -5 -6

-1 -2 -3 -8 -7

• Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

))'(),((max)(1

sVasRsV kak −⋅+= γ

Relevante Reinforcement Learning Verfahren

Temporal Difference Learning (TD Learning)

Ø schrittweise Update der value function

Ø Zustandswert wird beim Verlassen geupdated:

))(),(()()1()( 11 ++ ⋅++⋅−= tktktk sVasRsVsV γηη

Gliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FA

Ø ∆V(st) wird als temporal difference bezeichnet

Ø prinzipiell analog mit der Q-Funktion

Ø mit π als estimation policy

),()','(),( asQasQasRtdππγ −⋅+=

• Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

Vk

R+Vk

Relevante Reinforcement Learning Verfahren

Temporal Difference Learning (TD Learning)

Ø Strategien…Ø zur praktischen AnwendungØ zum Erlernen der Q-Funktion

Ø eine Strategie für beides Nutzen

Gliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FAØ eine Strategie für beides NutzenØ on-policy Verfahren (SARSA)

Ø jeweils eine unabhängige StrategieØ off-policy Verfahren (Q-learning)

• Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

Relevante Reinforcement Learning Verfahren

Generalisierung und Funktionsapproximation

Ø Problem: Sehr große Zustands- u. AktionsräumeØ zu wenig SpeicherplatzØ zu wenig RechenzeitØ zu viel Zeit zum Lernen benötigt

Ø Funktionsapproximation nach [Sutton u. Barto]:Ø Gradienten-Abstiegs-Methoden

Gliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FAØ Gradienten-Abstiegs-MethodenØ lineare Methoden

Ø Grob- u. TeilkodierungØ Kubische SplinesØ Radiale Basisfunktionen

Ø nicht lineare MethodenØ MustererkennungØ neuronale NetzeØ Regressionsmethoden

• Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

Inhal - Gliederung

Anwendungsfälle aus [Kaelbling u.a.]

Devilsticking robotDP

Anwendungsfälle

Gliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FA

Ø Boxpushing robots [Mahadevan](Q-learning)

Ø Fahrstuhlsteuerung [Crites u. Barto](Q-learning, MLP)

Backgammon [Tesauro] 2-gliedriges Pendel [Coulom]MLP mit TD(λ) TD(λ) mit MLP / Gauss network

• Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

Inhal - Gliederung

Prothese (Bein/Hüfte/Knie) aus [Thrasher]SL + RL [Williams] Reinforce Algorithmus

Anwendungsfälle

Gliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FA• Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

Inhalt - Gliederung

Ø Beschleunigung der LernverfahrenØ Vorwissen über die SystemumgebungØ Eligibility TracesØ Hybride AnsätzeØ Exploration vs Exploitation

Praktische Herausforderungen

Gliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FAØ Diskretisierung von Zustands- und Aktionsräumen

Ø Konferenzen, Symposia, WorkshopsØ National conference on Artificial Intelligence (24th in 2010)Ø Florida Artificial Intelligence Research Society (23th in 2010)

• Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

Inhalt - Gliederung

Beschleunigung der Lernverfahren

v Vorwissen über die Systemumgebung

Ø vorprogrammierte, menschliche VorkenntnisseØ geringerer Grad der Autonomie

Beispiele aus [Kaelbling u.a.]:

Praktische Herausforderungen

Gliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FABeispiele aus [Kaelbling u.a.]:Ø Erwartung bestimmter Funktionsverläufe (Approx.)Ø Passende, manuelle Diskretisierung des ZustandsraumsØ Vorkenntnisse über den ZustandsraumØ Erfahrungen aus Statistiken

• Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

Inhalt - Gliederung

Beschleunigung der Lernverfahren

v Eligibility Traces (e-traces)

Ø Erweiterung für TD VerfahrenØ Schnellere Erkundung des Zustandsraums durchØ Berücksichtigung von „Delayed Rewards“ undØ Einbeziehung der zuletzt besuchten Zustände

Praktische Herausforderungen

{ ssfallssese

≠⋅⋅= ),()(

γλ

Gliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FA{ tt ssfalls

sonst

se

t se≠⋅⋅

+ = ),(

,11)(

γλ

1/4 1/2 1

1/32 1/16 1/8

Beispiel mitλ = 0,5 u. γ = 1

• Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

Inhalt - Gliederung

Beschleunigung der Lernverfahren

v Hybride Ansätze

Ø Häufig zur Gewinnung von VorwissenØ Hart kodierte, menschliche Vorkenntnisse (s.o.)

Praktische Herausforderungen

Gliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FAØ In [Thrasher u.a.]:

Ø Kombination mit Supervised LearningØ Gelerntes auf ähnliche Anwendungsfälle anwenden

• Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

Inhalt - Gliederung

Beschleunigung der Lernverfahren

v Exploration vs Exploitation

Ø Methoden mit zufälliger AktionsauswahlØ ε-Greedy SucheØ Boltzmann ExplorationØ Simulated Annealing

Praktische Herausforderungen

Gliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FAØ Simulated Annealing

Ø Im Rahmen von SIRL* [Chen u. Dong]Ø Reinforcement Learning und Explorationen aufGrundlage von Quanten Charakteristiken

* SIRL: superposition-inspired reinforcement learning

• Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

Inhalt - Gliederung

Diskretisierung von Zustands- und Aktionsräumen

Ø kontinuierliche Zustandsräume (z.B Winkel) oderAktionsräume (z.B. Kräfte) praktisch unendlich groß

Ø Nutzung der üblichen Methoden durch Diskretisierungen

Gitteransatz von [Coulom] Gitteransatz fein/grob

Praktische Herausforderungen

Gliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FA• Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

Inhalt - Gliederung

Diskretisierung von Zustands- und Aktionsräumen

Mehrgitterverfahren Dreiecksverfahren

Praktische Herausforderungen

Gliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FA• Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

Zusammenfassung

Ø unzählige, verschiedenartige Anwendungsfälle

Ø in abgewandelten/erweiterten Formen

Ø spezifische Finessen

Ø Beschleunigung meist notwendig für praktikables Lernen

Gliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FA

Ø vielfältige Approximationsverfahren

Ø grundlegende Vorgehensweise konkretisiert

Ø ähnliche Anwendungsfälle als Anreize, Ideen

• Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

Inhalt - Gliederung

Ø keine aufwendigen Diskretisierungen erforderlich, aber

Ø Approximationen z.B. für Sollgeschwindigkeiten möglichØ Kubische Splines ?Ø Radiale Basisfunktionen ?

Ø träges Beschleunigungsverhalten → Einfluss der VorzuständeØ TD Verfahren bieten sich an

Bedeutung für eigene Arbeitsziele

Gliederung

Einführung

• Thema

• Problemstellung

Verfahren

• Dyn. Programmierung

• TD Learning

• Generalisierung u. FAØ TD Verfahren bieten sich anØ Nutzung von e-traces

Ø Exploration zeitunkritisch und unabhängig von Exploitation

Ø Vorwissen für schnellere Exploration nutzbar

Ø irgendwann Selbstlokalisierung notwendig (Odometriefehler)

Ø Reinforcement Learning Toolbox [Neumann]

• Generalisierung u. FA

Anwendungsfälle

Herausforderungen

• Beschleunigung

• Diskretisierung

Zusammenfassung

Bedeutung f. AZ

Literaturverzeichnis

[Chen und Dong]CHEN, Chun-Lin ; DONG, Dao-Yi: Superposition-Inspired ReinforcementLearning and Quantum Reinforcement Learning. In: Reinforcement Learning: Theoryand Applications. Wien, Österreich : I-Tech Education and Publishing, 2008, S. 59–84. – ISBN 978-3-902613-14-1

[Coulom]COULOM, M. R.: Apprentissage par renforcement utilisant des réseaux de neurones, avec des applications au contrôle moteur, Nationales Institut für PolytechnikGrenoble, Doktorarbeit, 2002

[Crites u. Barto]CRITES, R.H.; BARTO, A.G.; Improving elevator performance using reinforcement learning. In Touretzky, D., Mozer, M., Hasselmo, M. (Eds.); Neural Information Processing Systems 8

[Kaelbling u.a.]KAELBLING, Leslie P.; LITTMAN, Michael L.; MOORE, Andrew W.: Reinforcement Learning: A Survey. In: Journal of Artificial Intelligence Research (JAIR). 4 (1996), S. 237-285

[Mahadevan]MAHADEVAN, S.; CONNELL, J.; Automatic Programming of behavior-based robots usingreinforcement learning. In: Proceedings of Ninth National conference on ArtificialIntelligence, Anaheim, CA

Literaturverzeichnis

[Neumann]NEUMANN, Gerhard: The Reinforcement Learning Toolbox, ReinforcementLearning for Optimal Control Tasks, University of Technology Graz, Diplomarbeit, 2005

[Sutton und Barto]SUTTON, Richard S. ; BARTO, Andrew G.: Reinforcement Learning- An Introduction. Cambridge : MIT Press, 1998. – ISBN 978-0262193986

[Tesauro]TESAURO, Gerald; Practical issues in temporal difference learning. Machine Learning, 8, TESAURO, Gerald; Practical issues in temporal difference learning. Machine Learning, 8, 1992, S. 257-277TESAURO, Gerald; Temporal difference learning and TD-Gammon. Communications ofthe ACM, 38(3), 1995, S. 58-67

[Thrasher u.a.]THRASHER, Adam; ANDREWS, Brian; WANG, Feng: Control of FES using Reinforcement Learning: Accelerating the learning rate. In: Proceedings – 19th International Conference – IEEE/EMBS. Chicago, IL., USA : IEEE Computer Society, 1997, S. 1774-1776. – ISBN 0-7803-4262-3

[Williams]WILLIAMS, R.J.; Simple statistical gradient-following algorithms for connectionistreinforcement learning, Machine Learning, 8, 1992, S. 229-256

Vielen Dank für die Aufmerksamkeit!Vielen Dank für die Aufmerksamkeit!

Fragen?