Projekt 70b: Bau eines Labyrinths für EV3-Roboter

Autoren: Hinners Eileen, Klauke Patrick

Einleitung

Im Rahmen des Praktikums der angewandthen Elektrotechnik im Modul ingenieurwissenschaftliche Vertiefung II des Masterstudienganges Business and Systems Engineering, soll ein Mindstorm EV3 Roboter durch ein selbst gebautes Labyrinth finden. Ziel des Artikels ist es, nachfolgenden Gruppen eine nachhaltige Dokumentation zum leichteren Einstieg zu hinterlassen.

Aufgabe

Im einfachsten Sinne soll der Roboter den Ausgang aus einem Labyrinth finden.

Das Projekt teilt sich in 3 Schritte auf. Im 1. Schritt (Kartographie) wird der Roboter willkürlich im Labyrinth ausgesetzt, von seiner zufälligen Startposition aus fährt der Roboter solange gerade aus bis er rechts eine Kreuzung vorfindet. Der Roboter biegt rechts ab und folgt weiter diesem Weg bis sich rechts wieder eine Kreuzung vorfindet(Rechte-Hand-Prinzip). Kreuzungen die sich links vom Roboter ergeben merkt er sich und erkundet diese unbekannten Wege nach dem Last in-first out Prinzip (nach dem der Roboter mit der rechten Hand Regel nicht mehr weiterkommt).

Im Zweiten Schritt der Ortung wird der Roboter willkürlich im Labyrinth positioniert. Von dieser Startposition aus folgt der Roboter der rechten Hand Regel, bis seine Position eindeutig innerhalb des Labyrinths bestimmt ist. Nach erfolgreicher Ortung sucht der Roboter wieder seine Startposition auf.

Im 3. und letzten Schritt „Schnellster Weg“ soll der Roboter den schnellsten Weg aus dem Labyrinth finden. Den Weg den der Roboter fahren soll wird durch die „Tiefensuche“ vorher errechnet. Von seiner eingenommen Position aus Schritt 2 aus, fährt der Roboter den schnellsten (kürzesten Weg) hinaus.

Erwartungen an die Projektlösung

Aufbau und Planung eines flexiblen Labyrinths (z.B. Styrodur)
Robotervorschlag wurde bereits aufgebaut
Recherche SLAM
SLAM Ortung und Navigation via US oder IR Sensor(en)
Inbetriebnahme mit Matlab/Simulink
Realisierung der Flucht aus dem Labyrinth durch SLAM.
Machen Sie spektakuläre Videos, welche die Funktion visualisieren.
Test und wiss. Dokumentation
Live Vorführung während der Abschlusspräsentation

Stimmen Sie sich mit Projekt 70a bezüglich Roboterdesign und Labyrinth ab, so dass die Labyrinthteile kompatibel sind.

Schwierigkeitsgrad

Mittel (***)

Verwendete Bauteile

EV3 Medium Motor 1x
EV3 Large Motor 2x
EV3 Ultraschallsensor 1x
EV3 Gyrosensor 1x
EV3 Brick 1x
Diverses Zubehör von Lego
Styrodur 15cm x 30 cm x 5cm 30x
Styrodur 15cm x5cm x 5cm 15X
Holzdübel Ø6cm x 30mm ^ 50x
Holzplatten

Projekt

Projektplan

Für die Umsetzung des Projekts bis hin zur Abschlusspräsentation sind 4 Monate innerhalb des Semesters eingeplant. Der Arbeitsaufwand sollte laut Modulplan bei 17 Stunden pro Student liegen (wurde deutlich überschritten). Um möglichst effizient über das Semester arbeiten zu können, wurde das Projekt in verschiedene Arbeitsvorgänge unterteilt. Als erstes musste bis zum 22.10.2017 innerhalb von 1,5 Wochen eine Bestellliste erstellt werden, da die HSHL viel Zeit für die Bearbeitung der Bestellvorgänge benötigt. Bauteile die am Anfang bei der Projektplanung nicht berücksichtigt wurden, können nachträglich nicht bestellt werden. Daher ist eine Vorabplanung äußerst wichtig.

Labyrinth

Das Labyrinth für den Roboter ist modular aufgebaut d.h. die Position der Wände und die Größe des Labyrinths kann verändert werden. Die Modularität des Labyrinth wurde dadurch erreicht, dass die Wände aus Styrodur eine feste Bohrungsrasterung zu den Bodenplatten aufweisen. In den Wänden stecken Holzdübel und in den Bodenplatten sind die passenden Bohrungen.

Die Bodenplatte besteht aus mehreren einzelnen Platten, die wie ein Puzzel miteinander verbunden sind. Je nach Anwendung kann die Bodenplatte rechteckig oder quadratisch aufgebaut werden.

Roboter

Der EV3-Roboter wurde fertig zusammengebaut übernommen und darf nicht umgebaut werden, da der Roboter in seiner Form noch in anderen Praktika verwendet wird.

Ultraschallsensor

Die Abstandsreglung zur Wand wird mit einem Ultraschallsensor realisiert. Eigenschaften des EV3 Ultraschallsensors:

Misst Entfernungen zwischen 3 und 250 cm (1 bis 100 Zoll)
Messgenauigkeit: +/- 1 cm (0,394 Zoll)

Der digitale EV3 Ultraschallsensor erzeugt Schallwellen und „liest“ deren Echos, um Objekte zu erkennen und deren Entfernung zu messen Ultraschallsensoren als Abstandssensoren sind in der Lage, Objekte berührungslos zu erkennen und ihre Entfernung zum Sensor zu messen. Die Abstandserfassung von Ultraschallsensoren arbeiten nach dem Prinzip der Laufzeitmessung von hochfrequenten Schallimpulsen. Der Ultraschallsensor strahlt zyklisch einen kurzen, hochfrequenten Schallimpuls aus. Dieser pflanzt sich mit Schallgeschwindigkeit in der Luft fort. Trifft der Ultraschallimpuls auf einen Gegenstand, wird er reflektiert. Das so entstehende Echo wird vom Sensor wieder aufgenommen und aus der Zeitspanne zwischen dem Senden und dem Empfangen des Schallimpulses, wird der Abstand zum Objekt berechnet. Dieses Prinzip der Abstandmessung mithilfe von Ultraschallwellen verwenden im Tierreich Fledermäuse. Ultraschallsensoren sind unempfindlich gegenüber Lichteinstrahlung

Gyrosensor

Drift-linke-Seite

Zur Kartographierung des Labyrinths und um genau 90 Grad Kurven zufahren wird ein Gyrosensor verwendet. Ein Gyrosensor ist ein Beschleunigungs- oder Lagesensor, der auf kleinste Beschleunigungen, Drehbewegungen oder Lageänderungen reagiert. Das Prinzip des Gyrosensors basiert auf der Massenträgheit.

Genauigkeit der Winkelmessung: +/- 3 Grad
Maximale Ausgabe: 440 Grad/Sekunde
Erfassungsrate: 1 kHz

Bilder Drift. Wird der Gyrosensor mit der EV3-Programiersofware verwendet, muss keine Drift Kompensation ausgeführt werden. Untenstehende Graphik stellt den Drift eines EV3 Gyrosensors außerhalb der EV3-Programiersoftware dar. Der Gyrosensor wurde auf einem mittleren EV3-Motor montiert und anschließend 90° nach links und 90° nach rechts (von der Ausgangsposition aus) geschwenkt.

Bauphase

Nach der Lieferung des Styrodurs beginnt die Fertigung des Labyrinths. Das Styrodur wird mit dem Messer in 30 x 15 x 2cm Platten und in Eckverbinder mit den 2x 2x 2 cmzugeschnitten. Zudem besitzen die Seitenwände Bohrungen für Dübel.

Programmierung

PAP

Der Programmcode wurde mit dem PAP-Designer erstellt und anschließend im Matlab/Simulink umgesetzt. Für die Programmierung wurde zunächst ein Programmablaufplan erstellt. Dieser kann allerdings nicht ins Wiki geladen werden. Eine Version liegt im SVN bzw. ist direkt bei uns zu erhalten. Zunächst soll der Roboter das Labyrinth in dem er ist kartographieren. Dafür wird die Tiefensuche verwendet. Danach wird er an einer zufälligen Stelle ausgesetzt und wird über den Partikelfilter geortet. Im Anschluss an die Ortung wird der Roboter über den Dijkstra-Algorithmus den schnellsten Weg zum Ausgang nehmen. Neben dem PAP wurde ein UML-Diagramm mit den wichtigsten Klassen für die Programmierung erstellt. Die gesamte Programmierung enthält fünf Klassen und insgesamt mehr als 25 Funktionen.

SLAM-Algorithmen

Die standardisierten SLAM-Algorithmen basieren vor allem auf dem Kalman-Filter. Der Partikelfilter (Fast-SLAM) bringt im Hinblick auf unser Projekt allerdings einige Vorteile mit.

Der Partikelfilter

Ein Partikelfilter ist ein rekursiver Zustandsschätzer, der Partikel verwendet, um die Verteilung des geschätzten Zustands zu abzubilden. Dabei wird eine bestimmte (vorher definierte) Anzahl an Partikeln zufällig über das gesamte Labyrinth gestreut. Im nachfolgenden Schritt, werden die Abstände zu den Wänden gemessen und mit denen des EgoRoboters verglichen. Je besser die Übereinstimmung, desto besser ist auch die Güte des Partikels. Danach werden eine bestimmte Anzahl an Partikeln mit der besten Güte herausgesucht (Über den MR1a-Algorithmus) und alle Partikel auf die Positionen der besten Partikel verteilt. Als nächstes wird der EgoRoboter bewegt und auch alle Partikel (um die gleiche Schrittweite, wie der EgoRoboter). Ab jetzt wird der Vorgang solange wiederholt, bis vereinfacht gesehen nur noch eine Partikelposition vorhanden ist. Diese ist dann die Schätzung des EgoRoboters. Damit der Partikel Filter optimal funktioniert, müssen Parameter wie Anzahl der Partikel, die Anfangs Partikelposition und die Methode zur Schätzung des Zustandes richtig gewählt werden.

Der Kalman-Filter

Das Kalman-Filter dient dazu, Fehler in realen Messwerten zu reduzieren und Schätzungen für nicht messbare Systemgrößen zu liefern. Die Funktion des Partikel-Filters unterscheidet sich im wesentlichen von der des Kalman-Filters, dass beim Parikel-Filter die Schätzung durch eine Wahrscheinlichkeitsverteilung modelliert wird. Beim Kalman-Filter wird dieses durch die Koavarianzmatrix beschrieben. Das Kalman Filter wird durch die Zustandsraummatrix beschrieben.

Algorithmen zum Durchlaufen von Graphen

Tiefensuche

Obwohl die Tiefensuche ein Verfahren aus der Informatik, zum Suchen von Knoten in einem Graphen oder im unseren Fall Labyrinth ist, ist die Idee dahinter einfach. Bei der Tiefensuche wird zunächst ein Pfad vollständig in die Tiefe erkundet, bevor ein abzweigender Pfad erkundet wird. Welche Knoten zuerst durchlaufen werden, hängt von der Realisierung des Graphs ab. Dieser kann bspw. als verkettete Liste, inzidenzmatrix oder als Adjazenzmatrix implentiert werden. In unserem Projekt haben wir die Tiefensuche genutzt um jedes Feld in unserem Labyrinth zu finden. Dadurch kann Aufschluss über jedes Feld und seine Wände erhalten werden. Zunächst ist der Roboter im Startfeld. Dieses analysiert er und findet ein Nachbarfeld. Das Nachbarfeld wird in einem Stack (LIFO-Prinzip) von zu besuchenden Feldern gespeichert. Danach geht er auf direkten Wege (Dijkstra-Algorithmus) zum letzen Knoten im Stack. Sobald dieser erreicht wurde, wird er aus dem Stack entfernt und eine neue Messung bzw. Suche nach Nachbarn gestartet. Diese werden ebenfalls an den Stack eingefügt. Diese Vorgehensweise wird solange durchgeführt, bis kein Knoten mehr im Stack vorhanden ist.

Der kürzeste Weg nach Dijkstra

Dieser Algorithmus wurde nach dem niederländischen Informatiker Edsger W. Dijkstra benannt. Der Algorithmus liefert den kürzesten Weg von einem Startknoten zu einem Zielknoten. Dabei bekommen zunächst alle Knoten des Graphen bzw. Felder des Labyrinthes eine unendlich hohe Gewichtung. Der Startknoten bekommt darauf die Gewichtung 0. Nun werden die direkten Nachbarn betrachtet. Sie bekommen die Gewichtung 1. Eine Gewichtung wird danach auch für deren Nachbarn durchlaufen usw.. Sollte ein Knoten bereits eine Gewichtung von 10 haben, aber nun durch einen Weg mit der Gesamtgewichtung 7 erreicht werden können, so wird die Gewichtung des Knoten ersetzt und der neue Vorgänger gespeichert.

Ergebnis

Im Verlauf des Projektes sind einige Probleme aufgetreten. Das Simulink EV3 Support Package ist nicht lauffähig, da wie bei der anderen Gruppe Projekt 70a, Error 1 angezeigt wird. Das Matlab Support Package ist nicht ausimplentiert, d.h. es ist nur eine begrenzte Anzahl an Grundbefehlen vorhanden z.B. kann man den Motoren nicht wie im NXT Package eine Umdrehungszahl vorgeben, sondern nur ein Speed.level welches der Kraft des Motors entspricht. Bei gleichzeitigen ansteuern zweiter Motoren sind diese nicht miteinander gekoppelt, sodass bei gleichem Speed.level ein Motor schneller dreht als der andere.

Zudem gab es Probleme mit dem EV3 Wifi Dongel. Der Wifi Dongel stellt eigentlich eine Drahtlose Komunikation zwischen dem Host-Rechner und EV3 Roboter ein. Leider arbeitet der EV3 Roboter nicht zuverlässig mit diesen Wifi Dongel, es kam vermehrt zum nicht erkennen des Hostes und Fehlern beim einwählen in das Netzwerk.

Fazit

Das Projekt einen EV3 Roboter auf kürzesten Weg aus einen Labyrinth entkommen zu lassen, war sehr interessant obwohl es einige Probleme mit Simulink und EV3 Firmware gibt. Gleichermaßen wurde klar, das Teamarbeit ein wichtiger Bestandteil des Projektes ist und jeder einzelne seine Stärken mit einbringt. Zudem konnten weitere Erfahrungen im programmieren in Matlab gesammelt werden.

Als Abschluss lässt sich sagen, dass das Projekt noch mehr Zeit benötigt hätte, da die Kommunikation zwischen Matlab und EV3 Firmware nicht optimal ist. Die Dokumentation in SVN oder im WIKI ,ist eine sehr Gute Basis und ermöglicht es nachfolgenden Studenten das Projekt weiterzuführen,

Literatur

Monjazeb, A.: Autonomous Robot Navigation Based on Simultaneous Localization and Mapping. Carleton University (Canada), 2008. ISBN 978-049-4368-29-9
Nüchter, A.: 3D Robotic Mapping: The Simultaneous Localization and Mapping Problem. Heidelberg: Springer, 2009. ISBN 978-354-0898-83-2
Stachniss, C.: Robot Mapping. Uni Freiburg: Vorlesung, WS 13/14. URL: http://www2.informatik.uni-freiburg.de/~stachnis/. Stand: 01.01.15
Thrun, S.; u.A.: Probabilistic Robotics. Cambridge: MIT Press, 2005. ISBN 978-026-2201-62-9.
Thrun, S.; u.A.: FastSLAM: A Scalable Method for the Simultaneous Localization and Mapping Problem in Robotics. New York: Springer, 2007. ISBN 978-354-0463-99-3
Wang, Z. u.A.: Simultaneous Localization and Mapping: Exactly Sparse Information Filters. Singapore: 2011. ISBN 978-981-4350-31-0

Weblinks

Projektunterlagen

YouTube Video

Youtube Video zu Projekt 70b

→ zurück zum Hauptartikel: Angewandte Elektrotechnik (WS 17/18)