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.
ProjektinhaltIm
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
AufgabenstellungErstellen 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
AllgemeinGp-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)
CrossoverEs
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.
MutationDie
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???
ReproductionDas
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-SeiteDie 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-SeiteAuch 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).
ProblemeProbleme 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 SchemaAls 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 - WagenDer 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
|
Categories: AMS-Projekte, Maschinelles Lernen
