KI-Projekt WS 1999/2000 - Genetisches Programmieren einfacher Roboterfähigkeiten

How can computers learn to solve problems without being explicitly programmed?
In other words:

How can computers be made to do what is needed to be done, without being told exactly how to do it?

Arthur Samuel, 1950s

Artur Samuel formulierte damit in den 50er Jahre ein heute immer noch zentrales Problem der Informatik. Ein Ansatz zur Lösung dieses Problems ist die Genetische Programmierung.

Projektinhalt
Im KI-Projekt des 7. Semesters haben wir nun die Leistungsfähigkeit der genetischen Programmierung zum maschinellen Entdecken von Bewegungsmustern in realen autonomen Sytemen untersucht.
Das Testszenario bestand aus einem GP-System und einem realen Roboter mit zufälliger Morphologie.


Konkret hieß dies:
Ein zufällig zusammengeschraubtes Gebilde aus sechs Servomotoren sollte dazu gebracht werden, sich selbständig fortzubewegen.

Genetisches Programmieren einfacher Roboterfähigkeiten
(Paper und Vortrag, 4. Mechatronik-Workshop an der FH Brandenburg 9/2000)

Die Aufgabenstellung
Erstellen Sie aus 6 Servo-Motoren einen Roboter, wobei die Konstruktion zufällig entstehen soll. Finden Sie mit Hilfe der Genetischen Programmierung ein Programm, daß den Roboter befähigt, sich geradeaus vorwärts zu bewegen.

Projektteam

Gruppe 1 - Thilo Voigt, Thomas Rappe, Hr. Puchert
Gruppe 2 - Roman Zippel
Gruppe 3 - Daniel Stys, Hr. Blech (auch 2A)

Projektplanung

Teilaufgaben

Die folgenden Texte und Bilder stammen aus den Projektberichten der einzelnen Gruppen.

Gruppe 1:

Teil A:
Konstruktion des Wagens: möglichst leichtes, leichtlaufendes, einfach nachzubauendes Gefährt zur Aufnahme des Eyebots und der Akkus
mechanische Kopplung zum Roboter
Genaue Messung des zurückgelegten Weges und des Winkels mittels Kamera oder Odometrie

Versuchsaufbau

Roboter Hier eine Komplett-Ansicht des Versuchsroboters.

Das Servorium Der Roboter besteht aus 6 Servo-Motoren. Sie sind untereinander mit verschieden langen Gewindestangen verbunden. Welcher Servo mit welcher Stange verbunden wurde, bestimmte das Würfelschema, um die Zufälligkeit der Konstruktion zu gewährleisten. Die einzelnen Servoanschlußkabel wurden mittels Verlängerungs-Flachbandkabel mit dem Board verbunden. Somit konnte eine bessere Beweglichkeit des Roboters sichergestellt werden.

Der Meßwagen Die Bedingungen für den Bau des Wagens waren die Aufnahme des Eyebots, des Akkus und der Wegmesseinrichtung (Odometrie). Unter diesen gegebenen Vorraussetzungen war es sehr schwierig, mit Hilfe von LEGO-Bausteinen, ein möglichst leichten, leichtlaufenden und einfach nachzubauenden Wagen zu konstruieren. Um das Gewicht des Wagens zu reduzieren, wurde der Akku durch eine externe Stromversorgung ersetzt. Für die Odometrie war für jedes Rad eine inkrementelle Encoder-Scheibe verantwortlich. Die Drehbewegung der Räder wurde über Zahnräder auf die Scheiben übertragen. Durch diese Methode war es uns möglich, das Übersetzungsverhältnis zu beeinflussen.

Kurze Beschreibung des Ablaufs Das auf dem PC auf unsere Situation angepaßte GP-Programm wird über die serielle Schnittstelle auf den Eyebot geladen. Danach wird das genetische Programm gestartet. Es generiert Individuen, testet sie am Roboter aus und bewertet diese an Hand der Meßwerte der Odometrie. Während des Ablaufs wird auf dem Display des Eyebots und auf dem Bildschirm des PC`s die Bewertung des aktuellen Individuums und die Fitness des bis dahin besten Individuums angezeigt. Das Experiment ist beendet, wenn eines der Individuen die Fitness 0 erhält oder 80000 Induviduen getestet wurden. Zum Schluß soll das beste Individuum am Roboter angewendet werden, um zu sehen ob der Versuch erfolgreich war.

Wegmessung Odometrie ist die am weit verbreitetste Methode für die Wegmessung von mobilen Robotern. In unserem speziellen Fall nahmen wir inkrementelle Encoder-Scheiben zu Hilfe. Zuerst nutzten wir eine zweizeilige Scheibe. Dabei traten jedoch unüberwindbare Probleme auf. Die eingesetzten Sensoren, zuerst Optokoppler, konnten die feine Strichstruktur nicht zuverlässig auflösen. Nach einigen Versuchen mit anderen Auflösungen mußten wir erkennen, daß diese Variante der Encoder-Scheiben nicht einsetzbar ist. Nach einigen Überlegungen und nachfolgenden Tests kamen wir zu dem Schluß, daß einzeilige Scheiben mit breiterer Strichstruktur besser sind. Zudem wechselten wir die Optokoppler gegen eine Kombination aus IR-Sender und Empfänger. Um diese Sensoren nutzen zu können, mußte die Encoder-Scheibe bis auf die schwarzen Felder des Strichcodes transparent gemacht werden.

Teil B:
Programmieren der Funktionen und Terminale (Servos, analoge Sensoren, sleep...)
Programmieren der Beobachtungsfunktion zur Fitnessmessung

Fitness-Messung

Eine der Grundfunktionen für die Genetische Programmierung ist die Fitness-Funktion. Um festzustellen inwieweit eine Aktion (bspw. Vorwärtsbewegen) erfolgreich war, benötigt man eine Rückmeldung. Meist besteht diese Rückmeldung aus einem Zahlenwert. Ein vom GP-System generiertes Programm das den Roboter vorwärtsbewegt, soll gut bewertet werden. Dementsprechend soll ein Programm das den Roboter rückwärtsbewegt natürlich schlecht bewertet werden. Durch diese Bewertung kann das GP-System entscheiden welche Individuen (Programme) wie verwendet werden (entfernen, mit anderen Individuen kreuzen, mutieren). Diese Bewertung des Individuums findet in der Fitnessfunktion statt. Das GP-System befragt das Individuum nach seiner Fitness. Da unser Roboter lernen soll sich vorwärts zu bewegen musste ein Weg gefunden werden die Vor/Rückwärtsbewegungen in einen Zahlenwert abzubilden. Dazu wurden die Räder des Roboters über ein mechanisches System (Zahnräder) mit je einer odometrischen Scheibe gekoppelt. Diese werden optisch abgetastet (Lichtschranke). Auf den Scheiben sind abwechselnd auf zwei Spuren schwarze und weisse (d.h durchsichtige) Balken aufgetragen. Die Spuren sind versetzt aufgetragen (siehe Abbildung).

Durch die versetzten Spuren sind 4 Zustände ermittelbar:

1.Weiss - Schwarz
2.Schwarz - Schwarz
3.Schwarz - Weiss
4.Weiss - Weiss

Durch diese Zustände und den Übergängen von einem Zustand in einen anderen kann man nun feststellen in welche Richtung die Räder sich drehen.Zusätzlich
kann man die Entfernung die zurückgelegt wurde durch die Anzahl der Rundenumläufe ermitteln. Es ergibt sich folgendes Zustandsübergangsdiagramm:

durchgezogene Pfeile - z.Bsp. Vorwärts
gestrichelte Pfeile - z. Bsp. Rückwärts

Die Fitness-Funktion arbeitet somit folgende Schrittfolge ab:

1.Lese Licht-Sensoren aus
2.Ermittle aktuellen Zustand
3.Vergleiche vorherigen mit aktuellen Zustand
4.Entscheide aufgrund des vorherigen Vergleichs die Richtung
5.Merke aktuellen Zustand für nächste Messung
6.Wenn alle Zustände einmal durchlaufen wurden zähle Entfernungszähler weiter
7.Gebe positiven Wert bei Vorwärtsbewegung , negativen Wert bei Rückwärtsbewegung zurück

Die Fitness-Funktion wird zyklisch durch ein Timer alle 20 ms aufgerufen. Sie gibt immer ein Zahlenwert (Vorzeichen = Richtung , Betrag = Entfernung) zurück.
Dieser Rückgabewert wird danach auf einen Wertebereich zwischen 0 und -10000 normalisiert. Je größer der Wert um so besser die Fitnes Gruppe 2:
Teil A:
GP-Quick verstehen, Quelltext kommentieren, zur Nutzung vorbereiten
Einführung der anderen Gruppen in GP-Quick (Dateien, Klassen, Objekte, Steuerfluss, ..., Codebesprechung, wo ist was änderbar)

GP-Quick

Allgemein
Gp-Quick ist ein C++-Programm in dem ein genetischer Algorithmus fertig implementiert ist. Will man dieses Programm für eigene Anwendungen nutzen, muss man die Parameter in Gp-Quick entsprechend anpassen und wenn notwendig eigene Prozeduren (z.B. zur Ein- und Ausgabe) implementieren. Der genetische Algorithmus in Gp-Qick arbeitet prinzipiell so wie er von "Koza" (dem "Vater" genetischer Algorithmen) beschrieben wird. Zusätzlich sind noch einige Verfeinerungen implementiert. (siehe Abb. 1)
>

(zu Abb 1 : "pxxxWt" -> Parameter zur Einstellung der Wahrscheinlichkeiten ; "( pxxx )" -> zusätzliche, interne Parameter)

Crossover
Es findet eine Vorauswahl aus zwei möglichen Alternativen statt. Bei der ersten Alternative "CrossOver" kann jedes Individuum per zufälliger Auswahl aus der Gesamtpopulation, am Turnier teilnehmen. Es haben also auch Individuen mit schlechter Fitness eine Chance "Kinder" zu erzeugen. Bei der zweiten Alternative "Anneal Crossover" wird eine Vorauswahl getroffen, wer per Zufall für ein Turnier ausgewählt wird. Bei dieser Vorauswahl werden Individuen mit schlechter Fitness aussortiert. Es haben also nur Individuen mit guter Fitness die Chance sich weiter zu entwickeln und "Kinder" zu erzeugen. Dies beschleunigt den Prozess der Evolution.

Mutation
Die Beziehung der Alternativen "Mutate" und "Anneal Mutate" entspricht derselben wie beim Crossover. Danach bieten sich drei Alternativen wie das Individuum mutieren soll. "MutateConst" entspricht einer Permutation. Das heißt, daß Teiloperationen (Verzweigungen) des Individuums mit sich selbst vertauscht werden. Bei "MutateShrink" werden Verzweigungen des Baumes abgeschnitten und verworfen. MutateNode???

Reproduction
Das ausgewählte Individuum bleibt unverändert.

Die Wahrscheinlichkeiten (wie oft der Pfeil, wo, trifft) wurden grob folgendermaßen aufgeteilt :

Crossover ~ 80%
Mutation ~ 15%
Reproduction ~ 5%


Teil B:
Windows-Programm zum Abspeichern und Laden von erfolgreichen Individen vom Eyebot (über serielle Schnittstelle)

PC an Eyebot

Zur Kommunikation zwischen PC und Eyebot wurde fuer beide Seiten eine Bibliothek entwickelt, die auf der jeweiligen System-API aufsetzt und eine Packetübermittlung mit einfacher Fehlererkennung ermöglicht.

Probleme ergaben sich während der Tests durch vereinzelte Übertragungsfehler oder komplette Unterbrechung (Abziehen des Kabels), die eine ursprünglich vorgesehene bidirektionale Kommunikation erschweren. Um Fehler besser zu erkennen, sollte die Übertragung einseitig initiert und kontrolliert werden. Eine Seite sendet Daten oder fordert diese an und muss dabei aber auch kontrollieren, ob diese wirklich ankommen und evtl. entsprechende Maßnahmen ergreifen.

PC-Seite
Die Grundfunktionen zur Kommunikation basieren auf der Win32-API und bestehen aus:

• BOOL ComInit(void);
  Liefert TRUE zurueck falls die COM-Schnittstelle erfolgreich geöffnet
  und initialisiert wurde, anderenfalls FALSE.
  
• BOOL ComRead(LPBYTE lpBuffer, DWORD nRead, LPDWORD lpRead);
  Liest maximal nRead Bytes von der COM-Schnittstelle. In lpRead wird die tatsächlich übertragene Anzahl zurueckgegeben (falls z.B. vorher ein Timeout ablief).
  
• BOOL ComWrite(LPBYTE lpBuffer, DWORD nWrite);
  ComWrite schreibt den kompletten Puffer und wartet dafür solange bis
  dies erfolgreich geschehen ist.
  Sowohl ComRead() als auch ComWrite() liefern lediglich ein FALSE
  zurück, falls schwerwiegende Fehler während der Übertragung
  auftraten.
  
• void ComClose(void);
  Schließt die COM-Schnittstelle.
  

Aufbauend auf diesen Funktion werden zwei Grundfunktionen realisiert.

• BOOL BotDownloadProg(void);
  überträgt ein neues Programm zum Eyebot, damit wird ein seperates
  Terminalprogram überflüssig, welches vorher dazu benutzt wurde (Die
  serielle Schnittstelle kann nicht gleichzeitig von zwei Programmen
  geöffnet werden, so daß ein ständiges Neustarten der
  einzelnen Programme notwendig war.)
  
• void BotDoListen();
  realisiert dieKommunikation mit den zuvor geladenem Programm. Diese ist paketorientiert, d.h. ein Paket beginnt mit einem bestimmten Zeichen, danach folgen die Daten (mit Checksumme). Zusätzlich schreibt
  BotDoListen()  die empfangenen Daten zur späteren Auswertung in
  eine Log-Datei. Diese Pakete sind in der Regel Strings die ein erzeugtes Individuum beschreiben, da es sich dabei um normalen Text handelt, bleiben die Individuen lesbar und interpretierbar.
  

Über BotDoListen() wird eine Reihe weiterer Funktionen zur Implementierung der Kommunaktion benutzt:

• BOOL BotGetPacket();
  Wartet auf ein bestimmtes Zeichen, welches den Anfang eines Packetes
  markiert. Danach folgt die Größe des Packets und schließlich
  die Daten selbst, gefolgt von einer Checksumme. Wenn ein komplettes Paket empfangen wurde, liefert BotGetPacket() TRUE zurück und die Daten in einem globalen Puffer.
  
• BOOL BotSendReplyPacket(LPBYTE data, DWORD size);
  Sendet ein Paket zum Eyebot und benutzt dabei dasselbe Protokoll wie
  BotGetPacket().
  
• BOOL BotRead(LPBYTE pbuf, int size);
  Ist eine Erweiterung zu ComRead() und wartet solange bis der Puffer komplett gefüllt ist.
  
• int BotGet(BOOL wait);
  Wartet auf einzelnes Zeichen von der COM-Schnittstelle, falls wait FALSE ist, kehrt BotGet() nach Ablauf eines Timeouts zurück, anderenfalls wartet es weiter.
  

Eyebot-Seite
Auch hier werden einige Funktionen definiert, die auf der System-API aufsetzen, um die Kommunikation über die serielle Schnittstelle zu ermöglichen (die Funktionen unterscheiden sich von den PC-Funktionen, da die Eyebot-Funktionen einfacher und weniger flexibel sind):

• bool SendChar(unsigned char ch);
  Sendet ein einzelnes Zeichen zur seriellen Schnittstelle.
  
• int GetChar(bool wait);
  Wartet bis ein Zeichen über die serielle Schnittstelle empfangen wurde, die wait Funktion ist hier nicht nutzbar, da sich das Timeout nicht einstellen laesst und andererseits aber zu groß ist.
  
• int CheckChar(void);
  Überprüft, ob ein Zeichen im internen Puffer wartet und liefert es
  zurück, anderenfalls liefert es eine -1 zurück.
  

Basierend auf diesen Funktionen werden die eigentlichen Kommunikationsfunktion realisiert:

• bool SendPacket(char *buff, int count);
  Sendet ein Packet zur PC-Seite. Das dabei benutzte Protokoll ist
  bereits bei BotGetPacket() beschrieben.
  
• bool ReqPacket(char *req, int count, char *dest, int *size);
  Ursprünglich dazu vorgesehen, um Packete vom PC anzufordern (z.B.
  einzulesende Individuen), wegen Zeitmangels im Projekt nur unvollständig realisiert (es fehlt die erforderliche Antwortroutine auf PC-Seite).
  

Probleme
Probleme ergaben sich während der Tests durch vereinzelte Übertragungsfehler oder komplette Unterbrechung (Abziehen des Kabels), die eine ursprünglich vorgesehene bidirektionale Kommunikation erschweren. Um Fehler besser zu erkennen, sollte die Übertragung einseitig initiert und kontrolliert werden. Eine Seite sendet Daten oder fordert diese an und muss dabei aber auch kontrollieren, ob diese wirklich ankommen und evtl. entsprechende Maßnahmen ergreifen.


Gruppe 3:
Teil A:
Einflußgrößen und ihre Wirkung bei GP
Welche Ergebnisse wurden in Dortmund erzielt?
Würfelschema zur zufälligen Konfiguration von Robotern (vorh. Material beachten)

Das Würfelschema

Das Würfelschema ist das Muster, nach dem der Roboter zusammen gebaut werden soll. Es ist ein festes Muster, mit dem jedesmal eine andere Konstruktion herauskommt. In diesem Experiment waren 6 Servomotoren, zu denen es je 5 Radtypen gab, über unterschiedlich lange Gewindestangen zu verbinden. Und an jedem Servo gab es je 5 Befestigungsmöglichkeiten. Die Gewindestangen konnten an den Servos auf 3 Arten befestigt werden. Zum einen konnten sie fest und starr angeschraubt werden, zum zweiten gab es ein Gelenk mit dem ein zweidimensionaler Bewegungsradius möglich war. Als letztes stand ein
Gelenk zur Verfügung, das fast in alle Richtung bewegbar war.

Das Schema
Als erstes erhält jeder Servomotor, jeder verwendete Radtyp, jede Befestigungsmöglichkeit am Servo und jede Befestigungsart eine eigene Nummer. Und dann wird gewürfelt.

Zu erst wird für jeden Servo das zu montierende Rad ausgewürfelt. Dann wird die Befestigungsmöglichkeit ausgewürfelt, an der das erste Verbindungsstück angebracht wird. Anschließend wird die Befestigungsart ermittelt. Falls als Befestigungsmöglichkeit das Rad ermittelt wurde, wird als Befestigungsart das Gelenk Eins verwendet, da nur dies dort befestigt werden kann. Dann wird der Servo ausgewürfelt, mit dem eine Verbindung hergestellt werden soll. Für diesen werden ebenfalls die Befestigungsmöglichkeit und die Befestigungsart ausgewürfelt. Und auch hier gilt, wird das Rad als Befestigungsmöglichkeit ausgewürfelt, kommt nur als Befestigungsart das Gelenk Eins in Frage.
Nach dieser ersten Runde sollte jeder der sechs Servos mit mindestens einen anderen verbunden sein. In der nebenstehenden Tabelle ist die erwürfelte Servo-Verbindungs-Kombination abgebildet:

Würfelrunde I
MotorNr.	Radtyp	Befestigung an	Halterungstyp
1	3	3	1
2	5	1	3
3	2	4	1
3	5	1	3
4	2	4	3
6	4	5	2

Nun beginnt die zweite Runde. Dabei wird nun wieder nach dem selben Schema vorgegangen. Man muß lediglich die schon belegten Befestigungsmöglichkeiten an den Servos ausschließen, bis auf das Rad, da dort mehre Verbindungen angebracht werden können. Nun kann man noch eine dritte Runde beginnen. Allerdings hat man an einigen Servos immer weniger Befestigungsmöglichkeiten. Zudem können immer noch Servos mit nur zwei Verbindungen dabei sein. Diesem Ungleichgewicht kann man entgegen wirken, indem man für die Servos mit zuwenig Verbindungen, weitere Verbindungen auswürfelt.

Jeder Servo sollte vier bis fünf Verbindungen zu anderen Servos haben. An den Rädern können ruhig zwei bis drei Verbindungen sein. Da im Betrieb erhebliche Kräfte wirken auf die Verbindungen wirken, ist es sehr wichtig für möglichst feste Verbindungen zu sorgen. Ein weiterer Punkt ist die Beweglichkeit. Verbindungen, die Servos im Dreieck miteinander verbinden, schränken die Gesamtbeweglichkeit ein. Im Viereck erhöht sie sich. Die Beweglichkeit und auch die Stärke der Verbindungen muß man austesten. Eventuelle Schwachstellen lassen sich so gut ausfindig machen und beseitigen. Man kann dann alternative Verbindungen herstellen, verkürzen, verlängern oder ganz weglassen. Manchmal reicht es auch eine Verbindungsstange einfach nur etwas zu verbiegen.

Wenn man nach diesem Schema verfährt, sollte jedesmal ein anderes Gebilde entstehen. So entstanden in dem Projekt ebenfalls zwei sehr unterschiedliche Gebilde.
Teil B:
Entwurf von Versuchen zur Untersuchung der Einflußgrößen bei GP (insbesondere Nutzung von Sensoren), Dokumentation wesentlicher Probleme, Ergebnisse und Ausblick

Probleme

Die Probleme des Projektes lagen hauptsächlich bei der Konstruktion des Roboters und des Wagens für die Odometrie.

Problem : Gewichtsunterschied Roboter - Wagen
Der Roboter selbst ist aufgrund seiner Konstruktion leicht. Da sich auf dem Wagen der Eyebot-Mikrocontroller der Akku zur Stromversorgung und die Meßvorrichtungen befinden, ist der Wagen relativ schwer, so daß es keine "leichte" Aufgabe für den Roboter ist, den Wagen überhaupt zu bewegen.

Lösungsansatz :
Da der Akku am meisten wiegt, wurde davon abgesehen ihn auf dem Wagen zu installieren. Statt dessen wurde der Eyebot über ein Kabel stationär mit Strom versorgt. Damit der Wagen möglichst leicht rollt, wurden schmale Plastikräder genommen die geringe Reibung verursachen. Die Servomotoren des Roboters wurden an den Stellen an denen sie mit dem Boden in Berührung kommen mit Gummi beklebt um dem Roboter eine möglichst hohe Kraftübertragung zu ermöglichen. Es musste eine einfache (also leichte) Konstruktion für dem Wagen gewählt werden die gleichzeitig stabil genug ist.

Problem : Stromversorgung
Die sechs Servomotoren des Roboters werden über die Platine des Eyebot mit Strom versorgt. Will nun ein Individuum mehr als vier Servomotoren des Roboters bewegen, können dafür bis zu drei Ampere benötigt werden, was zu viel für die Platine des Eyebots ist, so daß das laufende Programm abstürzt.

Lösungsansatz:
Dieses Problem wurde softwaretechnisch gelöst. Es wurde ein "Zeitfenster" implementiert, durch dessen Hilfe ständig kontrolliert wird, wieviel Servomotoren in der letzten Zeiteinheit (z.B. 1 Sek.) aktiviert wurden. Wenn innerhalb dieses Zeitrahmens (Zeitfensters) eine maximale Anzahl (z.B. 4) Servobefehle überschritten wird, werden alle neuen Servobefehle abgeblockt.

Problem : Odometrie -> Lesen der Scheiben
Mit Hilfe des am Roboter angehängten Wagens soll es, durch Registrierung der Drehungen der Räder, feststellbar sein ob sich der Roboter und folglich auch der Wagen vorwärts oder rückwärts oder auch seitwärts bewegt hat. Um Seitwärtsbewegungen festzustellen, müssen die Drehungen des linken und des rechten hinteren Rades separat ausgewertet werden. Da auch geringe
Bewegungen registriert werden sollen, muss die Messung sehr genau erfolgen. Dies geschieht über Photosensoren die Schwarz-Weiss-Scheiben abtasten. Diese Scheiben sind mit den Radachsen des jeweils linken und rechten Rades verbunden.
Anfangs wurden die Schwarz-Weiss-Felder der Scheiben über analoge Photosensoren abgetastet. Diese wurden mittels eines festgelegten Schwellwertes und der gemessenen Lichtintensität (0 bis 255) nach hell (weiss) oder dunkel schwarz) klassifiziert.

Jedoch arbeitete dieses Verfahren mit analogen Photosensoren sehr unzuverlässig. Erst der Einsatz von binären Photosensoren, die als Ergebnis der Abtastung entweder 0 (schwarz) oder 1 (weiss) liefern, brachte zuverlässige Ergebnisse.

Problem : Zeit -> Dauer der Experimentierphase
Für jedes Individuum muss seine Fitness festgestellt werden bevor es mit dem genetischen Algorithmus verarbeitet werden kann. Um die Fitness zu ermitteln ist es notwendig das Individuum mit dem Roboter für wenigstens 2 Sekunden zu testen.

Dieser Test sollte möglichst mehrmals (mindestens zweimal) mit dem selben Individuum durchgeführt werden. Bis ein gutes Individuum mit einer hohen Fitness aus der Population entsteht müssen ungefähr 4000 Fitnesstests ausgewertet worden sein.

Also :

2 * 2 *4000 sek = 16000 sek = 260 min = 4 bis 5 Stunden

bis ein Ergebnis zu erwarten ist. Dabei ist der Erfolg nicht garantiert wenn beim Start eine schlechte Population generiert wurde.
Aufgrund der begrenzten Projektzeit, soll nach Möglichkeiten gesucht werden den Prozess der Evolution zu beschleunigen.

Lösungsansätze :
Besonders in der Anfangsphase der Entstehung einer Population kommt es häufig vor, daß teilweise unbewegliche Individuen oder Individuen mit nur einem Servomotor-Befehl erzeugt werden. Man kann diese Individuen als "Todgeburten" betrachten und gleich softwaretechnisch aussondern ohne daß sie wertvolle Zeit auf dem Roboter verbrauchen. Dieses Verfahren könnte man auch als Starthilfe verstehen. Es wurde erfolgreich implementiert. Weiterhin wurden die Zeiten für jedes Individuum möglichst gering gehalten (zwei Sekunden) und die Anzahl der Versuche je Individuum auf zwei begrenzt. Eine zusätzliche Möglichkeit Zeit zu sparen, kann durch einfache Beobachtung durchgeführt werden, indem die ersten Fitnesstests auf dem Roboter hinsichtlich ihrer Beweglichkeit eingeschätzt werden. Bei einer Population von 100 Individuen müssten dann also die ersten 200 Tests vom Beobachter bewertet werden. Waren nur wenige schwache Bewegungen zu beobachten handelt es sich
wahrscheinlich um eine schlechte Population mit wenigen Erfolgschancen die man abbrechen sollte. Zusätzlich kann die bis hierher beste Fitness zur Entscheidung herangezogen werden.

Problem : Protokollierung
Zur Auswertung des Experimentes und zur Rückkopplung wie die Parameter für neue Experimente gesetzt werden müssen ist es notwendig, die jeweils besten Individuen am Ende des Experimentes abzuspeichern. Zusätzlich ist es auch sinnvoll, das schlechteste Individuum und die durchschnittliche Fitness aller Individuen abzuspeichern. Durch Vergleich mit den gesetzten Parametern, können so Rückschlüsse auf die Wirksamkeit der Parameter gezogen werden.

Lösungsansatz:
Hierzu wurde eine Routine implementiert die nach jedem Fitnesstest den Wert der aktuellen Fitness mit dem bisher besten und schlechtesten ermittelten Wert vergleicht und bei Über- bzw. Unterschreitung die Werte neu aktualisiert.

Ergebnisse

Ergebnisse Der Roboter hat eine zufällige Konstruktion Bewegungen des Roboters können registriert werden Die Hardware / Mechanik (Roboter, Odometrie) ist fertig implementiert Die Software (Schnittstellen, GP-Quick + zusätzliche Routinen) ist lauffähig Die Experimentierumgebung ist getestet und optimiert Erste Experimente wurden durchgeführt

Erkenntnisse Die Umsetzung der Theorie in die Praxis ist schwierig Optimierungsaufgaben mit genetischen Algorithmen benötigen viel Zeit Die Aufteilung der Projektarbeit in mehrere (abgeschlossene) Teilaufgaben ist sehr effektiv

Ausblick

Um das Projekt erfolgreich weiterzuführen sind umfangreiche Experimente zusammen mit genauer Protokollierung der Ergebnisse erforderlich. Mit Hilfe der Protokolldaten können dann Schlussfolgerungen auf sinnvolle Parametereinstellungen für neue Experimente gezogen werden.

Aus den bisher durchgeführten Experimenten ist zu erkennen, daß noch einige Verbesserungen bezüglich der Beweglichkeit des Roboters durchgeführt werden können. Es sollten längere und kräftigere Bewegungen zustandekommen. Dadurch würde dem genetischen Algorithmus eine größere und detailliertere Datenmenge über die "Fitnesslandschaft" der aktuellen Population zur Verfügung gestellt, wodurch ein höheres Potential an guten Individuen mit hoher Fitness erreicht würde.

Weitere Verbesserungen könnten erreicht werden wenn, neben den Sensordaten zur Fitness- auswertung, zusätzliche Sensordaten in die Berechnung mit einbezogen werden. Bis jetzt bauen alle Befehlsketten auf konstante Werte auf, die bei der Generierung der Population zufällig festgelegt wurden. Um eine bessere Rückkopplung des genetischen Algorithmus mit dem Roboter zu erreichen, könnten z.B. Tastsensoren am Roboter angebaut werden, die dann (eventuell in Zusammenhang mit If - Verzweigungen in den Befehlsketten) flexiblere Individuen hervorbringen würden. Dadurch könnten stabilere und erfolgversprechendere Generationen entstehen. Zusätzlich könnten auch die jeweils aktuellen Positionen der Winkel der Servomotoren abgefragt werden, was auch nutzbringende Informationen über den Zustand des Roboters liefert.

Neben den Untersuchungen und Auswertungen von Parametern, die sich auf den genetischen Algorithmus beziehen, sollten auch Einstellungen hinsichtlich der Zeiteinteilung geändert werden. So könnte man die Anzahl der Versuche, die jedes
Individuum zum Testen auf dem Roboter hat, erhöhen, oder die Dauer jedes einzelnen Tests pro Individuum verlängern (z.B. von zwei auf vier Sekunden).

Eine weitere Hilfe könnte das automatisches Sammeln und Zusammenfassen der Daten (z.B. der besten Fitness) während des laufenden Experimentes sein. Die Ergebnisse könnten graphisch ausgewertet werden um dann z.B. aus den Verlauf einer Kurve eine Stagnation der Evolution zu erkennen.

Im Buch über genetisches Programmieren von "Koza" wird empfohlen die Aufteilung der Wahrscheinlichkeiten von "Crossover", "Mutation" und "Reproduction" ungefähr folgendermaßen zu gestalten. :

Crossover ~ 80% der Fälle
Mutation ~ 15% der Fälle
Reproduction ~ 5% der Fälle

Da unter Gp-Quick der Mutation sehr viel Aufmerksamkeit mit vielen Variationen gegeben wurde,sollte man einige Experimente durchführen, bei denen die Mutation höher gewichtet wird (z.B. Gleichgewichtig mit Crossover) und diese Ergebnisse mit den anderen vergleichen.

Download: GP-Quick (zip)

Siehe auch: CMU AI Repository