Classes - McLain

You are here: start » ee490-11reports




This shows you the differences between two versions of the page.

ee490-11reports [2011/04/15 12:59]
ee490-11reports [2011/04/21 12:50] (current)
Line 115: Line 115:
==== Quad Trees-Sam Olson ==== ==== Quad Trees-Sam Olson ====
 +Quadtrees are already proven to work in robotic environments, so there was much more focus placed on finding out if quadtrees would work efficiently enough for our particular application, i.e. if the update time would be fast enough to keep up with the incoming laser data.  As such, all effort was immediately put into developing a C++ implementation.
 +Much of the code we have can be attributed to the vNet Project, which can be obtained free of charge from
 +After more careful analysis, we discovered that quadtree structures would likely be too slow for our purposes.  Our requirements demand an access time under 0.1 seconds, but this implementation (and many others that were investigated) exceeded that constraint significantly as more points were added.  Greater numbers of points obtained from laser scan data increased quadtree traversal time too significantly to be of any use.
 +The alternative we then began investigating is a gridmap solution called Gmapping (found at which uses Rao-Blackwellized particle filters to provide an individual map associated with every laser sample.  The advantage we see in Gmapping with Rao-Blackwellized filters over quadtrees is that speed is potentially much greater, and that it requires significantly fewer particles to build an accurate map.
 +Our conclusion is that quadtrees are much more suited to saving storage space rather than time.  Alternatives are still being researched.