Semesterbericht der Teilgruppe 42parti

Datum: 08.11.95
42

Autoren:

• J. Kollmann, A. Lankenau

Stichworte:

• Navigation
• Reinforcement Learning
• Robotik

Mit diesem Bericht dokumentieren wir unsere Semesterarbeit im Sommersemester 1995 im Rahmen der Gruppe 42 des Projekts SAUS. Wir haben uns dabei mit einem Navigationsverfahren beschäftigt, das von A. W. Moore entwickelt wurde: dem Parti-game Algorithmus

Einleitung

Die Grundlage dieser Arbeit ist das Paper The Parti-game Algorithm for Variable Resolution Reinforcement Learning in Multidimensional State-spaces von Andrew W. Moore und Christopher G. Atkeson, das in Machine Learning, Kluwer Academic Publishers, Boston erschien.

In dem vorliegenden Bericht wird Schritt für Schritt ein Algorithmus zum Erlernen von Wegen zu Zielregionen in höherdimensionalen kontinuierlichen Zustandsräumen entwickelt. Die Idee des Algorithmus ist es, den Rechenaufwand so gering wie möglich zu halten und die Lernfähigkeit zu maximieren, indem der Zustandsraum in eine Art Grid World partitioniert wird. Dabei hat das Raster eine höhere Auflösung in schwierigen (also hindernisreichen) Bereichen. Aufgrund dieser Überlegungen soll der Parti-game Algorithmus auch in höher-dimensionalen Zustandsräumen recht gute Ergebnisse liefern, während herkömmliche Reinforcement Verfahren dort versagen, da der Aufwand exponentiell mit Anzahl der Dimensionen steigt. Um in den meist mehrdimensionalen, kontinuierlichen Zustandsräumen der Anwendungsgebiete noch vernünftig arbeiten zu können, zerlegt man diese normalerweise in ein mehrdimensionales, diskretes Raster. Daß dieser Ansatz aber häufig zu unbefriedigenden Ergebnissen führt, zeigen die Autoren mit ihrem ersten Algorithmus, der auf einer solchen Zerlegung basiert. Der Parti-game Algorithmus geht von folgenden Annahmen über das zu lernende Steuerungsproblem aus:

• Zustands- und Aktionsräume sind kontinuierlich und mehrdimensional
• Aus der KI bekannte Greedy und Hill-climbing-Verfahren erreichen unter Umständen nie das Ziel
• Zufälliges Erkunden des Raumes verbraucht zuviel Zeit
• Die Dynamik des Systems und die Steuerungsgrundsätze sind unbekannt - sie müssen erlernt werden

Algorithmus 1: Festes Raster

Zunächst wird der kontinuierliche Zustandsraum in n sogenannte Zellen (Hyperrechtecke) zerlegt. Eine solche Zelle ist ein diskretes "Ding", das eine kontinuierliche Menge von reell-wertigen Zustandsvektoren enthält. Andersherum gehört jeder reell-wertige Zustand genau zu einer Zelle. Von jeder Zelle i lassen sich eindeutig deren Nachbarzellen NEIGHS(i) bestimmen. Der Algorithmus erhält als Eingabe ein Modell der Umwelt und eine Zerlegung des Zustandsraums. Ein solches Modell muß lediglich in der Lage sein, für jeden reell-wertigen Zustand, jedes Steuerkommando und jede Zeitspanne den nachfolgenden reell-wertigen Zustand bestimmen zu können. Der Algorithmus liefert als Ergebnis eine Vorgehensweise: Eine Abbildung, die für jede Zelle des Rasters beschreibt, welches die nachfolgende Zelle sein sollte. Der Algorithmus basiert auf der NEXT-PARTITION-Funktion, die feststellt, in welcher Zelle man hängenbleibt, wenn man aus einem gegebenen reell-wertigen Zustand zur Mitte einer gegebenen Zelle läuft, bis man entweder die Anfangszelle verläßt oder steckenbleibt. Der Nachteil dieses Algorithmus liegt auf der Hand. Er findet nicht die wirklich kürzeste Strecke, sondern die mit der geringsten Anzahl von Zellen. Außerdem findet er möglicherweise unsinnige Lösungen, da er stets denkt, die Verbindung zwischen zwei Zellen ginge vom Mittelpunkt der Startzelle aus.

Algorithmus 2: Nimmt den schlimmsten Fall an

Dieser zweite Algorithmus verfolgt eine "worst-case"-Strategie. Die aus einer Zelle noch nötigen Schritte bis zum Ziel werden nicht mehr angenähert durch den Durchschnitt der nötigen Schritte von allen reellen Zuständen innerhalb dieser Zelle bis zum Ziel, sondern durch den schlechtesten Wert. Jede Zelle hat einige zugehörige Aktionen, die jeweils durch die benachbarten Zellen bestimmt sind ("fahre zu Zelle 2"). Jede dieser Aktionen j in einer Zelle i hat eine Menge von möglichen nachfolgenden Zellen. In dieser Menge sind z. B. die Zelle i selbst sowie die angepeilte Nachbarzelle enthalten (was soviel bedeutet, daß man entweder das erhoffte Ziel erreicht oder in der Ausgangszelle hängenbleibt). Diese Menge wird im folgenden auch als die Outcomes der Zelle i bezeichnet. Der Algorithmus wechselt aus einer Zelle immer in die Nachbarzelle mit dem geringsten Jwc-Wert. Dabei ist Jwc(i) die kürzeste(bzgl. der Anzahl der durchlaufenen Zellen) Strecke aus einer gegebenen Zelle i zum Ziel. Dabei wird angenommen, daß nach Bestimmung der aktuellen Zelle und der anvisierten nachfolgenden Nachbarzelle jemand den Roboter auf die ungünstigste Position innerhalb dieser Zelle verschiebt, bevor der lokale Controller aktiviert wird. Geht dieser Jwc-Wert gegen Unendlich, so spricht man von einer "Verliererzelle", von der aus das Ziel nicht erreichbar ist. Dieser Algorithmus findet häufig keine Lösung, obwohl es eine gibt. Dies liegt einfach an der "worst-case"-Annahme. Falls der Algorithmus allerdings ein Ergebnis n liefert, so ist gewährleistet, daß man nach maximal n Zellübergängen am Ziel sein wird.

Algorithmus 3: Nimmt den schlimmsten Fall an und lernt

Im Unterschied zu Algorithmus 2 wird hier nicht der absolut schlechteste Zustand einer Zelle gewählt, sondern der schlechteste der bislang bekannten. Auf diese Weise wird vermieden, daß ein Zustand aus einem Teil einer Zelle, der noch nie besucht wurde, gewählt wird. Die weitergehende Idee dieses Algorithmus ist es, ohne vorgegebenes Modell der Umwelt zu arbeiten, d. h. die Informationen über die Umwelt sollen durch Erfahrung gelernt werden. Als Eingaben werden benötigt: Der aktuelle, reellwertige Systemzustand s, eine Zerlegung P des Zustandsraums und eine Wissensbasis D, die alle bereits beobachteten Zellübergänge enthält (also z. B. (gestartet in i, wollte nach j und bin in k gelandet)). Der Algorihmus liefert als Ausgaben den Systemzustand und einen boolschen Wert ERFOLG oder MISSERFOLG. Das Vorgehen ist eine Endlosschleife, die aus folgenden Schritten besteht:

• Bestimme die möglichen Ziele, die aus einer Zelle i beim Streben nach Zelle j erreicht werden können, indem Du zuerst in der Datenbasis nachguckst. Falls dort nichts steht, nimm einfach an, daß nur das angestrebte Ziel möglich ist.
• Berechne nach der "worst-case"-Methode die maximal nötige Anzahl von Zellübergängen zum Ziel
• Bist Du in der Zielzelle, dann melde ERFOLG
• Bist Du in einer "Verliererzelle", melde MISSERFOLG
• Ansonsten suche Dir die günstigste Nachbarzelle heraus und ergänze Deine Wissensbasis, um das Zahlentripel (i,j,ineu)(i ist die aktuelle Zelle, j die günstigste Nachbarzelle und ineu die Zelle, die den Zustand enthält, indem man gelandet ist, als man mit dem lokalen Controller versucht hat, von i nach j zu fahren!).

Der Parti-game Algorithmus

Hier wird das in den beiden vorigen Varianten entstandene Problem der "Verliererzellen" gelöst, indem deren Auflösung durch Teilung in mehrere kleine Zellen erhöht wird. Es wird also nicht sofort MISSERFOLG gemeldet (wie noch in Algorithmus 3) sondern eine neue Zerlegung berechnet. Dabei wird wie folgt vorgegangen:

• Führe Algorithmus 3 aus
• Falls MISSERFOLG gemeldet wird, bestimme die Menge aller Verliererzellen der Zerlegung, die "gute"(d. h. das Ziel ist in endlichen vielen Schritten erreichbar) Nachbarzellen haben und dieser Nachbarzellen selbst. Halbiere alle diese Zellen senkrecht zu ihrer längsten Achse. Tausche in der Zerlegung die neuen gegen die alten Zellen aus, und lösche aus der Datenbasis alle Einträge, die sich auf die gelöschten Zellen beziehen.

• Zu Beginn gibt es nur zwei Zellen, die als Zielzelle definierte Zielregion (die niemals zerlegt wird!) und den Rest des Zustandsraumes.
• Parti-game realisiert sowohl Planung als auch Lernen:
  • Planen insofern, als daß aus der Zerlegung und den "erfahrenen" Zellübergängen der kürzeste Weg zum Ziel berechnet wird.
  • Lernen insofern, als daß die Zellübergänge gemerkt werden, außerdem wird die Repräsentation des Zustandsraums durch das fortlaufende Teilen der Zellen angepaßt.

Grafischer Überblick (Flußdiagramm)

Eine grafische Übersicht zur Veranschaulichung des Kontrollflusses während der wichtigsten Phasen des Algorithmus ist in Abbildung flussdia zu sehen. (Abbildung: flussdia Flußdiagramm zum Algorithmus flussdia)

Klassenaufteilung

Nach dem Nachvollziehen des Parti-game Algorithmus haben wir versucht, eine Klassenaufteilung zu finden, die es ermöglichen soll, den eigentlichen Algorithmus möglichst direkt abschreiben zu können. Dazu haben wir das Programm zuerst grob in drei Bereiche aufgeteilt:

• Parti-game,
• Verwaltung des Zustandsraumes und der Wissensbasis und
• Greedy-Controller

• Basistypen: dies ist keine Klasse, sondern eine Ansammlung von Typen und Hilfsfunktionen, die von den meisten Klassen gebraucht und von jedem File importiert werden.
• Party: Diese Klasse beinhaltet die Wissensbasis, den Zustandsraum, den Greedy-Controller und das Wissen über das zu findende Ziel. Die beiden wichtigsten Funktionen sind party() und algo3(). Sie entsprechen den im Paper vorgestellten Funktionen. algo3() versucht mit Hilfe des Greedy-Controllers und der Wissensbasis, den kürzesten Weg zum Ziel zu fahren. Wenn das mißlingt, wird in party() die Zellteilung gemacht.
• Birnbaum: Hier werden die Klassen Baum und Knoten definiert, die für die Verwaltung und Benutzung eines einfachen Binärbaumes zuständig sind.
• Zelle: Diese Klasse wird von Knoten abgeleitet und stellt eine Zelle des Zustandsraumes dar. Sie beinhaltet im wesentlichen ihre Grenzen im Zustandsraum und das Wissen über ihre Nachbarzellen. Wenn ein Objekt dieser Klasse im Binärbaum Nachfolger besitzt, ist es ein Knoten, der das schnellere Finden einer Zelle ermöglicht. Nur Blätter des Baumes stellen gültige Zellen dar. Die Funktion J_{wc}() berechnet unter der "worst-case"-Annahme den kürzesten Weg von der Zelle zum Ziel.
• Liste: Die Template-Klassen Liste und ListenElement sind für die Verwaltung und Benutzung von einfachen Listen beliebiger Typen zuständig. Sie werden in diversen Klassen ausgiebig genutzt. Im wesentlichen sind sie für die Realisierung der Wissensbasis da, die aus einer Liste des Typs Eintrag (aus Basistypen) besteht. Sie soll in der nächsten Version in lokale Wissensbasen aufgebrochen werden, die in dem jeweiligen Zelle-Objekt untergebracht werden. Durch die Operatoren + (Vereinigung zweier Listen) und - (Differenz zweier Listen) wird es möglich, den Algorithmus zur Bestimmung der zu teilenden Zellen nahezu direkt abzuschreiben.
• Greedy: Diese Klasse beinhaltet die Schnittstelle zum Roboter (s. SimRobot) und die Funktion goTo(), die mit Hilfe dieser Schnittstelle versucht, den Roboter von der aktuellen Position im Zustandsraum direkt in den Zielzustand zu bringen.
• SimRobot: Diese Klasse ist von SIMULATION aus Simrobot abgeleitet und ermöglicht den Zugriff auf ebendiese Simulation. Sie muß in Zukunft durch eine Schnittstelle zur Rollstuhl-Hardware ersetzt werden.

Implementation

Wir haben uns entschlossen, den Zustandsraum als Binärbaum zu implementieren, weil dadurch einige Vorteile gewonnen werden:

• Das Finden einer Zelle, in der ein bestimmter Zustand liegt, ist schnell möglich, da nicht alle Zellen geprüft werden müssen. Statt dessen kann an jedem Knoten anhand der Grenzen seiner Nachfolger entschieden werden, in welchen der beiden Teilbäume verzweigt wird.
• Das Teilen einer Zelle ist leicht möglich, weil einfach die zwei neuen Zellen an sie angehängt werden können.
• Es ist möglich, eine Form des "Vergessens" einzubauen, indem der Baum an einer bestimmten Tiefe abgeschnitten wird. Dadurch wird die an problematischen Stellen erhöhte Auflösung wieder reduziert, so daß einfache Wege, die kurzzeitig verstellt waren, auch wieder ausprobiert werden.

Bei der Implementation des Zustandsraumes haben wir darauf geachtet, uns nicht auf eine bestimmte Dimensionstiefe festzulegen, auch wenn wir momentan nur einen dreidimensionalen Zustandsraum benötigen. Die Anzahl der Dimensionen und die einzelnen Indexbezeichnungen sind in Basistypen als Konstanten deklariert; momentan sind dies xpos, ypos und ausr für Position und Ausrichtung des Roboters. Außerdem sind die Konstanten START = erste Dimension und ende = höchste Dimension+1 deklariert, sodaß Schleifen über alle Dimensionen von START bis ende-1 laufen können. Beim aktuellen Greedy-Kontroller konnte die Unabhängigkeit von der Dimensionstiefe allerdings nicht durchgehalten werden, da zur Winkel- und Entfernungsbestimmung die Koordinaten benutzt wurden.

Zur Implementation der Funktion J_{wc}() haben wir "dynamische Programmierung" eingesetzt. Für alle (n) Zellen wird die Entfernung zum Ziel als "Entfernung der günstigsten Nachbarzelle plus Übergangskosten zur Nachbarzelle" berechnet. Danach ist die Entfernung für die direkt ans Ziel angrenzenden Zellen korrekt. Nach höchstens n Aufrufen dieser Prozedur ist für alle Zellen die ermittelte Entfernung korrekt. Eine leichte Erkennung von Verliererzellen ist hierdurch auch möglich: bei jedem weiteren Aufruf bleibt die (korrekte) Entfernung in Gewinnerzellen konstant, während die Entfernung in Verliererzellen gegen Unendlich geht.

Den Versuch einer rekursiven Implementierung von J_{wc}() haben wir abgebrochen, da von einer Verliererzelle das Ziel nicht erreichbar und damit kein Rekursionsabbruch gegeben ist. Dies ließe sich zwar vermeiden, indem für jede in der Rekursion untersuchte Zelle gemerkt wird, ob sie schon untersucht wurde, aber wir sind uns noch nicht darüber im klaren, ob diese Programmierung den jetzt vorhandenen Aufwand der Ordnung n^2 überschreiten würde. (Diese Funktion ist offensichtlich noch nicht optimiert.)

Testläufe

In den folgenden beiden Unterabschnitten möchten wir anhand von zwei Beispielräumen die Funktionsweise unserer Implementierung des Parti-game Algorithmus noch einmal erläutern.

Labyrinth

In der Abbildung labyrinth wird das relativ schnelle Lernverfahren des Parti-game Algorithmus veranschaulicht. (Abbildung: raum2 Lernverhalten im Labyrinth labyrinth) Im oberen Teil der Abbildung erkennt man deutlich das Explorationsverhalten des Parti-game Algorithmus. Zunächst wird die Zielregion in der rechten oberen Ecke des Bildes direkt angepeilt. Daß dieser Versuch nach kurzer Fahrt an der ersten Wand endet (1), führt dazu, daß eine Zellteilung vorgenommen wird. Es gibt dann zwei Zellen, eine linke Raumhälfte und eine rechte. Auf dem Weg zum Mittelpunkt der linken Zelle stößt der Roboter wieder gegen die Wand (2), woraufhin die linke Hälfte des Raumes als Verliererzelle markiert wird, so daß es erneut zur Zellteilung kommt. Es werden beide Zellen geteilt - die linke, weil es aus ihr keinen Weg mehr zum Ziel gibt, die rechte, weil sie eine Nachbarzelle ist, von der vermutlich ein Weg zum Ziel existiert. Daraufhin gibt es im Raum fünf Zellen: die rechte Raumhälfte, und die in vier Quadrate geteilte linke Raumhälfte. Zunächst versucht der Algorithmus, die beiden im - von links aus gesehen - zweiten Gang liegenden Zellen anzupeilen. Dies schlägt jedoch wegen der Wand fehl. Folglich wird die Zelle unten links anvisiert. Deren Zentrum läßt sich auch ohne Schwierigkeiten erreichen (3).

Leider ist aber von diesem Punkt aus nicht auf geradem Wege das Zentrum der Zelle in der rechten unteren Ecke der linken Raumhälfte zu erreichen, da die Wand stört. Also wird noch einmal geteilt. Da die Zelle in der unteren linken Ecke des Bildes sich als Verliererzelle herausgestellt hat, gilt dies nun auch für die darüber liegende Zelle, da der bisher noch für möglich gehaltene Weg verbaut ist. Wie bereits erwähnt, wird bei der Teilung einer Zelle das bisher über diese Zelle erworbene Wissen "vergessen". Dies führt dazu, daß der Algorithmus noch einmal "nachguckt", ob es nicht doch einen Weg durch die Wand gibt. Danach ist die Auflösung ausreichend hoch, so daß der Weg in den nächsten Gang gefunden wird. Die dortige Zellendichte reicht bereits aus, um in den dritten Gang zu gelangen. Dort wiederholt sich das hier geschilderte Spielchen. Nach insgesamt 29 Zellteilungen wird das Ziel erreicht.

Steuert man im Anschluß daran den Roboter zurück in die Startregion, so findet er den Weg ohne weitere Zellteilungen vorzunehmen, allerdings eckt er noch einige Male an, da die Wissensbasis noch nicht vollständig aktualisiert ist. Fährt man von der Startregion dann noch einmal zum Ziel und zurück, so wird auf dieser Strecke ein fehlerfreier Weg gelernt.

Auf dem dritten Hinweg zum Ziel (vgl. unteren Raum in Abbildung labyrinth) ist die gewählte Trajektorie zu erkennen. Der Algorithmus ist nun in der Lage, jeden Punkt innerhalb des Labyrinths anzufahren, ohne weitere Zellteilungen vorzunehmen.

Es soll nicht unerwähnt bleiben, daß dieser Testraum auch deshalb gewählt wurde, weil hier zumindestens die ersten Zellteilungen zu Zellgrenzen führen, die mit den Wänden im realen Raum zusammenfallen. Dieser Raum stellt also gewissermaßen eine Extremsituation dar. Ferner ist zu bedenken, daß das Ergebnis zwar nach sehr wenigen Versuchen bereits recht akzeptabel ist, daß es sich aber in Zukunft auch nicht mehr verbessern wird. Dies liegt ganz einfach an der Konzeption des Parti-game Algorithmus. Es spricht jedoch nichts dagegen, die vom Parti-game Algorithmus gefundene Trajektorie noch weiter zu bearbeiten, um eventuell einen sanfteren Streckenverlauf zu erhalten.

Wohnraum

In diesem Kapitel beschreiben wir eine etwas realistischere Testumgebung, die zumindest entfernt an ein Wohnzimmer, in dem ein Tisch, ein Stuhl und ein Schrank stehen, erinnern soll.

(Abbildung: raum3a Eigenständiges Lernen eines relativ guten Weges. selbst)

Wir präsentieren im folgenden zwei Lernsituationen. Im ersten Beispiel (vgl. Abbildung selbst) lernt der Roboter rein zufällig einen relativ guten Weg aus der Startregion ins Ziel. Zunächst versucht er, einen Weg in die Zielregion in der unteren linken Ecke des Bildes zu finden. Dieser Weg ist kein direkter, da der Schrank im Weg steht. Mehr oder wenig zufällig wird ein Weg zwischen Tisch und Stuhl hindurch zum Ziel gefunden. Zufällig deshalb, weil diese Trajektorie nur gewählt wird, weil die angepeilten Zellzentren gerade so günstig in dem Korridor zwischen Tisch und Stuhl liegen, daß eine fast fehlerfreie Fahrt (bis auf eine Kollision mit dem Stuhl) möglich ist.

Für den Rückweg zur Startposition ist noch kein Wissen vorhanden, deshalb wird wieder zuerst versucht, den direkten Weg zu nehmen. Dies scheitert auch wieder am Wandschrank, worauf der Roboter zwischen Schrank, Stuhl und Wand pendelt. Dabei finden einige Zellteilungen statt, die sich im weiteren Verlauf als günstig erweisen werden. Schließlich findet der Roboter wieder den Korridor zwischen Stuhl und Tisch und findet von dort zurück zum Start.

Beim zweiten Versuch, den Roboter zum Ziel zu bringen, ist durch die vorherigen Zellteilungen ein großer Teil der Erfahrungen wieder verloren worden. Deshalb nochmal der scheiternde Versuch, direkt nach unten zu fahren. Da aber durch die Zellteilungen die Auflösung höher ist, wird nun ein kleinerer Schritt nach rechts gemacht, so daß der kürzere Weg zwischen Schrank und Stuhl nun gefunden wird. Auch auf dem Rückweg gibt es jetzt kein Problem, diesen Weg zu benutzen. Hierbei wurde also durch günstige Zellteilungen von alleine der beste Weg gefunden.

(Abbildung: raum3b Trainieren eines besseren Weges. vormachen)

Im zweiten Beispiel findet der Roboter von selbst einen ungünstigen Weg, kann aber durch Training den günstigeren Weg lernen. Der Roboter startet in der Mitte des Raumes unten vor dem Tisch. Die Zielregion liegt in der rechten oberen Ecke des Raumes. Da im ersten Beispiel schon Zellen auf der linken Seite des Raumes geteilt wurden, gibt es jetzt zwei Möglichkeiten, zum Ziel zu gelangen: direkt und links um den Tisch herum. Da die direkte Möglichkeit kürzer ist, wird sie zuerst ausprobiert. Sie scheitert an der Tischecke, so daß dieser Zellübergang als Unmöglich gemerkt wird. Da noch die zweite Möglichkeit existiert, wird noch keine Zelle geteilt. Der Weg links um den Tisch ist erfolgreich und wird gelernt. Auf dem Rückweg gibt es die gleiche Situation: der direkte Weg scheitert wieder an der Tischkante, der Umweg ist erfolgreich.

Nun soll dem Roboter beigebracht werden, den kurzen Weg rechts um den Tisch zu lernen. Dazu wird zuerst ein Zwischenziel rechts unten angegeben, das ohne Hindernisse erreichbar ist. Von hier aus ist auch die Zielregion rechts oben problemlos erreichbar. Da nun die Erfahrung gemacht wurde, daß der Zellübergang zwischen dem Startbereich und der davon rechten Zelle doch möglich ist, wird auch für den Rückweg dieser kurze Weg genommen und gelernt.

Was können wir schon?

Unsere primäre Absicht in der ersten Phase der Beschäftigung mit dem Parti-game Algorithmus war das Nachvollziehen der im Paper von A. Moore vorgestellten Ideen und die anschließende Implementierung in einer übersichtlichen und erweiterbaren Form von C++-Quellcode. In diesem Zeitraum (von Mitte Juli bis Mitte August 1995) haben wir uns über die Klassenaufteilung verständigt und die in Moores Paper an einigen Stelle recht unklare Problembeschreibung hinreichend präzisiert, so daß wir in der Lage waren, im Projektplenum am 2. August 1995 unsere erste lauffähige Version zu präsentieren.

In der zweiten Phase haben wir uns hauptsächlich ums Debuggen und "verschönern" des Codes kümmern müssen. Unsere Überlegung dabei ist die folgende: Wir ziehen es vor, die Richtigkeit des grundlegenden Algorithmus gründlich zu überprüfen, bevor weitere Funktionalität eingeführt wird. In Einklang mit dieser Idee befindet sich auch unser Beschluß, vor dem Angehen der im nächsten Kapitel beschriebenen noch zu lösenden Aufgaben nun erst einmal den "State of the Art" zu dokumentieren, was mit diesem Dokument geschehen ist.

Nichtsdestotrotz haben wir aber den von Moore vorgeschlagenen Algorithmus an einigen Stellen bereits verbessern können. So wird inzwischen nicht mehr die Entfernung in der Einheit "Zellen" gemessen, sondern es wird der korrekte Abstand zum Ziel betrachtet. Wir rechnen also nicht mehr mit Kosten 1 für den Übergang von einer Zelle zur anderen, sondern mit dem euklidischen Abstand der beiden Zellzentren in der xy-Ebene voneinander.

Zur Zeit arbeiten wir aus den oben genannten Gründen mit einer Reihe von Einschränkungen bzw. Überbleibseln aus der "Moore-Version". Die für den Betrachter offensichtlichste Unzulänglichkeit ist der Agent, auf den unser Controller angewendet wird. Um uns ganz auf das Geschehen innerhalb des Parti-game Algorithmus konzentrieren zu können, haben wir das Problem des Greedy-Controllers, der sicherstellen soll, daß in einer hindernisfreien Umgebung stets von einem beliebigen Punkt A zu einem beliebigen Punkt B gefahren werden kann, bisher außen vor gelassen. Aus diesem Grund arbeiten wir derzeit noch mit einer omnidirektionalen Tonne und einem Greedy-Controller, der einfach in die angepeilte Richtung steuert. Berücksichtigt man diese Einschränkung, macht es auch keinen Sinn, bei der Partitionierung die dritte Dimension unseres Konfigurationsraumes (die Ausrichtung) zu beachten. Wir teilen die Zellen derzeit also nur bezüglich der x- bzw. der y-Achse.

Daher reicht es auch, bei der Berechnung der Kosten für einen Zellübergang (die wie oben erwähnt wurde, im Gegensatz zum Moore-Paper, nicht mehr immer 1 betragen!) die Entfernung in der xy-Ebene zugrunde zu legen. Ein weiterer Punkt, der in naher Zukunft geändert wird, ist die globale Speicherung der Wissensbasis. Es macht unserer Ansicht nach mehr Sinn, wenn jede Zelle die bisher gemachten Erfahrungen, die sie selbst betreffen, verwaltet. Dies ist nur ein Implementationsdetail, das im Gegensatz zu der folgenden Überlegung vermutlich nicht das Verhalten des Agenten verändern wird. In der aktuellen Version werden vor jedem Schritt alle Jwc-Werte neu berechnet. Es gilt auszuprobieren, wie man dieses sehr rechenintensive Vorgehen optimieren kann, ohne dabei einen Leistungsrückgang in kauf nehmen zu müssen.

Was möchten wir erreichen?

Nachdem mit dieser Dokumentation und der Präsentation im Projektplenum am 2. November 1995 nun die Phase des Verstehens und der Grundlagenforschung erfolgreich abgeschlossen wurde, steht die nächste Etappe bevor: die Verfeinerung des Algorithmus und die Anpassung an unsere Rollstuhlanwendung.

Zu diesem Zweck werden wir zunächst einmal die im vorigen Kapitel vorgeschlagenen Verbesserungen vornehmen. Dies sind in erster Linie die lokale Speicherung der Wissensbasis und eine intelligente Strategie bei der Jwc-Berechnung.

Im Anschluß daran wird der Quantensprung hin zum Rollstuhl vorgenommen, d.h. statt der omnidirektionalen Tonne wird zunächst in der Simulation mit dem Rollstuhlobjekt und bei Verfügbarkeit der Schnittstellen und der Hardware des realen Rollstuhls mit diesem gearbeitet werden. Die Umstellung auf ein derartig kinematisch beschränktes Objekt erfordert verständlicherweise eine grundlegend neue Version des Greedy-Controllers. Es ist noch die Frage, wieviel Intelligenz in diesen neuen Controller gelegt werden sollte. Ein Ansatz wäre zum Beispiel der von Christoph Herwig und Matthias Heger vorgeschlagene, bei dem der Greedy-Controller die von ihm erreichbaren Positionen auf einer gekrümmten Fläche im Konfigurationsraum bestimmt.

Um erfolgreich mit dem realen Rollstuhl arbeiten zu können, sind wir stark auf die Realisierung der Positionsbestimmung durch die Bildverarbeitungsgruppe angewiesen.

Dokumentation

Klassendokumentation

Datum: 08.11.95

Autoren:

• J. Kollmann, A. Lankenau

Stichworte:

• Klassendokumentation

Im folgenden Teil unseres Bericht werden die Klassen dokumentiert.

class SimRobot

Diese Klasse realisiert die Schnittstelle zu SimRobot. Sie wird vom Greedy-Controller benutzt, um Übergänge im Zustandsraum in Aktionen des Roboters umzusetzen und den neuen Zustand zu berechnen. Zur Anpassung an den Rollstuhl wird sie durch eine Klasse ersetzt, die die Schnittstelle zu den tatsächlich vorhandenen Hardware-Sensoren und Aktoren anspricht und mit Hilfe einer Karten-Klasse und einer Klasse der Bildverarbeitungsgruppe versucht, den Zustand des Rollstuhls zu bestimmen.

Definition

private:

ACTORPORT actoren[3];

Ein Array von ACTORPORTS, deren Indizes in basistypen.hh definiert sind: transX, transY und rotZ. Sie werden im Konstruktor initialisiert und sind für Bewegungen in X- und Y-Richtung (geradeaus und seitlich zur Ausrichtung) und Drehung zuständig. Tatsächlich werden im Moment nur transX und rotZ benutzt.

SENSORPORT execsensor;

Durch Abfragen dieses SENSORPORTS kann geprüft werden, ob eine an einem der ACTORPORTS ausgeführte Aktion erfolgreich beendet werden konnte, z.B ob eine Bewegung um n Schritte nach weniger als n Schritten zu einer Kollision geführt hat. Dies ist momentan die einzige zur Kollisionserkennung benutzte Methode. Da am Rollstuhl eine Kollisionserkennung durch Ansprechen der Bumper wohl etwas ungünstig wäre, wird sie dann schon ausgelöst werden, wenn die Ultraschallsensoren ein Hindernis innerhalb eines Mindestabstands detektieren.

public:

• SimRobot(char* filename);

  Der Konstruktor dieser Klasse. Parameter ist der Name eines Szenen-Beschreibungsfiles. Hier wird der SimRobot-Prozess mit dem übergebenen Szenen-Beschreibungsfile gestartet und dann die oben beschriebenen Variablen initialisiert.

• void gibZustand(Zustandsvektor& zustand);

  Diese Funktion bekommt als Referenzparameter einen Zustandsvektor übergeben. Die aktuelle Position und Ausrichtung im Raum werden bestimmt und in diesen Zustandsvektor eingetragen. Bei der Umsetzung auf den Rollstuhl wird diese Funktion das größte Problem, da der Parti-game Algorithmus sehr auf die Präzision ihres Ergebnisses angewiesen ist.

• bool setzeAktion(actorName action, double wert);

  Parameter dieser Funktion sind der Index eines ActorPorts (in Form seines Namens (siehe def. in "basistypen.hh")) und ein Entfernungswert zwischen -1 und 1. Die Bedeutung dieses Wertes hängt vom angegebenen Namen und den im Szenen-Beschreibungsfile angegebenen Werten ab. In unserer Testumgebung ist eine Schrittweite von 20 angegeben, so daß (transX,-1) 20 Schritte rückwärts und (transY,0.5) 10 Schritte nach rechts bewirken. Für rotZ ist eine Drehung zwischen -180 und 180 Grad möglich.

• ~SimRobot();

  Der Destruktor ist eigentlich für die Beendigung des SimRobot-Prozesses zuständig. Hier gibt es offenbar manchmal ein Problem, da sich teilweise bei Beendigung des Programmes der SimRobot-Prozess schon vorher beendet, wodurch ein Segmentation fault ausgelöst wird.

class Greedy

Der Greedy-Controller hat die Aufgabe, den Roboter auf direktem Weg vom aktuellen Zustand in den Zielzustand zu bringen. Hierbei sind keine Informationen über vorhandene Erfahrungen oder bekannte Hindernisse, sondern nur über die kürzeste Verbindung zwischen zwei Zuständen vorhanden. Als Ergebnis wird dem Parti-game Algorithmus Erfolg oder Mißerfolg gemeldet. Der vorhandene Greedy-Controller geht bei der Wegplanung von einer omnidirektionalen Tonne aus. Da hierfür nur ein dreidimensionaler Zustandsraum mit Koordinaten und Ausrichtung benutzt wird, sind nur zwei einfache interne Funktionen winkel() und dist() nötig, um zu den Zielkoordinaten zu gelangen.

Wenn die Simulation auf den Rollstuhl umgestellt wird, muß der Greedy-Controller auf die begrenzteren Bewegungsmöglichkeiten angepaßt werden. Eine provisorische Möglichkeit ist, die Drehung auf der Stelle durch kurzes Vor - und Zurückfahren mit Maximaleinschlag zu erreichen. Später könnte der Zustandsraum dann so verändert werden, daß der Controller durch Kurvenfahrten benachbarte Zustände erreichen kann, d.h. möglicherweise Aufgabe der Koordinaten.

Außerdem beinhaltet diese Klasse die Schnittstellenklasse zu den Sensoren, die die Positionsbestimmung realisiert. Im Moment ist dies die Klasse SimRobot, sie muß später durch eine Klasse ersetzt werden, die die tatsächlichen Sensoren ansteuern kann.

Definition

public:

• Zustandsvektor goTo(const Zustandsvektor& s1, const Zustandsvektor& s2, int& schritte);

  s1 und s2 sind Start - und Zielzustand, zwischen denen der Roboter bewegt werden soll. Der Rückgabewert ist TRUE, wenn der Zielzustand erreicht werden konnte. In die Referenzvariable schritte wird die tatsächlich (bis zum Ziel oder bis zum Hindernis) zurückgelegte Entfernung geschrieben.

• Greedy(char* name);

  Der Konstruktor von Greedy ruft den Konstruktor seiner Membervariable SimRobot auf und bekommt deshalb als Parameter den Namen des Szenen-Beschreibungsfiles für SimRobot.

SimRobot sim;

Über die Funktion sim.gibZustand() kann von dieser Variable der aktuelle Zustand des Roboters bekommen werden.

• double winkel(const Zustandsvektor& s1, const Zustandsvektor& s2);

  Diese interne Funktion berechnet den Winkel, den der Roboter einschlagen muß, um von s1 nach s2 zu kommen. Dazu werden dx und dy berechnet und folgende Unterscheidungen gemacht:

  Wenn dx==0 ist, wird $(+/-)Pi/2$ zurückgegeben (je nach Vorzeichen von dy), sonst wird der Winkel nach der Formel $alpha=atan(dy/dx)$ berechnet und je nach dem Quadranten von s2 Vorzeichen-korrigiert.

• double dist(const Zustandsvektor& s1, const Zustandsvektor& s2);

  Diese interne Funktion berechnet die Entfernung auf der x/y-Ebene zwischen s1 und s2. Dies wird einfach über die Formel $d=sqrt(dx^2+dy^2)$ erreicht.

class Liste

Diese Klasse stellt eine Schablonenklasse für Listen zur Verfügung, d.h. es können Listen mit Elementen beliebigen Typs verwaltet werden. Es stehen Funktionen zum Einfügen und Löschen von Elementen, zum Ausfiltern von Teillisten nach beliebigen Kriterien und zum Zuweisen und Verknüpfen von Listen mit Elementen gleichen Typs zur Verfügung.

ACHTUNG: da diese Klasse (noch) einige "undokumentierte Eigenheiten" besitzt, sollte sie momentan NUR von uns (siehe Autoren) und NICHT von anderen benutzt werden!!

Definition

public:

• Liste();

  Der Konstruktor legt eine neue Liste mit einem (leeren) Listenkopf an. Dabei beinhaltet der Listenkopf die eigentliche Liste, während Liste einen Pointer auf den Listenkopf enthält. Man kann sich Liste wie einen Link auf die Listenstruktur vorstellen, von dem es auch mehrere geben kann (s.a. Copy-Konstruktor und Zuweisungsoperator). Das hat den Vorteil, daß ein Listenobjekt lokal innerhalb einer Funktion angelegt und leichter als Rückgabewert zurückgegeben werden kann. Es wird ein Kopieren der Liste und Zerstören des lokalen Listenobjekts vermieden. Statt dessen legt der Copy-Konstruktor einen neuen "Link" an und beim Aufruf des Destruktors wird nicht die gesamte Liste, sondern nur der lokale "Link" freigegeben. Im Listenkopf wird die Anzahl der Verweise auf die Listenstruktur gezählt und erst beim Aufruf des Destruktors des letzten Links wird die komplette Liste freigegeben.

• Copy-Konstruktor Liste(const Liste&);

  Der Copy-Konstruktor legt einen neuen "Link" auf eine Liste an und initialisiert den darin enthaltenen Pointer auf die Listenstruktur der übergebenen Liste. Außerdem wird der Benutzungszähler im Listenkopf um eins erhöht.

• ~Liste();

  Der Destruktor verkleinert den Benutzungszähler im Listenkopf um eins. Wenn Null erreicht wird, was bedeutet, daß gerade der letze "Link" auf die Liste abgebaut wird, wird auch jedes einzelne Element der Liste freigegeben.

• int anzahlElemente() const;

  Rückgabewert ist (o Wunder) die Anzahl von Elementen in der Liste.

• int fuegeEin(const T&);

  Parameter ist ein Objekt beliebigen Typs, dessen Wert in eine Liste mit Elementen des gleichen Typs eingefügt werden soll. Dazu wird ein neues Objekt ListenElement angelegt, dessen Eintrag-Feld den gleichen Typ hat und mit dem Inhalt des übergebenen Objektes initialisiert wird. Dieses ListenElement wird am Anfang der Liste eingefügt, und der Elementzähler der Liste um eins erhöht. Es handelt sich also um eine FIFO-Listenverarbeitung.

  Rückgabewert ist 1 bei Erfolg und 0, wenn kein neues ListenElement angelegt werden konnte.

• bool loesche(bool (*) (ListenElement<T>*, void*), void* =NULL);

  Diese Funktion löscht bestimmte Elemente aus der Liste. Hierzu bekommt sie als Parameter eine Prädikat-Funktion der Form bool (*) (ListenElement<T>*, void*) (siehe Funktion IsElem()). Diese Prädikat-Funktion bekommt als Parameter jedes einzelne Element der Liste. Sie muß jeweils entscheiden, ob das Element gelöscht werden soll und das Ergebnis mit TRUE=ja oder FALSE=nein zurückgeben.

  Der zweite Parameter von loesche() wird jeweils an die Prädikatsfunktion übergeben und kann benutzt werden, um weitere Informationen durchzureichen.

  Der Rückgabewert ist TRUE, wenn mindestens ein Element gelöscht wurde, sonst FALSE.

• bool IsElem(ListenElement<T>* elem, void* v);

  Diese interne Funktion ist als Beispiel für eine Prädikatsfunktion (siehe Funktion loesche()) aufgeführt. Sie wird vom Differenz-Operator benutzt und bekommt als zweites Argument eine Liste. Wenn das zu prüfende Element in dieser Liste enthalten ist, wird TRUE=lösche zurückgegeben.

• Liste<T> filtereTeilliste (bool (*) (ListenElement<T>*, void*), void* =NULL) const;

  Die Parameter dieser Funktion sind genau dieselben wie die der Funktion loesche(). Es wird eine neue leere Liste angelegt und jedes Element, für das die Prädikatsfunktion TRUE entscheidet, wird zusätzlich in diese neue Liste eingefügt, ohne die alte Liste zu verändern. Damit kann in Listen nach beliebigen Kriterien gefiltert werden.

  Rückgabewert ist die neue Liste. Falls das Kriterium für kein Element erfüllt war, kann sie auch leer sein.

• Liste<T>& operator=(const Liste<T>&);

  Der Zuweisungsoperator funktioniert ähnlich dem Copy-Konstruktor. Zuerst wird für die Liste, auf die die Zuweisung angewendet wurde, der Destruktor aufgerufen. Dann wird ein neuer "Link" auf die als Parameter übergebene Liste angelegt (s.a. Copy-Konstruktor). Rückgabewert ist die gleiche Liste, da der Wert einer Zuweisungsoperation immer ihrem Parameter entspricht.

• ListenElement<T>* gibKopf() const;

  Durch diese Funktion kann auf das erste in der Liste vorhandene Element zugegriffen werden (s.a. Klasse ListenElement).

• Liste<T> operator+(const Liste<T>& a, const Liste<T>& b);

  Dies ist der Additionsoperator :-). Er legt eine neue Liste an und fügt die Vereinigungsmenge aller Elemente beider als Parameter übergebener Listen in die neue Liste ein. Rückgabewert ist die neue Liste.

• Liste<T> operator-(const Liste<T>& a, const Liste<T>& b);

  Dies ist der Differenz-Operator (s.o.). Er legt eine neue Liste an, in die alle Elemente der Liste a kopiert werden. Dann wird mit Hilfe der Funktion loesche() und der Prädikatsfunktion IsElem() jedes Element aus der neuen Liste gelöscht, das in Liste b enthalten ist. Das Ergebnis ist also eine Liste, die alle Elemente aus Liste a minus denen aus Liste b enthält. Wenn kein Element aus Liste b in Liste a enthalten ist, ist das Ergebnis Liste a.

private:

ListenKopf<T>* zgr;

Dies ist der sagenumwobene "Link" auf die tatsächliche Liste. Die Klasse ListenKopf<T> enthält einen Element-Zähler, einen Benutzungszähler und einen Zeiger auf das erste "ListenElement".

class ListenElement

Dies ist sozusagen der Container für ein Element der Liste. Er enthält ein Feld "eintrag" vom Element-Typ, einen Zeiger auf das nächste ListenElement, einen einfachen Konstruktor und eine Funktion zum Durchlaufen der Liste:

Definition

public:

• ListenElement* gibNaechstesElement();

  Durch diese Funktion kann auf das nächste Element in der Liste zugegriffen werden (s.a. Liste.gibKopf()). wenn das Ende der Liste erreicht ist, wird NULL zurückgegeben. Damit kann durch gibKopf() und wiederholtes Aufrufen von gibNaechstesElement() die gesamte Liste durchlaufen werden.

class Baum

Mit dieser und der Klasse "Knoten" wird ein einfacher Binärbaum gebildet. "Baum" beinhaltet als Felder nur einen Zeiger auf den Wurzel-"Knoten" und einen Zähler für die Anzahl der Blätter. Der Destruktor baut bei Vorhandensein den ganzen Baum ab.

Definition

public:

Knoten* wurzel;

Eben besagter Zeiger auf die Wurzel des Baumes.

int zellenanzahl;

Hier kann die Zahl der Blätter (nicht aller Knoten) gelesen werden. Beim Anfügen neuer Blätter muß die Variable entsprechend erhöht werden. Da diese Klasse nur zum Ableiten der Klasse "Zelle" benutzt wird, geschieht das dort.

• Baum(Knoten& wurzel);

  Der Konstruktor bekommt als Parameter einen Knoten, der als Wurzel eingesetzt wird. Außerdem wird zellenanzahl auf 1 gesetzt.

class Knoten

Diese Klasse bildet zusammen mit der Klasse "Baum" einen Binärbaum.

Definition

protected:

Baum* baum;

Jeder Knoten besitzt einen Zeiger auf seine Baumstruktur. Sie wird von der abgeleiteten Klasse "Zelle" genutzt.

• Knoten(Baum* baum);

  Der Konstruktor ist protected, damit sichergestellt ist, daß nur abgeleitete Klassen von "Knoten" angelegt werden können. Er bekommt als Parameter den Baum, in den der Knoten eingefügt werden soll. Das Einfügen muß die abgeleitete Klasse selbst machen.

public:

Knoten* links,* rechts;

Dies sind die beiden Zeiger, über die der Baum durchlaufen werden kann.

• virtual ~Knoten();

  Der Destruktor ist eine virtuelle Funktion, die in der abgeleiteten Klasse definiert werden muß (s.a. Zelle.~Zelle()).

• Knoten* gibWurzel();

  Über diese Funktion ist der Wurzel-Knoten jedes Knotens zu bekommen. Sie wird von der Klasse "Zelle" benötigt.

class Party

Eine Instanz dieser Klasse wird benötigt, um eine Aufgabe zu lösen, z.B. fahre von A nach B. Zu diesem Zweck enthält die Klasse PARTY die Membervariablen WISSENSBASIS, in der die gemachten Erfahrungen abgespeichert werden, ZIEL, was die anzupeilende Zielzelle ist, ZUSTANDSRAUM, ein Binärbaum, in dem die die Partionierung des Zustandsraumes repräsentierende Datenstruktur abgelegt ist und einen CONTROLLER, der festlegt, auf welche Art und Weise der Agent sich fortbewegen soll, falls er sich im hindernisfreien Raum befindet.

Definition

private:

Liste <Eintrag> wissensbasis;

Die Wissensbasis stellt einen Teil der Lernfähigkeit des Algorithmus dar. In ihr werden Erfahrungen der Form Als ich versuchte aus Zelle A nach Zelle B zu fahren, bin ich in Zelle C gelandet. Kosten: D gespeichert. Anhand dieser Wissensbasis entscheidet der Algorithmus, welchen Weg er zu wählen hat. Die Wissensbasis wird laufend erweitert wenn neue Erfahrungen gemacht werden. Sie wird jedoch auch wieder ausgedünnt, wenn es zu Zellteilungen kommt.

• bool algo3(Zustandsvektor& , Liste<Zelle*>& )

  Diese Funktion entspricht in etwa dem weiter oben vorgestellten Algorithmus 3 aus dem Paper von Moore. Die Funktion bekommt einen Zustandsvektor und eine Liste aller Zellen der aktuellen Partitionierung übergeben. Es wird versucht, von der aktuellen Position einen möglichst kurzen Weg zum Ziel zu finden. Dabei werden einerseits die in der WISSENSBASIS gespeicherten Erfahrungen herangezogen und andererseits auf eventuell vorhandene, bisher unbekannte Hindernisse geachtet. Dies geschieht, indem der Algorithmus versucht, aus der aktuellen Zelle in diejenige Nachbarzelle zu wechseln, die einen möglichst kurzen Weg zum Ziel verspricht. Dieser Weg berechnet sich aus den Zellübergangskosten von der aktuellen Zelle zu der Nachbarzelle (tatsächlicher Abstand der beiden Zellzentren) und der Entfernung von der Nachbarzelle zum Ziel. Falls irgendwann auf diese Weise die Zielzelle erreicht wird, bricht die Funktion ALGO3 erfolgreich ab. Falls es jedoch einmal dazu kommt, das der Algorithmus aus einer Zelle keinen Weg zum Ziel findet (weil die Wissensbasis zum Beispiel sagt, daß man von keiner Nachbarzelle das Ziel erreichen kann!), so bricht die Funktion mit einem Mißerfolg ab.

public:

Greedy controller;

Da der Controller unseres Agenten nicht durch den Algorithmus vorgegeben ist, sondern ein eigenständiges Modul darstellt, wird hier ein Controller-Objekt vereinbart. Die Idee und Funktionsweise des Greedy-Controllers sind in der Dokumentation der Klasse GREEDY nachzulesen.

Zelle* ziel;

Der Pointer auf die Zielzelle. Er kann mit der Memberfunktion Party::setzeZiel geändert werden. Dies macht zum Beispiel dann Sinn, wenn nach dem erfolgreichen Anpeilen eines Ziel noch ein anderes angesteuert werden soll.

Baum zustandsraum

Binärbaum, der die aktuelle Partitionierung des Konfigurationsraum repräsentiert. Die Blätter des Baumes sind die Zellen. Siehe auch Klasse Birnbaum.

• bool nln(ListenElement<Zelle*>*, void*)

  Prüft, ob eine Zelle mindestens eine Nachbarzelle hat, von der aus das Ziel zu erreichen ist. Wenn ja wird true zurückgeliefert. Ansonsten false.

• bool verlierer(ListenElement<Zelle*>*, void*)

  Liefert true, falls die betrachtete Zelle eine Loser-Zelle ist, d.h. daß es von dort keinen Weg zum Ziel gibt.

• void setzeZiel(const Zustandsvektor& , const Zustandsvektor& )

  Mit Hilfe dieser Funktion läßt sich durch Übergabe der Grenzen bezüglich jeder Achse eine neue Zielzelle definieren.

• bool zielErreicht(const Zustandsvektor& ) const

  Liefert true, wenn der übergebene Zustandsvektor in der Zielzelle liegt, ansonsten false.

• bool zielErreicht(const Zelle& ) const

  Liefert true, wenn die übergebene Zelle die Zielzelle ist, ansonsten false.

• Party(const Zustandsvektor& , const Zustandsvektor&, Zelle& , char*)

  Der Konstruktor dieser Klasse bekommt zwei Zustandsvektoren, die die Grenzen der Zielzelle markieren, einen Zeiger auf eine Zelle, der auf die Wurzel des den Konfigurationsraum repräsentierenden Binärbaum zeigt und einen String, der den Dateinamen der gewünschten SimRobot-Szene enthält. Es wird Speicher für eine Zelle (die Zielzelle) allokiert, die weiteren Initialisierungsaufgaben übernehmen die vom Party-Konstruktor aufgerufenen Konstruktoren der Klassen Birnbaum und Greedy.

• ~Party()

  Der Destruktor zerstört die vom Konstruktor angelegte Zielzelle.

• void party(Zustandsvektor )

  Diese Funktion, die den Startzustand einer Aufgabe als Argument erhält, bildet das Herz des Algorithmus. Die Funktion terminiert erst dann, wenn das Ziel erreicht ist, d.h. sie übernimmt die Aufgabe, den Agenten von einer beliebigen Startposition in die Zielzelle zu steuern. Dabei wird intensiv von der weiter oben beschriebenen Funktion algo3 gebrauch gemacht. Falls diese einmal nicht mehr weiter kommt, wird eine Zellteilung vorgenommen, da in einem solchen Fall die Auflösung der Partitionierung nicht fein genug ist, um zum Ziel zu gelangen. Dem im Paper vorgestellten Verfahren entsprechend werden alle Verliererzellen (Zellen, aus denen es keinen Weg zum Ziel gibt), die Gewinnerzellen (Zellen, aus denen es einen Weg zum Ziel gibt) als Nachbarn haben und diese Nachbarzellen selbst geteilt. Daraufhin muß natürlich die gesamte Datenstruktur wieder in Ordnung gebracht werden. Unter anderem werden aus der Wissensbasis alle Erfahrungen gelöscht, die mit den gerade geteilten Zellen zusammenhingen, da diese nicht länger von Interesse sind.

class Zelle

Diese Klasse stellt sämtliche Informationen und Funktionen bereit, die benötigt werden, um auf der Partitionierung des Konfigurationsraumes den Anforderungen des Algorithmus entsprechend operieren zu können. Die zur Repräsentation der Partition gewählte Datenstruktur wird in der Dokumentation zur Klasse BIRNBAUM erläutert. Eine Instanz der Klasse ZELLE entspricht einer Zelle, d.h. einem Hyperwürfel in dem möglicherweise mehrdimensionalen Konfigurationsraum, sofern es sich bei dieser Instanz um ein Blatt handelt. Ist eine Instanz kein Blatt, so ist die zu diesem Objekt gehörige Zelle zu einem früheren Zeitpunkt schon einmal geteilt worden. Die bekannten Informationen eines Objekts vom Typ ZELLE sind eine Liste der Nachbarzellen, seine Grenzen und seine Entfernung von der Zielzelle. Von einer Zelle lassen sich mit Hilfe von Memberfunktionen das Zentrum, die längste Achse, die Nachbarn, die Outcomes sowie die Entfernung zur Zielzelle bestimmen.

Definition

private:

Liste<Nachbar> nachbarn

Jede Zelle speichert lokal eine Liste ihrer Nachbarzellen. Zwei Zellen sind genau dann benachbart, wenn sie eine gemeinsame Kante haben die länger als nur eine Einheit ist, d.h. bei einem schachbrettartigen Muster sind Zellen entlang einer Diagonalen nicht benachbart. Die Zielzelle ist per Definition nicht in der Liste der Nachbarzellen enthalten.

• int gibLaengsteAchse()

  Ermittelt diejenige Dimension einer Zelle bezüglich welcher die Zelle die längste Kante hat. Zurückgegeben wird ein Integer-Wert, der dann als Enumerationstyp dim interpretiert werden kann.

• bool tangierend(const Zelle&, dim) const

  Prüft, ob eine Kante der aktuellen Zelle mindestens einen Punkt mit der durch das Argument vom Typ dim bestimmten Kante der übergebenen Zelle gemeinsam hat. Falls ja, wird true zurückgegeben.

• bool schneidend(const Zelle&) const

  Liefert true, falls die aktuelle Zelle (*this) die als Argument übergebene Zelle schneidet.

public:

int entfernung

Membervariable, in der die aktuelle Entfernung zur Zielzelle abgelegt ist.

Zustandsvektor min

Die Grenzen einer Zelle werden durch zwei Zustandsvektoren min und max definiert. Dabei beschreiben die Komponenten der beiden Vektoren jeweils die Ausdehnung der Zelle bezüglich einer Achse.

Zustandsvektor max

Siehe Zustandsvektor min

• bool istBlatt() const

  Liefert true genau dann, wenn es sich bei der aktuellen Zelle um ein Blatt des Binärbaumes handelt.

• Zustandsvektor center() const

  Berechnet den Zustandsvektor, der das Zentrum der aktuellen Zelle repräsentiert und liefert ihn zurück.

• bool istZustandInZelle(const Zustandsvektor&) const

  Liefert true falls der als Argument übergebene Zustandsvektor in der aktuellen Zelle liegt.

• friend Zelle& lieferZelleAusZustand(const Party&, const Zustandsvektor&)

  Bestimmt für den übergebenen Zustandsvektor, in welcher Zelle sich dieser befindet. Diese Zuordnung ist eindeutig, sie wird durch einfaches Durchlaufen des den Konfigurationsraum repräsentierenden Binärbaums realisiert.

• Zelle(const Zustandsvektor&, const Zustandsvektor&, Baum*)

  Der Konstruktor dieser Klasse ruft den der Klasse Knoten auf, um ein Objekt zu schaffen, das in den Binärbaum eingehängt werden kann. Ferner werden die Grenzen der aktuellen Zelle mit den übergebenen Werten initialisiert. Außerdem wird die Entfernung zur Zielzelle initial auf 0 gesetzt.

• Liste<Zelle*> bestimmeNachbarn(const Party&) const

  Diese Funktion bestimmt die Liste der Nachbarn der aktuellen Zelle und liefert sie zurück. Schneidet die aktuelle Zelle die Zielzelle, so wird die Zielzelle in diese Liste eingehängt.

• Liste<hint> bestimmeOutcomes(const Party&, const Zelle&) const

  Erstellt eine Liste, in der Paare von Zellzeigern und Kosten abgelegt sind. Dabei werden aus der Wissensbasis all die Einträge herangezogen, in denen Informationen zum Thema Beim Versuch aus der aktuellen Zelle in die als Argument übergebene Zelle zu fahren, bin ich in Zelle XY gelandet bei Kosten Z. Ein solches Paar (XY,Z) wird in die Liste eingetragen.

• Liste<Eintrag> gibWissenliste(const Party&, const Zelle&) const

  Liefert eine Liste von Wissensbasiseinträgen, die Informationen enthalten der Form Auf dem Weg von der aktuellen Zelle zu der als Parameter übergebenen Zelle....

• int Jwc(const Party&)

  Bestimmt die Entfernung einer Zelle zum Ziel. Unter der Voraussetzung, daß die Entfernung aller anderen Zellen bereits korrekt bestimmt worden sind, wird mit Hilfe der "Worst-Case"-Annahme diejenige Nachbarzelle ermittelt, über die der kürzeste Weg zum Ziel führt. Worst-Case deshalb, weil beim Vergleich der Übergangskosten in die Nachbarzelle die schlechteste bisher für diesen Übergang gemachte Erfahrung zugrunde gelegt wird.

• int teileZelle();

  Diese Funktion teilt die Zelle, auf die sie angewendet wird,in zwei gleichgroße neue Zellen auf. Dazu wird die längste Achse gefunden und getestet, ob durch eine Zellteilung die Mindestgröße von Zellen unterschritten wird. Wenn nicht, werden die beiden neuen Zellen angelegt und an die ursprüngliche angehängt.

  Dann werden die Nachbarschaftsbeziehungen der beiden neuen Zellen bestimmt: für jeden Nachbarn der alten Zelle wird geprüft, ob er Nachbar einer oder beider neuen Zellen ist. Dazu werden sie in zwei Gruppen geteilt: Nachbarn, die auf der "geteilten Achse" links oder rechts liegen, können nur Nachbar der linken bzw. rechten Zelle sein. Zellen, die auf einer anderen Achse an die Zellen grenzen, können (je nach Ausdehnung) zu beiden neuen Zellen benachbart sein. Außerdem sind beide neuen Zellen natürlich zueinander benachbart.

  Schließlich wird die this-Zelle aus den Nachbarschaftslisten aller seiner Nachbarn gelöscht. Damit ist sie keine Zelle mehr, sondern ein Knoten.

• Liste<Eintrag> gibWissensliste(const Party&, const Zelle&) const

  Filtert aus der zur Party gehörigen Wissensliste all diejenigen Elemente heraus, die Informationen der Form Beim Fahren von *THIS zur übergebenen Zelle... enthalten.