| Publication type: |
Article in Proceedings |
| Author: |
U. Frese |
| Editor: |
C. Freksa |
| Title: |
Treemap: An $O(log n)$ Algorithm for Simultaneous Localization and Mapping |
| Book / Collection title: |
Spatial Cognition IV |
| Page(s): |
455 – 476 |
| Year published: |
2005 |
| Publisher: |
Springer Verlag |
| Abstract: |
This paper presents 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. For keeping the matrices small only those landmarks are represented being observable from outside the region.
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 for $n$ overall landmarks.
The algorithm is evaluated for map quality, storage space and
computation time using simulated and real experiments in an
office environment.
|
| Internet: |
http://www.informatik.uni-bremen.de/agebv/en/Treemap |
| PDF Version: |
http://www.informatik.uni-bremen.de/agebv/downloads/published/fresesc04.pdf |
| Note / Comment: |
read the Autonomous Robots paper instead |
| Status: |
Reviewed |
| Last updated: |
27. 03. 2009 |
