Unser fertiger Roboter MazeMate entspricht nicht unserer ursprünglichen Idee. Zu Beginn des Labors wollten wir einen Roboter bauen, der eine Bierflasche aus einem Bierkasten holt und diese öffnet. Leider taten sich während der Weiterentwicklung dieser Idee mehrere Probleme auf. Zum einen wäre es nicht möglich gewesen, die Bierflaschen mit einem Elektromagneten aus dem Kasten zu heben, da die verfügbaren Magneten bei 12V einfach zu schwach dafür sind. Andererseits erwies sich auch das Öffnen der Flaschen als problematisch. Auch hier ist die nötige Kraft zu hoch für unsere Schaltungen. Zu diesem Zeitpunkt hatten wir bereits den Wagen mit dem Elektromagneten gebaut und wollten diesen unbedingt in unserem Roboter verbauen. Also verwarfen wir die Idee mit dem Bierroboter und diskutierten über andere Verwendungen für den Wagen. Schlussendlich entschieden wir uns für einen Roboter, der Labyrinthe lösen kann, und tauften diese Idee MazeMate.

Unser Roboter ist in der Lage Labyrinthe zu lösen. Diese werden auf einem 10×10 Raster durch weiße Unterlegscheiben dargestellt und können beliebig kompliziert sein. Der Roboter nimmt das Labyrinth über eine fest montierte Webcam auf, schneidet das aufgenommene Bild zu und bereitet es für den Lösungsalgorithmus vor. Dieser findet einen Weg durch das Labyrinth, zeichnet ihn auf dem Bildschirm des angeschlossenen Computers ein und schickt die Koordinaten der einzelnen Lösungspunkte an den Arduino. Zum Schluss werden alle weißen Unterlegscheiben auf dem Lösungsweg mithilfe des Elektromagnets auf dem Wagen durch rote ersetzt.

Die Basis des Roboters bildet eine 50x80cm Holzplatte. Darauf ist ein 25 cm breites Quadrat schwarz lackiert. Dieses Quadrat bildet das Spielfeld und ist mit Bleistiftlinien in ein 10×10 Raster unterteilt. Die einzelnen Rasterfelder sind 25mm breit. Darauf wird aus gleichgroßen weißen Unterlegscheiben der „begehbare“ Weg des Labyrinths gelegt. Neben dem Spielfeld befinden sich Stapel mit den restlichen weißen und roten Unterlegscheiben. Letztere sind für den Lösungsweg vorgesehen.

Die Webcam ist mittig über dem Spielfeld in einer Höhe von ca. 50 cm angebracht. Dafür haben wir rechts und links neben dem schwarzen Viereck zwei „Tischbeine“ in die Holzplatte geschraubt. Diese sind oben mit einem Holzbalken verbunden, an dem die Kamera senkrecht nach unten zeigend montiert. Sie ist nicht beweglich, damit das aufgenommene Bild immer den gleichen Ausschnitt des Spielfelds zeigt und somit keine weiteren Anpassungen vor jedem Start vorgenommen werden müssen.

Das Kernstück der Konstruktion ist der Wagen mit dem Elektromagneten. Er besteht aus zwei prinzipiell baugleichen Ebenen. Sie werden durch Stepper-Motoren mit Zahnrädern auf Zahnschienen bewegt. Damit nicht das gesamte Gewicht des Wagens auf den Zahnrädern am Stepper liegt, laufen beide Teile auf jeweils vier Rädern. Um den Wagen geradlinig bewegen zu können, werden die Räder durch kleine Hölzer in der Spur gehalten. Dabei fährt die untere Ebene neben dem Spielfeld auf der Grundplatte und die obere um 90 Grad gedreht auf der unteren. Oben auf dem kleinen Teil des Wagens ist das Steckbrett mit der kompletten Schaltung des Roboters angebracht. Dazu gehören die beiden Stepper für die Bewegung, der Elektromagnet und ein weiterer Stepper, der den Elektromagnet mit einer Seilwinde anheben und absenken kann (Abb. 3). Der Elektromagnet sitzt in der Mitte des Wagens und kann so die darunterlegende Unterlegscheibe austauschen.

Auf der Grundplatte ist neben dem Spielfeld und dem Wagen noch Platz für einen Laptop. Dieser wird benötigt, da der Arduino nicht genug Rechenleistung für Bildverarbeitung bzw. Processing hat. Also ist der Laptop mit der Webcam und dem Arduino verbunden. Außerdem benötigt die Schaltung ein Netzteil oder einen Akku, da der Arduino nur mit 5V läuft, die Stepper und der Elektromagnet jedoch 8V benötigen.

1. Holzplatte 50x80cm
2. 3x Kanthölzer à 50cm
3. 2x Winkel
4. Schrauben
5. 8x Rad mit 3cm Durchmesser
6. Holzplatte für untere Ebene 40x15cm
7. Holzplatte für obere Ebene 15x15cm
8. Hölzer zur Spurhaltung 200cm
9. 4 Zahnschiene à 25cm
10. 3x Stepper
11. 2x Zahnrad
12. Steckbrett
13. Arduino Nano
14. 3x Treiber für Stepper
15. 4x Kondensator
16. 3x Widerstand
17. Kabel
18. Elektromagnet
19. Mosfet für Elektromagnet
20. 15 cm Faden
21. Webcam
22. Netzteil
23. Ca. 150 Unterlegscheiben
24. Weißes und rotes Klebeband

Die gesamte Software ist mit Processing geschrieben. Arduino konnte nicht verwendet werden, da es keine Möglichkeiten zum Arbeiten von Bildern bietet. Dafür ist mehr Rechenleistung nötig als der Arduino Nano hat, deshalb wird die gesamte Berechnung von einem angeschlossenen Laptop über Processing gemacht. Um das Labyrinth zu lösen, sind mehrere Schritte nötig. Zuerst muss das Spielfeld aufgenommen und angepasst werden. Dann wird es durch einen Algorithmus gelöst, anschließend auf dem Bildschirm dargestellt und zum Schluss werden die Unterlegscheiben ausgetauscht. Für jeden dieser Schritte ist eine andere Methode im Code zuständig.

Mit Bildverarbeitung ist das Fotografieren des Labyrinths und das Anpassen des entstandenen Fotos auf den Lösungsalgorithmus gemeint. Sobald der Roboter gestartet wurde, wird auf dem Bildschirm ein Livebild des Spielfelds gezeigt. Allerdings wird das Bild in binärem Schwarz-Weiß dargestellt. Das bedeutet, dass alle Pixel, die heller als ein bestimmter Grenzwert sind, weiß und alle dunkleren schwarz eingefärbt werden. Somit gibt es nur zwei Farben auf dem gesamten Bild. Da der Untergrund des Spielfelds schwarz angemalt ist und alle Unterlegscheiben weiß beklebt sind, ist der Weg des Labyrinths im Webcambild klar definiert. Nach dem Betätigen einer Taste wird ein Screenshot gemacht, mit dem weitergearbeitet werden kann. Der Screenshot wird noch so zugeschnitten, dass nur das Spielfeld und keine umliegenden Ränder zu sehen sind. Danach in ein 10×10 Felder großes Raster unterteilt. Jedes Feld soll einem Feld auf dem realen Spielfeld entsprechen. Um zu entscheiden, welches Feld schwarz oder weiß ist, wird für jeden weißen Pixel in einem Feld dessen Wert um eins erhöht und für jeden schwarzen Pixel um eins verringert. Ist der Wert des Feldes am Ende mindestens null, wird das Feld als weiß behandelt. Bei einem negativen Wert schwarz. Anschließend wird um das 10×10 Raster virtuell ein schwarzer Rahmen gelegt. Das ist aufgrund einiger Eigenschaften des Lösungsalgorithmus nötig. Als letzter Schritt der Bildverarbeitung wird für jedes weiße Feld die Anzahl umliegender weißer Felder gezählt. Davon wir eins abgezogen, man erhält die Anzahl der möglichen Wege von diesem Feld, da man von einem der Nachbarn herkommt. Die Anzahl der Felder mit mehr als einem Weg entspricht so auch der Anzahl der Kreuzungen im Labyrinth.

Abbildung 4: Virtuelle Vergrößerung des Vierecks

Der Lösungsalgorithmus sucht den Weg durch das Labyrinth. Dabei müssen Start- und Endpunkt fest vorgegeben sein. Der Algorithmus untersucht ob der aktuell betrachtete Punkt eine Kreuzung ist, also mehr als einen möglichen Weg hat. Wenn dem so ist werden alle bereits vorhandenen Kreuzungen in ihrer Reihenfolge um eins hochgestuft. Die neue Kreuzung wird als Kreuzung 0 abgespeichert, aus der vorherigen Kreuzung 0 wird Kreuzung 1 usw. Danach beginnt die eigentliche Wegfindung. Der Algorithmus untersucht nun, ob der Punkt unterhalb des aktuellen begehbar ist, also weiß, mit mindestens einem verfügbaren Weg und noch nicht Teil des Lösungswegs. Sollte dies der Fall sein werden die offenen Wege des aktuellen Punkts um eins verringert, der aktuelle Punkt als Lösungspunkt abgespeichert und der Punkt unterhalb wird der neue aktuelle Punkt. Wenn es aber nicht möglich ist nach unten zu gehen, werden im Uhrzeigersinn die Nachbarn des aktuellen Punkts betrachtet. Sobald einer davon begehbar ist, macht der Algorithmus einen Schritt in diese Richtung und beginnt wieder von vorn. Sollte es keine Möglichkeit mehr geben sich weiterzubewegen, springt der Algorithmus zur letzten Kreuzung, also Kreuzung 0. Dann löscht er alle Lösungspunkte, die er nach Kreuzung 0 besucht hat. Anschließend untersucht der Algorithmus wie viele Wege an Kreuzung 0, also dem aktuellen Punkt, noch offen sind. Wenn mehr als ein Weg verfügbar ist, unternimmt der Algorithmus nichts und beginnt wieder von vorn. Bei genau einem offenen Weg ist Kreuzung 0 faktisch keine Kreuzung mehr und wird daher als Kreuzung gelöscht. Alle anderen Kreuzungen dann runtergestuft, sodass Kreuzung 1 zu Kreuzung 0 wird. Anschließend wiederholt sich der Algorithmus. Auf diese Weise findet der Algorithmus immer einen Weg durchs Labyrinth, solange dieser vorhanden ist. Das Labyrinth gilt als gelöst, wenn der aktuelle Punkt dem angegebenen Endpunkt entspricht. Sobald das eintritt, werden zwei Arrays mit den x- und y-Koordinaten der Punkte des Lösungswegs angelegt. Es ist auch möglich, dass das Labyrinth Schleifen enthält. Sollte dies der Fall sein, ist nicht garantiert, dass der Algorithmus den kürzesten Weg findet.

Abbildung 5: Schaubild Lösungsalgorithmus

Wenn der Lösungsalgorithmus das Labyrinth erfolgreich abgearbeitet hat, kann der Lösungsweg auf dem Bildschirm dargestellt werden. Der Algorithmus liefert zwei Arrays mit den x bzw. y-Koordinaten der Lösungspunkte. An diesen Koordinaten werden nun rote Kreise in den Screenshot des Spielfelds eingefügt.

In der folgenden Tabelle werden die verschiedenen Belegungen der Eins beschrieben. Dabei werden alle Eins als Digitalpins verwaltet.

Zum jetzigen Zeitpunkt kann unser Roboter das Labyrinth aufnehmen, umwandeln und lösen. Der Lösungsweg kann auf dem Bildschirm angezeigt werden und der Wagen kann sich in alle Richtungen bewegen. Der Magnet kann auf und ab bewegt werden. Die Bewegung ist zwar präzise genug, um mittig über den 2,5cm breiten Feldern zu landen, allerdings summiert sich der Spielraum von unter einem Millimeter pro Feld bei der Bewegung über längere Strecken. Der grundsätzliche Ablauf für das Austauschen der Scheiben steht auch schon fest, aber wurde noch nicht getestet. Auch die Werte für die genauen Abstände zwischen z.B. dem Stapel der roten Scheiben und den Punkten des Lösungswegs haben wir noch nicht ausgemessen. Demnach kann der Roboter zwar jede erforderliche Teilaufgabe für das Lösen, aber das Austauschen beherrscht er noch nicht.

Als erstes sollte die Bewegung, also das Austauschen der Scheiben finalisiert werden. Dazu muss noch etwas mit den Abständen und Werten experimentiert werden. Danach kann der Roboter in einigen Belangen verbessert werden. Die Position des Elektromagneten wird momentan nur über die Umdrehungen der Stepper berechnet. Diese Methode ist ziemlich ungenau und anfällig für Manipulationen. Denkbar wäre es, die Webcam zu nutzen um die Position des Elektromagneten zu überwachen oder auf Grundlage dieser Daten die Bewegung auszuführen. Der Code ist sicherlich auch einfacher realisierbar. Außerdem könnte die Fertigungsqualität verbessert werden, also alle Holzteile begradigt und geschliffen, die Stepper durch mehr als Kabelbinder befestigt und insgesamt die Konstruktion stabilisiert werden. Des Weiteren wäre denkbar, den Roboter auch für andere Zwecke als das Labyrinth-Lösen zu verwenden. Dazu kann der Wagen verändert und zusätzlicher Code geschrieben werden. Unsere Idee wäre dazu, dass der Roboter verschiedene Brettspiele wie z.B. Mensch-ärger-dich-nicht erlernt.

code.zip