Simultaneous Localization and Mapping

Als SLAM (englisch Simultaneous Localization and Mapping; deutsch Simultane Positionsbestimmung und Kartierung) wird ein Verfahren der Robotik bezeichnet, bei dem ein mobiler Roboter gleichzeitig eine Karte seiner Umgebung erstellen und seine räumliche Lage innerhalb dieser Karte schätzen muss. Es dient damit dem Erkennen von Hindernissen und unterstützt somit die autonome Navigation.

Aufgabenstellung

Eine der grundlegenden Probleme eines mobilen Roboters besteht darin, sich zu orientieren, also zu wissen, wie seine Umgebung aussieht und wo er sich (absolut) befindet. Dafür ist der Roboter mit verschiedenen Sensoren ausgerüstet, wie Ultraschall, Kameras oder Lidar, mit dessen Hilfe seine Umgebung dreidimensional erfasst wird. Dies ermöglicht einem Roboter sich lokal zu bewegen, Hindernisse rechtzeitig zu erkennen und zu umfahren. Wenn darüber hinaus die absolute Position des Roboters bekannt ist, z. B. aus zusätzlichen GPS-Sensoren, kann eine Karte aufgebaut werden. Dabei misst der Roboter die relative Position möglicher Hindernisse zu ihm und kann mit seiner bekannten Position dann die absolute Position der Hindernisse bestimmen, die anschließend in die Karte eingetragen werden.

Die Herausforderung bei SLAM

Das Erkunden einer unbekannten Umgebung und das Orientieren in dieser wird von uns Menschen intuitiv verrichtet. Über unsere Sinnesorgane: Augen, Haut, Ohren und Nase nehmen wir Informationen, in Form von Reizen, aus unserer näheren Umwelt auf. Diese Informationen werden in unserem Gehirn kombiniert und zu einer Positionsbestimmung und Charakterisierung unserer Umgebung verarbeitet. Bewusst oder unbewusst erkennen wir markante Merkmale, die wir zu einer räumlichen Beziehung verknüpfen, um eine abstrakte Vorstellung eines Lageplans zu erhalten, mit deren Hilfe, je nach Aufgabe und Ziel, navigiert wird.

Ähnlich wie beim Menschen soll dies auch bei mobilen Systemen erreicht werden. Ohne jegliches Vorwissen soll aus den Daten von Sensoren, die in einer mobilen Systemeinheit integriert sind, bei gleichzeitiger Kartierung der Umgebung durch einfache dreidimensionale Punkte oder komplexere Konstrukte, auf die Position und Orientierung geschlossen werden. Hierbei bezeichnet man den Vorgang der Kartenerstellung im Englischen als mapping und das Erkennen der Position einer mobilen Systemeinheit als self-localisation.

Eine große Herausforderung solcher Systeme ist, dass für eine genaue Positionsbestimmung eine entsprechend detaillierte Karte benötigt wird und für die Generierung einer detaillierten Karte die genaue Position der mobilen Systemeinheit bekannt sein muss. Daraus wird deutlich, dass diese zwei Anforderungen, Kartenerstellung und Selbstlokalisierung, nicht unabhängig voneinander gelöst werden können. SLAM ist somit ein Henne-Ei-Problem, da weder die Karte noch die Position bekannt ist, sondern diese gleichzeitig geschätzt werden sollen.

Anwendung

Für viele Einsatzorte von mobilen Robotern gibt es keine Karten und auch keine Möglichkeit, die absolute Position, z. B. über GPS, zu schätzen. Ohne SLAM müsste vor dem Einsatz eine Karte erstellt werden, was den Einsatz verzögern und verteuern kann. Daher ist es je nach Anwendungsgebiet wichtig, dass ein Roboter in der Lage ist, autonom eine neue Umgebung zu erkunden und eine Karte zu erstellen, die er dann später zur Navigation nutzen kann.

Die SLAM-Methode ist ein aktives Forschungsgebiet innerhalb der Robotik und in Computer Vision, welches weltweit von zahlreichen Forschergruppen bearbeitet wird. Beispielsweise werden die Mars-Landefahrzeuge der NASA-Mission Mars Exploration Rover "Spirit" und "Opportunity" mit solchen Verfahren betrieben.

Ansätze

Es gibt viele verschiedene Ansätze, wobei es grundlegende Ähnlichkeiten gibt. Da ein Roboter normalerweise nur einen Teil der Umgebung sehen kann, wird die Karte inkrementell aufgebaut: Zunächst ist keine Karte vorhanden und die Position des Roboters definiert den Ursprung seines Koordinatensystems. Damit ist trivialerweise die absolute Position des Roboters bekannt und die erste Messung der Umgebung kann direkt in die Karte eingetragen werden. Danach bewegt sich der Roboter und misst erneut seine Umgebung. Wenn sich der Roboter nicht zu weit bewegt hat, wird er einen Teil der schon bekannten Umgebung wiederum, aber auch einen bisher unbekannten Bereich zum ersten Mal vermessen. Aus der Überlappung der neuen Messung mit der bisherigen Karte kann die Bewegung des Roboters berechnet werden, so dass wieder die absolute Position bekannt ist und damit auch die neue Messung in die Karte integriert werden kann. In dieser Vorgehensweise wird die Karte inkrementell erweitert, bis das gesamte Gebiet vermessen ist.

Da die Bestimmung der Bewegung des Roboters zwischen zwei Messungen aber nie exakt ist, wird die berechnete Position des Roboters von der wahren immer weiter abweichen, womit auch die Qualität der Karte abnimmt. Damit die Karte trotzdem konsistent bleibt, muss der Algorithmus in der Lage sein zu erkennen, wenn ein schon bekannter Teil der Umgebung erneut vermessen wird (Loop Closing).

SLAM-Verfahren

• EKF SLAM (Extended Kalman Filter)
  • SEIF (Sparse Extended Information Filter)
  • UKF (Unscented Kalman Filter)
• SLAM mit Partikelfiltern
  • FastSLAM
  • Grid-basierte Verfahren mit Rao-Blackwellisierten Partikelfiltern
  • DP-SLAM
• Expectation-Maximization-Filter
• Graph-basierende Techniken
  • GraphSLAM, TORO, HOG-Man, TreeMap
  • Relaxationstechniken
  • Smoothing-Techniken

Die Lösung von SLAM bedingt die Lösung des Datenassoziationsproblems, d. h., es muss ermittelt werden, welche (Umgebungs-)Merkmale korrespondieren. Dieses Problem ist besonders schwierig, da sich Merkmale nicht mit absoluter Sicherheit extrahieren lassen. Scanmatching-Verfahren kommen ohne Merkmale aus, da sie ganze Scans, bzw. Punktwolken, berücksichtigen und anschließend Graph-basierende Techniken einsetzen.

Literatur

• Andreas Nüchter: 3D Robotic Mapping. Springer-Verlag GmbH, Berlin 2009, ISBN 978-3-540-89883-2 (Springer Tracts in Advanced Robotics).
• Cyrill Stachniss: Robotic Mapping and Exploration. Springer-Verlag GmbH, Berlin 2009, ISBN 978-3-642-01096-5 (Springer Tracts in Advanced Robotics).
• Sebastian Thrun, Wolfram Burgard, Dieter Fox: Probabilistic Robotics. The Mit Press, 2005, ISBN 978-0-262-20162-9.
• Michael Montemerlo, Sebastian Thrun: FastSLAM: A Scalable Method for the Simultaneous Localization and Mapping Problem in Robotics. Springer Verlag, 2007, ISBN 3-540-46399-2.
• Austin Eliazar, Ronald Parr: DP-SLAM: Fast, Robust Simultainous Localization and Mapping Without Predetermined Landmarks. 2003.
• F. Lu, E. Milios: Globally consistent range scan alignment for environment mapping. In: Autonomous Robots. 1997.
• Dorit Borrmann, Jan Elseberg, Kai Lingemann, Andreas Nüchter, Joachim Hertzberg.: Globally consistent 3D mapping with scan matching. In: Journal of Robotics and Autonomous Systems (JRAS). Elsevier Science, 2008 (PDF).
• Giorgio Grisetti, Cyrill Stachniss, Wolfram Burgard: Improved Techniques for Grid Mapping with Rao-Blackwellized Particle Filters. In: IEEE Transactions on Robotics. 2007 (PDF).
• Giorgio Grisetti, Cyrill Stachniss, Wolfram Burgard: Non-linear Constraint Network Optimization for Efficient Map Learning. In: IEEE Transactions on Intelligent Transportation Systems. 2009 (PDF).
• Udo Frese, Per Larsson, Tom Duckett: A Multilevel Relaxation Algorithm for Simultaneous Localisation and Mapping. In: IEEE Transactions on Robotics. 2005.
• Frank Dellaert: Square Root SAM (Smoothing and Mapping). In: Robotics: Science and Systems. 2005.

Weblinks

• SLAM Paper Repository – Publikationsübersicht zu SLAM
• 3D Scan Matching and Registration – Übersicht zu 3D Scan Matching
• OpenSLAM – Online Repository zu Implementierungen von verschiedenen SLAM-Algorithmen
• Mobile Robot Programming Toolkit – Umfangreiches Slam-Toolkit für Linux/Windows
• HOG-Man – L-GPL Library zum Lösen des Graph-basierten SLAM Problems
• SLAM6D – GPL Tools zum vollständigen Lösen von SLAM für 3D Laserscans (Datenassoziation und SLAM-Löser)
• Artificial Intelligence for Robotics (engl.) Udacity-Kurs zur künstlichen Intelligenz von Robotern
• SLAM lectures (engl.) Online SLAM Kurs auf Basis von Python