Basic skills for a mobile robot system are localization and navigation. Any possible service task, such as floor cleaning, fetching and carrying objects, or assistance of the handicapped, requires these skills.
Implementing such skills involves answering the questions ``Where am I?'', ``Where am I going?'', and ``How do I get there?''. These questions can only be answered with a map: to name a place or path, a representation of the environment is needed. The first question therefore is: “What is my map?”
The most convincing approach, both from the perspective of autonomy and of applications, is to have the robot create its own map while moving. The Simultaneous Localization and Mapping (SLAM) approach addresses this problem.
The main source of errors in the map is the odometry. As the odometric error accumulates, locally consistent but globally very uncertain maps are generated. The use of identifiable landmarks, moving along the same doorway, allows integration of new measurements to advance the quality of the existing map. The optimal integration 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 the Extended Kalman Filter (EKF) are more efficient but still need O(n2) computation time and suffer from linearization errors.
To overcome these computational problems, we have developed a very efficient SLAM algorithm that works by hierarchically dividing the map into local regions. At each level of the hierarchy, regions are represented by a matrix storing the accumulated measurements of the region’s landmarks. On the level of finest subdivision, these matrices are naturally small as they represent, say, a single room with few landmarks. At higher levels, regions are larger and may contain many landmarks. To keep the corresponding matrices small, only the landmarks observable from outside are represented. This allows the integration of a new measurement in O(k3log(n)) time for n total landmarks and a maximum of k in a single region at lowest level.
12/03:[fre03b] U. Frese, T. Duckett: A Multigrid Approach for Accelerating Relaxation-based SLAM, 18. Fachgespräch Autonome Mobile Systeme (AMS03), Karlsruhe (Read fre03 instead)
08/03:[fre03] U. Frese, T. Duckett: A Multigrid Approach for Accelerating Relaxation-based SLAM, Proc. Workshop Reasoning with Uncertainty in Robotics, IJCAI 2003, Acapulco, Mexiko, pages 39-46
06/01: [fre01] U. Frese, G. Hirzinger, Simultaneous Localization and Mapping - A Discussion, IJCAI01 Workshop Reasoning with Uncertainty in Robotics, 2001, Seattle
06/00: [fre00] U. Frese, M. Hörmann, B. Bäuml, Global konsistente visuelle Lokalisation ohne vorgegebene Karte, at - Automatisierungstechnik 6/00
11/99: [fre99] Global konsistente visuelle Lokalisation ohne vorgegebene Karte, U. Frese, M. Hörmann, B. Bäuml, 15. Fachgespräch Autonome Mobile Systeme (AMS99), München (Read [fre00] instead)