## Robot localization using a particle system monad

Posted by Eric Kidd Thu, 19 Apr 2007 20:43:00 GMT

**Refactoring Probability Distributions:**
part 1, part 2, part 3, part 4, **part 5**

Welcome to the 5th (and final) installment of *Refactoring Probability
Distributions!* Today, let’s begin with an example from
Bayesian Filters for Location Estimation (PDF), an excellent paper by Fox and colleagues.

In their example, we have a robot in a hallway with 3 doors. Unfortunately, we don’t know *where* in the hallway the robot is located:

The vertical black lines are “particles.” Each particle represents a possible location of our robot, chosen at random along the hallway. At first, our particles are spread along the entire hallway (the top row of black lines). Each particle begins life with a weight of 100%, represented by the height of the black line.

Now imagine that our robot has a “door sensor,” which currently tells us that
we’re in front of a door. This allows us to rule out any particle which is located *between* doors.

So we multiply the weight of each particle by 100% (if it’s in front of a door) or 0% (if it’s between doors), which gives us the lower row of particles. If our sensor was less accurate, we might use 90% and 10%, respectively.

What would this example look like in Haskell? We *could* build a
giant list of particles (with weights), but that would require us to do a
lot of bookkeeping by hand. Instead, we use a monad to hide all the
details, allowing us to work with a single particle at a time.

```
localizeRobot :: WPS Int
localizeRobot = do
-- Pick a random starting location.
-- This will be our first particle.
pos1 <- uniform [0..299]
-- We know we're at a door. Particles
-- in front of a door get a weight of
-- 100%, others get 0%.
if doorAtPosition pos1
then weight 1
else weight 0
-- ...
```

What happens if our robot drives forward?

Read more...