AIRWiki - User contributions [en]

2D Mapping Using a Quadtree Data Structure

2010-05-20T20:51:44Z

MauroBrenna:

== 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:

# choose a resolution limit;
# 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 [http://en.wikipedia.org/wiki/Bresenham's_line_algorithm 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

User:MauroBrenna

2010-05-20T20:49:19Z

MauroBrenna:

{{Student
|firstname=Mauro
|lastname=Brenna
|email=mauro(dot)brenna(at)mail(dot)polimi(dot)it
|advisor=MatteoMatteucci
|projectpage=LURCH_-_The_autonomous_wheelchair
|photo=MauroBrenna.jpg |
|status=active
}}

'''Mauro Brenna'''

nato a Como (CO) il 22-05-1985

'''Istruzione e formazione'''

- ''2007- 2010'' Ingegneria informatica (2° livello) votazione 110 e lode con tesi ''Scan Matching, Covariance Estimation and SLAM: Models and Solutions for the scanSLAM Algorithm''. La tesi è stata svolta nel contesto del progetto [[LURCH - The autonomous wheelchair]]

- ''2004 - 2007'' Laurea in Ingegneria informatica (1° livello) votazione 110 e lode con tesina:"Costruzione di mappe basate su quadtree". Una piccola descrizione è presente a questo indirizzo: [[2D Mapping Using a Quadtree Data Structure|2D Mapping Using a Quadtree Data Structure ]]

'''Attività in AIRLab'''

Svolta tesi laurea in Ingegneria informatica (2° livello). Tematiche trattate: scanmatching, autocalibrazione e odometria su laser, tecniche di filtraggio (Extended Kalman Filter).

'''Tesi e Materiale'''

- Master's Thesis titled ''Scan Matching, Covariance Estimation and SLAM: Models and Solution for the scanSLAM Algorithm'': [[Media:MauroBrennaMastersThesis2010.pdf‎]] (in English)

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

'''Contatti'''

[http://it.linkedin.com/in/maurobrenna Linked in]

File:MauroBrennaTesiTriennale.pdf

2010-05-20T20:40:21Z

MauroBrenna: Mauro Brenna bachelor's thesis titled ''Costruzioni di mappe basate su quadtree'' (in Italian)

Mauro Brenna bachelor's thesis titled ''Costruzioni di mappe basate su quadtree'' (in Italian)

LURCH - The autonomous wheelchair

2010-05-20T20:35:55Z

MauroBrenna:

{{Project
|title=LURCH - the autonomous wheelchair
|image=LURCH wheelchair.jpg
|short_descr=augmenting commercial electric wheelchairs with autonomous navigation and obstacle avoidance
|coordinator=MatteoMatteucci
|tutor=SimoneCeriani;DavideMigliore
|collaborator=GiulioFontana
|students=MatteoRossi;MauroBrenna
|resarea=Robotics
|restopic=Robot development
|start=2007/02/01
|end=2010/12/31
|status=Active
}}


L.U.R.C.H. is the acronym of "Let Unleashed Robots Crawl the House".

LURCH is an extended version of an commercial electric wheelchair (Rabbit by OttoBock) equipped with:
# An interface circuit for digital drive via a radio serial link (XBee modules)
# Two on-board computers ([[PCBricks]]), powered by wheelchair batteries
# A 7-inch touchscreen monitor ([http://www.xenarc.com/product/700tsv.html Xenarc 700TSV]), 800x480 resolution (16:10 AR)
# Two laser scanners Hokuyo URG 04LX
# A colour camera FireI400 (resolution 640×480)
# An odometry system based on encoders applied to the rear wheels


Main goals of the LURCH project are:
# Add sensors and robotic functionalities to the powered wheelchair.
# Add various command interfaces, such as Joypad wireless, speech command, [[Brain-Computer Interface|brain-computer interface]].
# Semi-autonomous navigation with collision and obstacle avoidance.
# Autonomous navigation by path planning and localization.

Functions currently provided by LURCH:
# Driving by the original joystick or a Logitech RumblePad2 wireless joypad.
# Obstacle sensing using planar scanner lasers.
# Basic collision and obstacle avoidance behaviours.
# Indoor localization by a ''fiducial marker system''
# Path planning and basic autonomous navigation.
# [[Brain-Computer Interface|Brain-computer interface]] driving system

==Media Coverage==
Lurch project appeared in many national and international media. You can see the related articles and videos in the [[MediaCoverage]] page.

==Available Documentation==

- Documentation on the interface circuit between the wheelchair joystick and computer: [[Media:LurchCircuitDocument.pdf]].

- '''WARNING''': the circuit was modified and the documentation above is upgraded by this new file: [[Media:LurchXBee.pdf]].

- How to modify the wheelchair joystick to connect to the interface circuit: [[Media:LurchCircuitJoystick.pdf]].

- Brief discussion about the interface circuit between the wheelchair joystick and computer: [[Media:LurchCircuitJoystickBrief.pdf]].

- Brief description of the LURCH project: [[Media:LurchBriefDesc.pdf]].

- Brief description of the communication between the wheelchair interface circuit and a PC via RS232 port: [[Media:LurchProtocol.pdf]].

- Source code for PIC 18F452 microprocessor and Eagle project (schematic and board): [[Media:LurchCircuitProject.zip]].

- Battery replacement done on May 2009, description of work: [[Media:LurchBatteryReplacement.pdf]].

- Thesis by Simone Ceriani, titled ''Sviluppo di una carrozzina autonoma d'ausilio ai disabili motori'' (Development of an autonomous wheelchair to help motor-disabled persons): [[Media:LurchThesisCeriani.pdf]] (in Italian)

- Thesis presentation by Simone Ceriani (note: Videos don't work, you can found similar videos below): [[Media:LurchPresentazioneThesisCeriani.zip]]

- Thesis by Marco Dalli, titled ''Sviluppo di un sistema di controllo basato su odometria per una carrozzina robotica'' (Development of a control system based on odometry for a robotic wheelchair): [[Media:LurchThesisDalli.pdf]] (in Italian)

- Thesis presentation by Marco Dalli: [[Media:LurchPresentazioneThesisDalli.zip]]

- Thesis by Marco Assini, titled ''Sviluppo di un pianificatore di percorsi geometrici per una carrozzina autonoma'' (Development of a geometric path planner for an autonomous wheelchair): [[Media:LurchThesisAssini.pdf]] (in Italian)

- Thesis presentation by Marco Assini (the file contains a ppt version, a pptx, and a simplified pdf version without animation): [[Media:LurchPresentazioneThesisAssini.zip]]

- Thesis by Mauro Brenna, titled ''Scan Matching, Covariance Estimation and SLAM: Models and Solution for the scanSLAM Algorithm'': [[Media:MauroBrennaMastersThesis2010.pdf‎]] (in English)

- Pdf with ArtoolKitPlus Fiducial Markers collection. Dimension are 160x160mm. [[Media:ArtoolKitPlusMarkers-160mm.pdf.zip]]

==PCBricks Configuration==
PCBrick-03 and PCBrick-05 feature Xubuntu Linux 7.10, Xfce Window Manager, Openchrome graphics drivers and eGalax touchscreen drivers v1.08.1227 (Drivers [http://210.64.17.162/web20/TouchKitDriver/linuxDriver.htm here]).
The touchscreen is configured and calibrated on both machines, hence it can be used with either one or the other indifferently.

==Electronics development==
We are currently designing a new electronic main board for the wheelchair.

The idea is to base the whole system on a CANbus, allowing a complete modularization of the on-board electronics.

[[Lurch_electronics_development|Read more on this topics here...]]

==Software development==
* Try a different sw architecture, now we are examinating orocos [http://www.orocos.org]
* Integrate Marco Assini's thesis (RRT planning) with current release
* Develop an improved navigation system [[Navigation_system_for_LURCH|Read more on this topics here...]]

==LURCH YouTube Videos==

{{#ev:youtube|7bZ45sGf3qs}}

*[http://www.youtube.com/watch?v=7bZ45sGf3qs External link]

{{#ev:youtube|PFjlmcTbGVs}}
*[http://www.youtube.com/watch?v=PFjlmcTbGVs External link]

{{#ev:youtube|RBfIq8eQJ6Q}}
*[http://www.youtube.com/watch?v=RBfIq8eQJ6Q External link]

{{#ev:youtube|iRw8PhY8IF4}}
*[http://www.youtube.com/watch?v=iRw8PhY8IF4 External link]

{{#ev:youtube|zlhePZbRxZA}}
*[http://www.youtube.com/watch?v=zlhePZbRxZA External link]

=People Involved=

[[User:AndreaBonarini|Andrea Bonarini]]

[[User:MatteoMatteucci|Matteo Matteucci]]

[[User:DavideMigliore|Davide Migliore]]

[[User:GiulioFontana|Giulio Fontana]]

[[User:BernardoDalSeno|Bernardo Dal Seno]]

[[User:MarcoDalli|Marco Dalli]] (ex-Tesista)

[[User:SimoneCeriani|Simone Ceriani]] (Assegnista di ricerca)

[[User:MatteoRossi|Matteo Rossi]] (Tesista)

[[User:MarcoAssini|Marco Assini]] (ex-Tesista)

[[User:MauroBrenna|Mauro Brenna]] (Tesista)

=== Laboratory work and risk analysis ===

Laboratory work for this project is mainly performed at AIRLab/Lambrate. It includes some mechanical work and electrical and electronic activity. Potentially risky activities are the following:
* Use of mechanical tools. Standard safety measures described in [http://airlab.elet.polimi.it/index.php/airlab/content/download/461/4110/file/documento_valutazione_rischi_AIRLab.pdf Safety norms] will be followed.
* Use of soldering iron. Standard safety measures described in [http://airlab.elet.polimi.it/index.php/airlab/content/download/461/4110/file/documento_valutazione_rischi_AIRLab.pdf Safety norms] will be followed.
* Transportation of heavy loads (e.g. robots). Standard safety measures described in [http://airlab.elet.polimi.it/index.php/airlab/content/download/461/4110/file/documento_valutazione_rischi_AIRLab.pdf Safety norms] will be followed.
* Robot testing. Standard safety measures described in [http://airlab.elet.polimi.it/index.php/airlab/content/download/461/4110/file/documento_valutazione_rischi_AIRLab.pdf Safety norms] will be followed.

File:MauroBrennaMastersThesis2010.pdf

2010-05-20T20:27:55Z

MauroBrenna: Mauro Brenna master's thesis: "Scan Matching, Covariance Estimation and SLAM: Models and Solutions for the scanSLAM Algorithm"

Mauro Brenna master's thesis:

"Scan Matching, Covariance Estimation and SLAM: Models and Solutions for the scanSLAM Algorithm"

Tips 'n' tricks

2009-11-04T12:32:28Z

MauroBrenna:

Below you can find some useful ideas or info about common tasks or problems.

== AIRWiki ==
* When you are facing a problem, before starting to browse the Internet and scratch your head, take a look to AIRWiki: it's possible that other users already solved it for you. If you don't find the solution on AIRWiki and have to look elsewhere for it (and possibly do a lot of work), when you finish... add it to AIRWiki!
* If you find a page useful and you want to know if someone ever adds other good stuff to it, you can ''watch'' the page. Just click on the ''watch'' button at the top of the page you're interested in. You will receive an email notification for any update.

== Writing and reading==
* Give a look at some [[Tesi|suggestions]] for preparing your thesis (only in Italian for now... translators are welcome!).
* You can access all the papers for which Politecnico has bought a subscription even when you are at home if you enable the [[http://www.asi.polimi.it/rete/proxy/index.html Politecnico proxy]]. The instruction page is provided by the nice people of [[http://www.asi.polimi.it/ ASI]] in Italian only. For an English version of the page, try to poke them if you find a way to contact them.
* For [http://ph.dei.polimi.it/phday PhDay08] we've set up an [http://www.easychair.org Easychair] account for paper reviews. Here's a little [[EasyChair Reviews|tutorial for reviewers]] that might be useful in case you have to review somehing/teach someone how the system works.

== Software and programming ==
* Someone wrote some advice about [[Writing Good Code|writing code]]
* Info about [[Mathematica]]
* How to plot using gnuplot in your C/C++ project [[Gnuplot in cpp]]
* The ever-growing AIRLab guide about [[Getting Started With PIC(TM) MCU]]

== Hardware ==
* Need to learn how to solder? Check the following links: [http://www.wireless.hackaday.com/2007/10/26/how-to-introduction-to-soldering/ 1] [http://www.wireless.hackaday.com/2007/10/28/followup-soldering-how-to/ 2] [http://www.make-digital.com/make/vol01/?pg=166 3]
* Some useful addresses and links about shops, stores, factories. With some of them we have partnerships for discounts. You can found information [[Shops| here]].

== Producing videos and publishing them ==
* Usually, at the end of the project, people tend to produce a video and put it on the web. The best way to do this is to [[produce a video]] and then send it to [[User:AndreaBonarini | Andrea Bonarini]] to have it published on the YouTube channel of the AIRLab. Then you can put the link wherever you want, hopefully also in the page of your project on AIRWiki, as done, e.g. in [[ROBOWII]]

== Miscellanea (uncategorized) ==
* If you are searching the homepage of a DEI professor (or PhD Student) try this [http://mycroft.mozdev.org/download.html?name=dei+people&skipcache=yes Mozilla plugin]

Gnuplot in cpp

2009-11-04T12:11:44Z

MauroBrenna:

'''How to plot using gnuplot in your C/C++ programs'''

This is a little guide that shows you how you can add a plotting function in your C/C++ program.
This approach has some advantages and disadvantages:

PROS
- You don't need to write on files or similar and plot in a second moment through a Matlab/Octave/Gnuplot script

CONTRAS
- You don't have all the potentiality of Matlab/Octave plotting even if you can program your plotting utilities

'''HOW TO'''

# You should download gnuplot-cpp library. I suggest you to use my version [[Media: Gnuplot-cpp_modified.zip‎]] because the official one [http://code.google.com/p/gnuplot-cpp/ gnuplot-cpp] has problems, (see below).
#To use the plotting library you should only need to include: "gnuplot-cpp/gnuplot_i.hpp"
# A code snippet is here presented that simply plots a 2D set of points:
<code>
if(ANIMATIONON){
// GNUPLOT
// GNUPLOT INITIALIZATION
Gnuplot gp("My plot");
//std::vector<double> x,y; // this are the vector containing (x,y) points
// END GNUPLOT INITIALIZATION
try {
gp.remove_tmpfiles(); // it is always better to do it
gp.reset_plot(); // delete the plot (like Matlab figure())
cout << endl << endl << "*** user-defined lists of points (x,y)" << endl;
gp.set_grid();
gp.set_style("points").plot_xy(x,y,"user-defined points 2d");
//sleep(1);
//usleep(3e5);
}
catch (GnuplotException ge)
{
cout << ge.what() << endl;
}
} // END GNUPLOT

</code>

'''HOW IT WORKS'''

For what I understood, the program writes a temp file (/tmp) in GNU/Linux and use it to plot in the correct way using [http://www.gnuplot.info/ Gnuplot].

'''PROBLEM OF THE OFFICIAL VERSION'''

Up to now (read the data of this post), the official package provided [http://code.google.com/p/gnuplot-cpp/ gnuplot-cpp] it has problems that deals with tempFiles. In many cases, for example in the destructor the function ''remove_tmpfiles()'' is commented. In this way many and many files are created in /tmp and after the max files limit is reached no other plots are created. Note that this could be useful if you want to save your points in a file for other processing.
Moreover a major problem is due to the wrong use of the header file. Some functions are not inline and global constats are defined. These cause linking problems when you include official "gnuplot-cpp/gnuplot_i.hpp" in more than one source files.

Gnuplot in cpp

2009-11-04T12:09:40Z

MauroBrenna:

'''How to plot using gnuplot in your C/C++ programs'''

This is a little guide that shows you how you can add a plotting function in your C/C++ program.
This approach has some advantages and disadvantages:

PROS
- You don't need to write on files or similar and plot in a second moment through a Matlab/Octave/Gnuplot script

CONTRAS
- You don't have all the potentiality of Matlab/Octave plotting even if you can program your plotting utilities

'''HOW TO'''

# You should download gnuplot-cpp library. I suggest you to use my version [[Media:Gnuplot-cpp_modified.zip‎]] because the official one [http://code.google.com/p/gnuplot-cpp/ gnuplot-cpp] has problems, (see below).
#To use the plotting library you should only need to include: "gnuplot-cpp/gnuplot_i.hpp"
# A code snippet is here presented that simply plots a 2D set of points:
<code>
if(ANIMATIONON){
// GNUPLOT
// GNUPLOT INITIALIZATION
Gnuplot gp("My plot");
//std::vector<double> x,y; // this are the vector containing (x,y) points
// END GNUPLOT INITIALIZATION
try {
gp.remove_tmpfiles(); // it is always better to do it
gp.reset_plot(); // delete the plot (like Matlab figure())
cout << endl << endl << "*** user-defined lists of points (x,y)" << endl;
gp.set_grid();
gp.set_style("points").plot_xy(x,y,"user-defined points 2d");
//sleep(1);
//usleep(3e5);
}
catch (GnuplotException ge)
{
cout << ge.what() << endl;
}
} // END GNUPLOT

</code>

'''HOW IT WORKS'''

For what I understood, the program writes a temp file (/tmp) in GNU/Linux and use it to plot in the correct way using [http://www.gnuplot.info/ Gnuplot].

'''PROBLEM OF THE OFFICIAL VERSION'''

Up to now (read the data of this post), the official package provided [http://code.google.com/p/gnuplot-cpp/ gnuplot-cpp] it has problems that deals with tempFiles. In many cases, for example in the destructor the function ''remove_tmpfiles()'' is commented. In this way many and many files are created in /tmp and after the max files limit is reached no other plots are created. Note that this could be useful if you want to save your points in a file for other processing.
Moreover a major problem is due to the wrong use of the header file. Some functions are not inline and global constats are defined. These cause linking problems when you include official "gnuplot-cpp/gnuplot_i.hpp" in more than one source files.

File:Gnuplot-cpp modified.zip

2009-11-04T12:04:09Z

MauroBrenna: The source package of the modified version of gnuplot-cpp. For the official one see: http://code.google.com/p/gnuplot-cpp/

The source package of the modified version of gnuplot-cpp.
For the official one see: http://code.google.com/p/gnuplot-cpp/

Gnuplot in cpp

2009-11-04T12:02:00Z

MauroBrenna: How to plot using gnuplot in your C/C++ project

'''How to plot using gnuplot in your C/C++ programs'''

This is a little guide that shows you how you can add a plotting function in your C/C++ program.
This approach has some advantages and disadvantages:

PROS
- You don't need to write on files or similar and plot in a second moment through a Matlab/Octave/Gnuplot script

CONTRAS
- You don't have all the potentiality of Matlab/Octave plotting even if you can program your plotting utilities

'''HOW TO'''

# You should download gnuplot-cpp library. I suggest you to use my version LINKHERE because the official one [http://code.google.com/p/gnuplot-cpp/ gnuplot-cpp] has problems, (see below).
#To use the plotting library you should only need to include: "gnuplot-cpp/gnuplot_i.hpp"
# A code snippet is here presented that simply plots a 2D set of points:
<code>
if(ANIMATIONON){
// GNUPLOT
// GNUPLOT INITIALIZATION
Gnuplot gp("My plot");
//std::vector<double> x,y; // this are the vector containing (x,y) points
// END GNUPLOT INITIALIZATION
try {
gp.remove_tmpfiles(); // it is always better to do it
gp.reset_plot(); // delete the plot (like Matlab figure())
cout << endl << endl << "*** user-defined lists of points (x,y)" << endl;
gp.set_grid();
gp.set_style("points").plot_xy(x,y,"user-defined points 2d");
//sleep(1);
//usleep(3e5);
}
catch (GnuplotException ge)
{
cout << ge.what() << endl;
}
} // END GNUPLOT

</code>

'''HOW IT WORKS'''

For what I understood, the program writes a temp file (/tmp) in GNU/Linux and use it to plot in the correct way using [http://www.gnuplot.info/ Gnuplot].

'''PROBLEM OF THE OFFICIAL VERSION'''

Up to now (read the data of this post), the official package provided [http://code.google.com/p/gnuplot-cpp/ gnuplot-cpp] it has problems that deals with tempFiles. In many cases, for example in the destructor the function ''remove_tmpfiles()'' is commented. In this way many and many files are created in /tmp and after the max files limit is reached no other plots are created. Note that this could be useful if you want to save your points in a file for other processing.
Moreover a major problem is due to the wrong use of the header file. Some functions are not inline and global constats are defined. These cause linking problems when you include official "gnuplot-cpp/gnuplot_i.hpp" in more than one source files.

Gnuplot in cpp

2009-11-04T12:01:32Z

MauroBrenna:

'''How to plot using gnuplot in your C/C++ programs'''

This is a little guide that shows you how you can add a plotting function in your C/C++ program.
This approach has some advantages and disadvantages:

PROS
- You don't need to write on files or similar and plot in a second moment through a Matlab/Octave/Gnuplot script

CONTRAS
- You don't have all the potentiality of Matlab/Octave plotting even if you can program your plotting utilities

'''HOW TO'''

# You should download gnuplot-cpp library. I suggest you to use my version LINKHERE because the official one [http://code.google.com/p/gnuplot-cpp/ gnuplot-cpp] has problems, (see below).
#To use the plotting library you should only need to include: "gnuplot-cpp/gnuplot_i.hpp"
# A code snippet is here presented that simply plots a 2D set of points:
<code>
if(ANIMATIONON){
// GNUPLOT
// GNUPLOT INITIALIZATION
Gnuplot gp("My plot");
//std::vector<double> x,y; // this are the vector containing (x,y) points
// END GNUPLOT INITIALIZATION
try {
gp.remove_tmpfiles(); // it is always better to do it
gp.reset_plot(); // delete the plot (like Matlab figure())
cout << endl << endl << "*** user-defined lists of points (x,y)" << endl;
gp.set_grid();
gp.set_style("points").plot_xy(x,y,"user-defined points 2d");
//sleep(1);
//usleep(3e5);
}
catch (GnuplotException ge)
{
cout << ge.what() << endl;
}
} // END GNUPLOT

</code>

'''HOW IT WORKS'''
For what I understood, the program writes a temp file (/tmp) in GNU/Linux and use it to plot in the correct way using [http://www.gnuplot.info/ Gnuplot].

'''PROBLEM OF THE OFFICIAL VERSION'''
Up to now (read the data of this post), the official package provided [http://code.google.com/p/gnuplot-cpp/ gnuplot-cpp] it has problems that deals with tempFiles. In many cases, for example in the destructor the function ''remove_tmpfiles()'' is commented. In this way many and many files are created in /tmp and after the max files limit is reached no other plots are created. Note that this could be useful if you want to save your points in a file for other processing.
Moreover a major problem is due to the wrong use of the header file. Some functions are not inline and global constats are defined. These cause linking problems when you include official "gnuplot-cpp/gnuplot_i.hpp" in more than one source files.

Gnuplot in cpp

2009-11-04T11:54:01Z

MauroBrenna:

Gnuplot in cpp

2009-11-04T11:53:44Z

MauroBrenna:

Gnuplot in cpp

2009-11-04T11:53:11Z

MauroBrenna:

Gnuplot in cpp

2009-11-04T11:46:54Z

MauroBrenna: How to plot using gnuplot in your C/C++ project

User:MauroBrenna

2009-05-31T13:46:53Z

MauroBrenna:

{{SMWUser
|firstname=Mauro
|lastname=Brenna
|email=mauro(dot)brenna(at)mail(dot)polimi(dot)it
|advisor=MatteoMatteucci
|projectpage=LURCH_-_The_autonomous_wheelchair
|photo=MauroBrenna.jpg |
}}

'''Mauro Brenna'''

nato a Como (CO) il 22-05-1985

'''Istruzione e formazione'''

- ''2007- '' Ingegneria informatica (2° livello)
- ''2004 - 2007'' Laurea in Ingegneria informatica (1° livello) votazione 110 e lode con tesina:"Costruzione di mappe basate su quadtree" Una piccola descrizione è presente a questo indirizzo: [[2D Mapping Using a Quadtree Data Structure|2D Mapping Using a Quadtree Data Structure ]]

'''Attività in AIRLab'''

Svolgimento tesi laurea in Ingegneria informatica (2° livello). Tematiche da trattare: scanmatching, autocalibrazione e odometria su laser, tecniche di sensor fusion.

User:MauroBrenna

2009-05-31T13:11:35Z

MauroBrenna:

{{SMWUser
|firstname=Mauro
|lastname=Brenna
|email=mauro(dot)brenna(at)mail(dot)polimi(dot)it
|advisor=MatteoMatteucci
|projectpage=LURCH_-_The_autonomous_wheelchair
|photo=MauroBrenna.jpg |
}}

'''Mauro Brenna'''

nato a Como (CO) il 22-05-1985

'''Istruzione e formazione'''

- ''2007- '' Ingegneria informatica (2° livello)
- ''2004 - 2007'' Laurea in Ingegneria informatica (1° livello) votazione 110 e lode con tesina:"Costruzione di mappe basate su quadtree"

'''Attività in AIRLab'''

Svolgimento tesi laurea in Ingegneria informatica (2° livello). Tematiche da trattare: scanmatching, autocalibrazione e odometria su laser, tecniche di sensor fusion.

File:MauroBrenna.jpg

2009-05-31T13:11:09Z

MauroBrenna: Photo of Mauro Brenna for the profile

Photo of Mauro Brenna for the profile

User:MauroBrenna

2009-05-31T12:55:44Z

MauroBrenna: New page: {{SMWUser |firstname=Mauro |lastname=Brenna |email=mauro(dot)brenna(at)mail(dot)polimi(dot)it |advisor=MatteoMatteucci |projectpage=LURCH_-_The_autonomous_wheelchair |photo= a.jpg| }} '''...

{{SMWUser
|firstname=Mauro
|lastname=Brenna
|email=mauro(dot)brenna(at)mail(dot)polimi(dot)it
|advisor=MatteoMatteucci
|projectpage=LURCH_-_The_autonomous_wheelchair
|photo= a.jpg|
}}

'''Mauro Brenna'''

nato a Como (CO) il 22-05-1985

'''Istruzione e formazione'''

- ''2007- '' Ingegneria informatica (2° livello)
- ''2004 - 2007'' Laurea in Ingegneria informatica (1° livello) votazione 110 e lode con tesina:"Costruzione di mappe basate su quadtree"

'''Attività in AIRLab'''

Svolgimento tesi laurea in Ingegneria informatica (2° livello). Tematiche da trattare: scanmatching, autocalibrazione e odometria su laser, tecniche di sensor fusion.

2D Mapping Using a Quadtree Data Structure

2007-11-15T20:23:09Z

MauroBrenna:

== 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.

== Quad-tree Used and Insertion Method ==

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

# choose a resolution limit;
# 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 [http://en.wikipedia.org/wiki/Bresenham's_line_algorithm 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

2D Mapping Using a Quadtree Data Structure

2007-11-15T20:22:02Z

MauroBrenna:

== 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.

== Quad-tree Used and Insertion Method ==

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

# choose a resolution limit;
# 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 [http://en.wikipedia.org/wiki/Bresenham's_line_algorithm 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