2D Mapping Using a Quadtree Data Structure

Abstract

This undergraduate dissertation is intended to investigate the opportunity to use a quad-tree data structure in an effective way in order to provide a consistent global map. The sensor employed was a laser range finder (Hokuyo URG-04LX). The raw data are inserted in the global map using directly the quad-tree so as to produce an occupancy grid without get through an intermediate evenly grid map representation. A scan matcher algorithm is implemented to adjust/accommodate perception according to sensor noise and uncertainty in the motion model (supposed unknown in the work).

The following parts of the document are used to give you hints about techniques and software used so that you can speed up your software development without bothering about trifling details.

- Bachelor's Thesis titled Costruzioni di mappe basate su quadtree Media:MauroBrennaTesiTriennale.pdf‎ (in Italian)

Quad-tree Used and Insertion Method

The idea is using directly the quad-tree map representation from the very start. Simply:

1. choose a resolution limit;
2. select a way to retrieve the occupancy probability of each cell, for instance : occprob= occ/vis.

occ value indicates how many times the laser endpoint is bound in that cell, while vis expresses how many times the 'segment' sensor-laser_endpoint passes through that cell.

The starting quad-tree is a simple 4 squared map. Every time a single laser acquisition is read, just create the tree deepening only the cell where the point is bound 'till the resolution limit is reached. Then you can update the occupancy probability of the interested cell. In creating the 'segment' is advisable exploit a line rasterization algorithm such as Bresenham's one to avoid possible discretization problems.

Scan Matcher

For that phase, it's possible to use the classic scan matcher algorithms or look for something cheaper in terms of computational resources exploiting the tree map. For an overview of the techniques in references you can find worth reading papers. A simple observation occurs if a a similar quad-tree to the former described one is used: if you are looking for the cells with the highest occupancy probability value you should look the maximum resolution nodes only. To compare/correlate the local map you have just retrieved with a reference scan you may:

• use the global map formed by these max resolution cells only;
• use the previous scan, saving it in memory, and find the correlation between the two.

A nutty, and for many reason opinable, method consists in use as correlation value the sum of the occupancy probability of each cell in which the data of the current scan is bound (given a testing pose).

From Quad-tree Map Representation to Human Readable Map

Now that the hard work is done it would be nice and pleasant to build a JPG/PNG image describing the global map. Here you can find some advice.

First, which library to use? Probably Image Magick[++] or OpenGL. Testing the former we can assure you that it is not suitable for creating maps above 3000x3000px; At this threshold, compile and running the program to build the image can last very long and cause errors. Anyway in every image manipulation library you should find a method like create_square(geometry,colour). Obviously you can set the colour mapping the grey-scale to occupancy probability values. The second thing you would probably want to point out is uncouple the robot quad-tree map generation and the human readable output (not to CPU time during the SLAM). The easiest way is to provide a method for each node that write a string that is an instruction of the image manipulation library (the create_square()s ). You can generate a sort of map log file visiting the tree and calling this method for each node. Offline you can assemble that file with other two, for example the beginning of a C program which includes that library and its end, using a simple script; compile it and run the program to create the image. This technique is easy to automate and waste the least amount of time. You may also think about a vector format image, e.g. SVG, in order to skip the 'assemble and compile' phase.

References:

http://openslam.org/

http://www.opengl.org/

http://www.imagemagick.org/www/Magick++/

http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

G. Grisetti, C. Stachniss, and W Burgard. Improved techniques for grid mapping with rao-blackwellized particle filters, 2006.

A. Censi, L. Iocchi, and G. Grisetti. Scan matching in the hough domain, in proc. of intern. conference on robotics and automation (icra’05), 2005. Technical report, 2005.

Sebastian Thrun, Wolfram Burgard, and Dieter Fox. Probabilistic robotics. MIT Press, 2005.

Y. Kang D. Caveney and J.K. Hedrick. Probabilistic mapping for unmanned rotorcraft using point-mass targets and quadtree structures. In Proc. of ASME IMECE Orlando, FL, Nov., 2005.

Gerhard K. Kraetzschmar, Guillem Pag`s Gassull, and Klaus Uhl. Probabilistic quadtrees for variable-resolution mapping of large environments. In M. I. Ribeiro and J. Santos Victor, editors, Proceedings of the 5th IFAC/EURON symposium on Intelligent Autonomous Vehicles, Lisbon, Portugal, July 2004. Elsevier Science.

Ioannis M. Rekleitis. A particle filter tutorial for mobile robot localization. (TR-CIM-04-02), 2004.

J.-S. Gutmann, C. Schlegel, "AMOS: comparison of scan matching approaches for self-localization in indoor environments," eurobot, p. 61, 1st Euromicro Workshop on Advanced Mobile Robots (EUROBOT), 1996