Kalman Filtering
From Experimental Robotics
The Kalman filter is an efficient infinite impulse response|recursive filter which estimates the state of a dynamic system from a series of incomplete and noise measurements.
Contents |
Examples of applications
An example of an application would be to provide accurate continuously-updated information about the position and velocity of an object given only a sequence of observations about its position, each of which includes some error. It is used in a wide range of engineering applications from radar to computer vision. Kalman filtering is an important topic in control theory and control systems engineering.
For example, in a radar application, where one is interested in radar tracker, information about the location, speed, and acceleration of the target is measured with a great deal of corruption by noise at any time instant. The Kalman filter exploits the dynamics of the target, which govern its time evolution, to remove the effects of the noise and get a good estimate of the location of the target at the present time (filtering), at a future time (prediction), or at a time in the past (interpolation or smoothing).
The Kalman Filter
The Kalman filter is a recursive estimator. This means that only the estimated state from the previous time step and the current measurement are needed to compute the estimate for the current state. In contrast to batch estimation techniques, no history of observations and/or estimates are required. It is unusual in being purely a time domain filter; most filters are formulated in the frequency domain and then transformed back to the time domain for implementation.
The state of the filter is represented by two variables:
- The estimate of the state at time k;
- The error covariance matrix (a measure of the estimated accuracy of the state estimate).
The Kalman filter has two distinct phases: Predict and Update. The predict phase uses the estimate from the previous timestep to produce an estimate of the current state. In the update phase, measurement information from the current timestep is used to refine this prediction to arrive at a new, more accurate estimate.
Predict
(predicted state)
(predicted estimate covariance)
Update
(innovation or measurement residual)
(innovation (or residual) covariance)
(optimal Kalman gain)
(updated state estimate)
(updated estimate covariance)
The formula for the updated estimate covariance above is only valid for the optimal Kalman gain.
Invariants
If the model is accurate, and the values for 
and 
accurately reflect the distribution of the initial state values, then the following invariants are preserved: all estimates have mean error zero
and covariance matrices accurately reflect the covariance of estimates
Example
Consider a vehicle on perfectly frictionless, infinitely long straight rails. Initially the vehicle is stationary at position 0, but it is buffeted this way and that by random acceleration. We measure the position of the truck every Δt seconds, but these measurements are imprecise; we want to maintain a model of where the vehicle is and what its velocity is. We show here how we derive the model from which we create our Kalman filter.
There are no controls on the vehicle, so we ignore Bk and uk. Since F, H, R and Q are constant, their time indices are dropped.
The position and velocity of the truck (or more generally, even a point particle) is described by the linear state space
where 
is the velocity, that is, the derivative of position with respect to time.
We assume that between the (k − 1)th and kth timestep the vehicle undergoes a constant acceleration of ak that is normally distributed, with mean 0 and standard deviation σa. From Newton's laws of motion we conclude that
where
and
We find that
(since σa is a scalar).
At each time step, a noisy measurement of the true position of the vehicle is made. Let us suppose the noise is also normally distributed, with mean 0 and standard deviation σz.
where
and
We know the initial starting state of the vehicle with perfect precision, so we initialize
and to tell the filter that we know with perfect position, we give it a zero covariance matrix:
If the initial position and velocity are not known perfectly the covariance matrix should be initialized with a suitably large number, say B, on its diagonal.
The filter will then prefer the information from the first measurements over the information already in the model.
See also
- Compare with the multimodal Particle Filtering.
External links
- An Introduction to the Kalman Filter, SIGGRAPH 2001 Course, Greg Welch and Gary Bishop
- Kalman filtering chapter from Stochastic Models, Estimation, by Peter Maybeck
- Kalman Filter webpage, with lots of links
- Kalman Filtering
- The unscented Kalman filter for nonlinear estimation
- Kalman Filters, thorough introduction to several types, together with applications to Robot Localization
References
- Gelb A., editor. Applied optimal estimation. MIT Press, 1974.
- Kalman, R. E. "A New Approach to Linear Filtering and Prediction Problems", Transactions of the ASME - Journal of Basic Engineering Vol. 82: pp. 35-45 (1960)
- Kalman, R. E., Bucy R. S., "New Results in Linear Filtering and Prediction Theory", Transactions of the ASME - Journal of Basic Engineering Vol. 83: pp. 95-107 (1961)
- [JU97] Julier, Simon J. and Jeffery K. Uhlmann. "A New Extension of the Kalman Filter to nonlinear Systems." In The Proceedings of AeroSense: The 11th International Symposium on Aerospace/Defense Sensing,Simulation and Controls, Multi Sensor Fusion, Tracking and Resource Management II, SPIE, 1997.
- Harvey, A.C. Forecasting, Structural Time Series Models and the Kalman Filter. Cambridge University Press, Cambridge, 1989.
- Roweis, S, and Z Ghahramani. "A Unifying Review of Linear Gaussian Models". Neural Computation Vol 11 No 2 (1999)
- Stengel, R. F., Optimal Control and Estimation Dover, 1994
