An O(log n) algorithm for simultaneous localization and mapping of mobile robots in indoor environments

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.