Die Situation ist so, dass der Roboter theoretisch irgendwo in einem beliebigen Labyrinth positioniert ist. Da wir mit der Helligkeit arbeiten, ist das Labyrinth der Einfachheit halber lediglich schwarz/weiß, wobei darauf geachtet werden muss, dass es sich eher um ein weiß-auf-schwarz-Labyrinth handelt, als schwarz auf weiß, da das Erbenis sonst eventuell verfälscht werden könnte, wenn die Kamera nicht präzise ausgerichtet ist. Desweiteren sollte die Kamera mit der kleinstmöglichsten Bildgröße arbeiten, da die Pixelanzahl entscheidend für die Zeit der Berechnung ist.

Der Programmcode aktiviert die Kamera und arbeitet dann mit einem aufgenommenen Bild weiter. Dieses wird zunächst in ein Array umgewandelt, wo jeder Pixel einen entsprechenden Wert bekommt, nachdem das Bild nach Helligkeit ausgewertet wurde, sprich in hell und dunkel geteilt ist. Während die dunklen Flächen die Hindernisse markieren, stellen die hellen Stellen die vom Roboter befahrbaren Wege dar. Für diese wird dann jedem Pixel mithilfe eines Floodfill-Prinzips ein Wert zugewiesen, welcher die Distanz zum Ziel repräsentiert. Vom Startpunkt aus wird dann nachfolgend immer geprüft, in welche Richtung (oben, unten, links oder rechts) der Weg zum Ziel am kürzesten ist. Diese Informationen werden dann als Geh- und Dreh-Befehle an den Roboter gesendet. Damit sollte dieser in der Lage sein, den Ausweg aus dem Labyrinth zu finden.

Klicken für die Darstellung der gif-Datei.

Unser Projekt wurde in zwei Gruppen gesplittet, wobei die Projektgruppe A_Maze_Sing den mechanischen Teil übenahm, und den Roboter baute, der dann von uns mitbenutzt werden konnte. Das bedeutet, dass unsere Aufgabe den Fokus auf der Programmierung der benötigten Eigenschaften lag.
Beispielsweise die Kommunikation zwischen den Geräten, sprich die Kamera aktivieren, Befehle vom PC an den Roboter senden und umgekehrt, ein Bild aufnehmen, umwandeln und daraus den Weg berechnen, wofür zuvor die Distanz ermittelt werden muss.

Unser Projekt funktioniert nur, wenn sich dass aufgenommene Bild deutlich in hell und dunkel teilen lässt; den Fall, dass die Hindernisse hell sind haben wir bewusst vorerst nicht berücksichtigt, um uns auf die grundsätze Idee zu konzentrieren. Ebenso wird nur der Fall bedacht, dass sich nach dem Aufnehmen des Bildes nichts im Labyrinth ändert, da nur ein Bild gemacht wird, und nicht etwa in regelmäßigen Zeitabständen, um den Weg gegebenenfalls zu korrigieren.

Da wir, wie zuvor beschrieben, mit einem Bild arbeiten wollen, wurde uns geraten mit Processing zu arbeiten - eine Entwicklungumgebung, spezialisiert auf Animation, Grafik und Simulation. Dadurch waren für so ziemlich alle unsere Probleme bereits passende Libraries und typisierte Befehle und Methoden verfügbar.

Aufgrund der Tatsache, dass Processing eine java-basierte Programmiergsprache ist, konnten wir für die wenigen speziellen Javaskills (z.B. Verwendung von Listen) die benötigeten Bibliotheken problemlos nachladen.

Beispiel-Kamerabild
(Wege aus weißem Papier auf dunklem Teppichboden)

Um diese Aufgaben zu lösen, haben wir mit der Capture-Klasse gearbeitet, wofür zuvor processing.video.* importiert werden muss. Es wird dann eine Variable angelegt, welche die Höhe und die Breite des aufgenommenen Bildes speichert. Mittels verschiedener Methoden können wir mit der Kamera kommunizieren, z.B. sie starten, sodass sie filmt, prüfen, ob ein Bild vorhanden ist, und ein Bild aufnehmen (sozusagen ein Standbild des seit dem Start gedrehtem Video). Mit einem solchen Bild, dessen Informationen in der oben bereits erwähnten Variablen gespeichert sind, kann man dann arbeiten.

Wir hatten die Idee, einen 2-dimensionalen Array zu erstellen, dessen einzelnen Stellen den jeweiligen Pixeln des Bildes entsprechen. In diesem Array geben wir jedem Pixel eine bestimmte Information, einen Wert, in unserem Fall eine ganzahlige Zahl. Durch Nutzung der bereits vorhandenen Methode brightness() bekommen wir für die einzelnen Bildpixel Helligkeitswerte geliefert, und anhand eines im Vorfeld von uns festgelegten Grenzwerts wird geprüft, ob die Stelle hell oder dunkel ist (also befahrbar oder nicht). Dieser Information haben wir die Werte 0 und -1 zugewiesen, das bedeutet, dass wenn wir den Array ausgeben lassen würde, wären die Farben (schwarz/weiß) durch Zahlen (-1/0) dargestellt. Die beiden Abbildungen verdeutlichen dies.

Die Methode, die den Weg berechnet, funktioniert eigentlich ganz einfach. Im Prinzip wird an der aktuellen Position geschaut, welcher der umliegenden Pixel den geringsten Abstand zu den Zielkoordinaten hat. Damit diese Information geprüft werden kann müssen den Pixeln erst einmal ein Abstandwert zugewiesen werden [im folgenden Abschnitt]. Der ermittelte Weg wird dann nach und nach dem Roboter geschickt (siehe Datenübertragung).

Wir wissen ja bereits, an welcher (x/y-)Position der Weg für den Roboter befahrbar ist (der Array hat an jener Stelle den Wert Null). Im Hinblick auf das Ziel, den kürzesten Weg zum Ziel zu finden, wollen wir nun jedem Pixel einen Wert zuweisen, welcher die Information enthält, wie viele Pixel es von dieser Position aus noch bis zum Ziel sind.

Abbildung 1 Floodfill-Prinzip
(Klicken: gif-Datei)

Dafür bedienen wir uns am Floodfill-Prinzip.
Bei der ganz normalen Floodfill-Funktion besteht das Ziel darin, alle Kästchen einer Farbe in eine andere Farbe zu färben. Auf unser Problem angewendet, heißt dies, jedem Pixel statt einer anderen Farbe einen Distanzwert zu geben. Wenn die Distanz aber lediglich um eins erhöht wird, kommen wir zu einem falschen Ergebnis (siehe Abbildung 1). Angenommen das Kästchen mit der 1 ist das Ziel, dann wäre das Kästchen rechts daneben ein Kästchen entfernt, müsste also den Wert 2 haben. Dem ist aber nicht so, da bei dieser Variante ein Pixel nach dem anderen betrachtet wird, was beim Farb-Beispiel kein Problem ist, jedoch das Ergebnis stark verändert sobald man mit konkreten Werten arbeitet.

Abbildung 2
Baumdiagramm

Daher die Idee, gleichzeitig alle Richtungen (oben, unten, links, rechts) zu prüfen, vergleichbar mit der Struktur eines Baumdiagramms (siehe Abb. 2). Sofern es sich bei der geprüften Richtung nicht um einen als dunkel abgespeicherten Pixel handelt, wird dann bei jeder Verzweigung die Distanz um eins erhöht. Diese Abwandlung ist in Abbildung 3 dargestellt.

Abbildung 3
Floodfill in alle Richtungen

Da selbst ein recht kleines Bild in der Summe trotzdem noch sehr viele Pixel hat, welche zudem auch noch alle mehrfach geprüft werden (0 oder -1 oder bereits eine zugewiesene Distanz ? ), erfordert diese Methode eine enorme Rechenleistung (und Zeit), sodass unser Programm sich des Öfteren auch mal aufgehangen hat bzw. abgestürzt ist. Besonders am Anfang, als wir versucht haben den Code mit einer rekusiven Funktion zu realisieren. Um dieses Problem zu umgehen, haben wir zum einen den Code der Funktion iterativ geschrieben und zum anderen ab dem Punkt an mit einer LinkedList gearbeitet.

Bereits während der Routenberechnung werden dem Roboter Befehle gesendet. Das Programm zählt die Schritte in eine Richtung, z.B. nach oben, und wenn sich die Richtung ändert wird dem Roboter die Summe der Schritte in die jeweilige Richtung geschickt, sowie ein Dreh-Befehl in die neue Richtung. Das ganze erfolgt über OSC, was über WiFi läuft. Durch bestimmte Befehle erstellen wir eine OSC-Nachricht, welche dann an die IP-Adresse des Roboters gesendet wird. Dieser Befehl enthält zwei Zahlen, welche den Steppermotoren des Roboters sagen, wie viele Schritte ausgeführt werden sollen. Damit der Roboter, statt mit Befehlen überflutet zu werden, die Befehle nacheinander ausführt, haben wir auch hier eine LinkedList verwendet, in der wir Objekte einer zuvor dafür erstellten Klasse speichern. Diese Objekte entsprechen an sich dem Befehl der an den Roboter gesendet werden soll, das heißt, ob er fahren oder sich drehen soll (im Gegensatz zum normalen Fahren, drehen sich die Stepper beim Drehen in unterschiedliche Richtungen) und wie viele Steps jeweils. Sobald der Roboter den Befehl, den er bekommen hat, ausgeführt hat, soll er eine OSC-Nachricht an das Programm senden, welches daraufhin das nächste Element aus der Befehlsliste zieht, sprich dem Roboter den nächsten Befehl schickt.

• Logitech-Webcam
• USB-Kabel
• einen PC (mit Processing)
• WiFi
• einen Roboter…

An sich sind wir sehr zufrieden mit dem Stand des Projekts. Unsere TO-DO-Liste wurde eigentlich fast fertig abgearbeitet. Fast, weil wir beispielsweise nicht mehr geschafft haben die Datenübertragung via OSC an dem Roboter zu testen (weshalb der Code evtl. auch noch nicht fehlerfrei kompilierbar ist), da zum einen der Roboter noch nicht ganz fertig ist und zum anderen, weil wir es auch nicht so ganz hinbekommen haben, uns mal alle gemeinsam zu treffen, also beide Gruppen, daher war es etwas schwierig.

Abbildung 4

Ein weiter Punkt den wir theoretisch noch in Angriff nehmen wollten, war die Farberkennung, so dass wir zum Beispiel die Koordinaten des Startpunktes anhand der Stelle ermitteln, wo die Farbe Rot die höchste Intensität hat (roter Punkt auf dem Roboter), gleiches mit einer anderen Farbe zur Zielpunkt-Bestimmung. Und eigentlich wollten wir auch noch geschafft haben, dass der Roboter dann einen Mindestabstand zum Hindernis hält. Denn zur Zeit ist der kürzeste Weg zum Ziel halt meistens direkt an der Mauer lang, wie die Simulation des Fahrwegs unseres Roboters in einem optimierten Labyrinth zeigt (Abbildung 4).

Aber abgesehen von der Praxis läuft unsere Idee. Wir haben uns zwar manchmal ganz schon verzettelt und gefühlt ewig an ein und demselben Problem gesessen ohne voran zu kommen, aber wir haben durchgehalten und nun leztenendes ein unserer Meinung ordentliches Ergebnis zustande gebracht.

Alle oben beschriebenen Aspekte wurden weitesgehend auch so im Code kommentiert, damit unsere Schritte gut verständlich sind.

Unseren Code haben wir in Processing geschrieben, daher ist es notwendig, dieses Programm zu installieren.
Beim Download müssten alle - von uns verwendeten - Libraries mit dabei sein. Ansonsten ganz einfach manuell herunderladen (könnte evtl. bei OSCP5 der Fall sein).

Quellcode zum Projekt:
skycamcode.zip (Stand: 24.02.2016)