christoph löwer

Projekt: Lego Mindstorms Roboter

Projektbeschreibung

Ein aus Lego Mindstorms Komponenten konstruierter autonomer mobiler Roboter soll so programmiert werden, dass er einen Weg aus einem, mit Klebestreifen modellierten Labyrinth findet. Daraus soll er den kürzesten Weg berechnen und speichern um diesen dann abfahren oder an einen anderen Roboterübertragen zu können. Die dargestellte Lösung besteht zum Einen aus einer Vorstellung des Roboters und den verwendeten Komponenten. Zum Anderen werden die Lösungen der Programmierungsseite, nämlich die Festlegung des Verhaltens, das heißt die Entwicklung von Algorithmen und deren Umsetzung erläutert. Die Wichtigsten Punkte sind dabei die Wegerkennung, die Datenspeicherung, die Berechnung des kürzesten Wegs, die Datenübertragung und das Abfahren des kürzesten Wegs. Zusätlich werden noch Schwächen des verwendeten Entwicklungs- und Betriebssystems aufgezeigt und durch Messungen belegt und ein mögliches Alternativsystem vorgestellt.

Downloads

Dokumentation (PDF-Format)	Robotik_Doku.pdf
Source Files (Code, Tex-Files, Images)	Robotik.zip

Screenshots

FH-Projekt

Projekt zur Vorlesung: Robotik

Dokumentation

Die Original-Dokumentation wurde in Latex erstellt.

Inhalt

• 1. Abstract
• 2. Einleitung
• 3. Einführende Arbeiten
• 4. Grundlagen
• 4.1. Lego Mindstorms
• 4.2. LEGO Mindstorms Bauteile
• 5. Lösung
• 5.1. Roboter
• 5.2. Wegerkennung
• 5.3. Datenspeicherung
• 5.4. Berechnung des kürzesten Wegs
• 5.5. Datenübertragung
• 5.6 Abfahren des kürzesten Wegs
• 6. Implementierung
• 6.1. Wegerkennung mit Farbwerten
• 6.2. Datenspeicherung
• 6.3. Berechnung des kürzesten Weg
• 6.4. Datenübertragung
• 6.5. Abfahren des kürzesten Wegs
• 6.6. C/brickOS und NQC/Lego Firmware
• 7. Zusammenfassung

1. Abstract

Ein aus Lego Mindstorms Komponenten konstrierter autonomer mobiler Roboter soll so programmiert werden, dass er einen Weg aus einem, mit Klebestreifen modellierten Labyrinth findet. Daraus soll er den kürzesten Weg berechnen und speichern um diesen dann abfahren oder an einen anderen Roboter übertragen zu können. Die dargestellte Lösung besteht zum Einen aus einer Vorstellung des Roboters und den verwendeten Komponenten. Zum Anderen werden die Lösungen der Programmierungsseite, nämlich die Festlegung des Verhaltens, das heißt die Entwicklung von Algorithmen und deren Umsetzung erläutert. Die Wichtigsten Punkte sind dabei die Wegerkennung, die Datenspeicherung, die Berechnung des kürzesten Wegs, die Datenübertragung und das Abfahren des kürzesten Wegs. Zusätlich werden noch Schwächen des verwendeten Entwicklungs- und Betriebssystems aufgezeigt und durch Messungen belegt und ein mögliches Alternativsystem vorgestellt.

2. Einleitung

Bei dem zu lösendenden Problem handelt es sich um die Konstruktion und Programmierung eines autonomen mobilen Roboters. Dieser soll den kürzesten Weg aus einem Labyrinth finden, den Weg speichern und an einen anderen Roboter übertragen können. Darüber hinaus soll der Roboter, hat er von einem anderen Roboter, der bereits das Labyrinth abgefahren ist, einen Weg empfangen, diesen Weg nachfahren können und damit auf dem kürzesten Weg das Ziel des Labyrinths finden. Das Labyrinth ist in Form von Klebestreifen, die auf den Boden geklebt sind gegeben. Darüber hinaus werden verschiedenfarbige Klebestreifen zur Markierung des Fahrwegs, von Sackgassen und des Ziels benutzt. Einige Rahmenbedingungen wurden durch die bearbeitenden Gruppen festgelegt, die im folgenden Kapitel: Verwandte Arbeiten näher erläutert werden. Die Roboter werden mit Hilfe von Lego Mindstroms Komponenten konstruiert. Dabei sind vor allem der RCX (das programmierbare Bauteil), die Motoren, die den Roboter antreiben, und die Lichtsensoren, mit denen der Roboter den Boden und die Klebestreifen "sehen" kann, von Bedeutung. Diese bieten die Möglichkeit die geforderte Verhaltensweise des Roboters zu realisieren. Zunächst wurde ein Roboter gebaut, der die Voraussetzung schafft die Aufgabenstellung zu erfüllen. Er besteht aus dem RCX, zwei Power-Motoren, die zwei Ketten antreiben und zwei Lichsensoren an der Front des Roboters. Um den Roboter programmieren und damit die gewünschte Verhaltensweise realisieren zu können mussten einige Algorithmen entwickelt werden. Diese sollen die folgenden Fragestellungen beantworten:

• Wie kann der Roboter Wegeerkennen?
• Wie können Wegdaten gespeichert werden?
• Wie berechnet man aus den Wegdaten den kürzesten Weg zum Ziel?
• Wie überträgt der Roboter Wegdaten zu einem anderen Roboter?
• Wie kann der Roboter mit Hilfe der Wegdaten den kürzesten Weg aus dem Labyrinth finden?

Dies sind die Kernpunkte, welche zu beantworten sind, um ein entsprechendes Programm schreiben zu können. Im Zuge dieser Arbeit werden die genannten Fragen beantwortet und die algorithmischen Lösungen als auch die fertige Implementierung vorgestellt und erläutert werden. Darüber hinaus wurde ebenfalls eine Vergleichsuntersuchung von zwei Systemen zur Programmierung des RCX durchgeführt und wird im Kapitel: Implementierung vorgestellt werden. Durch die Ergebnisse der Untersuchung sollen einige Schwächen des NQC/Lego Firmware Systems aufgezeigt und eine mögliche Lösung dieser Schwächen angeboten werden.

3. Einführende Arbeiten

Zur Lösung der Problemstellung mussten zunächst einige Rahmenbedingungen geschaffen werden, das heißt Spezifikationen, innerhalb derer die Gruppen ihre Lösungen entwickeln. Dies ist vor allem in Bereichen von hoher Relevanz, in denen die Roboter in Interaktion mit einander stehen. Um diese Spezifikationen festlegen zu können, waren zunächst einige Überlegungen und empirische Untersuchungen nötig. Aus diesem Grund wurden zu untersuchende Bereiche festgestellt, eingeteilt und an die Gruppen verteilt, sodass jede Gruppe ein oder zwei Bereiche zu bearbeiten hatte. An dieser Stelle sollen nun einige dieser Bereiche kurz erläutert werden, die von anderen Gruppen bearbeitet wurden und die bei der Lösung der Aufgabenstellung besonders relevant sind. Da die Anwendung der Untersuchungsergebnisse einen wichtigen Teil der Lösung darstellen, folgen genaue Erläuterungen dazu ebenfalls in den folgenden Kapiteln: Lösung und Implementierung.

Kommunikation

Ein Teil der Problemstellung ist es, dass, hat ein Roboter einen Weg aus dem Labyrinth gefunden und den kürzesten Weg zum Ziel berechnet, er diesen an einen zweiten Roboter überträgt und der zweite Roboter diesen abfährt. Dazu ist es nötig Spezifikationen zu entwickeln, die festlegen, wie die Roboter untereinander kommunizieren können. Es wurde dafür von einer Gruppe ein Kommunikationsprotokoll erarbeitet und den anderen Gruppen eine Referenzimplementierung zur Verfügung gestellt, welche als Richtlinie und Vorgabe für die eigenen Lösungen genutzt werden konnte.

Kreuzungen/Wege

Es musste festgelegt werden, in welcher Weise der Roboter den Weg vom Start zum Ziel des Labyrinths speichert. Die diesen Bereich bearbeitende Gruppe ist zu dem Ergebnis gekommen, dass Weginformationen über die Kreuzungen gespeichert werden, oder, genauer gesagt, an welcher Kreuzung der Roboter in welche Richtung zu fahren hat. Das heißt es liegt kein zweidimensionaler Scan des Labyrinths vor und damit auch keine Informationen über Weglängen oder Änhliches. Der Grund für diese Entscheidung ist zum Einen ökonomischer Natur und zum Anderen in den Fähigkeiten beziehungsweise Ressourcen der Lego Mindstorms Komponenten begründet.

Zyklen

Es wurde festgelegt, dass das abzufahrende Labyrinth zyklenfrei zu sein hat. Das heißt das ein Weg einer Kreuzung nicht auf ein Wegstück führen darf, das bereits abgefahren sein kann. Der Grund dafür ist, dass das Zulassen von Zyklen ein unverhältnismäßig höheren Entwicklungsaufwand zur Folge gehabt hätte.

Kreuzungen/Wege

Sackgassen werden mit einem, sich vom normalen Weg in der Farbe unterscheidenden Klebestreifen gekennzeichnet. Die Alternative wäre gewesen den Weg einfach enden zu lassen, was aber einer Erhöhung des Komplexitätsgrads und damit ebenfalls einen erhöhten Entwicklungsaufwand zur Folge gehabt hätte.

4. Grundlagen

Es sollen nun einige grundlegenden Aspekte der Lego Mindstorms Produktserie erläutert werden. Es wird dabei in die Bereiche Lego Mindstorms allgemein, Bauteile, Sensoren und Betriebssysteme und Programmierung respektive Software untergliedert.

4.1. Lego Mindstorms

Definition (LEGO Mindstorms)

LEGO Mindstorms ist der Name einer Produktserie der LEGO Company, die einen programmierbaren Baustein (RCX genannt), sowie Elektromotoren, Sensoren und LEGO Technik Teile (Zahnräder, Achsen, Lochbalken, Pneumatik Teile usw.) enthält, um Roboter und andere autonome und interaktive Systeme zu konstruieren und programmieren. Text aus Wikipedia

4.2. Lego Mindstorms Bauteile

RCX

Der Kern des Lego-Mindstorms Systems ist der programmierbare RCX-Baustein. Er koordiniert und wertet alle Daten aus. Außerdem leitet er die entsprechenden Befehle an die jeweiligen Bauteile (Sensoren, Motoren) weiter. Über eine Infrarotverbindung kann der RCX von einem PC mit Programmen versorgt werden. Im Inneren arbeitet ein Hitachi H8300 Microcontroller mit 8Bit und 16MHz. An Speichern stehen 16k ROM und 32k RAM zur Verfügung. Die 16k ROM enthalten die Basistreiber z.B. für die Infrarotschnittstelle und einige Low-Level-Funktionen. Artikel von Javamagazin

Bild von Lego Mindstorms Webseite

IR-Tower

Zur Datenübertragung zwischen PC und RCX wird ein IR-Sender /Empfänger (IR-Tower) benutzt. Dabei können Programme oder Firmwares ausgetauscht werden.

Bild von Lego Mindstorms Webseite

Motor

Es gibt momentan drei unterschiedliche LEGO-Technikmotoren, die ein 9V Spg. Versorgungsteil benutzen und elektrische Stecker der Standard-Lego-Art benutzen.

• Standard-Motor
• Mikro-Motor
• Power-Motor

In dieser Arbeit findet der Power-Motor Anwendung. Dieser Motor hat interne Zahnradübersetzungen und ein Schwungrad. Infolgedessen hat der Motor eine mittlere Geschwindigkeit mit hohem Drehmoment und läuft sehr glatt. Es ist sehr empfehlenswert, diesen Motor zu verwenden, wann immer es geht. Er braucht nur 10 mA während des Normalbetriebs und 250 mA, wenn er festgefahren ist.

Bild von Lego Mindstorms Webseite

Sensoren

Drucksensor: Dieser passive Sensor ist einfach ein normalerweise geöffneter Schalter, der in einen Baustein 2x4 eingebaut wurde.

Bild von Lego Mindstorms Webseite

Lichtsensor: Ein aktiver Sensor, der eine LED und einen Fototransistor miteinschließt, eingebaut in einen Baustein 2x4. Laut Lego Mindstorms kann der Sensor entweder dazu benutzt werden , auf eine externe Lichtquelle reagieren oder auf das reflektierte Licht der LED.

Bild von Lego Mindstorms Webseite

4.3. Sensoren

Für viele Bastler ist es sicher interessant, den vom RCX ausgegebenen Sensorwert (0..1023) interpretieren zu können. Dieser Wert ergibt sich aus der am Sensoreingang anliegenden Spannung. Ohne Sensor beträgt diese 5 V, fällt aber ab, sobald ein Sensor mit einem endlichen Widerstand angeschlossen wird. Die Sensoren können in einem aktiven (Lichtsensor, Drehsensor) und einem passiven Modus (Schalter, Temperatursensor) betrieben werden. Im passiven Modus wird wie oben beschrieben nur der Spannungsabfall an den Sensoreingängen gemessen. Im aktiven Modus liegt für je 3 ms die Batteriespannung am Sensoreingang an, um den Sensor mit Strom zu versorgen. Für 0,1 ms wird dann in den passiven Modus geschaltet, um den Sensorwert zu erfassen. In dieser Zeit muss sich der aktive Sensor durch eine eigene Stromquelle (Kondensator) versorgen. Text aus Wikipedia

Sensordaten lassen sich auf verschiedene Weisen auslesen. Dazu dienen verschiedene Modi, die für jeden Sensoreingang separat geschaltet werden können. Die Wahl des Sensormodus ist primär abhängig von der Art des mit dem Sensoreingang verbundenen Sensors. Davon abgesehen lassen sich die Modi jedoch auch manuell umschalten, sollte der als Default eingestellte Modus nicht die gewünschten Ergebnisse liefern. Die folgende Tabelle gibt einen Überblick über die vorhandenen Modi.

Tabelle (Sensor-Modi)

SensorMode	Meaning
SENSOR_MODE_RAW	raw value from 0 to 1023
SENSOR_MODE_BOOL	boolean value (0 or 1)
SENSOR_MODE_EDGE	counts number of boolean transitions
SENSOR_MODE_PULSE	counts number of boolean periods
SENSOR_MODE_PERCENT	value from 0 to 100
SENSOR_MODE_FAHRENHEIT	degrees F - RCX only
SENSOR_MODE_CELCIUS	degrees C - RCX only
SENSOR_MODE_ROTATION	rotation (16 ticks per revolution)

Die Daten der Lichtsensoren werden standardmäßig als Prozentwerte, also im SENSOR_MODE_PERCENT ausgelesen, was bedeutet, dass die raw-Daten in Prozentwerte umgerechnet werden. Wie bereits erwähnt ist es möglich auf den Sensormodus SENSOR_MODE_RAW umzustellen. Text aus NQC-Guide

4.4. Betriebssysteme und Programmierung

Der RCX ist mittels einer Vielzahl von Betriebssystemen und Programmiersprachen programmierbar. Folgend eine Auswahl an Programmiersprachen mit den zugehörigen Betriebssystemen für LEGO Mindstorms.

Von LEGO erstellte (beide grafisch):

• RCX Code
• ROBOLAB (basiert auf LabVIEW)

Drittanbieter (alle textorientiert):

• Java mit leJOS
• NQC ("Not Quite C" [Nicht ganz C]) mit Lego Mindstorms Firmware
• C und C++ mit brickOS (ehemals LegOS)
• pbFORTH/FORTH mit pbFORTH
• Visual Basic

Es sollen nun zwei Systeme, welche im Folgenden eine tragende Rolle spielen, erläutert werden.

Definition (NQC mit Lego Firmware)

NQC steht für Not Quite C (nicht ganz C) und ist eine einfache Programmiersprache für mehrere Lego Mindstorms Produkte. Einige NQC-Eigenschaften sind von dem Mindstorms Produkt abhängig, welches Sie benutzen. Dieses Produkt wird als Zielgerät für NQC bezeichnet. Zur Zeit unterstützt NQC fünf Zielgeräte: RCX, RCX2 (ein RCX mit der Firmware-Version 2.0),CyberMaster, Scout und Spybotics. Text aus NQC-Guide

NQC ist ein sehr einfach gehaltener C-Subset, der jedoch alle Sensorinterfaces enthält und Multitasking unterstützt. Die größte Beschränkung ist jedoch der geringe verbleibende Speicher mit 6K für Programm und Daten. Es können auch nur 32 Integer-Variablen gespeichert werden. Artikel von Javamagazin

In NQC geschriebener Quellcode wird von dem Mindstorms Compiler in Byte-Code übersetzt, welcher dann auf den RCX übertragen wird. Dieser Bytecode wird dann von der Lego-Firmware ausgeführt. Es handelt sich dabei also nicht um Maschinencode, sondern um ein Zwischenprodukt.

Definition (C/C++ mit brickOS)

BrickOS ist ein alternatives Betriebssytem für den Lego Mindstroms RCX Controller. Es stellt zusätzlich eine C/C++ Enwicklungsumgebung für RCX-Programme, für die der gcc und g++ benutzt werden und alle nötigen Tools, um die Programme auf den RCX zu laden, bereit. BrickOS

Im Gegensatz zu dem zuvor erläuterten System wird bei diesem mit Hilfe des gcc/g++ mit einem Cross Compiler für den Hitachi H8300 Maschinencode erzeugt. Das heißt es wird keine Zwischenstufe sondern plattformabhängiger Code erzeugt. Dieser Code kann schneller verarbeitet werden (siehe Kapitel: C/brickOS und NQC/Lego Firmware).

5. Lösung

Die Lösung der vorgegebenen Aufgabenstellung gliedert sich zunächst in zwei Bereiche. Es handelt sich dabei zum Einen um die Konstruktion des Roboters. Das heißt es muss eine Architektur geschaffen werden, die fähig ist, die Aufgabe zu erfüllen. Zum anderen geht es um die Entwicklung von Algorithmen, mit denen das gewünschte Verhalten des Roboters realisiert werden kann.

Erster Bereich befasst sich wie bereits erwähnt mit der Konstruktion des Roboters und behandelt daher lediglich Fragen architektonischer Natur. Es handlet sich dabei um eine Beschreibung des Aufbaus des Lego Roboters.

Zuletzt genannter Bereich untergliedert sich erneut in Teilbereiche und befasst sich mit den zentralen Punkten und Problemstellungen bei der Realisierung des geforderten Verhaltens. Es handelt sich hierbei um die Fragestellungen der Datenspeicherung, der Berechnung des kürzesten Wegs, der Datenübertragung und des Abfahrens des kürzesten Wegs.

5.1. Roboter

Der Roboter ist eine, auf die Aufgabe zugeschnitene Konstruktion und besteht aus den, im Kapitel 4 Grundlagen beschriebenen Bauteilen. Der RCX ist auf einer Platte befestigt, an deren Seiten die zur Fortbewegung benötigten Kettenkonstruktionen angebracht sind. Die Power-Motoren liegen hinter dem RCX und treiben die Räder der Ketten am Heck des Roboters an. Sie sind an die Ausgänge A und C des RCX angeschlossen. Die folgenden Abbildungen zeigen den Roboter in schräger Ansicht von Vorne und Hinten, respektive in Top- und Frontansicht.

Sensoren

Die Lichtsensoren 1,2 (Abbildung: Sensoren) befinden sich an der Front des Roboters. Sie zeigen direkt auf den Boden. Sensor 3 ist ein Touchsensor. Dieser Sensor wird beim Senden und Empfangen von Daten benötigt (Kapitel: Datenübertragung).

5.2. Wegerkennung

Kreuzungsarten und Fahrbahnmarkierungen

Die Fahrbahn, bzw. der Weg des Labyrinths wird durch einen einfachen weißen Klebestreifen dargestellt. Der Streifen repräsentiert die Mitte des Weges. Zusätzlich werden noch Kreuzungen, Sackgassen und das Ziel mit Hilfe weiterer Farben dargestellt.

Die folgenden Formen können im Labyrinth vorkommen:

(a) Ziel des Labyrinths: Grüne Streifen repräsentieren das Ende des Labyrinths. Hier stoppt der Roboter. (b) Sackgasse: Ein einfacher schwarzer Streifen stellt eine Sackgasse dar. Der Roboter dreht an dieser Stelle um. (c) 2-Wege Kreuzung(Abzweigung): Die fehlenden Wege der Kreuzung werden mit schwarzen Streifen gekennzeichnet. (d) 3-Wege Kreuzung: Der fehlende Weg der Kreuzung wird mit einem schwarzen Streifen gekennzeichnet. (e) 4-Wege Kreuzung: Alle Abzweigungen besitzen einen weißen Klebestreifen.

Der Roboter muss das gesamte Labyrinth bis zum Ziel abfahren, um den kürzesten Weg zu berechnen. Bei der 1. Abfahrt des Labyrinths wird jeder Weg abgefahren. Der Roboter biegt an den Kreuzungen immer rechts ab. Somit fährt der Roboter systematisch das gesamte Labyrinth ab. An Sackgassen dreht er einfach um. Am Ziel hält der Roboter an und beendet das Abfahren.

Abscannen des Wegs

Der Roboter besitzt 2 Lichtsensoren. Die Sensoren zeigen direkt auf den Boden. Sie sind am der Front des Roboters angebracht (siehe Abbildung: xyz). Ein Klebestreifen ist ungefähr 1,5cm breit. Der Abstand zwischen den Lichtsensoren beträgt ungefähr 3cm. Dieser Abstand muss größer als die Breite der Klebestreifen sein, damit auf einer geraden Strecke immer nur ein Sensor den weißen Klebestreifen erkennt. Während der Abfahrt des Labyrinths können die folgenden Sensorpositionen auftreten, die erkannt und verarbeitet werden.

"Geradeaus"-fahren (a)

Beim Abfahren eines geraden Stückes soll der linke Sensor immer einen weißen Klebestreifen erkennen (a). Der rechte Sensor nur den Untergrund. Dies ist der optimale Zustand beim Abfahren eines geraden Stückes. Da der Roboter nicht genau geradeaus fährt oder durch einen nicht geraden Streifen bedingt kommt es unter Umständen zum Abdriften des Roboters vom Fahrtweg. Das heißt der Roboter kommt vom Weg ab und der linke Sensor erkennt keinen weißen Streifen mehr. Dann kann es zu einem der beiden folgenden Zustände kommen. 1. Der Roboter ist nach Rechts abgedriftet. Beide Sensoren erkennen keinen Klebestreifen, nur den Untergrund (b). Dann stoppt der Roboter und dreht nach Links bis der linke Sensor wieder einen weißen Klebestreifen erkennt. 2. Der Roboter driftet nach Links ab. Beide Sensoren erkennen keinen Klebestreifen mehr (c). Nach Position (b) stoppt der Roboter und dreht nach Links. Nun erkennt der linke Sensor keinen Klebestreifen, dafür aber der rechte Sensor. Der Roboter dreht sich um einen gewissen Grad nach rechts bis er Position (a) erreicht hat.

''Abzweigung(weißer Klebestreifen)''-erkennen

Sobald der Roboter auf eine Kreuzung mit einem Abzweigung nach rechts trifft, erkennen beide Sensoren einen weißen Klebestreifen (d). Der Abstand zwischen den Sensor ist größer als die Breite der Streifen. Somit kann die Position (d) nur bei einer Kreuzung erkannt werden. Hat der Roboter eine Abzweigung erkannt, so fährt er bis in die Mitte der Kreuzung und dreht 90 Grad nach Rechts. Danach fährt er wieder geradeaus.

''Tote Abzweigungen(schwarze Klebestreifen)''-erkennen (f)

Erkennt der rechte Sensor einen schwarzen Klebestreifen, so weiß der Roboter, das er eine tote Abzweigung erkannt hat. Nun könnte er die Information speichern und geradeaus weiterfahren. Er muss jedoch zwischen den beiden Möglichkeiten unterscheiden: 1. Der Roboter ist auf eine Abzweigung nach links getroffen, d.h. geradeaus ist eine weitere schwarze Abzweigung. Er Roboter fährt also nach vorne und überprüft, ob er eine weitere schwarze Markierung findet. 2. Der Roboter findet einen weißen Klebestreifen. Er ist also auf eine 3er-Kreuzung getroffen und muss geradeaus weiterfahren.

''Sackgasse''-erkennen (e)

Bei einer Sackgasse scannt der linke Sensor einen schwarzen Klebestreifen und der rechte Sensor nur den Untergrund (e). Diese Position kommt nur bei einer Sackgasse entstehen. Der Roboter kann also stoppen, die Information speichern und eine 180 Grad Drehung vollführen. Danach kann er seinen Weg fortsetzen.

''Ziel''-erkennen (f)

Das Ziel ist durch einen breiten grünen Klebestreifen gekennzeichnet. Beide Sensoren erkennen einen grünen Klebestreifen (f). Diese Position existiert nur am Ziel. Der Roboter ist am Ziel.

5.3. Datenspeicherung

Eine Kreuzung besitzt max. 4 Wege, d.h. 4 mögliche Richtungen. Die Weginformationen bestehen aus den Abzweigungsinformationen der einzelnen Kreuzungen. Der Richtung aus der der Roboter als erstes kam wird nicht im Stack festgehalten. Fährt der Roboter alle möglichen Abzweigungen einer Kreuzung ab und findet kein Ziel, so gehört die Kreuzung nicht zum Weg zum Ziel und kann aus dem Stack gelöscht werden. Somit kann der gesamte Weg in einem Stack mit 2bit Integerzahlen gespeichert werden.

• 1 = rechts
• 2 = geradeaus
• 3 = links

Dieser Integerwert wird in einem Stack gespeichert. Der Stack wurde von einer weiteren Gruppe implementiert. Die Implementation besteht aus einem Array und zugehöriger Funktionen. Die Daten des Stacks werden also in einem Array gespeichert. Das Verhalten eines Stacks beschreiben die Funktionen: pop, push, clean.

5.4. Berechnung des kürzesten Wegs

Der Roboter fährt an Abzweigungen immer rechts herum, soweit möglich. Nach dem Abfahren muss der kürzeste Weg berechnet werden. Die angetroffenen Kreuzungen werden in einen Stack eingefügt und beim wiederholten Abfahren erweitert. Wurde die Kreuzung 4. mal gescannt, so ist die Kreuzung für den kürzesten Weg ohne Belang und kann aus dem Stack gelöscht werden. Am Ende sind alle unnötigen Kreuzungen entfernt und der kürzeste Weg steht im Stack. Folgendes Beispiel verdeutlicht den Sachverhalt. Der Roboter findet eine neue Kreuzung und trägt einen neuen Wert in den Stack (1 = rechts). Danach fährt er nach rechts. Findet er nun als nächstes wieder eine Kreuzung, so fügt er wieder einen neuen Wert in den Stack. Findet er jedoch eine Sackgasse, so dreht er rum, speichert die Information eine Sackgasse gefunden zu haben und fährt zurück. Nun trifft er wieder auf die 1. Kreuzung. Er weiß, dass er diese Kreuzung schon besucht hat und erhöht den obersten Wert des Stacks auf 2 (= geradeaus) und fährt nach rechts. Wiederholt sich dieser Vorgang weitere 2 mal, so wird das oberste Element auf 3(= links) erhöht und dann aus dem Stack gelöscht. Keine Abzweigung der Kreuzung führt zum Ziel. Sie kann also aus dem Stack gelöscht werden.

5.5. Datenübertragung

Nachdem der Roboter das Labyrinth abgefahren hat und den kürzesten Weg berechnet hat, überträgt er diesen Weg an einen anderen Roboter. Die Übertragung des Stacks findet in einem weiteren Modul statt. Das Modul pathsend.nqh wurde von einer anderen Gruppe implementiert. Die dazugehörigen Funktionen sind receive und send. Bevor der Roboter den Stack senden kann, muss der andere Roboter bereit sein den Stack zu empfangen. Dazu wird die Funktion: receive gestartet. Nun kann der erste Roboter den Weg übertragen. Drückt man Knopf 3 (Abbildung 8: Sensoren) beginnt der 1. Roboter denn Weg zu senden. Hat der 2. Roboter den Weg empfangen ertöhnt ein Bestätigungston. Die Roboter beenden das Senden und Empfangen.

5.6. Abfahren des kürzesten Wegs

Nachdem der Weg übertragen wurde, wird der Roboter an den Anfangspunkt gesetzt und mit dem Knopf 3 (Abbildung 8: Sensoren) gestartet. Der Roboter fährt nun den kürzesten Weg ab. Findet er eine Abzweigung, so nimmt er das unterste Element vom Stack und fährt in die gewünschte Richtung (siehe Datenspeicherung).

6. Implementierung

Das folgende Kapitel soll die Seite der Implementierung der im Lösungskapitel vorgestellten theoretischen Lösungen erläutern. Die Teilbereiche entsprechen denen des vorangegangenen Kapitels: Wegerkennung, Datenspeicherung, Berechnung des kürzesten Wegs, Datenübertragung, Abfahren des kürzesten Wegs. Darüber hinaus soll in einem weiteren Bereich, in der Realisierung aufgetretene Probleme, nämlich Schwächen des NQC/Lego Mindstorms Firmware-Systems vor allem im Aspekt Performance, vorgestellt und erläutert werden. Eine mögliche Lösung dazu bietet das C/brickOS-System, welches ebenfalls in diesem Bereich vorgestellt wird.

6.1. Wegerkennung mit Farbwerten

Der Lichtsensor erkennt verschiedene Farben und Oberflächenstrukturen. Im Standard-Modus(SENSOR_MODE_PERCENT) werden die Werte als Prozentwerte, d.h. von 0 bis 100 ausgegeben. Im Raw-Modus(SENSOR_MODE_RAW) werden die Daten ohne diese Umrechnung ausgegeben. Der Raw-Wertebereich ist größer und somit sind die Werte bei Raw-Modus auch differenzierter. Ein einfaches Programm soll die verschiedenen Sensorwerte scannen und speichern, um so herauszufinden, welche Farben sich als am vorteilhaftesten zur Lösung der Aufgabenstellung erweisen. Der Roboter soll ein gewisses Stück geradeaus fahren und in regelmäßigen Abständen den Grund scannen und den Sensorwert in ein Datalog speichern.

NQC-Code für datalogging

Algorithmus (Datalogging)

  			 task datalogging() {  	CreateDatalog(400);  	int i = 0;  	for (i = 0; i <= 400; i++) {  		AddToDatalog(SENSOR_1);  	} 	PlaySound(SOUND_DOWN);  } 		

Das Datagramm kann später ausgelesen und in einem Diagramm dargestellt werden (siehe Abbildungen 11 + 12) Die Klebestreifen werden nebeneinander aufgeklebt. Der Roboter fährt über die Streifen und scannt ihre Farbe und Beschaffenheit.

Auf Grund der beiden Diagramme erscheinen die folgenden Farben als beste Wahl: Weiß, Schwarz und Grün. Diese Klebestreifen bieten die besten Vorrausstzungen, d.h. sie können am besten von den anderen Farben unterschieden werden. Alle Elemente des Labyrinths können durch 3 Farben erstellt werden.

Um vernünftige Sensordaten zu bekommen, müssen zuvor die beiden folgenden Fragen geklärt werden: Wie wirken sich unterschiedliche Lichtverhältnisse auf Sensordaten aus? Und unterscheiden sich die einzelnen Sensoren voneinander?

Mehrere Tests mit unterschiedlichen Lichtsensoren und mit unterschiedlichen Lichtverhältnissen ergeben die folgende Tabelle. Die Sensordaten sind Standard-Daten (SENSOR_MODE_PERCENT).

Tabelle (Lichtsensordaten)

Sensordaten bei unterschiedlichen Sensoren und Lichtverhältnissen

Farbe	S1	S2	S2 + Licht	S1 + Licht	S1 + gr. Abstand
Untergrund	48,5	52	70,5	71	46
Blau	47,5	49,5	69,5	70,5	44,5
Schwarz	39 & 40,5	54	54,5	36,5
Grün	42,5	44,5	64	64,5 & 41
Gelb	55	56,5	76	76	51
Rot	53	54,5	73 & 72	48
Weiß	56	58,5	77	76	54

Man erkennt sehr deutlich, dass die Sensoren unterschiedliche Ergebnisse liefern. Die Sensoren sind nicht gleich und liefern auch keine gleichen Ergebnisse bei gleichem Untergrund. Die äusseren Lichtverhältnisse beeinflussen die Scanwerte. Je höher die äussere Lichteinstrahlung, desto höher sind die Sensordaten. Die Sensoren sollten also abgeschirmt werden um immer die gleichen Ergebnisse zu bekommen. Zusätzlich muss jeder Sensor speziell kalibriert werden.

Abscannen des Wegs

Im Laufe des Labyrinth-Abfahrens scannt der Roboter mit seinen Lichtsensoren verschiedene Klebesteifen und Untergründe. Fährt der Roboter auf einem geraden Wegstück entlang, so erkennt der linke Sensor einen weißen Klebestreifen und der rechte Sensor den Boden. D.h. er fährt geradeaus weiter, wenn linker Sensor = ''weiß'' und rechter Sensor = ''Untergrund''. Die folgende Tabelle zeigt alle möglichen Sensorbelegungen und welche Aktion bzw. Funktionen gestartet werden.

Aktionen, nach bestimmten Sensordaten

Tabelle (Aktionen)

linker Sensor	rechter Sensor	Aktion, Funktion
Untergrund	Untergrund	Dreht sich nach Links
Untergrund	weiß	Dreht sich 25 Grad nach Rechts
weiß	Untergrund	Fährt geradeaus
weiß	weiß	Erkennt Kreuzung
schwarz	X(=egal)	Erkennt Sackgasse
X(=egal)	schwarz	Erkennt tote Abzweigung
grün	grün	Erkennt Ende

Diese Aktionen mussten in der Implementierung berücksichtigt werden. In der Funktion: refreshColors wird die Farbe des Untergrundes bestimmt. In einer Endlosschleife überprüft der Roboter den Untergrund, wertet die Untergrundfarbe aus und speichert die Farbinformationen in die beiden Integer-Variablen: colorLeft, colorRight refreshColors(). Die beiden Variablen bekommen einen Integerwert zugewiesen(0 = Untergrund, 1 = weiß, 2 = schwarz, 3 = grün). Anschließend wird die Kombination der Farbwerte überprüft und die entsprechende Funktion gestartet.

Algorithmus (Abscannen des Weges)

  			 task main() {  	...  		 	refreshColors();   	if ((colorLeft == 0) && (colorRight == 0)) {  		turn_left(0);  	} 	if ((colorLeft == 0) && (colorRight == 1)) {  		turn_right(50); 	}  	if ((colorLeft == 1) && (colorRight == 1)) {  		//Kreuzung gefunden  		foundX();  	}  	if ((colorLeft == 1) && (colorRight == 0)) {  		drive_forward(0);  	}  	if (colorLeft == 2) {  		//Sackgasse gefunden  		foundDeadEnd();  	}  	if (colorRight == 2) {  		//Tote Abzweigung gefunden  		checkBlackRight();  	}  	if ((colorLeft == 3) && (colorRight == 3)) {  		//Ziel gefunden  		exit();  	}  	 	...  } 		

6.2. Datenspeicherung

Um die Wegdaten speichern zu können, wird eine Datenstruktur benötigt. Die Lego Firmware in der Version 1.x bietet dazu keine adäquate Lösung, da lediglich Integer-Variablen benutzt werden können. Die Nachfolger-Version 2.0 bietet zusätzlich die Möglichkeit zur Verwendung von Arrays. Über die Verwendung von Arrays lässt sich ein Stack nachbilden, der ein geeignetes Mittel zur Speicherung von Wegen darstellt.

Ein neuer Stack wird folgendermaßen angelegt:

  			 path_clear(); 		

Nun können verschiedene Zahlen auf den Stack gelegt werden:

  			 path_push(1);  path_push(2);  path_push(3); 		

Und anschliessend wieder herausgelesen werden.

  			 int value;  path_pop(value); 		

6.3. Berechnung des kürzesten Weg

Findet der Roboter eine Kreuzung, eine Sackgasse oder eine tote Abzweigung, so wird die Funktion: checkRoute gestartet. Diese Funktion repräsentiert die Berechnung des kürzesten Wegs. Neue Kreuzungen werden in den Stack gespeichert, gefundene Kreuzungen werden verändert oder wieder aus dem Stack gelöscht. Als Parameter: status wird die Art des gefundenen Wegstücks folgendermaßen angegeben (1 = Kreuzung, 2 = tote Abzweigung, 3 = Sackgasse).

Wurde eine Kreuzung gefunden muss der Algorithmus unterscheiden, ob der Roboter eine neue oder eine bereits abgefahrene Kreuzung gefunden hat. Die Variable onback ist ein 0-1 Integerwert. Wird als nächstes eine neue Kreuzung gefunden, so ist onback = 0, Ist onback = 1 befindet sich der Roboter auf dem Rückweg zu einer Kreuzung. Das heißt die nächste Kreuzung, auf die der Roboter trifft, wurde bereits erkannt. Das oberste Element wird aus dem Stack gelesen. Ist der Wert <3 wird er erhöht und wieder in den Stack eingefügt. Ist der Wert = 3, d.h. der Roboter hat schon alle 4 Richtungen der Kreuzung untersucht, so kann die Kreuzung gelöscht werden, der Wert wird nicht mehr in den Stack eingefügt. Die Variable onback bekommt den Wert 1, falls der Roboter sich auf dem Rückweg befindet, d.h. wenn er eine Sackgasse oder eine tote Abzweigung gefunden hat. Eine tote Abzweigung kann als einfache Abzweigung mit anschließender Sackgasse interpretiert werden. Der status == 2 (tote Abzweigung gefunden) wird zu status = 1 und onback bekommt den Wert 1.

Algorithmus (Berechnung des kürzesten Weg)

  			 int onback = 0;  void checkRoute(int status){ 	//status = 1 wenn Kreuzung gefunden 	//status = 2 wenn tote Abzweigung gefunden 	//status = 3 wenn Sackgasse gefunden   	//status == 2, wenn eine schwarzer Kreuzungsstreifen gefunden wurde 	if (status == 2){ 		onback = 1; 		status = 1; 	}   	//status == 3, wenn Sackgasse gefunden wurde 	if (status == 3){ 		onback = 1; 	}   	//status == 1, wenn Kreuzung gefunden wurde 	if (status == 1){   		//onback = true, wenn Robot auf dem Rückweg ist 		if (onback == 1){ 			onback = 0; 			increaseStack(); 		}else{ 			SetUserDisplay(1 , 2); 			path_push(1); 		} 	} } 		

6.4. Datenübertragung

Nachdem der Roboter am Ziel angekommen ist und den kürzesten Weg berechnet hat, der Weg an einen anderen Roboter gesendet werden. Sobald Sensor 3 gedrückt wird versendet der Roboter den gesamten Weg (path send()).

Algorithmus (Senden)

  			 while (true) {  	if (SENSOR_3 == 1){  		path_send();  		if (comm_error == 0)  			PlaySound(SOUND_UP);  		else 			PlaySound(SOUND_DOWN);  	}  } 		

Soll der Roboter den kürzesten Weg abfahren, so muss er zuvor erst einmal den Weg empfangen. Wird das ''Driver''-Programm gestartet, so wartet der Roboter bis er einen Weg gesendet bekommt. Bis dahin ist sein Status = ''Receive''.

Algorithmus (Empfangen)

  			 do {  	path_receive();  	AddToDatalog(comm_error);  	PlaySound(SOUND_CLICK);  } while (comm_error != 0); 		

Nachdem der Weg in Form eines Stacks empfangen wurde ertönt ein Bestätigungston. Nun wartet der Roboter bis Sensor 3 gedrückt wird. Danach startet er das Abfahren des Labyrinths.

6.5. Abfahren des kürzesten Wegs

Beim Abfahren des kürzesten Weg wird wie schon beim Abfahren des Labyrinths in einer Endlosschleife die Lichtsensorwerte des Untergrunds bestimmt (refreshColors()) und anschliessend eine entsprechende Aktion ausgeführt. Findet der Roboter eine Kreuzung, so liest er die Weginformation vom Stack und fährt in die entsprechende Richtung driveNextStackValue().

Algorithmus (Abfahren des kürzesten Weg)

  				 ... refreshColors();   if ((colorLeft == 1) && (colorRight == 0)) { 	drive_forward(0); } if ((colorLeft == 0) && (colorRight == 0)) { 	turn_left(0); } if ((colorLeft == 0) && (colorRight == 1)) { 	turn_right(50); } if ((colorLeft == 1) && (colorRight == 1)) { 	driveNextStackValue(); } if ((colorLeft == 1) && (colorRight == 2)) { 	driveNextStackValue(); } ... 		

6.6. C/brickOS und NQC/Lego Firmware

Die Not Quite C Programmiersprache in Zusammenhang mit der Lego Firmware besitzt einige gravierende Schwächen, vor allem im Bereich Performance. Durchgeführte Messungen ergaben dass die Abtastgeschwindigkeit der Lichtsensorwerte bei etwa 0,1 Sekunden liegt. Diese Werte sind zu groß um die Farbe des Bodens vernünftig zu berechnen. Die Geschwindigkeit des Roboters und die Abtastgeschwindigkeit lassen keine bessere Berechnung, wie zum Beispiel eine Mittelwertberechnung zu. Somit kann man nur mit einzelnen, möglicherweise recht ungenauen Werten rechnen, welche nicht exakt genug für eine perfekte Wegeberechnung sein können. Eine mögliche Lösung dieses Problems bietet das alternative Betriebssystem brickOS.

Die folgenden Abbildungen zeigen Benchmark-Ergbnisse, bei denen jeweils der gleiche Test auf einem RCX mit NQC und Lego Firmware und auf einem RCX mit brickOS mit C durchgeführt wurde. Dabei stellt sich klar der Performancevorteil von brickOS heraus. Die Unterschiede in der Bearbeitungszeit der Aufgaben sind derart groß, dass sich die Ergebnisse nicht in einem Diagramm darstellen lassen.

Test ohne eine Testfunktion

Tabelle (Test: Ohne Test-Funktion)

Test-Funktion	Anzahl	NQC(sec)	brickOS(sec)
-	1000	5,9	0,012
	2000	11,8	0,024

Tabelle (Test: Arithmetische Operationen)

Test-Funktion	Anzahl	NQC(sec)	brickOS(sec)
z=x+y	1000	11,6	0,024
z=x*y	1000	11,6	0,046
z=x/y	1000	11,6	0,069
z=((x+y)*y)/x	1000	17,5	0,102
z=x+y*y/x	1000	20,4	0,102

Tests mit einer arithmetischen Operationen mit unterschiedlichen Wiederholungen

Tabelle (Test: Arithmetische Operation mit mehr Wiederholungen)

Test-Funktion	Anzahl	NQC(sec)	brickOS(sec)
z=x+y	1000	11,6	0,024
z=x+y	2000	23,1	0,048
z=x+y	4000	46,3	0,094
z=x+y	8000	92,4	0,189

Test mit Verzeigung(if-Anweisung)

Tabelle (Test: if - Operationen)

Test-Funktion	Anzahl	NQC(sec)	brickOS(sec)
if (x>1);	1000	8,8	0,013
if (x==1);	1000	8,8	0,013
if (x==1){ z=x+y };	1000	14,5	0,03
if (x==1){ z=x+y } else { z=x-y };	1000	17,2	0,032
if (x==1){ z=x+y }; if (x!=1){ z=x-y };	1000	17,5	0,033

Test mit meheren Funktionen

Tabelle (Test: Funktionsaufrufe)

Test-Funktion	Anzahl	NQC(sec)	brickOS(sec)
callFunction(); void callFunction(){ z=x+y };	1000	11,6	0,031
callFunction1(); void callFunction1(){ callFunction2 }; ... void callFunction3(){ z=x+y };	1000	11,6	0,047
callFunction1(); void callFunction1(){ callFunction2 }; ... void callFunction7(){ z=x+y };	1000	11,6	0,075

7. Ergebnis

Das brickOS/C System ist in allen getesteten Bereichen um ein Vielfaches schneller. Nachteilig ist allerdings der erhöhte Komplexitätsgrad bei der Installation und Konfiguration zu erwähnen, bis man das System problemlos nutzen kann. Darüber hinaus müssen bei dem brickOS System Abstriche in der Bedienbarkeit in Kauf genommen werden. Die NQC API-Referenz lässt sich als eindeutig benutzerfreundlicher einstufen als die des brickOS Systems. Die bessere Bedienbarkeit liegt aber vor allem auch in der höheren Popularität und somit in dem besseren Angebot an Beispielen und Hilfen im Imternet begründet. Damit muss die Wahl des Betriebsystems für den RCX anhand der Intentionen und der Prioritäten des Nutzers getroffen werden. Kurz zusammengefasst ergibt sich folgende Tablle mit Vor- und Nachteilen.

Gesamteindruck NQC und brickOS

Tabelle (Gesamteindruck)

Bereich	NQC	brickOS
Installation	++	- -
Bedienbarkeit	+	-
Performance	- -	++

Zusammenfassung

Im Zuge dieser Arbeit wurde eine mögliche Lösung des vorgestellten Problems erläutert. Der Roboter hat die Fähigkeit einen Weg zum Ziel eines Labyrinths zu finden und daraus den kürzesten Weg zu berechnen. Dieser kann dann zu einem anderen Roboter übertragen werden oder aber ein bereits berechneter Weg empfangen, gespeichert und abgefahren werden.

Zunächst wurde der Roboter an sich, also die Konstruktion die die Grundlage der Lösung bildet vorgestellt. Die darauf folgenden Erläuterungen beziehen sich auf die Entwicklung von Algorithmen und deren Umsetzung, die es ermöglichen den Roboter entsprechend der Aufgabenstellung zu programmieren.

Als ersten Teilbereich ist hierbei die Wegerkennung zu nennen. Darunter fallen Untersuchungen der möglichen Kruzungsarten, die Möglichkeiten der Fahrbahnmarkierungen und die dafür zu wählenden Farben und die Fähigkeit des Roboters mittles Lichtsensoren die Fahrbahnmarkierungen als solche zu erkennen. Als Fahrbahnmarkierung wurde die Farbe Weiß, als Markierung der Sackgassen die Farbe Schwarz und als Zielmarkierung Grün gewählt, da diese laut Messungen am besten durch die Lichsensoren unterscheidbar sind. Kreuzungen bestehen immer aus vier Klebestreifen, wobei nicht befahbahre Abzweigungen mit der Farbe für Sackgassen gekennzeichnet sind. Darüber hinaus wurde in diesem Bereich ebenfalls erläutert wie sich der Roboter während der Fahrt durch das Labyrinth verhält, genauer gesagt wie es dem Roboter möglich ist der Fahrbahn zu folgen und an Kreuzungen richtig zu reagieren.

Der zweite Teilbereich befasst sich mit den Möglichkeiten der Datenspeicherung, also um die Speicherung von Wegdaten um den kürzesten Weg berechnen zu können. Wegdaten werden immer über Kreuzungen gespeichert, das heißt der Roboter speichert an welcher Kreuzung er in welche Richtig gefahren ist. Informationen über Weglängen sind nicht vorhanden. Die Wegdaten werden in einem Stack abgelegt.

Der dritte Bereich behandelt die Berechnung des kürzesten Wegs zum Ziel des Labyrinths. Dies wird erreicht, indem der Roboter an jeder Kreuzung nach rechts abbiegt, sofern dies möglich ist. Der Wert der Kreuzung wird dabei von null immer um eins erhöht und, erreicht er vier, wird diese Kreuzung aus dem Speicher gelöscht, da sie dann für den kürzeseten Weg irrelevant ist. Folgend wurde die Datenübertragung, das heißt die Übertragung von Wegdaten von einem Roboter zum anderen vorgestellt. Dazu wurde ein dediziertes Protokoll verwendet welches es erlaubt, die Daten in Form des Stacks mittels Infrarot zu übertragen.

Im letzten Bereich wurde erläutert wie der Roboter einen empfangenen oder berechneten Weg abfahren kann. Dafür werden die Kreuzungswerte nacheinander von unten aus dem Stack genommen und der Roboter biegt in die entsprechende Richtung ab.

Zusätzlich dazu wurden Schwächen des NQC/Lego Mindstorms Systems im Bereich Performance aufgezeigt und über Messungen belegt. Vergleichmessungen des brickOS/C Systems zeigen, dass dieses System die Schwächen überwindet und als echte alternative Entwicklungs- und Einsatzumgebung gesehen werden kann.

Literaturverzeichnis

Webseite	www.wikipedia.de
Webseite	NQC Guide
Webseite	Lego Mindstorms
Webseite	Facharbeit der Uni Paderborn: Lego Mindstorms
Webseite	Java Magazin:Java goes to space
Webseite	BrickOS at SourceForge
TechReport	Anthony Hirst and Jeffrey Johnson and Marian Petre and Blaine A. Price and Mike Richards , What is the Best Environment-Language for Teaching Robotics Using Lego MindStorms?
Webseite	pbForth Weblog Home

Special thanks to

Dominik Rost