Robot Colocation · Projects · Amittai Siavava

Localization asks where a robot is, given only a stream of noisy sensor readings and a map. A hidden Markov model fits the setting: the hidden state is the robot's cell in the maze, transitions encode how it moves between adjacent cells, and each cell emits a sensor reading — a color, here — corrupted by a known error rate. From a sequence of readings the model recovers a probability distribution over the robot's position, a belief that spreads across the grid and then tightens as evidence arrives.

Localizing by motion alone — no sensor at all. The belief is the SET of cells the robot could occupy (shaded uniformly, since every candidate is equally likely; darker as the set shrinks). A move is deterministic: a candidate blocked by a wall or the grid edge stays put, the rest step, and two candidates landing on the same cell merge into one — so a cell empties on a move only when nothing steps into it and its own candidate steps out. The arrow in each panel is the robot's actual step. Seven moves through the maze's walls funnel twelve candidates down to a single cell, pinning the robot's location without ever reading a sensor. The circle is its true (unknown) cell, always among the candidates.

The HMM factors the problem into a transition model and a sensor model, and the map fixes both:

Transition model $P (s ∣ s^{'})$ . From cell $s^{'}$ the robot steps to an adjacent cell; walls and the grid boundary zero out the illegal moves, and the legal neighbors split the remaining probability. Applied to a belief, this model diffuses mass outward — uncertainty grows with every step taken blind.
Sensor model $P (e ∣ s)$ . Each cell carries a color. A reading equals the cell's true color with probability $1 - ϵ$ and, with the leftover $ϵ$ , reports one of the other colors. Applied to a belief, this model sharpens it — mass is pulled toward cells whose color matches the reading.

Filtering tracks a belief $α_{t} (s)$ , the probability the robot sits in cell $s$ at time $t$ given the readings $e_{1 : t}$ . It updates in two steps: predict through the motion model, then weight by the new reading's emission probability,

α_{t} (s) = P (e_{t} ∣ s) s^{'} \sum P (s ∣ s^{'}) α_{t - 1} (s^{'}),

renormalized to sum to one. The two models pull in opposite directions each step: the sum over $s^{'}$ is the predict step, diffusing the previous belief through the transition model, and the leading $P (e_{t} ∣ s)$ is the update step, sharpening it against the new reading. Evidence compounds. A cell keeps its mass only while it stays consistent with every emission seen, so a belief that starts near-uniform collapses toward a few cells, or one, as readings accumulate. Where the map repeats a color pattern the belief can stay multimodal — split across the matching regions — until a distinguishing reading breaks the tie.

Algorithm:

\textsc{Forward}(e_{1:T})

— filter the position distribution over time

1
input: readings $e_1 \ldots e_T$ , motion model $P(s \mid s')$ , sensor model $P(e \mid s)$
2
for each cell $s$ do $\alpha_0(s) \gets$ prior belief
3
for $t \gets 1$ to $T$ do
4
for each cell $s$ do
5
$\alpha_t(s) \gets P(e_t \mid s) \sum_{s'} P(s \mid s')\, \alpha_{t-1}(s')$
6
normalize $\alpha_t$ so that $\sum_s \alpha_t(s) = 1$
7
return $\alpha_1 \ldots \alpha_T$

Filtering conditions only on past readings. The forward-backward algorithm adds a backward pass $β_{t} (s)$ carrying the influence of future readings, then multiplies the two, $γ_{t} (s) \propto α_{t} (s) β_{t} (s)$ , to refine every past estimate with the full sequence. When the goal is the single most likely trajectory rather than per-step marginals, the Viterbi algorithm replaces the sums with maxima and reads the best path off back-pointers.

References

Project repository
Reference notes: Probabilistic Reasoning over Time
Reference notes: Reasoning over Time: Tracking and Data Association

╌╌ END ╌╌