{"id":425,"date":"2023-01-05T14:17:09","date_gmt":"2023-01-05T19:17:09","guid":{"rendered":"https:\/\/blogs.mathworks.com\/autonomous-systems\/?p=425"},"modified":"2023-01-05T14:18:51","modified_gmt":"2023-01-05T19:18:51","slug":"intuition-behind-the-particle-filter","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/autonomous-systems\/2023\/01\/05\/intuition-behind-the-particle-filter\/","title":{"rendered":"Intuition Behind the Particle Filter"},"content":{"rendered":"

Autonomous Navigation with Brian Douglas: Part 5<\/h2>\n

This post is from\u00a0Brian Douglas<\/a>, YouTube content creator for Control Systems and Autonomous Applications.\u00a0<\/em><\/p>\n

\n

In the previous post<\/a>, we learnt what is localization and how the localization problem is formulated for robots and other autonomous systems. For the next two posts, we\u2019re going to reference the localization problem that is demonstrated in the MATLAB example, Localize TurtleBot using Monte Carlo Localization<\/a>. This example simulates a TurtleBot moving around in an office building, taking measurements of the environment, and estimating its location using a particle filter<\/strong>.<\/p>\n

\"\"<\/h2>\n

If you\u2019re not familiar with a particle filter it may be confusing as to why the solution has a bunch of blue dots appearing and moving around each time step, and then somehow converging on the real location of the TurtleBot after 60 or so updates.\u00a0 What is the filter doing and how does this seemingly random set of dots help us determine the location of a robot?<\/p>\n

To understand how the particle filter solves localization problems, we should develop a little intuition behind the filter with a thought exercise that doesn\u2019t involve robots at all.<\/p>\n

Imagine you wake up in a strange, pitch-black room. You\u2019ve never been in this room before but you\u2019ve been given a map which shows four walls, two locked doors, and the location of a button that opens the doors. You have a small light that allows you to see a few feet in front of you but beyond that it\u2019s total darkness. Our goal is to determine where we are on the map, and then use our location to find the button that will let us out. This is a localization problem.<\/p>\n

\"\"<\/p>\n

At the beginning, we have no idea where we are in the room. We might say that it is equally probable that we are anywhere on the map and facing any direction.<\/p>\n

\"\"<\/p>\n

We turn on our light and we see we are directly facing a wall that is about 3 feet away. From this first observation, can we tell where we are on the map?<\/p>\n

Not for sure. There are four walls in this room and we might be facing any one of them, or anywhere along each of the walls. However, we can tell that we are not looking at a corner or the doors, and we are not in the middle of the room since the wall is so close. Knowing that we\u2019re facing a wall at a specific distance away constrains us to one of these positions and orientations.<\/p>\n

\"\"<\/p>\n

However, since all observations have some amount of noise and error, we might claim that we could be a little closer or further away from the wall than what we are estimating, and we might be slightly turned in one direction or another. Also, we can\u2019t say for sure that we\u2019re not in the middle of the room since it\u2019s possible that we\u2019re looking at a temporary flat obstacle that wasn\u2019t on the map. It\u2019s is a lower probability that that\u2019s the case, but it is still possible so we can\u2019t rule it out.<\/p>\n

Therefore, after this first measurement, we may say that the probability distribution of where we are looks something like the image below. With the brighter yellow locations meaning higher probability, and the darker locations lower probability.<\/p>\n

\"\"<\/p>\n

This is already a very non-Gaussian probability distribution. Kalman filters require Gaussian probability distributions which is why we can\u2019t use it for this localization scenario. We\u2019ve already failed that constraint with the first observation! A particle filter, on the other hand, does not have that constraint which is why we\u2019re eventually going use it to solve this problem.<\/p>\n

Ok, enough foreshadowing, let\u2019s get back to our thought exercise! Remember, we\u2019re in this pitch black room and all we can see is a wall a few feet in front of us. It makes sense that we can\u2019t be certain where we are from this single measurement, so we need to move around and make another observation. Let\u2019s say we turn to the left and continue to follow the wall for what feels like about 30 feet, eventually reaching a corner. What can we now deduce about where we are currently? We know we\u2019re looking at a corner, so we must be in one of these four areas, right?<\/p>\n

\"\"<\/p>\n

 <\/p>\n

However, we felt like we walked 30 feet, which had to have been almost the entire length of the wall and we didn\u2019t see a door. Therefore, we can rule out the lower right corner and upper right corner as possible locations since we would have had to walk past the door to get to those corners.<\/p>\n

This is how we can use our knowledge of past observations along with our knowledge of how we moved to come up with a better estimation of where we are. Our probability distribution now is highest in the two left corners and lower everywhere else. We\u2019re starting to narrow in on our exact location!<\/p>\n

\"\"<\/p>\n

Let\u2019s turn once more to the left and keep walking. After about 15 feet we come to a door. Now there are two locations where we could be: facing the bottom door, or facing the right door.\u00a0 However, based on our past observations and our knowledge of how we turned and how far we walked, we can confidently claim that we\u2019re looking at the bottom door. There is only one place on this map where we could turn left, walk 30 feet, then turn left again and walk 15 feet and reach a door.<\/p>\n

\"\"<\/strong><\/p>\n

With our location known, we can finally use the map to navigate to the exit button and get out of this crazy room!<\/p>\n

As we saw, no single observation was enough to determine our location or pose within the map, however, through successive observations we were able to consolidate where we thought we were into smaller regions, narrowing the probability distribution further until we were confident we knew where we were.<\/p>\n

What we did in this example is essentially the same thing a particle filter is doing. If we revisit the TurtleBot example in MATLAB we can start to see how the blue dots represent the possible locations of where the robot is in the office building. As the filter runs, it blends together observations of the environment (sensor measurements) with an estimate of how far the robot travels between measurements and in which direction (motion model) to estimate its location on a map (environment model). Intuitively, this makes sense, right? So, how can we give a robot this ability? How can it remember multiple successive measurements in a way that allows it to hone in on its exact location over time? Well, as we\u2019ve already said, one popular way is with a particle filter, and we\u2019ll talk more about that in the next post.<\/p>\n

\n
\n
\n

To learn more on these capabilities, you can watch this detailed video on “<\/em>Autonomous Navigation, Part 2: Understanding the Particle Filter<\/a>“. You can also learn more about the Monte Carlo Localization algorithm here<\/a>. Thanks for sticking around till the end! If you haven\u2019t yet, please Subscribe and Follow this blog to keep getting the updates for the upcoming content.\u00a0<\/em><\/p>\n<\/div>\n<\/div>\n

\n
\n

<\/a><\/p>\n