Das Projekt SnowPlow

SnowPlow – The Game

Bei diesem Spiel geht es um das Räumen von Schnee auf einem Flughafen.

Ziel des Spiels ist es, eine möglichst hohe Punktzahl durch das Räumen von möglichst viel Schnee zu erreichen. Die Schneeräumfahrzeuge können vom Spieler frei auf der Wegekarte (Map) des Flughafens bewegt werden. Die Map besteht einerseits aus Transportwegen, die mit einem Fahrzeug geräumt werden und andererseits aus Start-/Landebahnen (Runways), für die mehrere Fahrzeuge gleichzeitig benötigt werden. Zusätzlich gibt es die Wegkreuzungen, an denen der Spieler Entscheidungen über die weitere Fahrtrichtung der Fahrzeuge treffen muss.

snowplow

Das Problem ist, mehrere Fahrzeuge in einem komplexen Wegenetz so zu koordinieren, dass möglichst schnell und effektiv geräumt wird.

Der entscheidende Punkt bei diesem Spiel ist, dass der Spieler zusätzlich gegen einen virtuellen Gegner antritt. Hierbei handelt es sich um einen Hochleistungs-Algorithmus der neuesten KI-Generation. Er heißt Snowi, ist lernfähig und kann sich innerhalb von Sekunden auf wechselnde Umgebungsbedingungen einstellen.

Für dieses Spiel wurde Snowi auf die Aufgabe des Schneeräumens trainiert. Snowi verfügt demnach nicht über fest programmierte Lösungen der jeweiligen Aufgabe, sondern versucht jedes Mal, wie der menschliche Spieler auch, im Rahmen des Spielverlaufs eine möglichst hohe Punktzahl zu erzielen.

Wie funktioniert Snowi ?

Eine herkömmliche analytische Lösung des beschriebenen Schneeräumproblems ist aufgrund der hohen Komplexität (viele Fahrzeuge, viele mögliche Wege) und der großen Anzahl von sich ständig ändernden Variablen (Schneeaufkommen, Flugplanänderungen, Hindernisse, usw.) nicht in Realtime möglich.

SnowPlow bedient sich deshalb eines evolutionären Algorithmus (Snowi), der entwickelt wurde, um bei hochkomplexen Problemen, in unendlich vielen möglichen Lösungen, innerhalb kürzester Zeit eine sehr gute Lösung zu finden.

Der Lösungsansatz über diesen neuartigen evolutionären Algorithmus unterscheidet sich zudem grundsätzlich von einem analytischen Ansatz:

Das Programm selbst benötigt kein Wissen über das eigentliche Problem (in Form von passend erstellten Formeln und Regeln). Was es dagegen benötigt sind:

a) Eine wirklichkeitsnahe Simulationsumgebung des Problembereichs, um die Problemlösung zu simulieren

b) Einen effektiven evolutionären Motor, der eine große Anzahl von Lösungsvorschlägen produzieren, gegeneinander auswerten, miteinander kombinieren und dadurch stetig verbessern kann.

c) Ein Punktesystem, das die Lösungen mithilfe von „Belohnungen“ und „Strafen“ in eine gewünschte Richtung treibt.

Dass Snowi kein inneres Wissen über das Problem besitzt, und trotzdem hochkomplexe Probleme lösen kann, mag verwirren. Aber das ist die Funktionsweise der künstlichen Evolution: unter einem simulierten evolutionären Überlebensdruck, mit Hilfe einer großen Anzahl von Varianten, sich stetig verbessernde Lösungsansätze zu entwickeln. Es ist genau diese Art der Lösungsfindung, die Snowi beim Schneeräumen benutzt. Und es ist genau diese Art der Lösungsfindung, mit der unser Algorithmus auch beliebige andere Optimierungsprobleme lösen kann.

Mehr zu diesem Thema finden Sie in unserem Sachbuch C-SYSTEME, Consystology, bestellbar unter www.cs-books.com

Oder haben Sie Lust bekommen, das Spiel SnowPlow auszuprobieren ? Den kostenlosen Download finden Sie ebenfalls auf www.cs-books.com

Wie funktioniert Snowi ?  – Die etwas technischere Sichtweise.

Ein evolutionärer Algorithmus (EA) findet Lösungen, indem er in einer virtuellen Welt von Bergen und Tälern auf die eine oder andere Weise nach Optimi sucht (Maximi = Berggipfel oder Minimi = Täler). In der Regel werden diese Optimi dadurch gefunden, dass sogenannte Agenten von einem Startpunkt aus in verschiedene zufällig gewählte Richtungen losgeschickt werden. Nach einer Wanderung von einer gewissen Länge wird gemessen, ob die neue Lage optimaler ist oder nicht. Ist sie es nicht, wird die Lösung verworfen, ist sie es, dient sie als Ausgangspunkt für eine neue Suche.

Im Beispiel von Snowi sucht das Programm nach einem möglichst hohen Gipfel, der in der Realität der Beseitigung von möglichst viel Schnee in möglichst kurzer Zeit entsprechen sollte.

Diese reale Zielvorgabe muss auf die eine oder andere Weise in virtuelle Täler und Berge umgesetzt werden.

Eine direkte Umsetzung, bei der die Evaluierungsfunktion (also die Funktion, die für jeden gegebenen Punkt in der virtuellen Welt die Höhe der Berge berechnet) durch „beseitigter Schnee / Zeit“ ausgedrückt würde ist in der Regel sehr ineffektiv.

Ein EA findet Lösungen dagegen durch eine Wanderung, bei der jeder Schritt zwar zufällig gewählt wird, jedoch nicht unbedingt mit gleicher statistischer Wahrscheinlichkeit. So kann man dem Programm beispielsweise unter die Arme greifen, indem ein Schritt der nach „oben“ führt wahrscheinlicher ist, als ein solcher, der nach „unten“ führt.

Wählt das Programm jedoch IMMER einen Schritt nach oben, dann ist garantiert, dass das Programm den nächsten Hügel erklimmen wird, andere viel höhere Gipfel, die einen kurze Wanderung durch ein Tal benötigt hätten, jedoch nie erreichen wird. Daher muss das Programm auch mal „nach unten“ gehen können.

Wenn wir ein Problem mit Hilfe eines EA lösen wollen, müssen wir also

a) das reale Problem möglichst wirklichkeitsgetreu durch eine virtuelle Landschaft darstellen, sodass theoretische Lösungen (Berggipfel) in der Realität als optimal empfunden werden,

b) dafür sorgen, dass eine Lösung, die in der Realität als optimal empfunden wird, überhaupt gefunden wird.

c) dafür sorgen, dass eine Lösung, die in der Realität als optimal empfunden wird, statistisch wahrscheinlich ist.

Explizit auf Snowi bezogen haben wir nun ein Programm, dessen gelieferte optimale Lösungen tatsächlich das reale Problem optimal lösen würden (a), bei dem die Qualität dieser Lösungen durch gezielte Einstellungen der Suchparameter schrittweise verbessert werden kann (b) und das schließlich diese Lösungen auch schnell genug findet (c).

Die weitere Forschungsarbeit wird darauf fokussieren, „Fehler“ in den Lösungsvorschlägen zu identifizieren (z.B. auf einer geräumten Strecke hin und herfahren, anstatt eine lange Pause zu machen, oder eine fast „räumreife“ Strecke zu befahren, anstatt etwas zu warten und sie dann zu räumen). Diese Art der Fehler kann drei Ursachen haben:

1) Die gewählte Lösung ist tatsächlich besser, weil dadurch der Wagen etwas eher an z.B. einer Runway ankommt, um diese zusammen mit anderen wartenden Wagen zu räumen, anstatt diese warten zu lassen.

2) Die Prioritäten verschiedener Aufgaben sind unzureichend exakt gesetzt, und die Lösung ist zwar in der virtuellen Welt optimal, nicht jedoch in der realen. Hier gilt es das Verhältnis zwischen virtueller und realer Welt besser zu untersuchen.

3) Die gefundene Lösung ist weder in der virtuellen noch der realen Welt gut und wurde gewählt, weil eine bessere Lösung statistisch sehr unwahrscheinlich war und daher nicht gefunden wurde. Hier gilt es diese Wahrscheinlichkeiten näher zu untersuchen und eventuell den Programmcode so zu ändern, dass die optimale Lösung leichter gefunden werden kann.

Unseres Erachtens nach, liegen mehr als 95% der kommenden Forschungsarbeit im Bereich 3), während parallel dazu die „Wirklichkeitstreue“ der virtuellen Welt stetig verbessert werden kann (Karten, die mit tatsächlichen Flughäfen übereinstimmen; realistische Fahrbewegungen und Fahrgeschwindigkeiten der Wagen; realistische „Hindernisse“ wie Verkehrsregeln, andere Fahrzeuge etc; realistische Rahmenbedingungen wie Arbeitszeiten, Pausen für die Fahrer oder das Tanken der Wagen etc) Letzteres sollte jedoch in Zusammenarbeit mit einem realen Anwender mit spezifischen Kenntnissen geschehen.