Welcome back. In module two,

we'll learn about one of the most famous algorithms

in all of engineering; the Kalman filter.

In today's world of advanced machine learning,

the Kalman filter remains an important tool

to fuse measurements from several sensors to

estimate in real-time the state of

a robotic system such as a self-driving car.

In this module, we'll learn some of the history of

the Kalman filter and introduce its basic linear formulation.

We'll present why the Kalman filter is

the best linear unbiased estimator and then

extend the linear formulation to nonlinear systems through linearization.

Discuss limitations of this linearization approach, and finally,

present a modern alternative to

linearization through the unscented transform.

By the end of this lesson, you'll be able to describe the common filter as

a state estimator that works in two stages; prediction and correction.

Understand the difference between motion and measurement models,

and then use the Kalman filter formulation

in a simple 1D localization example.

Let's begin with a bit of history.

The Kalman filter algorithm was published in 1960 by Rudolf E. Kalman,

a Hungarian born professor and engineer who was

working at the Research Institute for Advanced Studies

in Baltimore Maryland.

Years later in 2009,

American President Barack Obama awarded Kalman

the prestigious National Medal of Science for his work on

the Kalman filter and

other contributions to the field of control engineering.

After its publication in 1960,

the Kalman filter was adopted by

NASA for use in the Apollo guidance computer.

It was this ground-breaking innovation that played a pivotal role in

successfully getting the Apollo spacecraft to the moon,

and to our first steps on another world.

The filter helped guide

the Apollo spacecraft accurately through its circumlunar orbit.

The engineers at NASA's Ames Research Center,

adopted Kalman's linear theory and extended it to nonlinear models.

We'll look at this specific extension in upcoming module.

But first, let's talk about the basic linear Kalman filter.

The Kalman filter is very similar to the linear

recursive least squares filter we discussed earlier.

While recursive least squares updates the estimate of a static parameter,

but Kalman filter is able to update and estimate of an evolving state.

The goal of the Kalman filter is to take

a probabilistic estimate of this state and

update it in real time using two steps; prediction and correction.

To make these ideas more concrete,

let's consider a problem of estimating the 1D position of the vehicle.

Starting from an initial probabilistic estimate at time k minus 1,

our goal is to use a motion model which could be derived from

wheel odometry or inertial sensor measurements to predict our new state.

Then, we'll use the observation model derived from GPS for example,

to correct that prediction of vehicle position at time

k. Each of these components, the initial estimate,

the predicted state, and the final corrected state are all

random variables that we will specify by their means and covariances.

In this way, we can think of the Kalman filter as a technique to fuse

information from different sensors to produce

a final estimate of some unknown state,

taking into account, uncertainty in motion and in our measurements.

For the Kalman filter algorithm,

we had been able to write the motion model in the following way;

the estimate at time step k is

a linear combination of the estimate at time step k minus 1,

a control input and some zero-mean noise.

The input is an external signal that

affects the evolution of our system state.

In the context of self-driving vehicles,

this may be a wheel torque applied to

speed up and change lanes, for example.

Next, we will also need to define a linear measurement model.

Finally, we'll need a measurement noise as before and

a process noise that governs how certain we are

that our linear dynamical system is actually correct,

or equivalently, how uncertain

we are about the effects of our control inputs.

Once we have our system in hand,

we can use an approach very similar to that we

discussed in the recursive least squares video.

Except this time, we'll do it in two steps.

First, we use the process model to predict how our states, remember,

that we're now typically talking about evolving states and

non-state parameters evolved since the last time step,

and will propagate our uncertainty.

Second, we'll use our measurement to correct that prediction

based on our measurement residual or innovation and our optimal gain.

Finally, we'll use the gain to also propagate

the state covariance from our prediction to our corrected estimate.

In our notation, the hat

indicates a corrected prediction at a particular time step.

Whereas a check indicates

a prediction before the measurement is incorporated.

If you've worked with the Kalman filter before,

you may also have seen this written with plus and minus

signs for the corrected and predicted quantities, respectively.

Let's recap. We start with a probability density over

our states and also maybe parameters at time step k minus 1,

which we represent as a multivariate Gaussian.

We then predict the states at time step k using

our linear prediction model and

propagate both the mean and the uncertainty;

the covariance, forward in time.

Finally, using our probabilistic measurement model,

we correct our initial prediction by optimally

fusing the information from our measurement together with

the prior prediction through our optimal gain matrix k. Our end result is

an updated probabilistic estimate for our states at time

step k. The best way

to become comfortable with the Kalman filter is to use it.

Let's look at a simple example.

Consider again the case of

the self-driving vehicle estimating its own position.

Our state vector will include

the vehicle position and its first derivative velocity.

Our input will be a scalar acceleration that could come from

a control system that commands our car to accelerate forward or backwards.

For our measurement, we'll assume that we're able to determine

the vehicle position directly using something like a GPS receiver.

Finally, we'll define our noise variances as

follows: Given this initial estimate and our data,

what is our corrected position estimate after we perform

one prediction step and one correction step using the Kalman filter?

Here's, how we can use these definitions to solve for

our corrected position and velocity estimates.