Roboter mit Neato Lidar und SLAM

Hallo an alle,

ich war hier lange inaktiv, habe aber immer mal zwischendurch reingeschaut :D In letzter Zeit fällt hier öfters das Thema Lidar und Kartenerstellung, weshalb ich mir dachte, dass ich einfach mal mein letztes größeres Projekt, bei dem es im wesentlichen darum geht, vorstelle :D

Ich erzähle jetzt erstmal ein bisschen was zur Vorgeschichte, wie es zu dem Projekt gekommen ist, und gehe danach auf das Projekt selbst ein :)

1) Einleitung
1.1) RoboCup
Mein Teamkollege und ich nehmen nun seit vier Jahren am RoboCup Junior Rescue B teil, wo ein Roboter in einem Rettungsszenario autonom in einem Labyrinth nach verschütteten Opfern suchen muss. Unseren Fortschritt dokumentieren wir (mehr oder weniger konsequent, in letzter Zeit passiert recht wenig und wir haben aufgrund unserer Abiturvorbereitung nicht sonderlich viel Zeit) auf unserem Blog.
Hier mal ein kleines Video, dann kann man sich das vielleicht besser vorstellen:
http://www.youtube.com/watch?v=p45Iu_JTwB4

1.2) Idee: Facharbeit und SLAM im RoboCup?
In der 11. Klasse muss man bei uns eine Facharbeit erstellen. Bei unseren Teilnahmen am RoboCup konnten haben uns besonders die Rettungsroboter der Studenten immer sehr fasziniert. Diese fahren autonom durch ein wesentlich komplexeres „Gebäude“ als unsere Rescue B Arena und erstellen mit teueren Sick Laserscannern und Kinect Kameras richtige 3D Bilder der Umgebung.
In der Facharbeit, die von jedem Schüler alleine erstellt werden muss, habe ich mir dann überlegt, einen sehr simplen SLAM Algorithmus, der für die Anwendung in Rescue B Robotern geeignet ist, zu programmieren. Problematisch ist für diese Roboter immer, wenn sie irgendwo anecken: Es dürfen keine Sensoren mit Lasern benutzt werden, weshalb man auf IR Entfernungssensoren angewiesen ist, die eine relativ kleine Reichweite haben. Sowas wie anecken kann man in so einer Karte ohne erheblichen Aufwand nicht leicht erkennen. Beim Anecken an Wänden verliert der Roboter fast immer die Position in der Karte (die Position in der Karte stimmt nicht mehr mit der realen Position überein), was die Karte unbrauchbar macht. So ein Fehler kann über den Vergleich von Wänden aber zumindest recht zuverlässig erkannt werden. Die Idee war dann, einfach eine neue Karte zu erstellen und diese während der Erstellung solange über die alte Karte zu legen, bis eine sehr wahrscheinliche Übereinstimmung gefunden wurde. Diese Arbeit ist auch hier veröffentlicht, da gehe ich jetzt aber erstmal nicht weiter drauf ein :)

1.2) Jugend Forscht
Nach der letzten Saison kam dann die Idee auf, diese Arbeit auch einfach mal bei Jugend Forscht einzureichen. Für mich selbst zum Experimentieren habe ich unabhängig davon mal einfach ein Neato XV-11 Lidar bei ebay als Ersatzteil aus den USA für ca. 100€ bestellt, außerdem ein STM32F4 Discovery Entwicklungsboard, weil ich auch mal Erfahrung im ARM Bereich sammeln wollte. Irgendwann konnte dann der ARM das Lidar auslesen und die Daten zum Computer streamen, dann kam noch ein Farbdisplay drauf und eins kam zum anderen und auf einmal lief dann SLAM auf dem ARM :D Na ja, so einfach ging es nicht, aber mehr dazu im nächsten Abschnitt :D

2) SLAM
Im Rahmen der Facharbeit habe ich mich dann auch recht viel mit SLAM beschäftigt. Grundsätzlich ist das natürlich nicht mal eben so zu implementieren (und für Anfänger sicherlich auch kein geeignetes Projekt), und ich bin eben auch nur ein Abiturient, kein Informatik Student (ich hoffe, die Fachleute hier sehen mir das nach), weshalb ich unter Umständen nicht alle Fachbegriffe richtig nutze ;) Jedenfalls besteht SLAM grundsätzlich aus diesen drei Schritten:

1. Scan der Umgebung anfertigen
2. Scan des Lidars verarbeiten und mit der Karte abgleichen, falls Karte bereits Daten enthält, ansonsten (erster Scan) direkt in die Karte integrieren
3. Position des Roboters durch Abgleich mit der Karte aktualisieren
4. Scan in die Karte integrieren
5. Roboter kann sich nun bewegen und die Position ggf über Odometer aktualisieren
6. Beginne bei 1

Es gibt nun verschiedene theoretische Ansätze, wie genau das alles abläuft. Genauer gehe ich darauf hier jetzt nicht ein, aber man kann entweder Merkmale aus dem Scan extrahieren (hier ist eine Wand, da ist eine Wand, und diese Merkmale in einer Datenbank abspeichern, oder man arbeitet direkt mit den rohen Daten der Karte, ohne Merkmale zu extrahieren. Da der zweite Ansatz für mich einfacher zu verstehen war und nicht mit tieferer Mathematik (Filtern etc...) verbunden war, habe ich mich dafür entschieden.

2.1) tinySLAM
Auf openslam.org sind verschiedene SLAM Ansätze veröffentlicht. Die meisten benötigen einen richtigen Computer mit viel Rechenleistung, sind in einer nicht für den STM32F4 nicht geeigneten Programmiersprache geschrieben oder einfach zu komplex. Lediglich der tinySLAM Algorithmus sah sehr vielversprechend aus. Der Algorithmus arbeitet mit einer Monte-Carlo Suche und besteht lediglich aus 200 Zeilen C-Code. Die Dokumentation ist allerdings mangelhaft, weshalb einiges erst einmal analysiert werden musste. Große Teile der Software (wie die Karte (in den RAM des STM32 passt eine 3m x 3m große Karte mit einer Auflösung von 1cm)) konnten ohne Änderung übernommen werden. Die eigentliche Selbstlokalisierung läuft dann quasi durch Ausprobieren: Wir haben unseren ersten Laserscan in die Karte integriert. Ausgehend von dieser Karte bewegt sich der Roboter nun einige cm und die Position wird grob über die integrierten Odometer aktualisiert. Nun wird der Laserscan in einem Bereich von etwa 5cm um die über Odometer geschätze Position bewegt und gedreht und die Passgenauigkeit des Scans in der Karte ermittelt. Man kann sich das vorstellen, als hätte man eine mehr oder weniger vollständige Landkarte und man weiß ungefähr, wo man ist, aber nicht exakt. Man hat außerdem ein Bild von der Umgebung so im Umkreis von 100m und weiß, welche Straßen in welche Richtung verlaufen. Man erstellt sich dann von diesem Ausschnitt der Umgebung eine kleine Folie und legt diese mit kleinen Variationen über die Landkarte. Nach einigen Versuchen (in der aktuellen Implementation ca. 1000) hat man dann die beste Überlappung gefunden und man weiß, wo man sich genau befindet und kann die Karte vervollständigen.

3) Fazit
Ziel war es, einen SLAM Algorithmus auf Basis des RoboCups Roboters zu implementieren, der über recht stark limitierte Rechenleistung und Speicherplatz verfügt. Das hat recht gut geklappt. Die Karte ist relativ genau (zumindest in großen Räumen funktioniert das sehr gut, wenn man aber ein stark verwinkeltes Labyrinth hat, wird die Karte recht bald ungenau, es muss also noch einiges optimiert werden). Für einen Staubsaugerroboter sollte das aber vollkommen ausreichen.
Im RoboCup können wir das Ganze leider wie gesagt nicht benutzen, da Laser verboten sind. Mit diesem erweiterten Projekt habe ich dann eben bei Jugend Forscht teilgenommen.

Das Ganze habe ich jetzt nur seeehr oberflächlich hier angekratzt und beschrieben. Diese Arbeit wollte ich Euch nicht vorenthalten - ich kann da aktuell keinen großen Nutzen mehr draus ziehen und bevor die Arbeit auf meinem Laptop versauert, möchte ich sie eben mit einer größeren Gemeinde teilen. Vielleicht kann ja jemand auf den von mir gemachten Erfahrungen aufbauen :D Grundsätzlich kann ich mir auch vorstellen, diese Arbeit über ein Open Source Projekt auszubauen... Ein Staubsaugerroboter oder so vielleicht? Oder ein generelles SLAM Projekt auf einer festen Plattform (bei Interesse kann ich auch mal den Schaltplan mit meinem Display und dem Dicovery Board rausgeben). Um ein neues Projekt zu starten, habe ich aktuell leider nicht so viel Zeit, aber grundsätzlich kann ich mir definitiv vorstellen, auch den Source Code offenzulegen und dann vielleicht daran mit zu arbeiten :)

Hier hänge ich jedenfalls erstmal meine Arbeit an (ich musste einige Bilder leider stark komprimieren, da der Anhang sonst zu groß geworden wäre). Würde mich freuen, wenn da vielleicht jemand mal noch mehr draus macht und natürlich freue ich mich auch über Kritik :D

Falls ihr fragen habt - nur zu, ich stehe Euch jederzeit zur Verfügung :D

Grüße
Jan

Anhang 29986

schicke arbeit, ich habe sie überflogen.
werde sie mir mal am we richtig zu gemüte führen :D

Hey, mich würde der konkrete Code interessieren. Wir arbeiten in einer Hochschulgruppe gerade an einem ähnlichen Projekt. (Nur draußen und man wirft mehr Sensoren in den Algorithmus)
Ihr habt aber meinen vollen Respekt in der Schule, so etwas zu implementieren. Die Ausarbeitung sieht auch sehr interessant aus.

Freut mich, dass es jetzt doch noch Feedback gibt :D

Hab' das Repository jetzt mal öffentlich gemacht. Hier könnt ihr Euch den Quelltext ansehen und herunterladen. Die Arbeit werde ich da mal bald auch noch hinzufügen.

Shepede, hört sich sehr interessant an! Da ich aber nur Schüler bin, habe ich nicht so viel Ahnung von den ganzen Themen, die recht komplexe Mathematik benötigen (Sensordatenfusion, Kalman Filter etc...), weshalb der implementierte SLAM Algorithmus eben sehr primitiv ist. Vielleicht hilft Euch das ja trotzdem etwas weiter :D

Grüße
Jan

Hey,
ihr habt geschrieben, dass ihr grad in der Abiturvorbeitung steckt. Wisst ihr schon wo ihr studieren wollt ?

Zur komplexen Mathematik. An der Uni hat man dann zwar Ahnung von der Mathematik aber meistens nicht so wirklich die Ahnung wie man die Algorithmen implementiert :D