SLAM

Kurzfassung / Summary

SLAM – Navigationskonzepte f¨ ur autonome

Fahrzeuge

Die Arbeit widmet sich mit dem ” Synchronous Localization and Map- ping“(kurz SLAM) einer grundlegenden Problematik der autonomen Robo- ter – Navigation. Neben der Problematik selbst werden einige Konzepte zur L¨ osung des Problems vorgestellt. Das grundlegende Standardkonzept des

EKF - SLAMs wird detaillierter behandelt. Diese genauere Analyse zielt auf

eine Implementierung auf dem ” Artificial Intelligence Concept Car“ (kurz AICC) Projektprototypen der im Projektjahr aus einer vollst¨ andigen Uber- arbeitung des TTcars entstanden ist. Die Implementierung dieses Navigati- ons - Konzepts wird in dieser Arbeit ebenso dokumentiert, wie auch die Er- kenntnisse und etwaige Weiterf¨ uhrungs- und Verbesserungsvorschl¨ age f¨ ur weiterf¨ uhrende Projekte.

Robotik, Navigation, SLAM, Kalman Filter, Extendet Kalman Filter, RANSAC, AICC

SLAM – Navigation - Concepts For

Autonomous Vehicles

Synchronous Localization and Mapping (SLAM) is a central problem in autonomous navigation. There is a wide range of methods to deal with this problem. After reviewing various possible solutions, this thesis discusses the choice of the method EKF – SLAM for the development of the Artificial Intelligence Concept Car (AICC) which was built in the Bachelor’s project. The discussion includes the implementation of this navigation concept and the evaluation of the results. Some suggestions for improvements and future projects are outlined.

Robotic, Navigation, SLAM, Kalman Filter, Extendet Kal- man Filter, RANSAC, AICC

  Inhaltsverzeichnis  

2  Inhaltsverzeichnis  

1  Einleitung  3

2   

5  uber SLAM Uberblick  

2.1  Gemeinsame Begriffe  5

2.1.2  Landmarken  6

2.3  EKF SLAM  10

2.4  FAST SLAM  11

2.5  Weitere Entwicklungen  12

13  3 EKF SLAM auf AICC  

3.1  Landmarkenfindung  13

3.1.1  RANSAC zur Wanderkennung  13

3.1.2  Ermittlung der Eckpunkte  18

3.2  Extended Kalman Filter  18

3.2.1  Aufbau und Inhalt der Filtermatrizen  19

3.2.2  Vorhersage (state prediction)  22

3.2.3  Datenassoziation  23

3.2.4  Korrektur (state correction)  24

3.2.5  Hinzuf ugen neuer Landmarken  26

  Abbildungsverzeichnis  31

  Literatur und Quellenverzeichnis  32

2

KAPITEL 1. EINLEITUNG

1 Einleitung

Ferngesteuerte Fahrzeuge und Maschinen sind heutzutage keine Seltenheit mehr, ebenso wenig exotisch sind Maschinen, die einem genau vordefinier- tem Programm folgen und damit auch Fahrzeuge die einem gewissen ge- nau abgesteckten Pfad folgen. Ferngesteuerte Systeme ben¨ otigen eine zu- verl¨ assige Verbindung und die Aufmerksamkeit eines Benutzers, und Skript

- gesteuerte Fahrzeuge sind sehr unflexibel gegen Ver¨ anderungen. In beiden F¨ allen wird das Problem: ” Wie komme ich von Punkt A nach Punkt B“ nicht vom System selbst gel¨ ost, sondern im Vorhinein durch den, der den L¨ osungsweg beschrieben hat (Skript) oder durch denjenigen der die Fern- steuerung bedient. Ein geskriptetes Verhalten scheidet also dann aus, wenn das Umfeld in dem sich das Fahrzeug nicht genau bekannt bzw. st¨ andigen ¨

Anderungen unterworfen ist und eine Fernsteuerung dann, wenn eine Re- mote - Verbindung zu teuer bzw. schwierig zu realisieren (z.B. in Bergwer- ken, unter Wasser) oder zu langsam(z.B. auf dem Mars) ist oder wenn es nicht zweckm¨ aßig ist, jede Aktion von einem Benutzer abh¨ angig zu ma- chen(z.B. Staubsauger - Roboter).

Die n¨ otige Flexibilit¨ at erh¨ alt man erst dann, wenn das System in der La- ge ist, das Problem: ” Wie komme ich von Punkt A nach Punkt B“ selbst zu l¨ osen. Dieses Problem enth¨ alt zwei verschiedene Problemstellungen. Ein Problem ist das finden m¨ oglicher Pfade(engl. pathfinding), die Routenpla- nung, die mit diversen Wegfindungsalgorithmen (z.B. A* und D* Algorith- mus) behandelt werden kann.

Die zweite Problemstellung ergibt sich aus den Voraussetzungen dieser Algorithmen, da sie ein konsistentes Bild der Umgebung ben¨ otigen, die eigene Position darin und die Position des Zielorts. Erschwerend kommt hinzu, dass das sonst omnipr¨ asente GPS (Global Position System) nur bei freier Sichtverbindung zu gen¨ ugend Satelliten verwendbar ist. Das ist z.B. in Geb¨ auden nicht der Fall und bedeutet, dass die Positionierung oft auch ohne dieses System auskommen muss.

Ein autonomes mobiles Robotersystem muss also, um navigieren zu k¨ on- nen, ¨ uber eine Karte seines Umfelds verf¨ ugen und seine Position darauf be- stimmen k¨ onnen. Sollte keine Karte (oder eine veraltete, fehlerhafte Karte) vorhanden sein, muss ein wirklich autonomes System in der Lage sein, Kar- tenmaterial selbst zu erstellen und zu aktualisieren. Um jedoch mit den Informationen aus der Sensorauswertung brauchbare Karten zeichnen zu k¨ onnen muss das System wissen an welche Stelle der Karte zum Beispiel das neu erfasste Hindernis einzutragen ist. Somit muss dass System auch

3

KAPITEL 1. EINLEITUNG 1.1. PROBLEMSTELLUNG

w¨ ahrend des Erstellens und Wartens der Karte immer seine aktuelle Posi- tion kennen. Diese Problemstellung wird in Fachkreisen meist mit SLAM (Simultaneous Localization And Mapping) bezeichnet.

1.1 Problemstellung

Das Projektfahrzeug ” Artificial Intelligence Concept Car“ (kurz AICC) soll, um seinem Namen einigermaßen gerecht zu werden, in der Lage sein sich selbstst¨ andig in Geb¨ auden zurecht zu finden, Wege zu gegebenen Zielen finden und ein Abbild seiner Umgebung zu erzeugen. Da f¨ ur diesen Robo- ter gilt, dass kein GPS zur Verf¨ ugung steht, ist eine L¨ osung des SLAM - Problems ein sehr wichtiger Schritt zur Umsetzung der vorgegebenen Ziele.

4

KAPITEL 2. ¨ UBERBLICK ¨

2 ¨

Uberblick ¨ uber SLAM

Zuerst nochmal der Hinweis, dass SLAM keinesfalls einen speziellen Algo- rithmus betitelt, sondern die Problemstellung an sich. Weiters haben Pro- bleme meist an sich, dass es mehr als eine m¨ ogliche L¨ osung gibt. Es gibt ei- ne Vielzahl von Konzepten mit unterschiedlichsten Implementierungen, die sich durch die eingesetzte Sensorik und das jeweilige Umfeld unterscheiden, in dem der Roboter navigieren soll. Um sich nicht in Sensorik - Konzepten zu verlieren werden nur einige Beispiele f¨ ur verschiedene M¨ oglichkeiten, bez¨ uglich der Zusammenf¨ uhrung und Verarbeitung der Sensorinformation genannt.

2.1 Gemeinsame Begriffe

Die verschiedene Navigationskonzepte bauen oft auf den selben Grundbe- griffen auf, deshalb ist es zielf¨ uhrend diese Begriffe zu Beginn zu erl¨ autern. Dieselben Begriffe werden auch in der Literatur [Mon] [Blas] beschrieben. Auf die folgenden Begriffe wird auch bei der Beschreibung der Konzepte zur¨ uckgegriffen.

2.1.1 Inertialnavigation (Dead Reckoning)

Der Begriff der Inertialnavigation(engl. dead reckoning), oder auch Koppel- navigation, beschreibt die Positionsbestimmung relativ zu einer zuvor be- stimmten Position(engl. fix) anhand des Kurses, der gefahrenen Geschwin- digkeit und der Fahrzeit. Dieses Verfahren wurde vor der Einf¨ uhrung des

GPS in der Schifffahrt und in Flugzeugen eingesetzt, wobei der Kurs an-

hand eines Kompasses bestimmt wurde und f¨ ur die Geschwindigkeitser- mittlung anhand eines Fahrtmessers mussten auch Wind und Str¨ omung ber¨ ucksichtigt werden. Heute wird es in der Raumfahrt eingesetzt, dort je- doch werden Beschleunigungssensoren ausgewertet. Weitere Anwendungen finden sich Flugzeugen, die auf diese Weise kurzzeitig die Position zwi- schen GPS - St¨ utzstellen bestimmen und bei fortschrittlicheren Navigati- ons - Systemen die so einen kurzzeitigen Ausfall oder Genauigkeitsverlust durch Tunnel oder Geb¨ aude ¨ uberbr¨ ucken. Diese Positionsbestimmung an- hand der Bewegung von einem vorher bestimmten Punkt ist ein wichtiger Bestandteil in vielen SLAM -Konzepten. In der Robotik werden fallweise elektronische Kompasse, Drehraten - Sensoren oder auch eine Kombination

5

KAPITEL 2. ¨ UBERBLICK ¨

aus beidem eingesetzt um die Bewegungsrichtung zu bestimmen. Wegstre- cke oder Geschwindigkeit werden meist aus den Inkrementalgebern der An- triebsmotoren ermittelt. Auf diese Weise l¨ asst sich mit ausreichend genauer Sensorik bereits f¨ ur gewisse Anwendungen eine gen¨ ugend genaue Naviga- tion realisieren.

Die gesamte Methodik beinhaltet jedoch einen großen Nachteil, da sich die Fehler der einzelnen Messungen aufsummieren. Ein Fehler der Inkre- mentalgeber - Auswertung von beispielsweise 1% der gefahrenen Wegstre- cke kann bereits zur folge haben, dass ein Roboter, der sich 10m von einer Wand weg bewegt und dann wieder zur¨ uck, 20cm hinter der Wand ste- hen bleiben w¨ urde. Kompasse sind naturgem¨ aß anf¨ allig gegen magnetische St¨ oreinfl¨ usse, w¨ ahrend Drehraten - Sensoren sogar eine zeitabh¨ angige Ab- weichung haben. So w¨ urde ein Roboter sogar am Stand mit der Zeit jegli- che Kenntniss ¨ uber die Ausrichtung verlieren. Um also noch einmal auf die Schiffsnavigation zur¨ uckzukommen, dort stellte man daf¨ ur an gef¨ ahrlichen K¨ usten Leuchtt¨ urme auf. Die Leuchtt¨ urme dienten als Anhaltspunkt um pr¨ azise zwischen gef¨ ahrlichen Riffen hindurch schiffen zu k¨ onnen. Das Prin- zip des Leuchtturms f¨ uhrt geradewegs zum n¨ achsten wichtigen Begriff in der Roboter - Navigation.

2.1.2 Landmarken

Ein Leuchtturm ist tats¨ achlich ein gutes Beispiel f¨ ur eine Landmarke, denn unter Landmarken versteht man Orientierungspunkte in der Umgebung die verwendet werden, um eine genauere Positionsbestimmung zu realisieren. Anhand der Idee des Leuchtturms k¨ onnen die Voraussetzungen erl¨ autert werden, die eine Landmarke erf¨ ullen muss, um f¨ ur SLAM einsetzbar zu sein. Man stelle sich vor, dass ein Schiff sich einem gef¨ ahrlichen Riff n¨ ahert und dieses durch Orientierung am Leuchtturm umschiffen will, doch der Leuchtturm befindet sich pl¨ otzlich an einer anderen Stelle. Der Navigator geht davon aus, dass dieser Leuchtturm an der richtigen Stelle steht und kann sich auch nicht vom Gegenteil ¨ uberzeugen, weil er außer dem Licht in der Ferne nichts sieht(siehe Abbildung (2.1)). So wird diese Fahrt wohl ein schreckliches Ende haben, weil das Schiff m¨ oglicherweise zielsicher auf das Riff zusteuert. Ebenso k¨ onnte es ausgehen, wenn das Licht des Leuchtturms erl¨ oschen ist und der Navigator keinen Anhaltspunkt hat.

Der Versuch zwei Leuchtt¨ urme aufzustellen, falls das Licht eines Turms erlischt, k¨ onnte den Navigator jedoch in die n¨ achste Zwickm¨ uhle f¨ uhren. Angenommen einer der beiden Leuchtt¨ urme f¨ allt aus, dann kann der Navi- gator m¨ oglicherweise nicht feststellen, welchen der beiden er noch sieht und navigiert ins Unheil, weil er die falschen Position verwendet. Diese T¨ urme m¨ ussten weit genug voneinander entfernt sein, dass er sie mit Hilfe seiner

6

KAPITEL 2. ¨ UBERBLICK ¨

Abbildung 2.1: Falsche Landmarkenpositionen bewirken Positionsfehler

vorherigen Kursberechnungen unterscheiden kann.

Anhand der Rolle des Leuchtturms in der Seefahrt erarbeitet muss eine brauchbare Landmarke also folgende Vorgaben erf¨ ullen:

• Die Position der Landmarke muss genau genug bekannt sein und darf sich nicht zuf¨ allig ver¨ andern, sie sollte station¨ ar sein

• Es m¨ ussen ausreichend Landmarken auffindbar sein um die Position genau genug ermitteln zu k¨ onnen

• Die Landmarke muss eindeutig und ohne Verwechslungen wieder- erkennbar und wiederauffindbar sein An sich ist es egal und von Implementierung zu Implementierung ver- schieden, was genau als Landmarke verwendet wird, solange die oben ge- nannten Bedingungen erf¨ ullt werden. Es kann sich je nach Anwendung und eingesetzter Sensorik um W¨ ande, Ecken, bestimmte Muster in Kamera- bildern, Funkfeuer (z.B. auch umliegende WLAN - Access Points) oder bei Nostalgikern sogar tats¨ achlich um Leuchtt¨ urme handeln.

2.1.3 Kalman Filter

Folgt man dem roten Faden, dann stellt sich die Frage, wie Informationen aus dem Dead Reckoning und aus den Landmarken zusammengef¨ uhrt wer- den sollen, um die jeweiligen St¨ arken nutzen zu k¨ onnen. Zu diesem Zweck werden aufw¨ andige Filteralgorithmen verwendet, die meist in irgendeiner Form auf dem sogenannten Kalman Filter aufbauen. Hierbei handelt es sich um einen adaptiven Filteralgorithmus der bereits 1960 von Rudolf Emil K´ alm´ an in [Kal] publiziert wurde. Dieses Filter kann zur Zustandser- mittung (engl. state estimation) linearer Systeme verwendet werden, die durch starkes gausssches weißes Rauschen nur schwer beobachtbar sind. Das Kalman Filter l¨ asst sich gut rekursiv implementieren und ben¨ otigt im Gegensatz zum Wiener Filter, der alle vorherigen Messwerte ben¨ otigt, nur die Informationen des vorherigen Zustands (engl. state). So w¨ achst die Berechnungszeit nicht mit der Anzahl der Iterationen.

7

KAPITEL 2. ¨ UBERBLICK ¨

Grundlegend l¨ asst sich jede Kalman Iteration in zwei Schritte untertei- len. Der erste Schritt beinhaltet eine Voraussage (engl. state prediction) des aktuellen Zustandes anhand der bereits gewonnenen Informationen ¨ uber das System ohne Messung des aktuellen Zustandes (a priori). Ist die Vor- hersage ¨ uber den aktuellen Zustand getroffen wird im zweiten Schritt der Messwert aufgenommen und die Abweichung von der Vorhersage (engl. in- novation) ermittelt. Wie stark diese innovation der aktuellen Messung in die Zustandsbestimmung eingeht, h¨ angt anfangs vom Initialisierungswert ab, danach davon wie lange das System bereits beobachtet wird bzw. wie genau dem Filter das Systemverhalten bereits bekannt ist. Dieser zweite Schritt beinhaltet also die Korrektur (engl. state correction) der Zustands- voraussage mit der neu erhaltenen Information aus der Messung. Eine gute Einf¨ uhrung in diese Thematik bietet [Wel]. Dem Kalman Filter widmet auch [Hay] ein Kapitel, w¨ ahrend [Blas] und das Kapitel [3.2] dieser Arbeit den Extended Kalman Filter f¨ ur die spezielle Anwendung im EKF - SLAM behandeln.

2.2 Landmarkenfindung

2.2.1 Pattern Matching

Beim Pattern Matching wird versucht Muster aus einer Messung deckungs- gleich ¨ uber Muster in vorherigen Messungen zu legen. Aus den daf¨ ur n¨ otigen Verschiebungen und Drehungen l¨ asst sich dann die Verschiebung und Dre- hung der Roboters zwischen den beiden Messungen ermitteln. So einfach sich diese Methode auch anh¨ ort, so schwierig kann die Implementierung sein. Die erste Schwierigkeit ergibt sich schon aus der Natur der Sensorik, die immer einen gewissen Messfehler mit sich bringt. Dieser Messfehler be- wirkt, dass es praktisch keinen Sinn macht nach 100% ¨ Ubereinstimmung

zu suchen, da dies in den seltensten F¨ allen eintreten wird. So muss immer ermittelt werden wie groß die ¨ Ubereinstimmung ist. Es muss eine Mindest

- ¨ Ubereinstimmung erarbeitet werden, ab der davon ausgegangen werden kann, das selbe Muster wiedergefunden zu haben. Jedoch darf dieses Mi- nimum nicht zu klein angesetzt werden, denn dann besteht Gefahr zu Ver- wechslungen. Auch nicht zu vernachl¨ assigen ist der Resourcen - Bedarf die- ser Methode, da einerseits komplette Messungen gepuffert werden m¨ ussen, mit denen verglichen werden kann. Andererseits m¨ ussen die Muster aus der neuen Messung mit denen in mehreren gespeicherten Messungen ver- glichen werden, um eine gr¨ oßere Robustheit und Genauigkeit zu erzielen. Zu alledem sollten die verwendeten Muster selbst aussagekr¨ aftig und nicht zu leicht verwechselbar sein und sich nicht zuf¨ allig bewegen, um den Krite- rien einer Landmarke zu entsprechen. Die Auswahl passender Muster durch das System setzt naturgem¨ aß die F¨ ahigkeit voraus Muster in der Messung richtig interpretiern zu k¨ onnen.

8