The Bayes Filter and the Predict-Update Cycle
Every state estimator from KF to particle filter is a Bayes filter with different assumptions — understand the cycle and you understand them all.
🎯 By the end you'll understand
How the Bayes filter unifies every state estimator you will use on FollowBot. What the predict step actually does to a belief distribution and why it always makes things worse. Why the update step multiplies (not adds) the likelihood. How to implement a discrete Bayes filter on a 1D corridor and read what the belief is telling you. The precise failure mode when the motion model underestimates process noise — why the filter becomes overconfident and why overconfidence is more dangerous than diffuse uncertainty.
KEY INSIGHTOne algorithm, infinite implementations
The Kalman filter, the particle filter, the histogram filter, and every variant in between are not separate inventions — they are the same two-step inference loop with different approximations chosen for computational tractability.
The Bayes filter is not a filter you ship in your robot. It is a mathematical framework with a recursive structure: maintain a probability distribution over the robot's state, called the belief; each cycle, first predict (propagate the belief forward through time using a model of how the robot moves), then update (sharpen the belief using a new sensor measurement). Ship it recursively until the robot finds its goal.
The predict step always spreads the belief — it makes you less certain about where you are. The update step always narrows the belief — a measurement eliminates possibilities. The filter is a conversation between these two tendencies. If you only predict and never update, uncertainty grows without bound. If you only update and never predict, you trust your last sensor reading forever, ignoring that the robot moved. The predict-update cycle is the minimal structure that balances both. Every filtering algorithm in Stage 4 is an implementation of this structure under specific assumptions about the shapes of the distributions involved.
CORE CONCEPTThe predict-update cycle derived from Bayes' rule
Start with the state at time t-1. The belief is a distribution over all possible states: bel(x_{t-1}). You want bel(x_t), the belief after one time step. Two things happened: the robot executed a control action u_t, and received a sensor measurement z_t. The Bayes filter processes them in order.
Predict step — propagate through the motion model
Before incorporating the new measurement, compute the prior belief at time t given only the motion:
bel̄(x_t) = ∫ p(x_t | u_t, x_{t-1}) · bel(x_{t-1}) dx_{t-1}
In words: for every possible current state x_t, sum over all previous states x_{t-1} the probability of being there times the probability of transitioning to x_t given the control u_t. The term p(x_t | u_t, x_{t-1}) is the motion model — a stochastic process model encoding that real robots do not execute commands perfectly. The result bel̄(x_t) is called the predicted belief or bar-bel. It is always more spread than the prior because integration through a stochastic model blurs probability mass.
Update step — incorporate the measurement
Now apply Bayes' rule using the new sensor reading z_t:
bel(x_t) = η · p(z_t | x_t) · bel̄(x_t)
The term p(z_t | x_t) is the measurement model (or observation likelihood) — it says: if the robot were truly at state x_t, how probable is this measurement? States that could have produced the measurement get amplified; states that couldn't get suppressed. η is a normalization constant (the inverse of the total probability mass) that ensures the result is a valid distribution summing to 1. This is exactly Bayes' rule: posterior = normalized (likelihood × prior).
Recurse
The posterior bel(x_t) becomes the prior for the next time step. The filter runs indefinitely, each iteration a predict-update pair. This Markov structure — where the current belief is sufficient to compute the next — is what makes the Bayes filter tractable. You never need the full history of measurements; the current belief encodes everything the filter knows.
Bayes' rule multiplies the likelihood by the prior, not adds. This makes intuitive sense: if the prior says you might be at position A (probability 0.3) and the measurement says position A is unlikely (likelihood 0.05), then the posterior for A is proportional to 0.3 × 0.05 = 0.015 — small, as it should be. A state that is both a priori likely AND consistent with the measurement gets amplified. A state that is inconsistent with either the prior or the measurement gets suppressed. Summing would not accomplish this selective suppression.
HOW IT WORKSThe motion model as a stochastic process
The motion model p(x_t | u_t, x_{t-1}) encodes physical realism: the robot's actuators are imperfect. You command "move forward 0.5 m" but wheel slip, motor backlash, and surface irregularities mean the robot might end up anywhere between 0.46 m and 0.54 m — or more, in rough terrain.
For a differential-drive robot like FollowBot, a standard motion model expresses the uncertainty as Gaussian noise on the commanded velocity and angular rate:
import numpy as np def sample_motion_model(x_prev, v_cmd, omega_cmd, alpha, dt): """ Sample from p(x_t | u_t, x_{t-1}) for a diff-drive robot. x_prev : [x, y, theta] — previous pose v_cmd : commanded linear velocity (m/s) omega_cmd : commanded angular rate (rad/s) alpha : [a1, a2, a3, a4] — noise params (tune per robot) dt : timestep (s) Returns sampled next pose [x, y, theta]. """ a1, a2, a3, a4 = alpha # Add noise to the commanded velocities — this IS the motion model v_noise = a1*v_cmd**2 + a2*omega_cmd**2 omega_noise = a3*v_cmd**2 + a4*omega_cmd**2 v = v_cmd + np.random.normal(0, np.sqrt(v_noise)) omega = omega_cmd + np.random.normal(0, np.sqrt(omega_noise)) # Integrate noisy velocity over dt (arc model) x, y, th = x_prev x_new = x + v*dt * np.cos(th + omega*dt/2) y_new = y + v*dt * np.sin(th + omega*dt/2) th_new = th + omega*dt return np.array([x_new, y_new, th_new])
The key engineering choice is the alpha vector. It controls how much the motion noise grows with commanded velocity versus commanded angular rate. Set alpha too small (underestimate noise), and the predict step barely spreads the belief — the filter is overconfident about where the robot went. Set it too large, and every predict step turns the belief into a diffuse fog, forcing heavy reliance on measurements. The widget below makes this concrete and explorable.
In the discrete (grid) case, the predict step is literally a discrete convolution: smear the probability mass from each grid cell into its neighbors according to the motion model's spread. In 1D, if the robot moves forward one cell with 80% probability, left-of-one-cell with 10%, and right-of-one-cell with 10%, the new belief at cell j is 0.8×bel(j-1) + 0.1×bel(j-2) + 0.1×bel(j). This is exactly bel̄ = motion_model * bel in the convolution sense. The Gaussian filters in later lessons replace discrete convolution with a matrix multiply, but the semantics are identical.
HOW IT WORKSThe measurement model as a conditional likelihood
The measurement model p(z_t | x_t) asks: given that the robot is truly at state x_t, how likely is the observed measurement? It is not asking where the robot is given the measurement (that would be the posterior, which is what the update step produces). The model captures sensor physics.
For a range-bearing sensor observing a known landmark at position m, the expected measurement when the robot is at pose (x, y, θ) is:
z_expected = sqrt((m_x - x)² + (m_y - y)²)
p(z | x) = N(z ; z_expected, σ²_sensor)
The Gaussian here has width σ_sensor, the measurement noise standard deviation. When the robot is near the landmark and measures a short range, states near the landmark become very likely. States far from the landmark (where the expected range would be large) get suppressed. The key parameter choice is σ_sensor:
| σ_sensor choice | Measurement model shape | Effect on belief after update | Risk |
|---|---|---|---|
| Too small (e.g., 0.01 m for a noisy LIDAR) | Narrow spike | Extremely sharp — one peak dominates | Inconsistent: filter rejects valid readings as outliers; easily loses track |
| Appropriate (matches real noise) | Moderate Gaussian | Gentle sharpening — good balance | Correct behavior |
| Too large (e.g., 2.0 m) | Broad, flat | Barely updates — measurement barely helps | Inefficient; slow convergence; sensor information wasted |
Getting both noise parameters right — process noise in the motion model and sensor noise in the measurement model — is the core calibration task of filter design. The widget makes this interactive.
SEE ITGrid Bayes filter — step through predict and update
A robot moves along a 1D corridor of 20 cells. Three landmarks are at cells 5, 11, and 17 in 1-indexed notation (cells 4, 10, 16 in the 0-indexed widget implementation — colored marks on the grid). At each step, the robot takes an action (move right by some number of cells) and then receives a measurement from the nearest visible landmark. Step through the cycle and observe how the belief evolves.
The bad decision to explore: set process noise to its minimum (sigma = 0.5) and watch what happens when you inject a wrong motion command — the filter becomes overconfident after predict, then stubbornly resists the measurement correction.
Notice the rhythm: predict widens, update narrows. With appropriate noise settings the filter quickly localizes the robot near a landmark. With process noise set to 1 (minimum) and a wrong motion command injected, watch the predicted belief shift in the wrong direction — and then observe how a large measurement-to-belief disagreement must overcome an overconfident (narrow) prior. The filter corrects, but slowly. This is the overconfidence failure mode.
CORE CONCEPTThe discrete Bayes filter — no approximation needed
The discrete Bayes filter (also called a histogram filter or grid filter) is the only Bayes filter variant that is exact within its representational choice. It represents the belief as a probability mass function over a finite set of discrete states — in our widget, 20 grid cells.
The algorithm is three steps:
import numpy as np N_CELLS = 20 LANDMARKS = [5, 11, 17] # known landmark positions (1-indexed, matching prose) def predict(bel, cmd, sigma_motion): """ Convolve belief with motion model. cmd: intended cells to move right sigma_motion: std dev of motion noise (in cells) """ bel_bar = np.zeros(N_CELLS) for x_prev in range(N_CELLS): if bel[x_prev] < 1e-10: continue # motion model: Gaussian centered at (x_prev + cmd) for x_new in range(N_CELLS): diff = x_new - (x_prev + cmd) p_motion = np.exp(-0.5 * (diff / sigma_motion)**2) bel_bar[x_new] += bel[x_prev] * p_motion # normalize total = bel_bar.sum() if total > 0: bel_bar /= total return bel_bar def update(bel_bar, z_measured, sigma_sensor): """ Multiply by likelihood and normalize. z_measured: range to nearest landmark (in cells) sigma_sensor: std dev of sensor noise (in cells) """ bel = np.zeros(N_CELLS) for x in range(N_CELLS): # expected range from x to nearest landmark dists = [abs(x - lm) for lm in LANDMARKS] z_exp = min(dists) likelihood = np.exp(-0.5 * ((z_measured - z_exp) / sigma_sensor)**2) bel[x] = likelihood * bel_bar[x] # normalize (eta) total = bel.sum() if total > 0: bel /= total return bel
The discrete filter is exact but does not scale. With 20 cells, the predict step is O(N²) = 400 operations. With a 2D map at 5 cm resolution over a 10×10 m room, N = 40,000 and the predict step becomes O(1.6 billion) operations per timestep — hopeless at 10 Hz. This is why real robots use the Kalman filter (which replaces the N-dimensional distribution with a Gaussian parameterized by mean and covariance, reducing cost dramatically) or the particle filter (which samples a manageable M ≪ N particles). You are still running the same Bayes filter; you have just chosen a different approximation to make it fast enough.
In low-dimensional, discrete state spaces. Global localization in a known 1D or small 2D map. Topological localization over a graph of N rooms. Any problem where the state space is small enough that storing a probability at every state is feasible. The discrete filter is also the gold standard for validating approximate filters: if your particle filter disagrees with the discrete filter on a small test case, your particle filter has a bug.
FOLLOWBOTThe Bayes filter at the heart of FollowBot's EKF
Everything FollowBot uses for state estimation in Stage 4 is an instance of the Bayes filter. The Extended Kalman Filter — which you will derive in Lesson 4.3 — is a Bayes filter under two assumptions: the state transition and measurement functions are nonlinear but locally linearizable, and all distributions are Gaussian. Swap out those assumptions and you get a different filter, but the predict-update structure stays identical.
Here is the mapping for FollowBot's EKF at Stage 4 milestone:
| Bayes filter concept | FollowBot EKF implementation |
|---|---|
bel(x_t) — belief distribution | Gaussian N(μ_t, Σ_t) with state vector [x, y, θ, v, ω] |
Motion model p(x_t | u_t, x_{t-1}) | Differential-drive kinematics + additive Gaussian process noise Q |
Measurement model p(z_t | x_t) | Wheel odometry observation model (H matrix); LIDAR scan-matching innovation; IMU angular rate observation |
| Predict step | f(μ_{t-1}, u_t) + F_t Σ_{t-1} F_t^T + Q — mean propagated through kinematics; covariance inflated by Q |
| Update step | Kalman gain K_t = Σ̄_t H_t^T (H_t Σ̄_t H_t^T + R_t)^{-1}; posterior = prior + K_t (z_t - ĥ(μ̄_t)) |
| Normalization η | Implicit in the Kalman gain formula — the posterior covariance Σ_t = (I - K_t H_t)Σ̄_t |
The process noise matrix Q is the EKF equivalent of sigma_motion in the discrete filter above. Get it wrong in exactly the same direction — set Q too small — and the EKF's predict step barely inflates the covariance. The filter becomes overconfident after every predict step and will resist large measurement innovations, leading to the divergence behavior described in the Mistakes section below. This is the dominant failure mode for FollowBot's EKF during the Stage 4 milestone.
import rclpy from rclpy.node import Node import numpy as np from nav_msgs.msg import Odometry from sensor_msgs.msg import Imu class FollowBotEKF(Node): def __init__(self): super().__init__('followbot_ekf') # State: [x, y, theta, v, omega] — 5D self.mu = np.zeros(5) self.Sig = np.eye(5) * 0.1 # initial covariance # Process noise Q — MUST be tuned; too small → overconfidence self.Q = np.diag([0.01, 0.01, 0.005, 0.05, 0.02]) self.create_subscription(Odometry, '/odom', self.odom_cb, 10) self.create_subscription(Imu, '/imu', self.imu_cb, 10) def predict(self, u, dt): # ---- BAYES FILTER PREDICT STEP ---- v, omega = u th = self.mu[2] F = np.eye(5) # Jacobian of f w.r.t. state (simplified) F[0, 3] = dt * np.cos(th) F[1, 3] = dt * np.sin(th) F[2, 4] = dt self.mu[0] += v * dt * np.cos(th) self.mu[1] += v * dt * np.sin(th) self.mu[2] += omega * dt self.Sig = F @ self.Sig @ F.T + self.Q # covariance grows by Q def update(self, z, H, R): # ---- BAYES FILTER UPDATE STEP ---- S = H @ self.Sig @ H.T + R K = self.Sig @ H.T @ np.linalg.inv(S) # Kalman gain y = z - H @ self.mu # innovation self.mu = self.mu + K @ y self.Sig = (np.eye(5) - K @ H) @ self.Sig # covariance shrinks def odom_cb(self, msg): v = msg.twist.twist.linear.x omega = msg.twist.twist.angular.z self.predict([v, omega], dt=0.05) # 20 Hz odom # then update with odom position observation… def imu_cb(self, msg): omega_imu = msg.angular_velocity.z H = np.zeros((1, 5)); H[0, 4] = 1.0 # observe omega R = np.array([[0.001]]) self.update(np.array([omega_imu]), H, R)
By the end of Stage 4, FollowBot's EKF fuses wheel odometry, IMU, and LIDAR scan-matching updates with state vector [x, y, θ, v, ω]. Filter consistency is validated using the Normalized Estimation Error Squared (NEES) test — if the EKF is consistent, NEES should be chi-squared distributed with 5 degrees of freedom. Position error below 0.1 m RMS in a known map. The predict-update cycle running in this lesson is exactly the structure you will have running in real time on FollowBot's Jetson.
WEAKNESSWhere the Bayes filter bites
This is the dominant EKF failure mode in practice. When the motion model's process noise (Q in the EKF, sigma_motion in the discrete filter) is set too small, the predict step barely inflates the uncertainty. The filter's posterior covariance stays narrow. Now a measurement arrives that disagrees significantly with the predicted mean — perhaps a wheel slipped and the robot moved further than expected. The update step weights the innovation by the Kalman gain K = Σ̄ H^T (H Σ̄ H^T + R)^{-1}. With small Σ̄ (overconfident predicted belief), K is small, meaning the measurement is barely incorporated. The filter is "trusting its model more than its sensors" — which is exactly wrong when the model is wrong. The symptom: the robot localizes well under normal motion, then after an unexpected event (wheel slip, push by a person) the filter diverges quickly and never recovers. The fix is tuning Q correctly — not the sensor noise R.
The general Bayes filter requires representing an arbitrary probability distribution over a continuous, potentially high-dimensional state space, and performing exact integration in the predict step. This is computationally impossible except for the linear-Gaussian case (Kalman filter) and the discrete case (histogram filter). Every other filter — EKF, UKF, particle filter — is an approximation. The approximation errors are not benign: the EKF can diverge on high nonlinearity; the particle filter can suffer particle deprivation in high-dimensional spaces. Understanding that you are always approximating the Bayes filter, and which approximation you are using and where it fails, is the difference between an engineer who understands their filter and one who treats it as a black box.
The Bayes filter's recursive structure requires the Markov property: the current belief encodes everything relevant about the past. This fails when the environment has perceptual aliasing — multiple distinct locations that produce identical measurements. In the widget's 1D corridor, if you had landmarks at cells 5, 11, and 17 that all look identical (same range, no distinguishing feature), the measurement update would amplify belief at all three equally. The filter converges to a multimodal distribution and never picks the right peak. This is global localization ambiguity, and it cannot be resolved by a Kalman filter (which only represents one Gaussian peak) — you need a particle filter. The dangerous failure mode: in a symmetric building (hallways that look alike), an EKF-based localizer may confidently report the wrong room without any error flag.
KEY INSIGHTHow it connects
- 4.1 · Probability for Robotics: Belief, Bayes, and Why Point Estimates Fail — the prior lesson established why distributions are necessary and what Bayes' rule means. This lesson instantiates those ideas as a recursive algorithm. The belief distribution introduced in 4.1 is exactly what the Bayes filter maintains and manipulates.
- 4.3 · The Kalman Filter: Derivation and Geometric Intuition — the Kalman filter is the Bayes filter restricted to linear dynamics and Gaussian distributions. Lesson 4.3 derives it from scratch and shows geometrically what the predict and update steps look like in 2D state space. Every formula you see in 4.3 is the closed-form solution to the integrals in this lesson's predict-update equations.
The predict-update cycle you have learned in this lesson will appear in every filter for the rest of Stage 4. When the EKF linearizes, it is approximating the predict integral. When the particle filter samples, it is approximating the same integral with Monte Carlo. When the UKF uses sigma points, it approximates the integral with a deterministic quadrature rule. Same cycle. Different approximations. Same failure modes at the same places.
GLOSSARYKey terms introduced
- Bayes filter
- A recursive algorithm that maintains a probability distribution (belief) over a robot's state. Each iteration has a predict step (propagate through the motion model) and an update step (multiply by measurement likelihood and normalize). Every practical filter is an approximation of the Bayes filter.
- Belief (bel(x_t))
- The probability distribution the filter maintains over the robot's state at time t. Represents everything the filter knows about where the robot is, encoded as a distribution rather than a point estimate.
- Motion model (p(x_t | u_t, x_{t-1}))
- A stochastic model of how the robot transitions between states given a control command. Encodes that actuators are imperfect. Its uncertainty parameter (process noise) must be calibrated to the real robot; underestimating it causes overconfidence.
- Measurement model (p(z_t | x_t))
- The likelihood that a particular measurement z_t would be observed if the robot were truly at state x_t. Used in the update step to amplify states consistent with the measurement and suppress states that are not.
- Process noise (Q)
- The noise term added to the covariance during the predict step, representing unmodeled forces, wheel slip, and actuator imprecision. Setting Q too small causes the filter to be overconfident after prediction and resistant to large measurement updates.
- Overconfidence (filter consistency failure)
- The condition in which the filter's estimated uncertainty (covariance) is smaller than the true estimation error. Caused by underestimated process or sensor noise. Diagnosed formally using the NEES test. A filter that is overconfident but wrong is more dangerous than one that is uncertain and correct.
- Discrete Bayes filter
- An exact implementation of the Bayes filter over a finite discrete state space. Computationally exact within its representational choice but does not scale to large continuous spaces. Useful for validation and low-dimensional localization problems.
- Perceptual aliasing
- The condition in which multiple distinct states in the environment produce identical or indistinguishable sensor measurements. Causes the measurement update to be ambiguous, leading to multimodal beliefs that Gaussian filters cannot represent. Requires particle filters or other multimodal representations to resolve.
ACTIVE RECALLCheck your understanding
Answer in your own words first, then reveal.
1Why does the predict step always increase uncertainty, and what parameter controls the size of that increase?›
The predict step convolves the belief with the motion model, which is itself a distribution with nonzero spread. Convolving two distributions always produces a distribution at least as wide as the wider of the two inputs — mathematically, variances add. In the EKF, the predicted covariance is Σ̄_t = F Σ_{t-1} F^T + Q: the old covariance propagated through the Jacobian, plus the process noise Q. Q is the parameter that directly controls how much uncertainty is added per timestep. It must be set to reflect the real mismatch between the commanded and actual motion — not zero, and not arbitrarily large. If you set Q to zero, the filter assumes the robot executes commands perfectly and never increases its uncertainty during prediction, which is physically wrong for every real actuator.
2The Bayes filter update step multiplies the prior by the likelihood and then normalizes. What would happen if you added instead of multiplied?›
Addition would not correctly implement Bayesian inference. The multiplication is required by Bayes' rule: the posterior is proportional to the likelihood times the prior. Multiplication achieves selective suppression — a state that scores low on either the prior or the likelihood gets suppressed, a state that scores high on both gets amplified. This is the mechanism by which the filter intersects what it already knew with what the sensor says. Addition would instead superimpose them: a state that had zero prior belief (completely ruled out) could still gain positive posterior probability if the likelihood were nonzero. That would violate the fundamental property that zero prior probability remains zero regardless of evidence.
3FollowBot's EKF is localizing well under normal operation, but after the robot is pushed sideways by a person (an unmodeled disturbance), the filter diverges and never recovers. What went wrong at the algorithmic level, and what is the fix?›
The process noise matrix Q is underestimated. When the robot is pushed, the actual motion differs from the commanded motion by more than Q allows for. The predict step barely inflates the covariance, so the posterior remains narrow even though the true state could be anywhere in a wide region. When the next measurement arrives, the Kalman gain K is small (because the predicted covariance Σ̄ is small), so the filter trusts the measurement very little and the innovation is absorbed weakly. The estimated state barely moves toward the true state. Over successive steps, the error accumulates faster than the filter can correct, and it diverges. The fix is correct calibration of Q — it should reflect the worst-case unmodeled disturbance the robot might experience, not just steady-state noise. A common approach is to log ground-truth vs. EKF-estimated state over multiple runs and fit Q to the observed prediction errors empirically, then validate filter consistency using the NEES test.
4What is the key difference between the discrete Bayes filter and the Kalman filter, and when would you choose one over the other?›
The discrete Bayes filter represents the belief as a probability mass at each cell in a discrete grid — it is exact and can represent any distribution shape, including multimodal beliefs. The Kalman filter represents the belief as a Gaussian parameterized by a mean vector and covariance matrix — this is an approximation (real posteriors are rarely exactly Gaussian) but is vastly more efficient: O(n³) for matrix operations on the state dimension rather than O(N²) on the number of grid cells. Choose the discrete filter when the state space is small (a corridor of 20 cells, or a topological map of 10 rooms), when multimodal beliefs matter (global localization), or when you need an exact reference to validate an approximate filter. Choose the Kalman filter when the state is high-dimensional (6-DOF pose plus velocity), the dynamics are near-linear, and you need to run at 10–200 Hz on limited compute. For FollowBot's indoor localization with a known map, the EKF is the right choice — the state space is too large for a grid, the dynamics are weakly nonlinear, and unimodal beliefs are sufficient once the robot is initialized near its true pose.