Autoren:
Datum:
Stichworte:
Zusammenfassung:
Das von Long-Ji Lin in seiner Doktorarbeit vorgestellte Verfahren zur Navigation autonomer mobiler Roboter orientiert sich an natürlichem Verhalten. Es ermöglicht einem Roboter, verschiedene grundlegende Verhalten zu lernen und diese dann sinnvoll zu kombinieren, um Navigationsaufgaben in komplexer Umwelt zu bewältigen. Unser erstes Ziel war es, eine geeignete Umsetzung der Ideen von Lin zu implementieren, die in der Lage ist, die Grundverhalten zu erlernen.
Die 1993 veröffentlichte Doktorarbeit von Long-Ji Lin (lin93 ) befaßt sich in erster Linie mit verschiedenen Verfahren des Reinforcement-Learnings (Der Begriff Reinforcement-Learning ist ein fester Begriff in der Literatur, so daß wir hier die Originalbezeichnung anstelle einer Eindeutschung verwenden werden. Reinforcement-Learning läßt sich nur unschön als "Verstärkungs-Lernen" übersetzen und bezeichnet das Lernen durch seine Umwelt mit Hilfe von Belohnungen und Bestrafungen. Ein genauere Erläuterung folgt später im Text. ) und insbesondere mit Möglichkeiten, den Lernvorgang zu beschleunigen. Eine gewählte Anwendung beschreibt dabei die Steuerung eines simulierten autonomen mobilen Roboters, der in einer komplexen Umgebung aus drei Räumen lernen soll, seine Ladestation zu finden und an ihr anzudocken. In der Gruppe 42 erschien uns der von Lin gewählte Ansatz sehr vielversprechend für unseren Rollstuhl, da er sich zum einen entfernt an dem Vorbild Natur orientiert und zum anderen außerordentlich flexibel und leicht erweiterbar ist.
Wie bereits erwähnt, besteht das wesentliche Ziel des Ansatzes in dem Erlernen eines Navigationsverfahrens für komplexe Umgebungen. Das von Lin vorgestellte Verfahren beschäftigt sich dabei in erster Linie mit dem Finden eines Weges von einer beliebigen Ausgangsposition zu einer vorgegebenen Zielposition; es läßt sich aber mit nur geringfügigem Aufwand auch auf mehrere unterschiedliche Zielpositionen erweitern.
Durch die Generalisierung mit Hilfe von neuronalen Netzen ist der vorgestellte Algorithmus in der Lage, auch sinnvoll mit Sensor- und Aktorfehlern umzugehen. In der von Lin benutzten Simulation führte auch die Verwendung von systematischen sowie stochastischen Sensorfehlern in der Größenordnung von 10 Prozent und stochastischen Aktorfehlern in der Größenordnung von 8 Prozent zu guten Resultaten.
Um die Lernzeiten des Roboters zu verkürzen, benutzt Lin die Integration des Lernens durch Vormachen (teaching). Diese Technik läßt sich problemlos und ohne viel Aufwand in das gewählte Verfahren integrieren und führt in den vorgestellten Beispielen bei gleichem Zeitaufwand (Anzahl der Lernschritte) zu beachtlichen Verbesserungen des Gesamtverhaltens. Eine weitere Verkürzung der Lernzeiten bringt die Nutzung eines hierarchischen Ansatzes, bei dem zuerst elementare Verhalten (behaviours) gelernt werden, die dann zur Lösung komplexerer Aufgaben beitragen. (Weiter unten folgt noch eine etwas ausführlichere Beschreibung dieser Idee.)
Um die Bewältigung der Aufgabe zu erleichtern und sie zu strukturieren, hat Lin in seiner Doktorarbeit einige einfachere Teilaufgaben formuliert, die elementare Navigationsprobleme lösen. In seinem Fall sind dies Wandverfolgung auf der rechten oder linken Seite, Durchfahren einer Tür und Andocken an der erwähnten Ladestation. Da es mit unserer Sensorik schwierig sein wird, so exakt zu navigieren, daß man an einem Schreibtisch o. ä. andocken kann, werden wir das letzte Verhalten zuerst weglassen, die anderen werden entsprechend übernommen. (Weitere Elementarverhalten lassen sich hier problemlos integrieren. Falls die Gesamtnavigation zu keinem befriedigendem Ergebnis führt, kann man beispielsweise hier über eine Erweiterung nachdenken.)
Von dem Roboter werden dabei für jedes Verhalten Situations-/Aktions-Paare gelernt. Eine Situation besteht dabei neben den aktuellen Sensordaten auch aus internen Informationen über die Vergangenheit und eventuell extern aufbereiteten Daten. (Da wir im Projekt mehrfach über eine globale Positionsbestimmung nachgedacht haben, bietet es sich beispielsweise auch an, falls diese zu vernünftigen Ergebnissen kommt, diese mit in die aktuelle Situation einzubeziehen. Solange an wesentlicher Sensorik für die Navigation nur die Ultraschallsensoren als entfernungsmessende Sensoren zur Verfügung stehen, wird dies vermutlich auch zwingend nötig sein, um die zwangsläufig häufig gleichartigen Sensorbilder unterscheiden zu können. Die Odometriedaten sollen später außerdem in ähnlicher Weise mit einfließen.) Um diese Paare zu lernen, werden neuronale Backpropagation- (für die Grundverhalten) und später auch Elman-Netze (für die Navigation) verwendet, wobei als Aktivierungsfunktion die symmetrische Sigmoidfunktion eingesetzt wird: (Die Standard-Sigmoidfunktion ist total und differenzierbar und bildet die gesamten reellen Zahlen in den Bereich zwischen 0 und 1 ab, wobei die größte Steigung bei 0 zu finden ist. Für Backpropagation-Netzwerke besitzt sie den Vorteil, daß sie nichtlinear ist und eine einfache Ableitung besitzt. Die symmetrische Sigmoidfunktion ist lediglich eine um -0.5 verschobene Variante der normalen und führt zu verkürzten Lernzeiten des Netzwerkes. (siehe auch die Dokumentation zu der Klasse Net))
Die grundlegende Idee des Reinforcement-Learning ist es, jede Aktion (des Roboters) zu bewerten, d. h. sie wird in Form eines Zahlenwertes belohnt (positive Werte) oder bestraft(negative Werte). Das Ziel des Agenten ist es nun, die Belohnungen zu maximieren bzw. die Bestrafungen zu minimieren. (Diese beiden Ansätze sind prinzipiell gleichwertig und sogar miteinander kombinierbar, so daß sie im weiteren Verlauf dieses Berichtes nicht mehr unterschieden werden.) Dazu ist es nötig, vorausschauend zu handeln, um nicht in Situationen zu geraten, in denen Bestrafungen unausweichlich sind. (In unserem Fall bedeutet dies, daß es beispielsweise ungünstig wäre, so nah an eine Wand heranzufahren, daß bei einem weiteren Vorwärtsschritt eine Kollision unvermeidelich wäre. Also muß schon bei der Aktion vorher berücksichtigt werden, daß einige Aktionen in eine Sackgasse führen können.) Es gilt also, die Summe über die Bewertungen aller zukünftigen Aktionen zu maximieren und nicht nur den unmittelbar nächsten Schritt zu betrachten. Da aber unter Umständen, insbesondere in der Anfangsphase des Lernens aber natürlich auch bei nicht-statischen Umgebungen, noch nicht genügend oder gar keine sinnvollen Informationen über mögliche zukünftige Bewertungen vorhanden sind und außerdem die unmittelbar nächste Bewertung prinzipiell wichtiger sein soll, als eine, die der Agent vielleicht irgendwann später einmal erhalten könnte, werden die einzelnen Reinforcement-Werte entsprechend gewichtet, so daß sie mit abnehmendem zeitlichen Abstand immer unwichtiger werden. Dies führt auch dazu, daß der Agent nach ausreichender Exploration seiner Umgebung auf dem kürzesten Weg zu seinem Ziel fährt, da die gewöhnlich dort zu bekommende hohe Belohnung dann am stärksten in die Vorhersage einfließt. Dieser Wert V, der im englischen als discounted cumulative reinforcement oder einfach utility bezeichnet wird, ließe sich theoretisch zum Zeitpunkt t folgendermaßen berechnen, wenn alle zu erwartenden Reinforcementwerte schon bekannt wären: Dabei bezeichnet r die Bewertung zum Zeitpunkt x und 0 < γ < 1 das Maß der Beachtung zukünftiger Bewertungen.
Um Vorhersagen machen zu können, wie hoch dieser Wert
bei der Auswahl einer bestimmten Aktion zum aktuellen Zeitpunkt
(vermutlich) sein wird, nutzt Lin für jede mögliche Aktion ein eigenes
neuronales Netzwerk (One Action - One Network, vgl. auch
Abbildung
oaonnets). Dies hat den
Sinn, daß der unten beschriebene Lernvorgang nur die Bewertung
einer Aktion in einer spezifischen Situation ändert und die anderen
dabei nicht beeinflußt. Die Netzwerke bekommen als Eingabe die
aktuellen (aufbereiteten) Sensordaten und sollen als
Ausgabe den geschätzten Nutzen liefern. Die einfachste Variante des
Lernens besteht dann darin, die höchstbewertete Aktion auszuführen und
diesen Schritt bewerten zu lassen. In der neuen Position läßt sich
dann der maximale geschätzte Nutzen, der von hier aus erreichbar ist,
ermitteln, indem die aktuellen Sensorwerte wiederum durch alle Netzwerke
geschickt werden. Diese beiden Werte zusammen ermöglichen eine
exaktere Vorhersage des zu erwartenden Nutzens als das Netzwerk in
der vorhergehenden Situation schätzen konnte, so daß dieses nun in
die entsprechende Richtung trainiert werden kann (s.u.). Die oben
erwähnte Maximierung des Nutzens geschieht in diesem Fall also einfach
dadurch, daß immer die höchstbewertete Aktion ausgeführt wird.
(Abbildung:
)
Offensichtlich kann das Verhalten, immer die vermutlich beste Aktion auszuwählen, zu einem Problem führen: Falls der Agent ein ungünstiges Verhalten lernt, daß aber zum Ziel führt, (In diesem Fall bedeutet das, daß der Nutzen in einer jeden Situation mindestens genauso groß ist, wie der Vorhergesagte, damit die Netzwerke, die an diesem Pfad beteiligt sind, nicht ihre Ausgabe verkleinern.) und den Rest seiner Umgebung gar nicht kennen sollte, so wird er nie mehr von diesem Weg abweichen. Das bedeutet, daß in irgendeiner Weise ein Explorationsverhalten integriert werden sollte. Lin entscheid sich hier für eine stochastische Aktionsauswahl, bei der die Wahrscheinlichkeit, daß eine Aktion ausgewählt wird, von ihrem durch die Netzwerke vorhergesagtem Nutzen abhängt, damit in fast allen Fällen Aktionen ausgewählt werden, die zu einem hohen Gesamtnutzen führen. Die Zufälligkeit dieses Auswahlprozesses ist dabei mit einem Parameter wählbar, so daß es möglich ist, anfangs ein relativ willkürliches Auswahlverfahren zu benutzen, um die Umgebung zu explorieren und später dann mit einer geringeren Streuung möglichst direkt auf dem kürzesten Weg zum Ziel zu gelangen. Die Wahrscheinlichkeit der Auswahl einer Aktion wird dabei mittels folgender Gleichung ermittelt: wobei x die aktuelle Situation und T die Zufälligkeit der Auswahl beschreibt. (T bestimmt die Steilheit der e-Funktion, so daß höhere Werte für T zu einer zufälligeren Auswahl führen. Lin schlägt vor, anfangs einen Wert von T=0.05 zu wählen und diesen während des Lernens langsam auf T=0.02 zu verringern.)
Der an die oben beschriebe Netzstruktur angepaßte Q-Learning-Algorithmus besitzt den folgenden algorithmischen Aufbau:
Damit der Agent mit Hilfe des oben vorgstellten Verfahrens ein sinnvolles Verhalten erlernen kann, ist es nötig, eine Funktion zu entwickeln, die jede Situation und/oder Aktion, je nach gewünschtem Verhalten, bewertet. Um dabei einen wirklich autonomen Roboter zu erhalten, ist es nötig, die Bewertung nicht von der Umwelt - also in diesem Fall einem externen "Lehrer" - vornehmen zu lassen, sondern eine entsprechende Reinforcement-Funktion in den Agenten zu integrieren, die in der Lage ist, die ausgeführte(n) Aktion(en) in Zusammenhang mit dem aktuellen Sensorbild zu belohnen oder zu bestrafen. Für die für uns interessanten Grundverhalten verwendet Lin dabei die folgenden Bewertungstabellen, wobei die Bedingungen jeweils in der angegebenen Reihenfolge überprüft werden:
Bei der Wandverfolgung (An vielen Stellen dieses Berichts wird von dem Erreichen eines Ziels gesprochen, bei dem der Agent belohnt wird. Bei der Wandverfolgung gibt es im eigentlichen Sinne kein Endziel, sondern viele kleine, die darin bestehen, möglichst immer in der Nähe der entsprechenden Wand zu bleiben und sich vorwärts zu bewegen.) wird der Agent für jeden Rückwärtsschritt ein wenig bestraft, um zu verhindern, daß einfach der richtige Abstand zur Wand eingehalten wird, indem immer nur vor und zurück gefahren wird. (Durch diese Bewertung wird der Agent automatisch auch dazu gezwungen, immer vorwärts entlang der Wand zu fahren, da in jedem Schritt eine auszuführende Aktion auszuwählen ist und zumindest bei Lin und in unserer Variante kein "Leerschritt" zugelassen ist.) Die Bewertung der Parallelität zu der zu verfolgenden Wand, indem einfach die Sensorwerte auf der entsprechenden Seite miteinander verglichen werden, führte nach Lin dazu, daß eine bessere Wandverfolgung gelernt wird, als bei einer konstanten Belohnung. Alle mit 0 bewerteten Schritte führen dazu, daß die Auswahl der Aktion nur von dem zu erreichenden Belohnungswert der darauffolgenden Situation abhängt, was wiederum zu einem Verhalten führt, daß die Aktion bevorzugen muß, die auf dem schnellsten Wege zum Ziel führt. Die Belohnungen bzw. Bestrafungen wurden dabei so gewählt, daß die einzelnen Q-Netze bei einem γ von 0.9 immer nur Werte zwischen -100 und 100 vorauszusagen brauchen.
Das normale Q-Lernen mit neuronalen Backpropagation-Netzwerken ist außerordentlich langsam, insbesondere da jeweils nur eine Aktion weit in die "Zukunft" geblickt wird. Da aber am Anfang die Vorhersagen der Netze im nächsten Schritt eigentlich keinerlei sinnvolle Informationen über die tatsächlich zu erwartende Bewertung haben, lernen die Netze anfangs nur, das direkt zu erwartende Reinforcement vorherzusagen, welches mit einer Art "Rauschen" durch das hinzuaddierte maximale Ergebnis der Netze im folgenden Schritt modifiziert wird. Da anfangs also keinerlei Informationen über gute oder schlechte Aktionen vorliegen, ist das Verhalten hier mehr oder weniger zufällig, und entsprechend kann es sehr lange dauern, bis einmal das gewünschte Ziel erreicht wird. Durch das fast ausschließliche Lernen des unmittelbaren Reinforcements ist also im ersten Durchlauf hauptsächlich der Schritt, der direkt zum Ziel führt, für ein sinnvolles Lernen des Grundverhaltens verantwortlich. In einem zweiten Durchlauf könnte man auch bei Aktionen, welche zu den Situationen führen, die zum Ziel führen, einen gute Lernvorgabe für das Netz erwarten, usw. Insgesamt sieht man aber, daß ein enormer Lernaufwand nötig ist, bis ein überall sinnvolles Verhalten zu erwarten ist. Dazu kommt noch, daß Backpropagation-Netzwerke im allgemeinen äußerst langsam lernen, also jedes Situations-/Aktionspaar möglichst häufig mit den gleichen Ergebnissen bewertet werden müßte.
Man sieht also, daß der normale Q-Learning Ansatz in Verbindung mit neuronalen Netzen für einen Roboter, der in einer realen Umwelt navigieren soll, viel zu langsam lernt. Die Lösung dieses allgemein bekannten Problems ist eine der Hauptaufgaben, die Lin in seiner Dissertation behandelt. Zum beschleunigten Erlernen der Grundverhalten haben sich in seinen Vorversuchen insbesondere zwei Verfahren als besonders effektiv herausgestellt, die im folgenden kurz erläutert werden sollen.
Um das Problem zu umgehen, daß der Roboter immer nur aus der unmittelbaren Bewertung der letzten Aktion und den Vorhersagen der Q-Netze in dieser Situartion lernt, hat Lin das Prinzip des experience replay, das auf den Ideen der temporal difference Methode von Sutton in (sutton88 ) basiert, eingeführt. Grundidee dieser Methode ist es, alle wichtigen Daten auf dem Weg des Agenten aufzuzeichnen, um auch in frühen Situationen aus den Bewertungen zu viel späteren Zeitpunkten lernen zu können. Aus diesem Grunde definiert sich Lin zwei Begriffe, die wir hier auch verwenden möchten, da sie die weiteren Erklärungen vereinfachen und übersichtlicher gestalten:
In dem erweiterten Verfahren werden nun alle bisher gemachten Erfahrungen während eines Versuchs aufgezeichnet, damit die ersten gewählten Aktionen nicht nur aus dem direkten Reinforcement, sondern auch aus den Bewertungen der folgenden Schritte profitieren können. Das Verfahren benutzt dabei eine über die zukünftigen Erfahrungen rekursive (Lin hat in seiner Beschreibung des Algorithmus eine iterative Darstellungsweise benutzt, aber die Grundidee des Algorithmus ist, wie man weiter unten sehen kann, rekursiv.) Variante des Q-Lernens, in der in jedem Schritt aus dem direkten Reinforcement und einem gewichteten Mittelwert der neuen Bewertung durch die Q-Netzwerke und dem zukünftigen Ergebnis eben dieser Berechnung für den folgenden Schritt gelernt wird. Die folgende algorithmische Beschreibung soll helfen, diese Zusammenhänge verständlich zu machen: (Der Algorithmus ist in etwas ungewöhnlicher Weise dargestellt und stellt eine Mischung zwischen der Beschreibung von Lin und unserer Implementation dar. Die grundsätzlich rekursive Vorgehensweise ist in Punkt 3 zu erkennen, wo jede Berechnung jeweils einen Wert aus der darauffolgenden Berechnung benötigt; der Algorithmus selber ist aber in Form einer Schleife über die Anzahl der Erfahrungen (m+1) notiert, d. h. es wird einfach vorausgesetzt, daß der benötigte Wert aus der nächsten Berechnung schon vorhanden ist. Lin stellt die Schleife in absteigender Form dar, wo dies dann auch der Fall ist. Unsere Umsetzung mit einer Erfahrungsliste verlangt aber die umgekehrte Vorgehensweise, so daß uns diese Notation näher an der Implementation erschien, die dadurch vielleicht einfacher verständlich ist. )
Die Technik des experience replay effektiviert zwar das Lernen im allgemeinen, löst jedoch noch nicht das Problem, daß der Agent zu Beginn des Lernvorgangs nur äußerst wenig über seine Aufgabe und seine Umgebung weiß, so daß er erst einmal zufällig "in der Gegend herumfahren" muß, bis er mit etwas Glück einige Male Aktionen ausführt, die belohnt werden. Dies sind unter Umständen in vielen verschiedenen Situationen gänzlich unterschiedliche Aktionen, die alle erst einmal "geraten" werden müssen. Offensichtlich muß hierfür unnötig viel Zeit aufgewendet werden, zumal der Benutzer bzw. Programmierer des Agenten höchstwahrscheinlich weiß, welches Verhalten er von seinem Roboter verlangt.
Als Lösung zu diesem Problem bietet sich das Lernen durch Vormachen (teaching) an, welches sich äußerst einfach und effektiv mit dem oben beschriebenen experience replay Algorithmus implementieren läßt. Die Idee dabei ist es, dem Roboter einen oder mehrere Wege zu zeigen, die möglichst das gewünschte Verhalten in bestimmten Situationen vorgeben. Die einzelne Schritte und die jeweiligen Sensorwerte mit den entsprechenden Bewertungen werden dabei in Form einer Lektion festgehalten, die am Ende des Lehrvorganges mit dem oben gezeigten Algorithmus einmal oder mehrmals gelernt wird. Dies hat den großen Vorteil, daß der Lehrer den Roboter gezielt in markante Situationen steuern kann, in denen sinnvolles Verhalten durch extreme Bewertungen (im positiven oder negativen Sinn) erlernt werden kann.
Der Vorteil dieser Art des Lehrens gegenüber dem herkömmlichen supervised learning, wo der Lehrer das optimale Verhalten vorgeben muß, also das, welches der Roboter auch später zeigen soll, ist, daß hier weiterhin jede Aktion durch die Reinforcementtabellen bewertet wird, was dazu führt, daß das letztlich erlernte Verhalten nur durch diese Tabellen bestimmt wird. Deshalb stellt es auch kein Problem dar, daß der Lehrer unter Umständen selber kein wirklicher Experte für die zu lernende Aufgabe ist und gelegentlich ein paar Fehler macht, da dies von der Reinforcementfunktion erkannt wird und nicht zu einem falschen Gesamtverhalten führt. Ganz im Gegenteil kann es sogar günstig sein, während des Lehrens auch mal extreme Fehler zu machen, um dann einen Ausweg aus derartigen Situationen aufzuzeigen. Das Ziel bei dieser Art des Lehrens ist in erster Linie, den Agenten in Situationen zu bringen, in denen durch positive oder negative Bewertungen Erfahrungen zum Erlernen des Zielverhaltens gemacht werden können.
Die erlernten Grundverhalten werden benutzt, um durch geschicktes Wechseln an den richtigen Positionen das gewünschte Ziel zu erreichen, d. h. auf der nächsthöheren Hierarchiestufe der Steuereinheit werden anstelle von Aktionen wie Vorwärtsfahren oder Kreisbogen fahren Grundverhalten wie z. B. Wandverfolgung benutzt.
Um das Navigationsgebiet zu
strukturieren, wird es bei dem Ansatz von Lin in kleinere, sich
überschneidende Gebiete unterteilt. Innerhalb eines jeden Gebietes
wird dann eine zentrale Position gewählt, die als eine Art Landmarke
dient und zum einen möglichst markante Sensorwerte liefern
und zum anderen einen günstigen Ausgangspunkt zur weiteren
Navigation darstellen sollte. Von dem System wird dann gelernt, aus
der näheren Umgebung einer solchen zentralen Position (von Lin als
subgoal bezeichnet) zu dieser zu fahren. Da sich die Gebiete
überschneiden, ist es dann möglich, von jeweils einem Unterziel zum
nächsten zu gelangen und so letztendlich zu seinem globalen
Ziel. Die Abbildung
subgoals demonstriert einen kleinen
Beispielraum mit 3 Unterzielen und deren Erfassungsgebieten, aus denen
heraus das jeweilige Unterziel erreicht werden kann.
(Abbildung:
)
Günstigerweise werden die Unterziele so gewählt, daß sie die Räume so strukturieren, daß sie jeweils auch Umschaltpunkte für die Elementarverhalten darstellen, was aber nicht zwingend der Fall sein muß. In der momentanen Ausführung von Lins Algorithmus müssen allerdings sowohl die Unterziele als auch die entsprechenden Ausmaße der zugehörigen Gebiete von Hand gewählt werden.
Gerade beim Erlernen der jeweiligen Funktionen zum Erreichen eines Unterziels aus seinem Einflußgebiet heraus bringt der "Lernen-durch-Vormachen"-Ansatz eine enorme Verbesserung der Lernzeiten, da das wahllose Experimentieren des Roboters anfangs häufig zu keinem sinnvollen Ergebnis führt und es deswegen auch sehr lange dauert, bis ein Großteil der Aktionen, die nicht zum gewünschten Ziel führen, durchprobiert und für schlecht befunden worden sind.
Zu dem Zeitpunkt, an dem dieser Bericht erstellt wurde, hatten wir diesen zweiten Teil - also die Navigation durch Auswahl elementarer Verhalten - noch nicht implementiert, da wir uns zuerst auf das Lernen der Grundverhalten konzentrieren wollten, welches allerdings mit einem kinematisch beschränktem Fahrzeug bislang zu keinem zufriedenstellenden Ergebnis führte, aber für die weitere Arbeit unerläßlich ist. Eine detailliertere Beschreibung des hierarchischen Lernens werden wir, falls der Algorithmus so erweitert werden kann, daß er für unsere Zwecke einsetzbar wird, zu gegebener Zeit zum besseren Verständniß zusammen mit unserer zugehörigen Implementierung nachliefern. Dieses Kapitel dient lediglich dazu, die weitere Arbeit von Lin anzureißen und den Blick auf das dahinterstehende Gesamtziel "Navigation" erkennen zu lassen.
Da wir uns in unserem Projekt für die Nutzung der objektorientierten Programmierpsrache C++ entschieden haben, bestand unser erster Ansatz zur Implementierung darin, das Gesamtproblem sinnvoll in Klassen zu zerlegen. Schon in der obigen Beschreibung der Algorithmen lassen sich dabei die folgenden Objekte separieren:
Eine genaue Erläuterung der einzelnen Funktionen mit ihren Parametern, Aufgaben und Rückgabewerten kann der beiliegenden Klassendokumentation entnommen werden.
An einigen Stellen seiner Dissertation benutzt Lin ungenaue oder nicht auf unsere Verhältnisse transferierbare Definitionen, die natürlich bei der Umsetzung in ein real existierendes Programm konkretisiert werden müssen. In erster Linie betrifft dies die Bewertungstabellen, bei denen er Sensorwerte für den richtigen Abstand zur Wand (in Inch) u. ä. vorgibt, die in SimRobot-konforme Werte, die immer zwischen 0 und 1 liegen, umzusetzen waren. Ein anderes Beispiel ist seine Bewertung der Parallelität zur Wand bei der Wandverfolgung, die nicht genauer als oben skizziert erläutert wird. Wir haben an dieser Stelle nur zwei verschiedene Rückgabewerte eingesetzt (10 und 8), wobei ein Wert von 8 dann vergeben wird, wenn die Differenz der Sensoren auf der entsprechenden Seite um mehr als 0.1 differiert.
Noch unklar ist die spätere Bewertung bei dem "Tür durchfahren"-Verhalten, da der Roboter bzw. die Reinforcementfunktion dabei selbständig in der Lage sein muß, zu erkennen, ob eine Türöffnung passiert wurde oder nicht, d. h., es müßte momentan aus einer Folge von Sensorbildern abgeleitet werden, ob die erfolgten Veränderungen den Prozeß des Durchfahrens einer Tür beschreiben. Dies ist mit den wenigen Ultraschall-Sensoren, die auf unserem virtuellen Versuchfahrzeug bzw. dem Rollstuhl vorhanden sind, paktisch unmöglich zu bestimmen. Abhilfe kann hier sicherlich die geplante Positionsbestimmung der Bildverarbeitungsgruppe schaffen, die alleine, aber auf jeden Fall zusammen mit der Karte, ausreichen muß, um zu erkennen, in welchem Raum man sich befindet. Bei SimRobot könnte man sich hier mit der internen Position des Vehikels helfen, die das Problem aber auf zu einfache, unrealistische Weise löst und deshalb für das spätere reale Verhalten nur wenig Aussagekräftig ist. Eine andere Möglichkeit wäre es, hier einen externen Lehrer einzuführen, der dem Roboter in irgendeiner Weise ein Signal gibt, wenn die Tür durchfahren wurde.
Ein weiteres Problem, das in der Dissertation nicht aufgelöst wird, ist die Vorhersage des insgesamt noch zu erwartenden Reinforcements durch Netze, die als Aktivierungsfunktion die verschobene Sigmoid-Funktion benutzen und daher nur Werte zwischen -0.5 und 0.5 ausgeben können, wobei der zu erhaltende Reinforcementwert maximal 100 betragen kann. Wir haben uns hier dafür entschieden, die Netze nicht direkt die maximal noch zu erwartenden Bewertungen voraussagen zu lassen, sondern stattdessen diesen Wert ebenfalls durch die Sigmoidfunktion zu konvertieren.
Da Lin in seiner Simulation einen Roboter benutzt hat, der in der Lage ist, sich auf der Stelle zu drehen, mußten wir die auf dem kinematisch beschränkten Roboter auszuführenden Aktionen komplett neu überlegen. Wir haben uns dafür entschieden, zehn unterschiedliche Aktionen zu definieren: (Bei der Definition der Aktionen ist darauf zu achten, daß es zu jeder Aktion eine "Gegenaktion" gibt, die die Wirkungen der vorherigen aufhebt. Sollte dies nicht der Fall sein, so kann es passieren, daß der Roboter sich unter ungünstigen Umständen so in eine Ecke manövriert, daß er diese nicht wieder verlassen kann.)
Um uns von der Funktionsfähigkeit des Ansatzes zu überzeugen und insbesondere auch seine Verwendbarkeit mit einem kinematisch beschränkten Vehikel zu testen, haben wir uns eine SimRobot Testszene entworfen, in welcher der Agent Wandverfolgung lernen sollte.
Wir haben den kinematisch beschränkten Roboter, der sich wie ein Fahrzeug mit einer lenkbaren und einer starren Achse verhält, für diesen Versuch mit 8 Ultraschallsensoren - zwei an jeder Seite - und einem Kompaß ausgestattet. Für das Wandverfolgungsverhalten ist dabei der Kompaß nicht von großem Nutzen, so daß die internen neuronalen Netze lernen müssen, von diesem Wert zu abstrahieren. Um das Verhalten des Lernverfahrens unter etwas realeren Bedingungen zu simulieren und zu überprüfen, inwieweit Sensorfehler den Lernvorgang und auch das später erlernte Verhalten beeinflußen, wurden alle Ultraschallsensoren mit einem stochastischen Fehler von 10 Prozent und der Kompaß mit einem stochastischen Fehler von 5 Prozent versehen. Da SimRobot kein "Verrauschen" der Aktorbefehle zuläßt, wurde auf diese Variante erst einmal verzichtet.
Die Umgebung, in
welcher der Roboter herumfahren soll, beinhaltet sowohl konkave als auch
eine konvexe Ecke, so daß auch erkannt werden kann, ob der Agent
wirklich Wandverfolgung oder nur Hindernisvermeidung betreibt - an der
konvexen Ecke muß bei der Wandverfolgung abgebogen werden, ohne daß
ein Hindernis bzw. eine Wand den weiteren Weg versperrt. Abbildung
lin1 zeigt die von uns gewählte Anfangskonfiguration in
dem Testraum.
(Abbildung:
)
Im ersten Versuch haben wir nur das oben beschriebene normale Q-Learning Verfahren mit Anpassung an die One Action - One Network Struktur benutzt und den Roboter ohne jegliches "Vorwissen" inmitten des Raumes plaziert. Die Netze liefern in diesem Zustand keine sinnvollen Werte, so daß die Auswahl der Aktionen anfangs prinzipiell nur zufällig stattfindet und entsprechend auch das Lernen nur durch das unmittelbare Reinforcement ermöglicht wird, da die Voraussagen im nächsten Zustand ebenfalls keinerlei Aussagekraft haben.
Tatsächlich erinnert das gezeigte Verhalten des Roboters anfangs auch größtenteils an eine zufällige Auswahl der auszuführenden Aktion. Wie wir oben bereits vermuteten, ist das größte Problem, was sich hier ergibt, daß der Roboter nur äußerst selten zufällig in Situationen gelangt, in denen er belohnt wird. Und falls dies doch einmal der Fall sein sollte, so lernen die Backpropagation-Netzwerke mit nur diesem einen positiven Beispiel so wenig (bzw. langsam), daß sich hieraus nur eine minimale Veränderung des Gesamtverhaltens ergibt. Entsprechend führt natürlich auch eine negative Bewertung nur zu minimalen Änderungen in den Netzaktivierungen, so daß es nicht nur in der Anfangsphase oftmals vorgekommen ist, daß der Roboter nach der Durchquerung des Raumes gegen die Wand fährt und, trotz des dort erhaltenen Reinforcements von -10, viele Male weiterhin versucht, vorwärts zu fahren.
Insgesamt ist zu sagen, daß der Roboter auch nach ca. 1000 Lernschritten - das sind ca. 17 komplette Raumdurchquerungen - noch kein sinnvolles Verhalten zeigte und nur äußerst selten Aktionen wählte, die dem gewünschten Verhalten "Wandverfolgung" entsprechen. Damit ist diese Variante aufgrund des äußerst langsamen Lernverhaltens für die Umsetzung auf dem Rollstuhl als unbrauchbar zu bezeichnen.
Um eine Beschleunigung des Lernverhaltens zu erzielen, haben wir als nächstes die Idee des experience replay mit integriert. Lin schlägt hier vor, daß dies am effektivsten ist, wenn man nicht nach einem "Trainingslauf" die gesamte Lektion noch einmal lernen läßt (batch mode), sondern stattdessen bei jedem Schritt auch schon wieder alle vorhergehenden Aktionsauswahlen trainiert (incremental mode). Dies führt zwangsläufig dazu, daß die gesamten Neuberechnungen der Netzwerke mit jedem Schritt mehr Zeit in Anspruch nehmen, so daß es bereits nach ca. 30 Aktionen auf einer Sparc Classic mehr als 5 Sekunden dauert, bevor ein weiterer Schritt ausgeführt wird. Aus diesem Grunde haben wir uns dafür entschieden, die Lektionen nach jeweils 30 Schritten abzubrechen und dann eine neue zu beginnen, da nach der Theorie auch dann eine enorme Verbesserung des Lernvorgangs zu erwarten ist.
Die entsprechenden Versuche haben allerdings die Theorie nicht zu unserer Zufriedenheit bestätigt. Zwar ändern sich die Bewertungen der einzelnen Netze in dieser Variante sehr viel schneller, das Verhalten erinnert aber ebensowenig an Wandverfolgung wie im ersten Versuch, d. h. das Verhalten scheint immer noch zum Großteil zufällig zu sein. Das Problem des langandauernden Fahrens gegen die Wand fällt in dieser Variante weg, aber die Kombination des schnelleren Lernens mit dem großen Unwissen über sinnvolle Aktionen, die auf jeden Fall anfangs herrscht, führt dazu, daß der Roboter bei längeren Fahrten mit Bewertung 0 auch ebenso schnell wieder verlernt, wie im Falle einer bevorstehenden Kollision zu reagieren ist.
Auch in dieser Variante hat der Algorithmus keine überzeugenden Ergebnisse geliefert. Ebenso wie bei Versuch 1 war der Lernvorgang viel zu langsam, als daß man ihn auf einem realen Roboter sinnvoll einsetzen könnte. Auch hier haben ca. 1000 Lernschritte nur zu einer äußerst unzureichenden Hindernissvermeidung, nicht aber zu einem als Wandverfolgung zu bezeichnenden Verhalten geführt.
Schließlich haben wir gehofft, mit der Möglichkeit des Lernens durch Vormachen die Leistung des Algorithmus wesentlich zu verbessern, da nach der Theorie ein Großteil des zufälligen "durch die Gegend fahrens" wegfallen soll. Nach Lin ist praktisch jede Lehrsequenz, die extreme Bewertungen erhält, für das spätere Verhalten von Nutzen. Aus diesem Grund haben wir unterschiedliche Experimente gemacht, bei denen wir verschiedene Möglichkeiten vorgegeben haben: Von nahezu absolut richtigem Verhalten bis hin zu einer äußerst schlechten Aktionswahl, die häufig zu negativen Bewertungen führte, und auch verschiedene Kombinationen aus diesen beiden Extremen.
Das Resultat dieser Experimente war allerdings größtenteils enttäuschend. Zwar war zu erkennen, daß der Roboter aus dem vorgegebenen Verhalten lernt, allerdings haben die neuronalen Netze hier die Eigenschaft, viel zu sehr zu generalisieren: Da während der normalen Wandverfolgung die Vorwärtsaktionen - geradeaus und leicht nach links oder rechts fahren - immer sehr hohe Bewertungen bekommen, wachsen die Ausgaben dieser Netze sehr viel schneller als alle anderen. Daraus folgt dann, daß der Roboter auch wenn er direkt vor einer Wand steht diese Aktionen hoch bewertet und dann geradewegs dagegen fährt. Die hieraus langsam folgende Abwertung der genannten Aktionen führt im Gegenzug dazu, daß auch das Wandverfolgungsverhalten, daß vorher noch zeitweise als sinnvoll zu bezeichnen war, nicht mehr funktioniert. Auch das Vormachen von Ausweichstrategien, mit denen man bevorstehenden Kollisionen sinnvoll entgehen kann, führten zu keiner Verbesserung dieses Verhaltens.
Ingesamt ist zu sagen, daß auch das Lernen durch Vormachen nicht den entscheidenden Durchbruch gebracht hat und die gleichen Probleme besitzt, wie die beiden anderen Varianten. Nachdem das einmal prinzipiell erlernte Verhalten wieder durch eine Kollision gestört wird, ist eigentlich keine assoziative Aktionsauswahl mehr erkennbar. Für die Umsetzung auf dem Rollstuhl ist auch dieser Algorithmus aufgrund seines immer noch viel zu langsamen Lernverhaltens nicht brauchbar.
Neben der Wahl der grundlegend unterschiedlichen Algorithmen, mit denen wir experimentiert haben, existieren noch weitere Parameter, die während des Lernvorganges verändert werden können.
Der von Lin gewählte Wert von 0.02 für die Lernrate der Backpropagation-Netzwerke erschien uns anfangs extrem niedrig und war das Erste, das wir veränderten, um zu einem schneller konvergierenden Lernverhalten zu gelangen. Tatsächlich aber scheint der Wert wenigstens in der richtigen Größenordnung zu liegen, da Werte von 0.2 und größer zu einem fast chaotischen Wechsel zwischen hohen und niedrigen Bewertungen führen.
Die Wahl des Faktors, der das Verhältnis zwischen unmittelbar erhaltenem Reinforcement und der nächsten Bewertung durch die Netzwerke bestimmt, scheint nicht sehr viel Bedeutung für das Lernverhalten zu haben. In der Theorie führt die stärkere Gewichtung des unmittelbar nächsten Schritts zu einem nicht so vorausschauendem Verhalten, sondern stattdessen zum schnelleren Lernen der Vorhersage der unmittelbar nächsten Aktion. In der Praxis änderte dies allerdings nichts an der oftmals unsinnigen Wahl der auszuführenden Aktion.
Schließlich ist auch die stochastische Aktionsauswahl ein problematischer Teil des Algorithmus. Die Werte der Netze sind anfangs größtenteils ähnlich, so daß die gewichtete zufällige Auswahl stark zu dem oben beschriebenen chaotischen Verhalten beiträgt. Außerdem kann die sporadische Wahl einer wirklich ungünstigen Aktion dazu führen, daß der Roboter einen prinzipiell guten Pfad verläßt und dann aufgrund mangelnder Informationen lange Zeit nicht zu dem gewünschten Verhalten zurückfindet. Dies ist zwar genau der Effekt, der mit dem Zufallselement bezweckt werden soll, er verstärkt aber aufgrund der angesprochenen starken Generalisierung der Netzwerke auch das Verlernen von bereits sinnvollem Verhalten. Unsere Experimente mit einer nicht-stochastischen Aktionswahl, wobei dann immer die höchstbewertete Aktion ausgewählt wird, führten insgesamt zu einem geringfügig schönerem Verhalten. Allerdings hatten wir hier des öfteren Probleme mit Kreisfahrten, die der Roboter im leeren Raum ausführt. Hier ist bei dem Wandverfolgungsverhalten die Situationsbewertung immer 0, so daß nur aus dem zukünftigen Ergebnis gelernt wird. Aufgrund der Gewichtung zwischen Netzwerkergebnissen und unmittelbarem Reinforcement ist zwar die erwartete Bewertung immer niedriger als die aktuelle, in der Realität kann dies aber dazu führen, daß der Agent äußerst lange im Kreis herumfährt, bevor er eine andere Aktion auswählt. Die folgende Ausgabe unseres Programmes dokumentiert eine derartige Situation: (Die Werte hinter "Network result" geben jeweils die Aktion an, deren Bewertung folgt. "Selected Action" ist die aufgrund dieser Informationen gewählte Aktion. "Actual reinforcement" ist die direkte Bewertung der erreichten Situation und "Expected reinforcement" das neue berechnete Ergebnis, welches nach neuerem Wissen eigentlich hätte vorausgesagt werden müssen. Im folgenden Schritt soll hier also das Netzwerk 2 in Richtung des Wert 0.670879 lernen. (Dieses Ergebnis entstammt einem Experiment mit einer anderen Aktivierungsfunktion, weshalb hier auch Werte größer als 0.5 enthalten sind.))
Die Veränderungen, die wir gegenüber der Dissertation von Lin vorgenommen haben, sind nur geringfügig. Die wesentlichen Unterschiede sind die Nutzung des kinematisch beschränkten Fahrzeugs und die Erweitwerung der Anzahl der möglichen Aktionen. Wenn man allerdings die Reinforcementgraphen (Ein Reinforcementgraph beschreibt das mittlere erhaltene Reinforcement in Abhängigkeit von den ausgeführten Schritten. Siehe hierzu auch S. 65 der Dissertation.) in der Dissertation genauer betrachtet, so kann man erkennen, daß auch Lin mit seinem omnidirektionalen simulierten Fahrzeug mindestens 50 trials benötigt, um ein halbwegs vernünftiges Wandverfolgungsverhalten zu bekommen. Ein trial hat dabei eine Länge von ungefähr 60 Schritten, so daß dies also insgesamt etwa 3000 Schritten entspricht. Gutes Wandverfolgungsverhalten wird dann nach etwa 2000 weiteren Schritten erreicht.
Leider konnten wir mit unserem relativ speicherintensiven Programm in Kombination mit SimRobot für XWindow, das einen Speicherfreigabefehler beinhaltet, nicht wesentlich mehr als die mehrmals genannten ca. 1000 Schritte ausführen, bevor kein Speicher mehr reserviert werden konnte. (Vermutlich gibt auch unser Programm nicht den gesamten genutzten Speicher wieder frei. Die Ursache hierfür müßte in der Schnittstelle zu den Netzwerken bzw. der Vektorklasse liegen, die kurz vor der Ausarbeitung dieses Berichtes noch einigen wesentlichen Veränderungen unterzogen worden sind, so daß an einigen Stellen Befehle für die Speicherfreigabe fehlen könnten. Diese Fehler werden in einer nächsten Version des Programmes, falls es diese geben sollte, behoben sein.) Aber ein Ansatz, der auf unserem Rollstuhl implementiert werden soll, sollte nach 1000 Schritten doch wenigstens ein halbwegs sinnvolles Verhalten zeigen, so daß aus diesen Versuchen die prinzipiellen Unzulänglichkeiten der Ideen von Lin für einen realen Einsatz bereits deutlich werden.
Das erste Ziel weiterer Änderungen muß natürlich die Verbesserung des Lernverhaltens der Grundverhalten sein, da ohne diese die Implementierung der höheren Hierarchiestufen zwecklos ist. Die Ideen des Reinforcement-Learning und die von Lin vorgenommenen Erweiterungen sind vielversprechend, und die äußerst langsam lernenden Backpropagation-Netzwerke scheinen das größte Problem für den Einsatz auf einem realen Rollstuhl zu sein. Daraus resultiert, daß ein anderes Verfahren zum Speichern der gemachten Erfahrungen gefunden werden muß.
Eine Möglichkeit wäre es, den Netzen nicht mehr die Erfahrungen in der chronologischen Reihenfolge zu präsentieren, sondern stattdessen eine zufällige Reihenfolge der Präsentation, zumindest beim Lernen einer Lektionen, zu wählen. Dies hätte den Vorteil, daß das Problem des starken Verlernens bestimmter Aktionen in lange nicht mehr erlebten Situationen reduziert wird. Während einer normalen Lektion werden bislang immer nur ähnliche Situationen nacheinander präsentiert.
Eine sehr viel radikalere Möglichkeit stellt der Austausch der Backpropagation-Netzwerke gegen andere Varianten von neuronalen Netzwerken dar. Beispielsweise wählte Nehmzow für seine Experimente gezielt keine Backpropagation-Netzwerke, sondern einfache Perzeptron-Netzwerke, aus genau dem oben genannten Grund des langsamen Lernverhaltens. Aufgrund des problematischen Verhaltens des Perzeptron nur linear separierbare Funktionen lernen zu können, eignet es sich für den Ansatz von Lin nicht, der in seiner Dissertation experimentell gezeigt hat, das bei seinem Ansatz nichtlineare Q-Funktionen zu lernen sind. Dennoch könnte es sich lohnen, nach anderen Alternativen zu den Backpropagation-Netzwerken zu suchen.
Schließlich wäre es, zumindest für die Grundverhalten, auch noch denkbar, das langsame Lernverhalten hinzunehmen und eine möglichste gute Abbildung des Rollstuhls und seiner späteren Umwelt in SimRobot vorzunehmen, damit die neuronalen Netze in der Simulation "vorlernen" können. Dies ist jedoch aufgrund des unterschiedlichen Verhaltens von Simulation und Realität äußerst problematisch, würde aber vermutlich die Lernzeiten des realen Rollstuhls erheblich reduzieren. Allerdings widerspricht dies völlig dem ursprünglichen Ansatz von Lin, der gerade lernen soll, in einer unbekannten Gegend zu navigieren. Hier wäre es dagegen nötig, erst einmal eine komplette und möglichst exakte Karte der Gegebenheiten anzufertigen, so daß man zuerst den Aufwand der Kartenerstellung hat und schließlich noch zusätzlich den Roboter die Gegend erkunden lassen muß, möglichst auch noch mit Trainingsdaten, die vom Benutzer bzw. Programmierer vorzugeben sind.