State Estimation

The perception pipelines of the scene understanding chapter estimate where the objects of interest are in the image coordinate frame. These estimates do not amount to what humans call understanding. Giving each object a symbolic identity is one step toward it, because it lets an embodied agent reason about the scene with the symbolic methods the AI community has developed over many decades.

Block diagram of an embodied agent: perception feeds probabilistic reasoning, which feeds planning and control, all interacting with the environment.

Where probabilistic reasoning sits in an embodied agent. The Bayesian inference section treated two random variables, captured by a joint distribution

p(x, y)

, and inferred the posterior of one given the other. This chapter extends that picture in two ways:

It introduces a state $s$ that gathers many random variables, and considers dynamical systems whose state evolves over time, often with nonlinear dynamics, as is common in robotics.
It makes the time index $t$ explicit, so the evolution of the state can be drawn as a graphical model.

The perception subsystem turns sensor data into noisy estimates, such as object detections. The noise comes both from the algorithms and from imperfect sensors. The model that maps the true state to these estimates is the measurement model, also called the sensor model. Together with the transition model, which describes how the state changes, it is all you need to apply Bayes’ rule recursively. The result is the recursive state estimator, better known as the Bayes filter. It lets the agent maintain an internal belief about the current state of the environment. This chapter covers state estimation techniques essential for robotics, including Bayesian filtering and Kalman filters.

Sections

The Bayes filter

Prediction and measurement update, worked through on a door example.

Discrete Bayes filter

The Bayes filter on a finite state space, tracking a robot along a hallway.

Kalman filters

Gaussian beliefs and linear models, built up in one dimension.

Extended Kalman filter

Linearizing nonlinear motion and measurement models, and where that fails.

An overconfident EKF prediction

One EKF prediction step on a TurtleBot, compared with samples of the robot’s real motion.

EKF localization

The Bayes filter with a known map, then tracking a robot’s pose against landmarks with known correspondences.

Importance sampling

Expectations under a target from samples of a proposal, with weights and resampling.

Particle filter

A sample-based Bayes filter, used to locate drone modems from LTE and 5G measurements.

Adaptive Monte Carlo localization

The particle filter that Nav2 runs to localize a robot in a saved map, and how its code departs from the textbook.

Video lectures on state estimation are available in the Media section under the Robotics course.

Found an error on this page? Report an issue.