| Abstract: |
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(n^2) 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(k^2) computation time for k landmarks in a subregion. When the robot moves to a different subregion a global update is necessary requiring only O(k^3 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 xperiments with a real mobile robot in an office environment.
|
