«

»

EKF-SLAM erklärt: Wie sieht ein Roboter die Welt?

Um eine detaillierte Karte der Umgebung zu erstellen, setzten wir auf einen EKF-SLAM Algorithmus. (Extendes Kalman Filter – Simultaneous Localization and Mapping)

Die Kartenerstellung mit EKF-SLAM ist eine Möglichkeit für Roboter, die Welt zu sehen. Um zu verstehen was das ist, sollte man jedoch zunächst einige Grundlagen betrachten.

Unser Roboter tastet mit zwei LIDAR-Scannern seine Umgebung 360° ab. Mit Hilfe dieser Sensoren können Objekte erkannt und Richtungsentscheidungen getroffen werden.

Allerdings kann der Roboter so nicht gezielt navigieren, sondern höchstens Objekten ausweichen.

Mit unserem Mapping Algorithmus speichern wir die Daten der Scanner und fügen sie Schritt für Schritt zu einer Karte zusammen. In dieser kann der Roboter sich dann lokalisieren und gezielt zu bestimmten Positionen fahren.

Das Erstellen einer Karte einer unbekannten Umgebung unter gleichzeitiger Lokalisierung des Roboters ist eines der großen Probleme in der Robotik. Die Lösungsansätze werden zu einer ganzen Klasse, den SLAM, Simultaneous Localisation And Mapping, Algorithmen,  also auf deutsch simultane Lokalisierung und Kartografierung zusammengefasst.

EKF-SLAM Karte über ein Satelitenbild gelegt

EKF-SLAM Karte über ein Satelitenbild gelegt. Rot ist die Route nach Android GPS und Weiß die Karte die der EKF-SLAm generiert hat. Diese ist deutlich besser als das Android GPS.

Für unseren Roboter Beteigeuze haben wir unterschiedliche SLAM-Algorithmen implementiert. Diese sind EKF-SLAM und ICP-SLAM, ersterer soll hier beispielhaft erklärt werden.

EKF-SLAM

Es handelt sich dabei um einen Kalman Filter. Dieser besteht aus einer Prädiktion und einer Korrektur. Die Prädiktion wird aus den Odometrie- bzw. Steuerdaten für die Bewegung generiert und die Korrektur aus den Lidardaten, welche eine Liste aus Entfernungen sind. Jedem Eintrag dieser Liste ist ein Winkel zugeordnet. Das bedeutet, dass die Lidar-Daten als Polarkoordinaten angesehen werden können. Der EKF-SLAM Ansatz bildet zunächst eine Liste aus den Differenzen der Werte der ersten Liste, so zu sagen eine Ableitung. Diese Ableitung hat den Vorteil, dass Ecken und Sprünge in den ursprünglichen Daten durch betragsmäßig große Werte in der Ableitung repräsentiert werden. Somit lassen sich also leicht Features aus den Lidardaten extrahieren. Für alle Werte, die als Feature klassifiziert wurden, wird der Punkt von Polarkoordinaten in Eulerkoordinaten transformiert. Diese Features werden Features, die aus der Karte extrahiert werden, zugeordnet und anschließend dem Kalman Filter als Korrektur gegeben.

Letztendlich generiert der EKF-SLAM eine Karte und eine Lokalisierung. Die Lokalisierung steht in unserer Implementation nur live zur Verfügung, wohingegen die Karten abgespeichert werden können. Auf den generierten Karten kann dann ein Planungsalgorithmus die Route bestimmen, die der Roboter fahren muss, um an sein Ziel zu gelangen.

Das Ergebnis einer solchen EKF-SLAM Lösung sieht man in der oberen Abbildung. Die rote Linie entspricht dem gefahrenen Weg, wie er durch das GPS bestimmt wurde. Offensichtlich ist diese nicht sehr genau und überschneidet sich sogar mit Gebäuden. In weiß ist die Karte eingezeichnet, welche der Roboter erstellt. Es wird lediglich alles als weiß markiert, was der Roboter sehen kann, und als befahrbar sieht.

Weitere 2D Karten ohne Satelitenbild. Darüber hinaus haben wir auch damit experimentiert 3D Karten der Werkhalle mithilfe der 2D Lokalisierung zu erstellen. Die Ergebnisse sind faszinierend und geben hoffentlich eine Einsicht wie ein Roboter die Welt mithilfe von SLAM sieht. Er sieht nicht nur, wo er sich gerade befindet, sondern generiert eine Karte und kennt seine aktuelle Position innerhalb dieser Karte.

Möchte man mehr über EKF-SLAM oder SLAM im allgemeinen erfahren, empfielt es sich einen Blick auf diese Vorlesung [1] an der Universität Freiburg zu werfen oder sich gleich die Liste aller Vorlesungen [2] zu dem Thema an zu schauen um die Grundlagen zu verstehen.

[1] http://ais.informatik.uni-freiburg.de/teaching/ws13/mapping/pdf/slam05-ekf-slam.pdf

[2] http://ais.informatik.uni-freiburg.de/teaching/ws13/mapping/pdf/