Value Iteration in Grid World
Bellman-Gleichung für Value Iteration:
V(s) = maxa Σs’ [P(s’|s,a) * (R(s,a,s’) + γ * V(s’))]
Wo:
- V(s) der Wert des Zustands s ist
- P(s’|s,a) die Übergangswahrscheinlichkeit ist (hier angenommen als deterministisch, daher = 1)
- R(s,a,s’) die Belohnung für die Übergangsfunktion von s nach s’ durch Aktion a ist
- γ (gamma) der Abzinsungsfaktor ist
- V(s’) der Wert des nächsten Zustands s’ ist
Belohnungswerte:
- Hindernisse haben eine Belohnung von -10
- Das Ziel hat eine Belohnung von 0, wenn es erreicht wird
- Normale Schritte haben eine Belohnung von -1
Optimale Wertfunktion
Optimale Politik
Explizit berechnete Werte
Erklärung des Prozesses:
Der Value-Iteration-Algorithmus wird verwendet, um die optimale Politik und Wertfunktion für eine gegebene Rasterwelt zu finden. Der Algorithmus iteriert über alle Zustände und berechnet die maximale erwartete Belohnung für jeden Zustand basierend auf möglichen Aktionen (gemäß der Bellman-Gleichung). Der Prozess dauert so lange, bis sich die Werteänderungen der Zustände unter einen bestimmten Schwellenwert (Theta) verringern. Hindernisse im Raster führen zu einer negativen Belohnung, während das Ziel eine neutrale Belohnung bietet, wenn es erreicht wird.