Bayes Filtering
Mathematical Foundations
Robot
World
Sense
Act
Robots can act and sense the world; but they can’t know the world completely -- they have to estimate the state of the world from the sensing and acting they can do.
The robot’s estimate of the world is often referred to as its belief about the true state of the world.
As the robot takes actions, the state of the world changes; but that state is hidden from us -- it can only be approximately observed. The model of a world as a chain like this is sometimes referred to as a hidden Markov model.
The robot can only (approximately) measure what’s circled in blue here, and (approximately) know its actions, in green. And it would like to estimate the states of the world in orange. We can express this as a probability question:
The robot’s belief about the world is the probability distribution over state x_{t} given its history of actions u_{1:t} and observations z_{1:t}.
We can use a lot of different tools to compute this belief about the world, but one of the most common methods in robotics is to use a class of algorithms called Bayesian Filters. This class of algorithms is powerful because they allow us to make some useful assumptions about our world that can be encoded as computational “tricks” for faster, real-time computing.
The basic Bayes filtering algorithm, as we would code it on a computer, looks like the following steps (which get repeated for each new timestep):
(1) Initialize!
(2) Predict!
(3) Correct!
The basic Bayes filtering algorithm, as we would code it on a computer, looks like the following steps (which get repeated for each new timestep):
(1) Initialize!
(2) Predict!
(3) Correct!
Start from an initial belief about the world (known as the prior), the first action of the robot, and the first observation of the robot...
The basic Bayes filtering algorithm, as we would code it on a computer, looks like the following steps (which get repeated for each new timestep):
(1) Initialize!
(2) Predict!
(3) Correct!
Apply the effect of your robot’s action on the initial guess of the world’s state.
This is a motion model -- you know this because you know how your robot works. This expresses the probability of the state of my world now, given what it was and my action.
The basic Bayes filtering algorithm, as we would code it on a computer, looks like the following steps (which get repeated for each new timestep):
(1) Initialize!
(2) Predict!
(3) Correct!
Apply the effect of your robot’s action on the initial guess of the world’s state.
This is what I think my world used to look like.
The basic Bayes filtering algorithm, as we would code it on a computer, looks like the following steps (which get repeated for each new timestep):
(1) Initialize!
(2) Predict!
(3) Correct!
Apply the effect of your robot’s action on the initial guess of the world’s state.
And we want to integrate over all possible states that my world could have been in, in order to propagate all those possibilities forward.
The basic Bayes filtering algorithm, as we would code it on a computer, looks like the following steps (which get repeated for each new timestep):
(1) Initialize!
(2) Predict!
(3) Correct!
Correct your predictions based on the actual measurements you make about the world.
We know this, because it’s your sensor model!
The basic Bayes filtering algorithm, as we would code it on a computer, looks like the following steps (which get repeated for each new timestep):
(1) Initialize!
(2) Predict!
(3) Correct!
Correct your predictions based on the actual measurements you make about the world.
This is your current prediction.
The basic Bayes filtering algorithm, as we would code it on a computer, looks like the following steps (which get repeated for each new timestep):
(1) Initialize!
(2) Predict!
(3) Correct!
Correct your predictions based on the actual measurements you make about the world.
This is a normalizing constant...this makes everything sum to one. In practice, getting this is tricky, so it is often heuristically defined.
The basic Bayes filtering algorithm, as we would code it on a computer, looks like the following steps (which get repeated for each new timestep):
(1) Initialize!
(2) Predict!
(3) Correct!
Let’s see where this algorithm comes from mathematically from Bayes Theorem...
This is the form of conditional Bayes theorem...
Plugging in our notation...
Observation model
Cumulative motion model
Normalizing constant...
Let’s take a closer look at each of these components...
Observation model
Our observation, at any time, is independent of the actions I have taken. This piece of evidence has no bearing on what I actually observe about the world. Thus, this part of Bayes rule is literally just my sensor model.
Cumulative motion model
Literally: what is the probability of my current world state, given my history of actions?
Practically, this is tricky to solve...we can make this easier on ourselves by applying a Markov assumption: that the state of my world right now, is simply a function of what my world was right before I took an action, and the effect of my action. This means I can ignore everything else! So, let’s restate this:
Nice! This is much easier to solve...it’s just our motion model! To compute this, we will want to integrate over all possible options of my previous world state. This is often expressed like this:
Normalizing constant...
Computing the denominator in Bayes rule is often intractable in practice -- it is literally: what is the probability of my history of observations, given my history of actions? To solve this requires marginalizing over all possible states of my world in my history. Even for small systems, this is...challenging at best. Rather than compute the denominator exactly, we can instead set a normalizing constant heuristically, or compute it by computing every possible numerator for the state that my world could be in now, and then selecting a constant by making sure all those numerators sum to 1.
We’ll walk through binary world example to see how all of this works by hand; then reconnect with our fundamental algorithm.
Robot
Door
1, if door open
0, if door closed
1, if robot pushes
0, if robot..doesn’t push
1, if door appears open
0, if door appears closed
Let’s imagine a simple binary world...(this is adopted from Probabilistic Robotics, a foundational text in modern computational robotics today)
Prior belief -- there is a 50/50 shot of the door being open or closed
Sensor model -- in practice, I could get this by characterizing my robot in controlled experiments
Motion model -- in practice, I could get this by characterizing my robot and world interactions in controlled experiments
Bayes Law...
Simplify this for our problem (normalizing constant substituted for the denominator)....
Let’s solve!
Bayes Law...
Simplify this for our problem (normalizing constant substituted for the denominator)....
Let’s solve!
As an exercise...what is the normalizing constant? Hint: the probability of our state x_1 = 1 and the probability of our state x_1 = 0 need to sum to 1....
When you get mu, you should find that the probability of x_1 = 1 given our observation and action is...
Bayes Law...
Simplify this for our problem (normalizing constant substituted for the denominator)....
Let’s solve!
Okay...so let’s take a step...
And apply the Markov assumption....
Bayes Law...
Simplify this for our problem (normalizing constant substituted for the denominator)....
Let’s solve!
Okay...so let’s take a step...
And apply the Markov assumption....
As an exercise...what is the normalizing constant?
When you get mu, you should find that the probability of x_2 = 1 given our observation and action is...
All we do here is make Bayes Law an incremental, sequential process -- see how it maps below:
Okay...cool so...how would we operationalize this algorithmically again?
(1) Initialize!
(2) Predict!
(3) Correct!
As an exercise, consider doing the robot problem we just did using the initialize-predict-correct equations!
Okay -- so what?
Bayes filtering provides a lot of nice assumptions we can use to make our problems simpler (the Markov assumption, for instance). However, what do we notice about the implementation?
It isn’t very scalable, especially if we need to solve for the normalizing constant. (for those familiar with big O notation, this process is squared in the number of states in the world. Oof!)
So in our really complex robotics applications -- indeed, like our Neato moving around the world! -- we typically need to approximate a Bayes Filter. That’s where all of the sub-categories of Bayes Filtering algorithms comes in, including our Particle Filter!
How is particle filtering an approximation of a Bayes Filter?
Every particle is a sample from a complex probability distribution.
So, let’s think about our binary world example. In this case, there were only two states that the world could possibly have -- door open, door closed. But what if we wanted to estimate the degree to which the door was ajar? Well, that would mean that there could be many, many, many states of our door (depending on how finely resolved our measurements were). We couldn’t possibly compute by hand all of those states. But what if we could subsample all of those states, and from that sample, get an approximate distribution over every state instead? That’s the particle filtering trick! -- each particle is a possible version of the world, and all the particles together approximate the distribution over every possible version of the world.
Using the particle trick, our computational complexity becomes linear in the number of particles which is absolutely rad.
(1) Initialize!
(2) Predict!
(3) Correct!
(1.1) Sample!
Draw N samples of possible states according to the probability distribution bel(x_{t-1})
Apply the motion model to all of your initial samples...this gets you a new set of particles.
Weigh your predicted set of particles with observations; this weighing places higher probability on particles (world states) that better align with observations, and gives you yet another set of particles...