This thesis addresses the Simultaneous Localization and Mapping (SLAM) problem, a key problem 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 first sensor is odometry, i.e. the observation of the robot's movement from the revolution 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 computation time, i.e. O((n+p)3) for n landmarks and p robot poses. Popular approaches like Extended Kalman Filter (EKF) are more efficient but still need O(n2) computation time and suffer from linearization errors. The first 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 identifies the error in the robot's orientation as dominant source. The second and main contribution is a very efficient SLAM algorithm that works by hierarchically 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 finest 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 efficient. A measurement is integrated into a local subregion using O(k2) computation time for k landmarks in a subregion. When the robot moves to a different subregion a global update is necessary requiring only O(k3 log n) computation time. Furthermore, the proposed hierarchy allows nonlinear 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 simulation experiments and experiments with a real mobile robot in an office environment.

Diese Arbeit beschäftigt sich mit dem Problem simultaner Lokalisierung und Kartierung (Simultaneous Localization and Mapping, SLAM), einem Schlüsselproblem für jeden wirklich autonomen 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 schätztheoretischen Perspektive betrachtet. Dabei liegt der Schwerpunkt auf dem zentralen Algorithmus, der eine auf zwei Sensorgrösen basierende Schätzung für die Karte und die Roboterposition liefert: Die erste Sensorgröse ist die Odometrie, das heist, die Bestimmung der Roboterbewegung über die Drehungen seiner Räder. Die zweite ist die Beobachtung von Umgebungsmerkmalen, so genannten Landmarken. Es gibt für dieses Problem eine optimale Lösung durch Maximum Likelihood bzw. quadratische Ausgleichsrechnung, die allerdings unmäsig hohe Rechenzeit, nämlich O((n+p)3) für n Landmarken und p Roboterpositionen benötigt. Gängige Ansätze, wie der Extended Kalman Filter (EKF), sind effizienter, brauchen aber immer noch O(n2) Rechenzeit und werden zudem durch Linearisierungsprobleme beeinträchtigt. Der erste Beitrag in dieser Arbeit ist eine Diskussion von SLAM, speziell der inhärenten Struktur der Unsicherheit einer Kartenschätzung. Das Schlüsselresultat läst sich als Sicherheit von Beziehungen trotz Unsicherheit von Positionen'' zusammenfassen. Weiterhin analysiert die Diskussion Linearisierungsfehler in SLAM und identifiziert den Fehler in der Roboterorientierung als dominante Ursache. Im Hauptteil wird ein sehr effizienter SLAM Algorithmus erarbeitet, der die Karte hierarchisch in lokale Regionen und Unterregionen aufteilt. Auf jeder Ebene der Hierarchie speichert jede Region eine Matrix, die einige der in der Region enthaltenen Landmarken repräsentiert. Auf der untersten Ebene, das heist der Ebene der feinsten Unterteilung, sind diese Matrizen automatisch klein, weil die Regionen klein sind und nur wenige Landmarken enthalten. Auf höheren Ebenen sind die Regionen gros und enthalten viele Landmarken. Um auch die in diesen Regionen gespeicherten Matrizen klein zu halten, werden nur die Landmarken repräsentiert, die von ausserhalb der Region beobachtbar sind. Dadurch ist sichergestellt, dass auch auf höheren Ebenen jede Matrix nur wenige Landmarken repräsentiert und Berechnungen effizient bleiben. Eine Messung wird in eine lokale Unterregion integriert unter Verwendung von O(k2) Rechenzeit für k Landmarken in der Region. Wenn der Roboter eine neue Unterregion betritt, muss eine globale Aktualisierung mit O(k3log n) Rechenzeit durchgeführt werden. Weiterhin ermöglicht 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 normalen Büroumgebung erfolgt eine Auswertung des Algorthmus bezüglich der Kartenqualität, des Speicherplatzbedarfs und der Rechenzeit.