🤖 Roboter-Navigator — MDP-Value-Iteration live

Die Value Iteration ist ein modellbasierter dynamischer Programmieralgorithmus zur Lösung eines Markov-Entscheidungsprozesses (MDP): ein Zustandsraum S, ein Aktionsraum A, ein bekanntes Übergangsmodell P(s'|s,a), eine Belohnungsfunktion R(s,a,s') und ein Diskontfaktor γ. Ausgehend von einer beliebigen Wertfunktion V(s) wendet sie wiederholt das Bellman-Optimalitäts-Backup V(s) ← max_a Σ_s' P(s'|s,a)[R(s,a,s') + γV(s')] gleichzeitig auf jeden Zustand an (ein synchroner Durchlauf). Da dieses Backup unter γ<1 eine Kontraktionsabbildung ist, konvergieren wiederholte Durchläufe nachweislich zur eindeutigen optimalen Wertfunktion V*, aus der sich die optimale Strategie π*(s) = argmax_a Σ_s' P(s'|s,a)[R(s,a,s') + γV*(s')] direkt ablesen lässt.

Die Value Iteration ist modellbasiert: Sie benötigt die Übergangswahrscheinlichkeiten P(s'|s,a) und die Belohnungsfunktion R(s,a,s') im Voraus und berechnet bei jedem Durchlauf einen exakten Erwartungswert über jedes mögliche Ergebnis jeder Aktion in jedem Zustand — es ist überhaupt keine Simulation oder Erkundung der Umgebung nötig. Q-Learning (behandelt in der separaten Simulation zum verstärkenden Lernen dieser Website) ist modellfrei: Der Agent kennt P oder R nicht im Voraus, muss also tatsächlich in der Umgebung handeln, abgetastete Übergänge (s, a, r, s') beobachten und Q(s,a) mit einer Temporal-Difference-Regel Q(s,a) ← Q(s,a) + α[r + γ·max_a' Q(s',a') − Q(s,a)] schrittweise aktualisieren. Die Value Iteration konvergiert bei bekanntem Modell in einer begrenzten Anzahl von Durchläufen zum exakten V*; Q-Learning konvergiert nur asymptotisch durch Versuch und Irrtum und benötigt überhaupt kein explizites Übergangsmodell. Diese Simulation implementiert bewusst den modellbasierten Fall, damit sich die beiden Algorithmenfamilien klar unterscheiden lassen.

Echte Roboter und physische Agenten führen eine Aktion selten perfekt aus — Räder rutschen, Sensoren driften, Böden sind uneben. Diese Simulation bildet das mit einem klassischen stochastischen Übergangsmodell ab: Die Bewegung in eine gewählte Richtung gelingt mit Wahrscheinlichkeit P(beabsichtigt) (einstellbar, Standard 0,80), während die verbleibende Wahrscheinlichkeit gleichmäßig auf ein Abweichen um 90° nach links und 90° nach rechts von der beabsichtigten Richtung verteilt wird. Das Bellman-Backup summiert über alle drei möglichen Ergebnisse, gewichtet nach ihren Wahrscheinlichkeiten — genau das macht dies zu einem echten MDP statt zu einer deterministischen Kürzeste-Wege-Suche: Die optimale Strategie muss sich gegen die Möglichkeit eines ungewollten Abrutschens in eine Wand oder ein Hindernis absichern.

Drei Belohnungsterme ergeben zusammen R(s,a,s'): kleine negative Schrittkosten (Standard −0,04), die bei jedem nicht-terminalen Zug anfallen und die optimale Strategie zu kürzeren Wegen drängen; eine Hindernis-/Wandstoß-Strafe (Standard −0,75), die anfällt, wann immer ein Übergang durch eine Wand, ein Hindernis oder den Gitterrand blockiert wird und die Strategie dazu drängt, einen Sicherheitsabstand zu Hindernissen einzuhalten, besonders wenn Übergänge verrauscht sind; und eine terminale Zielbelohnung (+1), die beim Betreten der Zielzelle vergeben wird und die das Erreichen des Ziels überhaupt erst lohnenswert macht. Die Value Iteration propagiert alle drei durch das Bellman-Backup, sodass Zellen nahe dem Ziel zuerst hohe Werte erhalten, und dieses hohe Wertsignal breitet sich Durchlauf für Durchlauf rückwärts aus, bis jeder erreichbare Zustand eine genaue Schätzung seines langfristigen erwarteten Ertrags besitzt.

Jeder synchrone Durchlauf zeichnet die maximale absolute Änderung im Wert eines Zustands auf, max_s |V_neu(s) − V_alt(s)|, und die Simulation stellt diese Größe in logarithmischem Maßstab gegen die Durchlaufzahl dar. Da der Bellman-Optimalitätsoperator eine γ-Kontraktion ist, ist garantiert, dass diese Max-Delta-Folge monoton gegen null schrumpft; die Simulation erklärt Konvergenz, sobald sie unter 1e-4 fällt. Zu diesem Zeitpunkt liegt V(s) innerhalb eines kleinen, begrenzten Fehlers vom wahren V*(s) entfernt, und die daraus extrahierte gierige Strategie π(s) = argmax_a Q(s,a) ist die optimale Strategie für den konfigurierten MDP.

Ja. γ bestimmt, wie stark der Wert eines Zustands von Belohnungen beeinflusst wird, die viele Schritte in der Zukunft liegen: Bei γ nahe 1 propagieren entfernte Zielbelohnungen fast ungeschmälert über das gesamte Gitter, sodass die optimale Strategie weit vorausplant und bereit ist, längere, sicherere Umwege um Hindernisse zu nehmen. Bei γ näher an 0,5 werden zukünftige Belohnungen stark abdiskontiert, sodass die Strategie kurzsichtig wird — sie akzeptiert möglicherweise eine kürzere, aber riskantere Route an einem Hindernis vorbei, weil der diskontierte Wert, das Ziel ein paar Schritte später zu erreichen, kaum weniger wert ist als es einen Schritt früher zu erreichen. γ bestimmt auch die Konvergenzgeschwindigkeit: Ein kleineres γ lässt den Bellman-Operator schneller kontrahieren, sodass niedrigere Diskontfaktoren typischerweise in weniger Durchläufen konvergieren.