A probabilistic, variable-resolution and effective quadtree representation for mapping of large environments

Abstract

In this paper, a probabilistic quadtree map is presented instead of traditional grids map which is used widely in robot mapping and localization field yet is confronted with prohibitive storage consumption. A quadtree is a well-known data structure capable of achieving compact and efficient representation of large two-dimensional environments. We extend this basic idea by integrating with probabilistic framework and propose a clamping scheme to update the map occupancy probability value, which eliminates the uncertainty of the system and facilitates data compression. Meanwhile, in order to speed the operation of locating quadtree nodes, a coding rule between a node coordinate and its corresponding access key is adopted. We also discuss a new implementation of the Rao-Blackwellized particle filter simultaneous localization and mapping (SLAM) based on quadtree representation. Experiments are conducted in different sizes of areas (even in a shopping mall of 23,700 m <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) demonstrate that the SLAM algorithm based on quadtree representation works excellently compared to grids map especially in large scale environments.