Bayes Filters and Grid Localization

A robot in a long hallway does not know where it is. It keeps a belief: a probability for every cell. Each time it moves, the belief shifts and blurs. Each time it senses a door or a wall, the belief sharpens around the places that match.

Door sensor accuracy Motion accuracy

The two steps

Predict after moving by control $u$: spread each cell's probability to where the robot could land.

$$\overline{bel}(x) = \sum_{x'} p(x \mid u, x')\,bel(x')$$

Update after sensing $z$: weight by how well each cell explains the reading, then normalize.

$$bel(x) = \eta\; p(z \mid x)\;\overline{bel}(x)$$

What to notice

At first the belief is flat. After seeing a door, it has peaks at every door, since the robot cannot tell which one. After moving and seeing another door, only the peaks consistent with both readings survive. Moving without sensing spreads the belief out again. This histogram filter is the Bayes filter at its simplest. The Kalman filter and the particle filter are faster ways to do the same two steps.