An O(log n) algorithm for simultaneous localization and mapping of mobile robots in indoor environments [Elektronische Ressource] = Ein O(log n)-Algorithmus für gleichzeitige Lokalisierung und Kartierung mobiler Roboter in Innenräumen / from Udo Frese

Sujets

• Informatik

Informations

• Publié par: friedrich-alexander-universitat_erlangen-nurnberg
• Publié le: 01 janvier 2004
• Nombre de lectures: 8
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

AnO(logn) Algorithm for Simultaneous Localization and
Mapping of Mobile Robots in Indoor Environments
EinO(logn) Algorithmus zur simultanen Lokalisierung und
¤Kartierung von mobilen Robotern in Innenraumen
Submitted to the
Technische Fakultat¤ der
Universitat¤ Erlangen Nurnber¤ g
in partial ful llment of the requirements for
the degree of
DOKTOR INGENIEUR
from
Udo Frese
Erlangen ? 2004As dissertation accepted by the
Technische Fakultat¤ der
Universitat¤ Erlangen Nurnber¤ g
thDate of submission: 7 January 2004
thDate of defense: 28 May 2004
Dean: Prof. Dr. rer. nat. A. Winnacker
Reviewer: Prof. Dr.-Ing. H. Niemann
Prof. Dr.-Ing. G. Hirzinger3
To Frauke4Abstract
This thesis addresses the Simultaneous Localization and Mapping (SLAM) problem, a key prob-
lem for any truly autonomous mobile robot. The task for the robot is to build a map of its
environment and simultaneously determine its own position in the map while moving.
The problem is examined from an estimation-theoretic perspective. The focus is on the core
estimation algorithm which provides an estimate for the map and robot pose from two sensor
inputs: The rst sensor is odometry, i.e. the observation of the robot’s movement from the revo-
lution of its wheels. The second is the observation of environment features, so called landmarks.
The optimal solution based on maximum likelihood or least square estimation needs excessive
3computation time, i.e. O((n +p) ) for n landmarks and p robot poses. Popular approaches
2like Extended Kalman Filter (EKF) are more ef cient but still needO(n ) computation time and
suffer from linearization errors.
The rst contribution of this thesis is an analysis of SLAM, in particular under the aspect of
the inherent uncertainty structure of a map estimate. The key result can be phrased as Certainty
of relations despite uncertainty of positions . The discussion further analyzes the linearization
error in SLAM and identi es the error in the robot’s orientation as dominant source.
The second and main contribution is a very ef cient SLAM algorithm that works by hier-
archically dividing the map into local regions and subregions. At each level of the hierarchy
each region stores a matrix representing some of the landmarks contained in this region. On the
level of nest subdivision, i.e. the lowest level, these matrices are naturally small because the
regions are small and contain few landmarks only. On higher levels regions are large and contain
many landmarks. For keeping the matrices stored at higher levels small only those landmarks are
represented being observable from outside the region. This way it is ensured that even on high
levels of hierarchy each matrix represents only few landmarks and computation is ef cient.
2A measurement is integrated into a local subregion usingO(k ) time fork land-
marks in a subregion. When the robot moves to a different subregion a global update is necessary
3requiring onlyO(k logn) computation time. Furthermore, the proposed hierarchy allows non-
linear rotation of the matrix stored at a certain region. Thereby linearization problems can be
removed.
The algorithm is evaluated for map quality, storage space and computation time using simu-
lation experiments and experiments with a real mobile robot in an of ce environment.
56 ABSTRACTKurzfassung
Diese Arbeit beschaftigt¤ sich mit dem Problem simultaner Lokalisierung und Kartierung (Si-
multaneous Localization and Mapping, SLAM), einem Schlusselproblem¤ fur¤ jeden wirklich au-
tonomen Roboter. In diesem Problem besteht die Aufgabe eines Roboters in Bewegung in der
Darstellung einer Karte seiner Umgebung sowie in der gleichzeitigen Bestimmung der eigenen
Position auf dieser Karte.
Das Problem wird aus einer schatztheoretischen¤ Perspektive betrachtet. Dabei liegt der
Schwerpunkt auf dem zentralen Algorithmus, der eine auf zwei Sensorgro en¤ basierende
Schatzung¤ fur¤ die Karte und die Roboterposition liefert: Die erste Sensorgro e¤ ist die Odometrie,
das hei t, die Bestimmung der Roboterbewegung uber¤ die Drehungen seiner Rader¤ . Die zweite ist
die Beobachtung von Umgebungsmerkmalen, so genannten Landmarken. Es gibt fur¤ dieses Pro-
blem eine optimale Losung¤ durch Maximum Likelihood bzw. quadratische Ausgleichsrechnung,
3die allerdings unma ig¤ hohe Rechenzeit, namlich¤ O((n +p) ) fur¤ n Landmarken undp Roboter-
positionen benotigt.¤ Gangige¤ Ansatze,¤ wie der Extended Kalman Filter (EKF), sind ef zienter,
2brauchen aber immer nochO(n ) Rechenzeit und werden zudem durch Linearisierungsprobleme
beeintrachtigt.¤
Der erste Beitrag in dieser Arbeit ist eine Diskussion von SLAM, speziell der inharenten¤
Struktur der Unsicherheit einer Kartenschatzung.¤ Das Schlusselresultat¤ la t¤ sich als Sicherheit
von Beziehungen trotz Unsicherheit von Positionen zusammenfassen. Weiterhin analysiert die
Diskussion Linearisierungsfehler in SLAM und identi ziert den Fehler in der Roboterorientie-
rung als dominante Ursache.
Im Hauptteil wird ein sehr ef zienter SLAM Algorithmus erarbeitet, der die Karte hierar-
chisch in lokale Regionen und Unterregionen aufteilt. Auf jeder Ebene der Hierarchie speichert
jede Region eine Matrix, die einige der in der Region enthaltenen Landmarken reprasentiert.¤ Auf
der untersten Ebene, das hei t der Ebene der feinsten Unterteilung, sind diese Matrizen automa-
tisch klein, weil die Regionen klein sind und nur wenige Landmarken enthalten. Auf hoheren¤
Ebenen sind die Regionen gro und enthalten viele Landmarken. Um auch die in diesen Re-
gionen gespeicherten Matrizen klein zu halten, werden nur die Landmarken reprasentiert,¤ die
von ausserhalb der Region beobachtbar sind. Dadurch ist sichergestellt, dass auch auf hoheren¤
Ebenen jede Matrix nur wenige Landmarken reprasentiert¤ und Berechnungen ef zient bleiben.
78 KURZFASSUNG
2Eine Messung wird in eine lokale Unterregion integriert unter Verwendung vonO(k ) Re-
chenzeit fur¤ k Landmarken in der Region. Wenn der Roboter eine neue Unterregion betritt,
3muss eine globale Aktualisierung mit O(k logn) Rechenzeit durchgefuhrt¤ werden. Weiterhin
ermoglicht¤ die vorgeschlagene Hierarchie die in einer Region gespeicherte Matrix nichtlinear
zu drehen . Damit werden Linearisierungprobleme vermieden.
Durch Simulationen und Experimente mit einem realen mobilen Roboter in einer norma-
len Buroumgeb¤ ung erfolgt eine Auswertung des Algorthmus bezuglich¤ der Kartenqualitat,¤ des
Speicherplatzbedarfs und der Rechenzeit.Acknowledgments
The research results presented in this thesis were conducted during my work at the Institute of
Robotics and Mechatronics of the German Aerospace Center (DLR). It is my pleasure to thank
Prof. Gerd Hirzinger for the opportunity to work in the exciting eld of robotics, for generous
support, inspiration and for the freedom to pursue the research topic I wished.
I am very grateful to Prof. Heinrich Niemann, the supervisor of this thesis, for the opportunity
to discuss my research at the Chair for Pattern Recognition (LME) at the University of Erlangen-
Nurnber¤ g.
I am very much indebted to those who helped me along with advice, discussions, critical
comments, and by making the robot work. Especially, I wish to thank Berthold Bauml,¤ Frauke
Bokemeyer, Christoph Borst, Tom Duckett, Matthias Hahnle,¤ Steffen Haidacher, Ulrich Hillen-
brand, Martin Hormann,¤ Christian Ott, Gisela Schef er, Norbert Sporer, and Michael Suppa.
I would like to thank my parents Ingrid and Jur¤ gen Frese for constant support and encourage-
ment. Finally, and most of all, I want to thank Frauke for patience and affection during the last
two years.
Oberpfaffenhofen, December 2003 Udo Frese
910 ACKNOWLEDGEMENTS