Um was gehts?
Zur Verinnerlichung der theoretischen Konzepte des bestärkenden Lernen in meinem Studium, habe ich neulich beschlossen einen Labyrinthlöser zu implementieren. Dieser soll Q-Lernen verwenden, um über die Trainingszyklen hinweg den besten Weg zum Ziel herauszufinden.
Q-Lernen 🧑🎓
Q-Lernen ist ein modelfreier Ansatz zum bestärkenden Lernen. Modelfrei heißt, dass der Agent die Umgebung nicht kennt. Der Agent fängt damit an, zufällige Aktionen auszuführen, um so über die Zeit die Umgebung kennenzulernen. Für jede Status in dem der Agent sich befindet, ermittelt er die für alle möglichen Aktionen die Q-Werte.
Ein Q-Wert beschreibt im Prinzip die Qualität der Aktion in diesem Zustand.
Im zweiten Schritt des Trainings kann der Agent die Q-Werte noch verfeinern, indem er weitestgehend die besten Aktionen verfolgt und nur manchmal von der besten Route abweicht.
Spielregeln 🎯
Spielfeld
Das Spielfeld ist ein 2D-Labyrinth, welches in der Konsole folgendermaßen visualisiert wird:
+---+---+---+---+
| | | | X |
+---+---+---+---+
| | # | # | |
+---+---+---+---+
| P | | | |
+---+---+---+---+
P: Agent
#: Wand
X: Ziel
Regeln
- Wenn der Agent gegen die Wand läuft, verbleibt er im selben Feld
- Das Spiel ist vorbei, sobald das Ziel erreicht wurde
Implementation 🔥
Spielfeld ♟️
Die Klasse Maze implementiert Methoden, um Aktionen auf dem Spielfeld auszuführen. Im Konstruktor wird ein Spielfeld aus einer Datei geladen:
// maze.ts
import { printTable } from '@lib/print_table';
import { readFileSync } from 'fs';
export interface MazePos {
x: number;
y: number;
}
export class Maze {
private board: string[][];
public width = 4;
public height = 3;
private startPos: MazePos;
private pos: MazePos;
constructor(templatePath?: string) {
let template = readFileSync(templatePath, { encoding: 'utf8' }).replaceAll('\r', '');
const playerIndex = template.indexOf('P'); // Find player position
if (playerIndex === -1) {
throw new Error(`No player position could be determined! Ensure that the maze "${templatePath}" has the player position set! ("P" character somewhere)`);
}
template = template.replace('P', ' ');
this.board = template.split('\n').map(row => row.split(''));
this.height = this.board.length;
this.width = this.board[0].length;
if (this.board.some(r => r.length !== this.width)) {
throw new Error(`Not every line has the same length! Maze file: "${templatePath}"`);
}
this.startPos = { x: playerIndex % (this.width + 1), y: Math.floor(playerIndex / (this.width + 1)) };
this.pos = structuredClone(this.startPos);
}
private isWall(x: number, y: number): boolean {
return this.board[y][x] === '#';
}
isAtGoal(): boolean {
return this.board[this.pos.y][this.pos.x] === 'X';
}
getPosId(): string {
return `${this.pos.x}-${this.pos.y}`;
}
moveUp(): void {
if (this.pos.y > 0 && !this.isWall(this.pos.x, this.pos.y - 1)) {
this.pos.y--;
}
}
moveDown(): void {
if (this.pos.y < this.height - 1 && !this.isWall(this.pos.x, this.pos.y + 1)) {
this.pos.y++;
}
}
moveLeft(): void {
if (this.pos.x > 0 && !this.isWall(this.pos.x - 1, this.pos.y)) {
this.pos.x--;
}
}
moveRight(): void {
if (this.pos.x < this.width - 1 && !this.isWall(this.pos.x + 1, this.pos.y)) {
this.pos.x++;
}
}
reset(): void {
this.pos = structuredClone(this.startPos);
}
printBoard(): void {
const printBoard = structuredClone(this.board);
printBoard[this.pos.y][this.pos.x] = 'P';
printTable(printBoard);
}
}
Training
Q-Werte Tabelle
Zuerst wird eine Map mit Zuordnungen von Status zu Q-Werte angelegt. Ein Eintrag könnte so aussehen:
"2-0" -> { up: 0.7, down: 0.7, left: 0.6, right: 1 }
Hier wird beschrieben wie qualtitativ die verschiedenen Aktionen sind, wenn sich der Agent auf dem Feld x: 2, y: 0 befindet.
Aktionsschleife
In der Aktionsschleife, führt der Agent in der ersten Hälfte zufällige Aktionen aus, um (ineffizient) zum Ziel zu kommen:
while (true) {
const posId = maze.getPosId();
const qPos: ActionQuality = q.get(posId) ?? {};
let nextAction = chooseNextActionRandomly();
actions.push([ posId, nextAction ]);
if (nextAction === 'up') { maze.moveUp(); }
if (nextAction === 'down') { maze.moveDown(); }
if (nextAction === 'left') { maze.moveLeft(); }
if (nextAction === 'right') { maze.moveRight(); }
if (maze.isAtGoal()) {
// Hurray!! We solved the maze :) Time to update the q values
maze.reset();
break;
}
}
Jede Aktion wird in einem Array (actions) für die Auswertung zwischengespeichert.
Auswertung
Zur Auswertung werden die vorgenommenen Schritte rückwärts durchlaufen und der Q-Wert in der Q-Tabelle aktualisiert, wenn ein neuer Höchstwert erziehlt wurde.
Der Diskontinuierungsfaktor wird verwendet, um Aktionen die den Agenten weiter von der Belohnung entfernen geringer zu bewerten. In dieser Implementation wird ein Diskontinuierungsfaktor von 0.9 verwendet.
Für Aktionen die mehrere Schritte vom Ziel entfernt liegen, wird der Diskontinuierungsfaktor mit sich selbst multipliziert um die Entfernung widerzuspiegeln.
Für eine Aktion, die 4 Schritte vom Ziel entfernt liegt, wird der Diskontinuierungsfaktor folgendermaßen berechnet:
Der letzte Schritt wird nicht berücksichtigt, da sich der Agent hier schon direkt am Ziel befindet.
for (let k = 0; k < actions.length; k++) {
const curDisconFactor = Math.pow(disconFactor, k);
const [ posId, action ] = actions[actions.length - k - 1];
const qPos = q.get(posId) ?? {};
const qVal = reward * curDisconFactor;
if (qPos[action] == null || qVal > qPos[action]) {
qPos[action] = qVal;
q.set(posId, qPos);
}
}
Zweiter Trainingsteil: Ausnutzen 🐍
Im zweiten Trainingsteil geht der Agent dazu über, meist die bestbewertesten Aktionen auszuführen. Hin und wieder führt er allerdings doch Aktionen aus, die schlechter bewertet sind. Dies diehnt dem Feintuning. Eventuell werden noch bessere Routen gefunden.
Dafür wird eine Methode verwendet, die die Aktionen gewichtet und dann zufällig basierend auf dem Gewicht die Aktion auswählt.
function chooseNextActionWeighted(qPos: ActionQuality): Action {
return weightedRandom(
Object.entries(qPos).filter(([ _, weight ]) => weight !== undefined),
([ _, weight ]) => weight
)[0] as Action;
}
function weightedRandom<T>(items: T[], weightFn: (item: T) => number): T {
if (items.length === 0) {
return null;
}
const weights = items.map(i => weightFn(i));
const weightSum = sum(weights);
const rand = Math.random() * weightSum;
let offset = 0;
for (let i = 0; i < items.length; i++) {
if (rand <= offset + weights[i]) {
return items[i];
}
offset += weights[i];
}
// This part should be never reached!
throw new Error('This function must have been implemented incorrectly! :O');
}
Test 🧪
Simples Labyrinth
Training im folgenden Labyrinth:
+---+---+---+---+
| | | | X |
+---+---+---+---+
| | # | # | |
+---+---+---+---+
| P | | | |
+---+---+---+---+
Training with 100000 training cycles took 1912 milliseconds! 😎
Average count of actions to solve the maze: 43 🤙
📃 Q table:
<Entfernt, da zu groß>
🗺️ Best route:
+---+---+---+---+
| | | | X |
+---+---+---+---+
| | # | # | |
+---+---+---+---+
| P | | | |
+---+---+---+---+
Performing action: up
+---+---+---+---+
| | | | X |
+---+---+---+---+
| P | # | # | |
+---+---+---+---+
| | | | |
+---+---+---+---+
Performing action: up
+---+---+---+---+
| P | | | X |
+---+---+---+---+
| | # | # | |
+---+---+---+---+
| | | | |
+---+---+---+---+
Performing action: right
+---+---+---+---+
| | P | | X |
+---+---+---+---+
| | # | # | |
+---+---+---+---+
| | | | |
+---+---+---+---+
Performing action: right
+---+---+---+---+
| | | P | X |
+---+---+---+---+
| | # | # | |
+---+---+---+---+
| | | | |
+---+---+---+---+
Performing action: right
+---+---+---+---+
| | | | P |
+---+---+---+---+
| | # | # | |
+---+---+---+---+
| | | | |
+---+---+---+---+
Q-Tabelle
Komplexes Labyrinth 😵💫
Das Labyrinth:
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | | | | | # | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | P |
+---+---+---+---+---+---+---+---+---+
Training with 100000 training cycles took 16375 milliseconds! 😎
Average count of actions to solve the maze: 713 🤙
📃 Q table:
<Entfernt, da zu groß>
🗺️ Best route:
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | | | | | # | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | P |
+---+---+---+---+---+---+---+---+---+
Performing action: left
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | | | | | # | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | P | |
+---+---+---+---+---+---+---+---+---+
Performing action: left
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | | | | | # | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | P | | |
+---+---+---+---+---+---+---+---+---+
Performing action: up
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | | | | P | # | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
Performing action: left
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | | | P | | # | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
Performing action: left
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | | P | | | # | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
Performing action: left
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | P | | | | # | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
Performing action: down
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | | | | | # | |
+---+---+---+---+---+---+---+---+---+
| | | | P | | # | | | |
+---+---+---+---+---+---+---+---+---+
Performing action: left
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | | | | | # | |
+---+---+---+---+---+---+---+---+---+
| | | P | | | # | | | |
+---+---+---+---+---+---+---+---+---+
Performing action: left
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | | | | | # | |
+---+---+---+---+---+---+---+---+---+
| | P | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
Performing action: left
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | | | | | # | |
+---+---+---+---+---+---+---+---+---+
| P | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
Performing action: up
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| P | # | | | | | | # | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
Performing action: up
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| P | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | | | | | # | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
Performing action: up
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| P | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | | | | | # | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
Performing action: right
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | P | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | | | | | # | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
Performing action: right
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | | P | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | | | | | # | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
Performing action: right
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | | | P | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | | | | | # | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
Performing action: up
+---+---+---+---+---+---+---+---+---+
| | # | | X | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | P | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | | | | | # | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
Performing action: up
+---+---+---+---+---+---+---+---+---+
| | # | | P | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
| | # | # | # | # | # | | | # |
+---+---+---+---+---+---+---+---+---+
| | # | | | | | | # | |
+---+---+---+---+---+---+---+---+---+
| | | | | | # | | | |
+---+---+---+---+---+---+---+---+---+
Q-Tabelle
Anwendungsideen
Navigation
Navigationsapps könnten ähnliche Algorithmen benutzen, um zum Ziel zu kommen. Vermutlich müsste man den Agent allerdings ein wenig intelligenter implementieren.
Robotik
Beispielsweise könnte ein Roboterarm möglichst effiziente Bewegungsabläufe erlernen.
Code 📃
Der Quellcode kann auf GitHub eingesehen werden: q-learn-maze
Weitere Ideen
Randomizing
In der echten Welt, klappt nicht jede Aktion so wie geplant. Dies könnte auch in dieser Implementation simuliert werden, indem manchmal zufällig eine andere Aktion ausgeführt wird.
Negative Belohnung
In vielen echten Anwendungsfällen sollten manche Aktionen bestraft werden. Zum Beispiel wenn ein Roboterarm in die Decke schlägt. Dies könnte auch in diesem Labyrinth simuliert werden, in dem es Felder mit Strafen gibt.
Dafür müsste der Algorithmus zum setzen der Q-Werte überarbeitet werden.
Weitere positive Belohnungen
Zusätzlich zu der Belohnung am Ziel, könnten weitere Belohungsfelder eingebaut werden. Der Agent würde sich dann eher über die Belohnungsfelder zum Ziel hangeln. Dies birgt weitere Komplexität. Der Agent könnte zum Beispiel versuchen immer wieder auf ein Belohnungsfeld zu gehen, um unendlich Belohnungen zu sammeln. Eventuell könnte das Problem gelöst werden, in dem es am Ziel mehr Belohnung gibt, als auf anderen Belohnungsfeldern.
Diagonale Schritte
Der Aktionsumfang könnte durch die Möglichkeit diagonaler Schritte ergänzt werden.