Kalman Filters

Colin Shaw

04.27.2017

  1. Introduction
  1. Welcome to Computer Science Club
  2. Thank you to RevUnit for sponsoring

  1. What are Kalman filters used for?
  1. General time series analysis
  1. Econometrics
  1. Motion planning
  1. Guidance
  2. Navigation
  3. Apollo lander and nuclear missiles
  1. Sensor fusion
  1. Lidar
  2. Radar

  1. How Kalman filters fit in the larger world
  1. Measurement
  1. Measuring the world around you
  2. Coordinates relative to you
  3. Examples
  1. Kalman filters
  1. Plain (linear) Kalman filters
  2. Extended Kalman filters
  3. Unscented Kalman filters
  1. Double Exponential Smoothing
  2. Recursive Total Least Squares
  1. Localization
  1. Measuring your position in the world
  2. Your position in larger map coordinates
  3. Examples
  1. Particle filters
  2. Histogram filters
  1. Both measurement and localization
  1. Simultaneous Localization and Measurement (SLAM)

  1. Torrid history of the introduction of the Kalman filter
  1. Rudolph Emil Kalman’s 1960 paper
  1. Hidden model was looked at with great skepticism
  2. Not met with open arms in the community
  3. EE journals would not publish it (ended up in ME)
  1. Unscented Kalman filters
  1. Met with skepticism
  2. Again hard to publish

  1. What type of process is a Kalman filter?
  1. Linear quadratic estimator
  1. Linear system
  2. RMSE can be minimized by minimizing quadratic
  1. Bayesian estimator
  1. Prior
  2. Distribution
  3. Posterior
  4. Conjugate priors
  1. Markov process
  1. Future probabilities determined by most recent state

  1. How are we presenting Kalman filters here?
  1. Developing intuition about a basic motion model
  2. Look at what we need to use the motion model
  3. Discuss noisy process and measurements
  4. Jump to talking about probability distributions
  5. Show the full set of Kalman filter equations
  6. Walk through a Kalman filter code example
  7. Discuss more complex motion models and sensor fusion
  8. Discuss deviation from a linear model

  1. Intuition regarding the motion model
  1. Draw measurements at time t = 0, 1, 2
  2. Infer measurement at time t = 3
  3. How do we know where the next point is?
  1. Mental model is more than the measurements
  2. It has implied velocity
  1. How do we correct for errors
  1. Error is the actual minus predicted (residual)
  2. Apply scaled residual to update model

  1. More formality to the motion model
  1. Vector of position x and velocity v (or ẋ)

state_vector.png

  1. State updates occur with a state transition function

state_transition.png

  1. We can only observe measurables, so there is a measurement function H

measurement_function.png

  1. The errors can be assumed to be acceleration noise
  1. There is a force causing the change in velocity
  2. There is an acceleration associated with the force
  3. This noise is distributed N(0, 𝝈a2)

  1. Adding the notion of noise
  1. What if we had noisy measurements only
  1. For each t = 0, 1, 2, … we assume position error is distributed N(0, 𝝈x2)
  2. What does this give us?
  1. The standard deviation at these positions
  2. In effect, nothing
  1. We need more information to be able to refine estimates of uncertainty
  1. Think about the Bayesian estimation notion of the problem
  2. We can use a prior and a new distribution to compute a posterior

  1. Brief probability distribution review
  1. Gaussian.ipynb 
  2. What is a normal distributed random variable
  1. Mean
  2. Standard deviation
  1. Adding normally distributed random variables
  1. Analytical result
  1. 𝜇 = 𝜇1 + 𝜇2
  2. 𝝈2 = 𝝈12 + 𝝈22
  1. Pointwise addition
  2. Convolution (ConvolutionAddition.ipynb)
  1. Multiplying Gaussians
  1. Analytical result
  1. 𝜇 = 𝜇1 𝝈22 + 𝜇2 𝝈12 / 𝝈12 + 𝝈22         (normalized weighted average)
  2. 𝝈2 = 𝝈12 𝝈22 / 𝝈12 + 𝝈22                 (parallel sum)
  1. PDF demonstration

  1. Kalman filter model
  1. Prediction
  1. Predicted State Estimate

predicted_state_estimate.png

  1. Predicted Estimate Covariance

predicted_estimate_covariance.png

  1. Measurement
  1. Innovation Residual

innovation_residual.png

  1. Innovation Covariance

innovation_covariance.png

  1. Optimal Kalman Gain

optimal_kalman_gain.png

  1. Updated State Estimate

updated_state_estimate.png

  1. Updated Covariance Estimate

updated_covariance_estimate.png

  1. Intuition about what the Kalman filter is doing
  1. PositionVelocity.ipynb
  2. Steps
  1. Initial position estimate (poor velocity knowledge)
  2. Project to arbitrary velocity distribution
  3. New measurement (decent position, poor velocity knowledge)
  4. Posterior distribution now has much better position and velocity
  5. Repeat
  1. Basic idea
  1. Additive noise (both prediction and measurement)
  2. Multiplicative refinement in the Kalman gain calculation

  1. Measuring error 
  1. Root Mean Squared Error (RMSE)
  1. How to compute

rmse.png

  1. Is not normalized
  2. Depends on knowing ground truth
  1. Normalized Innovation Squared (NIS)
  1. ChiSquared.ipynb
  2. How to compute

normalized_innovation_squared.png

  1. Is normalized
  2. Does not depend on ground truth

        

  1. Kalman filter code example
  1. KalmanFilter.ipynb
  2. Numpy for matrix arithmetic
  3. Steps
  1. Initialize state and covariance
  2. Compute state prediction
  3. Update with measurement
  4. Repeat
  1. Error estimation

  1. More complex motion models
  1. Sensor fusion
  1. Merge two (or more) types of measurements
  2. Get better results than any provide alone
  1. Example
  1. Radar
  1. Radius (inaccurate)
  2. Radial velocity (accurate)
  3. Angle (inaccurate)
  1. Lidar
  1. Radius (accurate)
  2. Angle (accurate)
  1. Measurement and state transfer function in general could be nonlinear

  1. Deviation from the linear Kalman filter model
  1. GaussianTransformation.ipynb
  2. Extended Kalman filters
  1. Linearize the nonlinear mappings
  2. Jacobian evaluation instead of matrix-vector multiplication
  3. Can be expensive to compute
  4. Not so good results in difficult cases
  1. Very nonlinear functions
  2. Non-normal distributions
  1. Unscented Kalman filters
  1. Sample sigma points
  2. Map sigma points
  3. Estimator of distribution without knowing specifics
  4. Relatively inexpensive to compute
  5. More stable results in most cases