Gleichzeitige Lokalisierung und Kartierung - Simultaneous localization and mapping

Der Gewinner der DARPA Grand Challenge 2005, STANLEY, führte SLAM als Teil seines autonomen Fahrsystems durch

Eine von einem SLAM-Roboter generierte Karte.

Simultane Lokalisierung und Abbildung ( SLAM ) ist das Rechenproblem der Erstellung oder Aktualisierung einer Karte einer unbekannten Umgebung, während gleichzeitig der Standort eines Agenten darin verfolgt wird. Obwohl dies zunächst ein Henne-Ei-Problem zu sein scheint, sind mehrere Algorithmen bekannt, um es zumindest annähernd in überschaubarer Zeit für bestimmte Umgebungen zu lösen. Beliebte Näherungsverfahren sind der Partikelfilter , der erweiterte Kalman-Filter , der Kovarianzschnittpunkt und GraphSLAM . SLAM-Algorithmen basieren auf Konzepten der Computergeometrieund Computer Vision und werden in der Roboternavigation , Roboterkartierung und Odometrie für Virtual Reality oder Augmented Reality verwendet .

SLAM-Algorithmen sind auf die verfügbaren Ressourcen zugeschnitten und zielen daher nicht auf Perfektion, sondern auf Betriebskonformität ab. Veröffentlichte Ansätze werden in selbstfahrenden Autos , unbemannten Luftfahrzeugen , autonomen Unterwasserfahrzeugen , planetaren Rovern , neueren Haushaltsrobotern und sogar im menschlichen Körper eingesetzt.

Mathematische Beschreibung des Problems

Bei einer Reihe von Kontrollen und Sensorbeobachtungen über diskrete Zeitschritte besteht das SLAM-Problem darin, eine Schätzung des Zustands des Agenten und eine Karte der Umgebung zu berechnen . Alle Größen sind normalerweise probabilistisch, daher besteht das Ziel darin, Folgendes zu berechnen: ${\displaystyle u_{t}}$${\displaystyle o_{t}}$${\displaystyle t}$${\displaystyle x_{t}}$${\displaystyle m_{t}}$

${\displaystyle P(m_{t+1},x_{t+1}|o_{1:t+1},u_{1:t})}$

Die Anwendung der Bayes-Regel gibt einen Rahmen für die sequentielle Aktualisierung der Position nach hinten, eine Karte und eine Übergangsfunktion gegeben . ${\displaystyle P(x_{t}|x_{t-1})}$

${\displaystyle P(x_{t}|o_{1:t},u_{1:t},m_{t})=\sum_{m_{t-1}}P(o_{t}|x_{ t},m_{t},u_{1:t})\sum _{x_{t-1}}P(x_{t}|x_{t-1})P(x_{t-1}|m_ {t},o_{1:t-1},u_{1:t})/Z}$

Ebenso kann die Karte sequentiell aktualisiert werden durch

${\displaystyle P(m_{t}|x_{t},o_{1:t},u_{1:t})=\sum_{x_{t}}\sum_{m_{t}}P( m_{t}|x_{t},m_{t-1},o_{t},u_{1:t})P(m_{t-1},x_{t}|o_{1:t-1 },m_{t-1},u_{1:t})}$

Wie bei vielen Inferenzproblemen können die Lösungen für das Zusammenführen der beiden Variablen zu einer lokalen optimalen Lösung durch abwechselnde Aktualisierungen der beiden Annahmen in Form eines Erwartungs-Maximierungs-Algorithmus gefunden werden .

Algorithmen

Statistische Techniken, die verwendet werden, um die obigen Gleichungen anzunähern, umfassen Kalman-Filter und Partikelfilter (auch bekannt als Monte-Carlo-Verfahren ). Sie liefern eine Schätzung der Posterior-Wahrscheinlichkeitsfunktion für die Pose des Roboters und für die Parameter der Karte. Verfahren, die das obige Modell unter Verwendung von Kovarianzschnittpunkten konservativ annähern, können das Vertrauen auf Annahmen der statistischen Unabhängigkeit vermeiden, um die algorithmische Komplexität für groß angelegte Anwendungen zu reduzieren. Andere Näherungsverfahren erzielen eine verbesserte Recheneffizienz, indem sie einfache Darstellungen der Unsicherheit mit begrenzten Bereichen verwenden.

Set-Membership-Techniken basieren hauptsächlich auf Intervall-Constraint-Propagation . Sie liefern ein Set, das die Pose des Roboters und eine Set-Approximation der Karte umschließt. Bundle Adjustment , und allgemeiner Maximum a posteriori Estimation (MAP), ist eine weitere beliebte Technik für SLAM unter Verwendung von Bilddaten, die gemeinsam Posen und Landmarkenpositionen schätzt, die Kartentreue erhöht und in kommerzialisierten SLAM-Systemen wie Googles ARCore verwendet wird , das ihre . ersetzt vorheriges Augmented-Reality- Projekt ' Tango '. MAP-Schätzer berechnen die wahrscheinlichste Erklärung der Roboterposen und der Karte anhand der Sensordaten, anstatt zu versuchen, die gesamte Posterior-Wahrscheinlichkeit zu schätzen.

Neue SLAM-Algorithmen bleiben ein aktives Forschungsgebiet und werden oft von unterschiedlichen Anforderungen und Annahmen über die Arten von Karten, Sensoren und Modellen angetrieben, wie unten beschrieben. Viele SLAM-Systeme können als Kombinationen von Auswahlmöglichkeiten aus jedem dieser Aspekte betrachtet werden.

Kartierung

Topologische Karten sind ein Verfahren zur Umgebungsdarstellung, das die Konnektivität (dh Topologie ) der Umgebung erfasst, anstatt eine geometrisch genaue Karte zu erstellen. Topologische SLAM-Ansätze wurden verwendet, um globale Konsistenz in metrischen SLAM-Algorithmen zu erzwingen.

Im Gegensatz dazu verwenden Rasterkarten Arrays (normalerweise quadratische oder hexagonale) diskretisierter Zellen, um eine topologische Welt darzustellen und Rückschlüsse darauf zu ziehen, welche Zellen besetzt sind. Typischerweise wird angenommen, dass die Zellen statistisch unabhängig sind, um die Berechnung zu vereinfachen. Unter dieser Annahme werden 1 gesetzt, wenn die Zellen der neuen Karte mit der Beobachtung am Standort übereinstimmen, und 0, wenn sie inkonsistent sind. ${\displaystyle P(m_{t}|x_{t},m_{t-1},o_{t})}$${\displaystyle o_{t}}$${\displaystyle x_{t}}$

Moderne selbstfahrende Autos vereinfachen das Kartierungsproblem meist fast zunichte, indem sie die im Voraus gesammelten hochdetaillierten Kartendaten umfassend nutzen. Dies kann Kartenanmerkungen auf der Ebene der Markierungsstellen einzelner weißer Liniensegmente und Bordsteine ​​auf der Straße umfassen. Ortsbezogene visuelle Daten wie Googles StreetView können auch als Teil von Karten verwendet werden. Im Wesentlichen vereinfachen solche Systeme das SLAM-Problem zu einer einfacheren Lokalisierungsaufgabe und ermöglichen möglicherweise, dass sich bewegende Objekte wie Autos und Personen nur zur Laufzeit in der Karte aktualisiert werden.

Sensorik

Akkumulierte registrierte Punktwolke von LIDAR SLAM.

SLAM wird immer mehrere verschiedene Sensortypen verwenden, und die Leistungsfähigkeit und Grenzen verschiedener Sensortypen waren ein wichtiger Treiber für neue Algorithmen. Statistische Unabhängigkeit ist die zwingende Voraussetzung, um metrische Verzerrungen und Rauschen bei Messungen zu bewältigen. Unterschiedliche Sensortypen führen zu unterschiedlichen SLAM-Algorithmen, deren Annahmen für die Sensoren am besten geeignet sind. Im Extremfall liefern Laserscans oder visuelle Merkmale Details zu vielen Punkten innerhalb eines Bereichs. Manchmal ist das Rendern von SLAM-Inferenzen unnötig, da Formen in diesen Punktwolken bei jedem Schritt über die Bildregistrierung einfach und eindeutig ausgerichtet werden können . Im Gegensatz dazu sind taktile Sensoren äußerst spärlich, da sie nur Informationen über Punkte in unmittelbarer Nähe des Agenten enthalten, sodass sie starke Vorgängermodelle benötigen, um in rein taktilem SLAM zu kompensieren. Die meisten praktischen SLAM-Aufgaben liegen irgendwo zwischen diesen visuellen und taktilen Extremen.

Sensormodelle lassen sich grob in Landmarken-basierte und Rohdaten-Ansätze unterteilen. Landmarks sind eindeutig identifizierbare Objekte auf der Welt, deren Standort von einem Sensor geschätzt werden kann – wie zum Beispiel WLAN-Zugangspunkte oder Funkfeuer. Rohdatenansätze gehen nicht davon aus, dass Landmarken identifiziert werden können, sondern modellieren direkt als Funktion des Standorts. ${\displaystyle P(o_{t}|x_{t})}$

Optische Sensoren können eindimensionale (Einzelstrahl) oder 2D- (Sweep) Laser-Entfernungsmesser , 3D High Definition LiDAR, 3D Flash LIDAR , 2D oder 3D Sonarsensoren und eine oder mehrere 2D Kameras sein . Seit 2005 wird intensiv an VSLAM (Visual SLAM) geforscht, bei dem hauptsächlich visuelle (Kamera-)Sensoren verwendet werden, da Kameras, beispielsweise in mobilen Geräten, zunehmend allgegenwärtig sind. Visuelle und LIDAR- Sensoren sind informativ genug, um in vielen Fällen die Extraktion von Orientierungspunkten zu ermöglichen. Andere neuere Formen von SLAM umfassen taktiles SLAM (Erkennung nur durch lokale Berührung), Radar-SLAM, akustisches SLAM und WLAN-SLAM (Erkennung anhand der Stärken nahegelegener WLAN-Zugangspunkte). Neuere Ansätze verwenden quasi-optisches drahtloses Ranging für Multi-Lateration ( RTLS ) oder Multi-Angulation in Verbindung mit SLAM als Tribut an unberechenbare drahtlose Maßnahmen. Eine Art SLAM für menschliche Fußgänger verwendet eine auf dem Schuh montierte Trägheitsmesseinheit als Hauptsensor und beruht darauf, dass Fußgänger in der Lage sind, Wände zu umgehen, um automatisch Grundrisse von Gebäuden durch ein Indoor-Positionierungssystem zu erstellen .

Für einige Außenanwendungen wurde SLAM aufgrund hochpräziser differentieller GPS- Sensoren fast vollständig beseitigt . Aus SLAM-Perspektive können diese als Positionssensoren angesehen werden, deren Wahrscheinlichkeiten so hoch sind, dass sie die Inferenz vollständig dominieren. GPS-Sensoren können jedoch gelegentlich ausfallen oder ganz ausfallen, z. B. in Zeiten militärischer Konflikte, die für einige Robotikanwendungen von besonderem Interesse sind.

Kinematikmodellierung

Der Begriff steht für die Kinematik des Modells, die normalerweise Informationen über Aktionsbefehle enthält, die einem Roboter gegeben werden. Als Teil des Modells ist die Kinematik des Roboters enthalten, um die Einschätzung der Wahrnehmung unter Bedingungen von Eigen- und Umgebungsgeräuschen zu verbessern. Das dynamische Modell gleicht die Beiträge verschiedener Sensoren, verschiedener Teilfehlermodelle aus und enthält schließlich in einer scharfen virtuellen Darstellung als Karte den Standort und die Fahrtrichtung des Roboters als Wahrscheinlichkeitswolke. Mapping ist die endgültige Darstellung eines solchen Modells, die Karte ist entweder eine solche Darstellung oder der abstrakte Begriff für das Modell. ${\displaystyle P(x_{t}|x_{t-1})}$

Bei 2D-Robotern wird die Kinematik meist durch eine Mischung aus Rotations- und „Vorwärts“-Befehlen vorgegeben, die mit zusätzlichem Motorgeräusch umgesetzt werden. Unglücklicherweise ist die durch unabhängiges Rauschen in Winkel- und Linearrichtung gebildete Verteilung nicht-gaußförmig, wird jedoch oft durch eine Gaußsche Verteilung angenähert. Ein alternativer Ansatz besteht darin, den kinematischen Begriff zu ignorieren und nach jedem Befehl Odometriedaten von Roboterrädern zu lesen – solche Daten können dann als einer der Sensoren anstatt als Kinematik behandelt werden.

Akustisches SLAM

Eine Erweiterung des gemeinsamen SLAM-Problems wurde auf den akustischen Bereich angewendet, wo Umgebungen durch die dreidimensionale (3D) Position von Schallquellen repräsentiert werden, genannt. Frühe Implementierungen dieser Technik haben Richtungs-of-Arrival (DoA)-Schätzungen des Schallquellenortes verwendet und beruhen auf Haupttechniken der Schalllokalisierung, um Quellenorte zu bestimmen. Ein Beobachter oder Roboter muss mit einem Mikrofonarray ausgestattet sein, um die Verwendung von Acoustic SLAM zu ermöglichen, damit die DoA-Funktionen richtig geschätzt werden. Acoustic SLAM hat die Grundlage für weitere Studien im Bereich der akustischen Szenenabbildung gelegt und kann eine wichtige Rolle bei der Mensch-Roboter-Interaktion durch Sprache spielen. Um mehrere und gelegentlich intermittierende Schallquellen abzubilden, verwendet ein akustisches SLAM-System Grundlagen der Random-Finite-Set-Theorie, um das unterschiedliche Vorhandensein akustischer Orientierungspunkte zu handhaben. Die Natur der akustisch abgeleiteten Merkmale macht Acoustic SLAM jedoch anfällig für Probleme von Nachhall, Inaktivität und Geräuschen in einer Umgebung.

Audiovisuelles SLAM

Audio-Visual SLAM wurde ursprünglich für die Mensch-Roboter-Interaktion entwickelt und ist ein Framework, das die Verschmelzung von Orientierungsmerkmalen bietet, die sowohl aus den akustischen als auch aus den visuellen Modalitäten in einer Umgebung gewonnen werden. Die menschliche Interaktion ist durch Merkmale gekennzeichnet, die nicht nur in der visuellen Modalität, sondern auch in der akustischen Modalität wahrgenommen werden; Daher müssen SLAM-Algorithmen für menschzentrierte Roboter und Maschinen beide Funktionen berücksichtigen. Ein audiovisuelles Framework schätzt und kartiert Positionen menschlicher Orientierungspunkte durch die Verwendung von visuellen Merkmalen wie der menschlichen Haltung und Audiomerkmalen wie der menschlichen Sprache und verbindet die Überzeugungen für eine robustere Karte der Umgebung. Für Anwendungen in der mobilen Robotik (z. B. Drohnen, Serviceroboter) ist es sinnvoll, leichte Geräte mit geringem Stromverbrauch wie monokulare Kameras oder mikroelektronische Mikrofonarrays zu verwenden. Audiovisuelles SLAM kann auch eine komplementäre Funktion solcher Sensoren ermöglichen, indem das enge Sichtfeld, Merkmalsverdeckungen und optische Beeinträchtigungen kompensiert werden, die bei leichten visuellen Sensoren mit dem vollen Sichtfeld und ungehinderten Merkmalsdarstellungen inhärent sind Audiosensoren. Auch die Anfälligkeit von Audiosensoren für Nachhall, Inaktivität von Schallquellen und Rauschen kann durch die Fusion von Orientierungswerten aus der visuellen Modalität entsprechend kompensiert werden. Die komplementäre Funktion zwischen den Audio- und visuellen Modalitäten in einer Umgebung kann sich als wertvoll für die Entwicklung von Robotik und Maschinen erweisen, die vollständig mit menschlicher Sprache und menschlicher Bewegung interagieren.

Kollaboratives SLAM

Kollaboratives SLAM kombiniert Bilder von mehreren Robotern oder Benutzern, um 3D-Karten zu generieren.

Verschieben von Objekten

Nicht statische Umgebungen, wie solche, die andere Fahrzeuge oder Fußgänger enthalten, stellen weiterhin Forschungsherausforderungen dar. SLAM mit DATMO ist ein Modell, das sich bewegende Objekte ähnlich wie der Agent selbst verfolgt.

Schlaufenverschluss

Schleifenschließung ist das Problem, einen zuvor besuchten Ort zu erkennen und die Überzeugungen entsprechend zu aktualisieren. Dies kann ein Problem sein, da Modell- oder Algorithmusfehler dem Standort niedrige Vorwerte zuordnen können. Typische Schleifenschließverfahren wenden einen zweiten Algorithmus an, um eine Art von Sensormessähnlichkeit zu berechnen und die Positionsprioritäten neu einzustellen, wenn eine Übereinstimmung erkannt wird. Dies kann beispielsweise durch Speichern und Vergleichen von Wortsackvektoren von SIFT- Merkmalen von jedem zuvor besuchten Ort erfolgen.

Erkundung

"Active SLAM" untersucht das kombinierte Problem von SLAM mit der Entscheidung, wohin man sich als nächstes bewegen soll, um die Karte so effizient wie möglich zu erstellen. Die Notwendigkeit einer aktiven Exploration ist besonders bei spärlichen Erfassungsregimen wie taktilem SLAM ausgeprägt. Aktives SLAM wird im Allgemeinen durchgeführt, indem die Entropie der Karte unter hypothetischen Aktionen angenähert wird . "Multi Agent SLAM" erweitert dieses Problem auf den Fall mehrerer Roboter, die sich koordinieren, um optimal zu erkunden.

Biologische Inspiration

In den Neurowissenschaften scheint der Hippocampus an SLAM-ähnlichen Berechnungen beteiligt zu sein, wodurch Zellen entstehen und er die Grundlage für bioinspirierte SLAM-Systeme wie RatSLAM bildet.

Implementierungsmethoden

Verschiedene SLAM-Algorithmen sind in den Open-Source- Roboter-Betriebssystembibliotheken (ROS) implementiert , die oft zusammen mit der Point Cloud Library für 3D-Karten oder visuelle Funktionen von OpenCV verwendet werden .

EKF SLAM

In der Robotik ist EKF SLAM eine Klasse von Algorithmen, die den erweiterten Kalman-Filter (EKF) für SLAM verwendet. Typischerweise sind EKF SLAM-Algorithmen merkmalsbasiert und verwenden den Maximum-Likelihood-Algorithmus für die Datenassoziation. In den 1990er und 2000er Jahren war EKF SLAM bis zur Einführung von FastSLAM die De-facto-Methode für SLAM .

Mit dem EKF verbunden ist die Annahme des Gaußschen Rauschens, die die Fähigkeit des EKF SLAM, mit Unsicherheit umzugehen, erheblich beeinträchtigt. Bei größerer Unsicherheit im Posterior versagt die Linearisierung im EKF.

GraphSLAM

In der Robotik ist GraphSLAM ein SLAM-Algorithmus, der spärliche Informationsmatrizen verwendet, die durch Generieren eines Faktorgraphen von Beobachtungsinterdependenzen erzeugt werden (zwei Beobachtungen sind miteinander verbunden, wenn sie Daten über denselben Orientierungspunkt enthalten).

Geschichte

Eine bahnbrechende Arbeit in SLAM ist die Forschung von RC Smith und P. Cheeseman über die Darstellung und Schätzung von räumlicher Unsicherheit im Jahr 1986. Weitere Pionierarbeiten auf diesem Gebiet wurden Anfang der 1990er Jahre von der Forschungsgruppe von Hugh F. Durrant-Whyte durchgeführt . die zeigte, dass Lösungen für SLAM im unendlichen Datenlimit existieren. Dieser Befund motiviert die Suche nach Algorithmen, die rechnerisch handhabbar sind und sich der Lösung annähern. Das Akronym SLAM wurde in der Arbeit „Localization of Autonomous Guided Vehicles“ geprägt, die erstmals 1995 in der ISR erschien .

Die selbstfahrenden STANLEY- und JUNIOR-Autos, angeführt von Sebastian Thrun , gewannen die DARPA Grand Challenge und wurden in den 2000er Jahren Zweiter bei der DARPA Urban Challenge und beinhalteten SLAM-Systeme, die SLAM weltweit bekannt machten. SLAM-Implementierungen für den Massenmarkt finden sich jetzt in Consumer-Roboter-Staubsaugern.

Siehe auch

Verweise

Externe Links

• Probabilistic Robotics von Sebastian Thrun , Wolfram Burgard und Dieter Fox mit einem klaren Überblick über SLAM.
• SLAM für Dummies (Ein Tutorial-Ansatz zur gleichzeitigen Lokalisierung und Kartierung) .
• Andrew Davison Forschungsseite am Department of Computing , Imperial College London über SLAM mit Vision.
• openslam.org Eine gute Sammlung von Open-Source-Code und Erklärungen zu SLAM.
• Matlab Toolbox von Kalman Filtering angewendet auf die gleichzeitige Lokalisierung und Kartierung von Fahrzeugen, die sich in 1D, 2D und 3D bewegen.
• FootSLAM-Forschungsseite im DLR mit den dazugehörigen Wifi SLAM- und PlaceSLAM-Ansätzen.
• SLAM-Vortrag Online-SLAM-Vortrag auf Basis von Python.