Simultaneous Localization and Mapping

Kernidee und Zweck

SLAM steht für „Simultaneous Localization and Mapping“, auf Deutsch „Simultane Positionsbestimmung und Kartierung“. Gemeint ist ein Verfahren der Robotik, bei dem ein mobiler Roboter gleichzeitig eine Karte seiner Umgebung erstellt und seine eigene räumliche Lage innerhalb dieser Karte schätzt.

SLAM ist wichtig für autonome Navigation: Ein Roboter soll Hindernisse erkennen, ihnen ausweichen und sich in einer Umgebung bewegen können, ohne dass ihm vorher schon eine fertige Karte oder eine sichere absolute Position bekannt ist.

Grundproblem der Orientierung

Ein grundlegendes Problem mobiler Roboter ist die Orientierung: Der Roboter muss wissen, wie seine Umgebung aussieht und wo er sich absolut befindet. Dazu kann er mit Sensoren wie Ultraschall, Kameras oder Lidar ausgestattet sein. Lidar ist ein Messverfahren, bei dem Entfernungen mit Licht beziehungsweise Laserstrahlen erfasst werden.

Mit solchen Sensoren kann die Umgebung dreidimensional aufgenommen werden. Dadurch kann sich ein Roboter lokal bewegen, Hindernisse rechtzeitig erkennen und umfahren.

Wenn zusätzlich die absolute Position des Roboters bekannt ist, zum Beispiel durch GPS-Sensoren, kann eine Karte einfacher aufgebaut werden. Der Roboter misst dann die relative Position möglicher Hindernisse zu sich selbst. Zusammen mit seiner bekannten eigenen Position kann er daraus die absolute Position der Hindernisse bestimmen und sie in die Karte eintragen.

Warum SLAM schwierig ist

Beim Menschen geschieht Orientierung in unbekannter Umgebung oft intuitiv: Informationen aus Sinnesorganen wie Augen, Haut, Ohren und Nase werden im Gehirn kombiniert. Dabei werden markante Merkmale erkannt, räumlich zueinander in Beziehung gesetzt und zu einer abstrakten Vorstellung eines Lageplans verarbeitet.

Bei mobilen technischen Systemen soll etwas Ähnliches erreicht werden. Ohne Vorwissen sollen aus Sensordaten einer mobilen Systemeinheit gleichzeitig eine Karte der Umgebung und die eigene Position und Orientierung bestimmt werden. Die Kartenerstellung heißt auf Englisch „mapping“, das Erkennen der eigenen Position einer mobilen Einheit „self-localisation“.

Die zentrale Schwierigkeit ist ein Henne-Ei-Problem: Für eine genaue Positionsbestimmung braucht man eine detaillierte Karte. Für eine detaillierte Karte braucht man aber die genaue Position der mobilen Systemeinheit. Karte und Position können deshalb nicht unabhängig voneinander bestimmt werden, sondern müssen gleichzeitig geschätzt werden.

Anwendungsbereiche

SLAM wird besonders dort benötigt, wo es für mobile Roboter keine vorhandenen Karten gibt und auch keine Möglichkeit besteht, die absolute Position sicher zu bestimmen, etwa über GPS. Ohne SLAM müsste vor dem Einsatz erst eine Karte erstellt werden. Das kann den Einsatz verzögern und verteuern.

Je nach Anwendungsgebiet ist es daher wichtig, dass ein Roboter eine neue Umgebung selbstständig erkunden, daraus eine Karte erstellen und diese später zur Navigation nutzen kann.

SLAM ist ein aktives Forschungsgebiet in der Robotik und in Computer Vision, also der maschinellen Verarbeitung und Auswertung visueller Informationen. Weltweit arbeiten zahlreiche Forschergruppen daran. Als Beispiel nennt der Artikel die Mars-Landefahrzeuge der NASA-Mission Mars Exploration Rover „Spirit“ und „Opportunity“, die mit solchen Verfahren betrieben werden.

Typischer Ablauf

Es gibt viele verschiedene SLAM-Ansätze, aber sie haben grundlegende Gemeinsamkeiten. Da ein Roboter normalerweise nur einen Teil seiner Umgebung sehen kann, wird die Karte inkrementell aufgebaut. Das bedeutet: Sie entsteht Schritt für Schritt.

Am Anfang gibt es keine Karte. Die aktuelle Position des Roboters definiert den Ursprung seines Koordinatensystems. Damit ist seine absolute Position zunächst trivial 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 er sich nicht zu weit bewegt hat, sieht er teilweise schon bekannte Bereiche wieder und vermisst zugleich neue Bereiche zum ersten Mal. Aus der Überlappung zwischen neuer Messung und bisheriger Karte kann seine Bewegung berechnet werden. Dadurch wird wieder eine absolute Position geschätzt, und die neue Messung kann in die Karte integriert werden.

Weil die Bewegungsbestimmung zwischen zwei Messungen nie exakt ist, weicht die berechnete Position des Roboters mit der Zeit immer stärker von der wahren Position ab. Dadurch kann auch die Qualität der Karte schlechter werden. Damit die Karte konsistent bleibt, muss der Algorithmus erkennen können, wenn ein bereits bekannter Teil der Umgebung erneut vermessen wird. Dies nennt man „Loop Closing“.

Verfahren und Datenassoziation

Der Artikel nennt mehrere SLAM-Verfahren und verwandte Techniken: EKF SLAM mit Extended Kalman Filter, SEIF als Sparse Extended Information Filter, UKF als Unscented Kalman Filter, SLAM mit Partikelfiltern, FastSLAM, grid-basierte Verfahren mit Rao-Blackwellisierten Partikelfiltern, DP-SLAM, Expectation-Maximization-Filter, graphbasierende Techniken wie GraphSLAM, TORO, HOG-Man und TreeMap sowie Relaxationstechniken und Smoothing-Techniken.

Eine wichtige Voraussetzung für die Lösung von SLAM ist die Lösung des Datenassoziationsproblems. Dabei muss ermittelt werden, welche Merkmale der Umgebung in verschiedenen Messungen miteinander korrespondieren, also dieselben Objekte oder Strukturen beschreiben. Das ist besonders schwierig, weil Merkmale nicht mit absoluter Sicherheit aus Sensordaten extrahiert werden können.

Scanmatching-Verfahren umgehen dieses Merkmalproblem teilweise, weil sie nicht einzelne Merkmale verwenden. Stattdessen berücksichtigen sie ganze Scans beziehungsweise Punktwolken und setzen anschließend graphbasierende Techniken ein.