Discrete Filters Technical Writeup

Every filter I have worked on, both the ball filter and the robot localizer, turns out to be the same idea underneath, and once that clicked the whole subject stopped looking like a collection of separate tricks and started looking like one method with different assumptions bolted onto it.

Idea

What we want is $P(x_t)$ , the distribution over where something is right now, and we are not starting from nothing because the previous step already left us with a belief $P(x_{t-1})$ . The entire job is therefore working out how to carry one into the other as data arrives.

That data comes in two kinds, and we step the estimate differently depending on which kind we have just received. Perceptual data is a measurement, something a sensor saw, whereas action data is a control or prediction command, something we told the robot to do. Everything past that distinction is bookkeeping.

Measurement

For a measurement we build a sensor model, which tells us what reading we ought to get if we were at a given state, so that if we are at $x=3$ the camera should report $x=3$ . That model is $P(z\mid x)$ , and it is worth noticing that this points the wrong way round for our purposes, since the quantity we do not know is $x$ and recovering it is the entire problem.

What we do have is a measurement $z$ together with the prior belief $P(x)=\overline{\text{Bel}}(x)$ , which is enough to flip the conditional using Bayes rule:

$$P(x\mid z)=\frac{P(z\mid x)P(x)}{P(z)}$$

Feeding the measurement we actually received into that expression gives us the corrected estimate. In practice the denominator is awkward to compute and does not depend on $x$ at all, so rather than evaluate it we drop it and normalise at the end instead, which leaves the update in the form

$$\text{Bel}(x_t)=\eta P(z_t\mid x_t)\overline{\text{Bel}}(x_t)$$

where $\eta$ is whatever constant makes the distribution sum to one. Forgetting that normalisation is the classic mistake, and because the result still looks like a distribution it tends to cost an afternoon before anyone notices.

Prediction

For an action we build a process model instead, which comes from physics rather than from a sensor and tells us what state we end up in given the state we were in, written as $P(x_t\mid x_{t-1})$ .

However, we do not know which $x_{t-1}$ we were actually at, since all we ever had was a distribution over it, so we sum across every possibility and weight each one by how likely it was:

$$\overline{\text{Bel}}(x_t)=\sum _{x_{t-1}}P(x_t\mid x_{t-1},u_t)\text{Bel}(x_{t-1})$$

which is marginalising $x_{t-1}$ out. On top of that we fold in the control input, where $u$ is what we commanded and $B$ maps that command into the state, so the expected value of the prior shifts by $Bu$ . This is exactly the term our localizer is currently missing, which is a large part of why it drifts.

Methods

Those two steps are the entire Bayes filter, and every practical filter is really a decision about how to represent $\text{Bel}(x)$ , since we cannot store a full distribution over a continuous space and have to approximate it somehow.

Kalman filters assume the belief is Gaussian, which means a mean and a covariance describe it completely, making them cheap and exact whenever that assumption actually holds, and they are what I used for the ball filter. Extended Kalman filters keep the Gaussian assumption but linearise a nonlinear model around the current estimate, which is the approach behind the localizer redesign. Particle filters abandon the Gaussian assumption altogether and represent the belief as a cloud of samples, which handles multimodal beliefs that the other two cannot but costs considerably more to run.

The representation changes, and the two steps do not.

Kalman filter writeup→Particle filter writeup→