Advertisement
Published in:
2005 | OriginalPaper | Chapter
Treemap: An O(log n) Algorithm for Simultaneous Localization and Mapping
Author : Udo Frese
Published in: Spatial Cognition IV. Reasoning, Action, Interaction
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.