Classes - Beard

You are here: start » ee490-11reports


|

Meta

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
ee490-11reports [2011/04/15 12:59]
ben
ee490-11reports [2011/04/21 12:50] (current)
eabryan
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 vnet@vnet-project.org. ​
  
 +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 http://​openslam.org/​) 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.
  
 +{{:​campus_challenge:​quadtree_in_c.zip|}}
 +
 +{{:​campus_challenge:​gmapping.zip|}}