Quelltext der Seite Simultaneous Localization and Mapping

Als '''SLAM''' ({{enS|'''Simultaneous Localization and Mapping'''}}; {{deS|''Simultane Positionsbestimmung und Kartierung''}}) wird ein Verfahren der [[Robotik]] bezeichnet, bei dem ein mobiler [[Roboter]] gleichzeitig eine [[Karte (Kartografie)|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 [[Global Positioning System|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.&nbsp;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 (Planet)|Mars]]-Landefahrzeuge der [[NASA]]-Mission [[Mars Exploration Rover]] "[[Spirit (Raumsonde)|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 [[Inkrementelles Vorgehensmodell|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 ([[Kalman-Filter|''{{lang|en|Extended Kalman Filter}}'']])
** SEIF (''{{lang|en|Sparse Extended Information Filter}}'')
** UKF (''{{lang|en|Unscented Kalman Filter}}'')
* SLAM mit [[Sequenzielle Monte-Carlo-Methode|Partikelfiltern]]
** FastSLAM
** Grid-basierte Verfahren mit [[Rao-Blackwellisierung|Rao-Blackwellisierten]] Partikelfiltern
** DP-SLAM
* [[Expectation-Maximization-Algorithmus|''{{lang|en|Expectation-Maximization-Filter}}'']]
* Graph-basierende Techniken
** GraphSLAM, TORO, HOG-Man, TreeMap
** [[Relaxation (Naturwissenschaft)|Relaxationstechniken]]
** Smoothing-Techniken

Die Lösung von SLAM bedingt die Lösung des Datenassoziationsproblems, d.&nbsp;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 ==
* {{Literatur |Autor=[[Andreas Nüchter]] |Titel=3D Robotic Mapping |Kommentar=Springer Tracts in Advanced Robotics |Verlag=Springer-Verlag GmbH |Jahr=2009 |ISBN=978-3540898832 |Ort=Berlin}}
* {{Literatur
    | Autor=Cyrill Stachniss
    | Titel=Robotic Mapping and Exploration
    | Kommentar=Springer Tracts in Advanced Robotics
    | Verlag=Springer-Verlag GmbH
    | Jahr=2009
    | ISBN=978-3-6420-1096-5
    | Ort=Berlin
    }}
* {{Literatur | Autor=[[Sebastian Thrun]], [[Wolfram Burgard]], Dieter Fox | Titel=Probabilistic Robotics | Verlag=The Mit Press | Jahr=2005 | ISBN=978-0-2622-0162-9}}
* {{Literatur | Autor=Michael Montemerlo, [[Sebastian Thrun]]| Titel=FastSLAM: A Scalable Method for the Simultaneous Localization and Mapping Problem in Robotics | Verlag=Springer Verlag | Jahr=2007 | ISBN=3-5404-6399-2}}
* {{Literatur | Autor=Austin Eliazar, Ronald Parr | Titel=DP-SLAM: Fast, Robust Simultainous Localization and Mapping Without Predetermined Landmarks | Jahr=2003}}
* {{Literatur | Autor=F. Lu, E. Milios | Titel=Globally consistent range scan alignment for environment mapping | Sammelwerk=Autonomous Robots |Jahr=1997}}
* {{Literatur |Autor=Dorit Borrmann, Jan Elseberg, Kai Lingemann, [[Andreas Nüchter]], Joachim Hertzberg. |Titel=Globally consistent 3D mapping with scan matching |Sammelwerk=Journal of Robotics and Autonomous Systems (JRAS) |Verlag=Elsevier Science |Jahr=2008 |Online=[http://plum.eecs.jacobs-university.de/download/ras2007.pdf PDF]}}
* {{Literatur | Autor=Giorgio Grisetti, Cyrill Stachniss, Wolfram Burgard | Titel=Improved Techniques for Grid Mapping with Rao-Blackwellized Particle Filters | Sammelwerk=IEEE Transactions on Robotics | Jahr=2007  |Online=[http://www.informatik.uni-freiburg.de/~stachnis/pdf/grisetti07tro.pdf PDF] }}
* {{Literatur | Autor=Giorgio Grisetti, Cyrill Stachniss, Wolfram Burgard | Titel=Non-linear Constraint Network Optimization for Efficient Map Learning | Sammelwerk=IEEE Transactions on Intelligent Transportation Systems | Jahr=2009 |Online=[http://www.informatik.uni-freiburg.de/~stachnis/pdf/grisetti09its.pdf PDF] }}
* {{Literatur | Autor=Udo Frese, Per Larsson, Tom Duckett | Titel=A Multilevel Relaxation Algorithm for Simultaneous Localisation and Mapping | Sammelwerk=IEEE Transactions on Robotics | Jahr=2005}}
* {{Literatur | Autor=Frank Dellaert | Titel=Square Root SAM (Smoothing and Mapping) | Sammelwerk=Robotics: Science and Systems | Jahr=2005}}

== Weblinks ==
* [http://www.cas.kth.se/SLAM/slam-papers.html SLAM Paper Repository] – Publikationsübersicht zu SLAM
* [http://www.cs.princeton.edu/~bjbrown/iccv05_course/ 3D Scan Matching and Registration] – Übersicht zu 3D Scan Matching
* [http://www.openslam.org/ OpenSLAM] – Online Repository zu Implementierungen von verschiedenen SLAM-Algorithmen
* [http://www.mrpt.org/ Mobile Robot Programming Toolkit] – Umfangreiches Slam-Toolkit für Linux/Windows
* [http://www.openslam.org/hog-man.html HOG-Man] – L-GPL Library zum Lösen des Graph-basierten SLAM Problems
* [http://slam6d.sourceforge.net SLAM6D] – GPL Tools zum vollständigen Lösen von SLAM für 3D Laserscans (Datenassoziation und SLAM-Löser)
* [https://www.udacity.com/course/cs373 Artificial Intelligence for Robotics] (engl.) [[Udacity]]-Kurs zur künstlichen Intelligenz von Robotern
* [https://www.youtube.com/watch?v=B2qzYCeT9oQ&list=PLpUPoM7Rgzi_7YWn14Va2FODh7LzADBSm SLAM lectures] (engl.) Online SLAM Kurs auf Basis von Python

[[Kategorie:Funknavigation]]
[[Kategorie:Geolokation]]
[[Kategorie:Robotik]]
[[Kategorie:Computer Vision]]