Lokalisierung (Robotik)

Lokalisierung (auch Lokalisation, von lat. locus: der Ort) bezeichnet in der Robotik die Fähigkeit eines autonomen mobilen Roboters, seine Position in seiner Umgebung festzustellen. Lokalisierung ist einer der Kernpunkte der Navigation eines autonomen Roboters, da er nur auf dieser Grundlage den Weg zu seiner Zielposition bestimmen kann. Häufig genutzte Ansätze zur Lokalisierung sind Kreuzpeilung bekannter Landmarken oder Template-Matching der aktuellen Sensormessungen (auch Scan-Matching).

Die Position eines mobilen Roboters ist in den seltensten Fällen genau bekannt. In der Regel sorgt eine nicht bekannte Startposition oder Messungenauigkeiten während der Bewegung des Roboters für Unsicherheit bezüglich der Position des Roboters.

Das Problem der Lokalisierung ist mit dem Problem der Kartenbildung gekoppelt. Ohne eine Karte der Umgebung kann der Roboter seine Position in der Umgebung nicht bestimmen. Sind weder Position des Roboters noch die Karte der Umgebung bekannt, spricht man vom Simultaneous-Localization-and-Mapping-Problem.

Aufgabenstellung

Die Lokalisierung eines Roboters hat zur Aufgabe, dessen Pose in seiner Umgebung zu ermitteln. Die Pose beschreibt die Position und Orientierung des Roboters vollständig. Die Aufgabe der Lokalisierung kann in der Robotik in zwei wesentliche Fälle unterschieden werden.

Lokale Lokalisierung

Die lokale Lokalisierung (auch Position Tracking: Nachführen der Position) ist die einfachste Art der Lokalisation. Bei der lokalen Lokalisierung ist die aktuelle Pose des Roboters in seiner Umwelt bekannt. Im Folgenden muss bei Bewegung des Roboters die Pose kontinuierlich aktualisiert und anhand fortlaufender Messungen auf ihre Richtigkeit überprüft werden. Die Bewegung des Roboters wird dabei in der Regel anhand der Odometrie-Sensorik geschätzt und die Position entsprechend korrigiert. Aufgabe der lokalen Lokalisierung ist es dabei, die inkrementellen Fehler der Odometrie-Sensorik zu korrigieren. Ohne diese Korrektur würden sich geringe Fehler in der Odometrie mit der Bewegung des Roboters zu einem großen Positionsfehler aufsummieren.

Globale Lokalisierung

Bei der globalen Lokalisierung ist die aktuelle Pose des Roboters in seiner Umwelt nicht bekannt. Im Gegensatz zur lokalen Lokalisierung müssen hier keine kleinen Positionsfehler korrigiert werden, sondern aufgrund der unbekannten Position ist der Fehler der initial geschätzten Position beliebig groß. Die Aufgabenstellung ist damit deutlich schwieriger als die der lokalen Lokalisierung.

Der Roboter muss durch das Finden von signifikanten Umgebungsmerkmalen seine Position bestimmen. Ist die Pose bestimmt, kann der Roboter mit lokaler Lokalisierung fortfahren.

Kidnapped-Robot-Problem

Neben der lokalen und globalen Lokalisierung ist hinsichtlich der Robustheit der Lokalisierungsverfahren das Kidnapped-Robot-Problem (engl.: entführter Roboter) interessant. Hierbei ist die Position des Roboters anfangs bekannt, anschließend wird der Roboter in seiner Umgebung umpositioniert ohne darüber informiert zu werden. Der Roboter muss in diesem Fall eigenständig feststellen, dass die vormals erfolgreiche Lokalisierung hinfällig ist und erneut eine globale Lokalisierung durchgeführt werden muss. Feststellen kann der Roboter die Umpositionierung zum Beispiel über unplausible Sensormessungen, also Messungen, die der vormaligen Lokalisierung stark widersprechen.

Die Lösung des Kidnapped-Robot-Problems erlaubt eine Aussage über die Robustheit der Lokalisierung hinsichtlich großer Positionsfehler und der Fähigkeit des Roboters, sich nach grober Fehllokalisierung wieder eigenständig zurechtfinden zu können.

Posenrepräsentation

Ziel und Ausgabe der Lokalisierung ist die Pose des Roboter. Da die Pose abhängig von der Genauigkeit und Güte der vorliegenden Sensorinformationen kleine bis große Unsicherheiten aufweisen kann, ist eine Repräsentation der Pose geeignet, die diese Unsicherheiten und Mehrdeutigkeiten darstellen kann. Häufig werden dazu entweder Wahrscheinlichkeitsverteilungen oder Partikelwolken verwendet.

Roboterpose. Wahre Pose des Roboters $x$ und unsichere Pose des Roboters (blaue Ellipse), dargestellt als Wahrscheinlichkeitsverteilung (zweidimensionale Gaußverteilung).

Verfahren

Um die Position eines Roboters zu berechnen, gibt es verschiedene Ansätze. Sie beruhen alle auf der Fusionierung von Daten, die durch die Odometrie und weitere Sensoren des Roboters geliefert werden. Gebräuchliche Sensoren für autonome Roboter sind Ultraschallsensoren oder Laserscanner.

Scan-Matching Bei diesem Ansatz schätzt der Roboter seine Position zunächst anhand der Odometriedaten ab. Anschließend versucht er, sie zu verifizieren, bzw. zu korrigieren, indem er eine Position ermittelt, an der seine Sensoren die Informationen liefern würden, die er im Moment empfängt. Aus diesen beiden Positionsschätzungen wird die tatsächliche Position berechnet.

Probabilistische Ansätze Diese Ansätze verwenden Methoden der Wahrscheinlichkeitsrechnung zur Bestimmung einer Wahrscheinlichkeitsverteilung über alle möglichen Positionen, an denen der Roboter sich befinden kann.

Partikel-Filter

Partikel-Filter (auch Monte-Carlo-Lokalisierung oder Sequenzielle Monte-Carlo-Methode) erlauben die Lösung aller drei Lokalisierungsprobleme. Einfache Implementierungen erlauben die lokale und globale Lokalisierung mittels Partikelfiltern, mit wenigen Erweiterungen der Methode kann außerdem das Kidnapped-Robot-Problem gelöst werden.

Bei der Lösung mittels Partikelfiltern wird die Pose des Roboters über eine Partikelwolke repräsentiert. Jedes Partikel stellt eine mögliche Pose des Roboters dar. Über den Partikelfilter wird jedes Partikel, also jede dadurch repräsentierte Pose, auf ihre Plausibilität überprüft. Die Wahrscheinlichkeit plausibler Partikel wird heraufgesetzt, die Wahrscheinlichkeit wenig plausibler Partikel wird reduziert. Fallen Partikel unter einen bestimmten Wahrscheinlichkeits-Schwellwert, werden sie verworfen.

Sensorik

Sensorik, die für die Lokalisierung von Robotern eingesetzt wird, lässt sich mit Blick auf die Anwendung in drei Kategorien unterscheiden:

Messung der Eigenbewegung

Odometriesensorik und Kompass.

Messung der Entfernung zu Landmarken

Entfernungsmessung zu unterscheidbaren Objekten der Umgebung, beispielsweise mittels Ultraschallsensorik, Laserscanner oder Kameras.

Messung der absoluten Pose

Messung der Pose in globalen Koordinaten mittels zum Beispiel GPS-Empfänger, vergleichbarer Innenraumsensorik oder Radiobaken.

Literatur

• Juan D. Tardós, Jose A. Castellanos: Mobile Robot Localization and Map Building. A Multisensor Fusion Approach. Springer, Boston 2000, ISBN 978-0-7923-7789-4. 
• Sebastian Thrun, Wolfram Burgard, Dieter Fox: Probabilistic Robotics (Intelligent Robotics and Autonomous Agents). The Mit Press, Cambridge 2005, ISBN 978-0-262-20162-9.