Module 3: Search in the Real World

Topic 4: Particle Filtering

How do we search if we don’t really know where we are?

This sounds like an existential question but it is doable:  how can we search if we don’t know where we are?  We might be lost in our car or we might be a robot in an unknown building, where we need to both figure out where we are and also build a map (a process known as Simultaneous Localization and Mapping, or SLAM).  This topic is covered in depth in the robotics classes and the math is mostly beyond the scope of this introductory class.  What I want to do with this topic is introduce the main ideas so you can see another approach to handling real-world situations.

 

Robotics Particle Filtering Example

From https://www.udacity.com/blog/2019/07/particle-filtering-part-1-beyond-groping-in-the-dark-for-robots.html

 

Particle Filtering

If you truly have no idea where you are (which does happen to humans, and happens even more often to robots or anything embedded in the real-world because it never has access to the full state of the world), you would quickly want to gather some information so that you would figure out where you are very quickly!  For a human, this might involve looking around, comparing what you see to a map of where you expect to be, changing your position and orientation,  and gathering additional data if you remain lost.  For a robot, it is much the same!  It uses sensors to gather information about what it is actually sensing and compares that to what it expects.

  • Read one or both of the following:  
    • The book has a very technical description of Particle filtering and SLAM in section 14.5.3.  If you have the math skills for this, go ahead and read it.
    • If you prefer a more general (and no math) overview, this overview from Udacity is quite nice!
  • Video
    • Rather than repeat what is already well covered on the net, I suggest a tutorial on particle filtering.  There are a LOT of them out there but I thought this one was well done and didn’t require the math background that many of the tutorials do.  I wanted to find one that fit the math pre-reqs of this class.  If you come in with more math background and prefer those tutorials, feel free to watch one or more of those!
    • Tutorial on particle filters

SLAM

One of the really cool applications of particle filters is figuring out both where you are AND what the unknown place you are looks like!  This sounds really hard and it is!  But the Simultaneous Localization and Mapping (SLAM) algorithm is designed for just this situation!

As with the particle filters, there are a lot of SLAM tutorials out there.  For example, I found a old list of such tutorials on GitHub.  If you watched the video I linked to above, I recommend following the next one in the series! 

 

Assignment

Next topic

 

MODULE MENU