M5-T1 — State, Controls, Measurements and the Markov Assumption

Learning objectives

After this lesson, you should be able to:

• Distinguish the state, the controls and the measurements of a robot, and give a state for a ground robot, a drone and a humanoid.
• Draw the dynamic Bayes network of a robot and name its two conditional distributions, the motion model and the measurement model.
• State the Markov assumption and derive the factorization of the joint distribution that it gives.
• Test whether a state is complete from data, and repair an incomplete state by adding variables.

The intuition

Three kinds of quantity appear in every robot filter, and keeping them apart avoids a great deal of confusion.

• The state $x_t$ is what the robot needs to know in order to predict what happens next: its pose, and often its velocity, sensor biases, or the positions of landmarks. It is hidden: nothing measures it directly, and the filter keeps a belief about it.
• The controls $u_t$ are what the robot does: a commanded speed and turn rate, or the wheel-encoder increments between two moments. They are known (though not exact), and they are the input of the motion model.
• The measurements $z_t$ are what the sensors report: ranges, bearings, images, GNSS fixes. They are known, and they depend on the state.

The structure that links them is the same for a vacuum robot and a spacecraft, and is drawn below. Time runs from left to right. The new state depends on the previous state and the control, and the measurement depends on the current state. Nothing else is connected: in particular there are no arrows from old states or old measurements straight into the new state.

The missing arrows are a claim about the world, the Markov assumption: once the current state is known, the past (earlier states, controls and measurements) carries no further information about the future. It is a statement about the choice of state. If the robot's next position depends on how fast it is going, and the speed is not in the state, then the assumption is false: the previous position also matters, because it reveals the speed. The repair is to put the speed in the state.

What goes in the state?

The state is a modelling choice with one test: does knowing it make the past irrelevant for predicting the future? If not, something is missing from it.

Definitions

State $x_t$

The collection of quantities that, if known, would make the future independent of the past. Not directly observed.

Control $u_t$

The action or its measured effect between time $t-1$ and $t$. Treated as a known input, although a command is not what the robot actually did.

Measurement $z_t$

The sensor data at time $t$.

Motion model $p(x_t \mid x_{t-1}, u_t)$

The distribution of the new state given the old state and the control: the physics, with its uncertainty.

Measurement model $p(z_t \mid x_t)$

The distribution of the reading given the state: the sensor, with its noise. Also called the observation or sensor model. As a function of $x_t$ with the reading fixed it is the likelihood of the last module.

Complete state

A state such that $x_t$ alone summarises everything in the past that is relevant for the future. Also called a Markov state.

Derivation: the factorization of a robot run

The joint distribution of everything a robot does and sees looks hopeless: it has one variable per state, per reading, for every moment of a run. The Markov assumptions collapse it into a product of small pieces. The derivation is the chain rule with some terms dropped.

1. $$p(x_{0:t}, z_{1:t} \mid u_{1:t}) = p(x_0)\; \prod_{k=1}^{t}\; p(x_k \mid x_{0:k-1}, z_{1:k-1}, u_{1:t})\;\, p(z_k \mid x_{0:k}, z_{1:k-1}, u_{1:t})$$

   The chain rule (the joint-probability lesson), ordering the variables in time: first $x_0$, then for each step the new state followed by the new measurement, each conditioned on everything before it.

2. $$p(x_k \mid x_{0:k-1}, z_{1:k-1}, u_{1:t}) = p(x_k \mid x_{k-1}, u_k)$$

   Markov assumption for motion. The new state depends on the previous state and the current control only. In particular it does not depend on later controls $u_{k+1:t}$: what the robot will do next cannot affect where it is now.

3. $$p(z_k \mid x_{0:k}, z_{1:k-1}, u_{1:t}) = p(z_k \mid x_k)$$

   Markov assumption for measurement. The reading depends on the state at that moment only.

4. $$p(x_{0:t}, z_{1:t} \mid u_{1:t}) = p(x_0)\; \prod_{k=1}^{t}\; p(x_k \mid x_{k-1}, u_k)\;\, p(z_k \mid x_k)$$

   Substitute. The joint is a product of one prior and $2t$ small conditional distributions, each over one or two variables.

Two consequences are worth stating, because they are what the filters of the next modules exploit.

• Recursion. To update the belief about $x_t$ you need only the belief about $x_{t-1}$, the new control and the new measurement. The history can be thrown away. This is what makes the filter a loop of constant cost per step.
• Conditional independence. Given the state, the readings of different times are independent, which is exactly what allows the product of likelihoods of M3-T3: Independence and Conditional Independence.

Testing completeness

If the state is complete, then adding more of the past to the conditioning does not sharpen the prediction: $p(x_t \mid x_{t-1}, x_{t-2}) = p(x_t \mid x_{t-1})$. So a practical test from logged data is to predict the next state from the last state alone and from the last two, and compare the errors. A large improvement means the past still carries information, and the state is incomplete. The worked example does exactly this.

The Markov assumption is a design decision about the state, not a law of nature. A state is complete when its past is irrelevant, and you make it complete by adding the variables through which the past still acts.

A worked example

A robot drives along a line. Its speed $v$ is about 1.2 m/s and drifts slowly (a random change of 0.02 m/s per step); the position follows the speed with a little extra noise, time step 0.1 s. We simulate 2000 steps and ask: is the position alone a complete state?

1. Predict from the last position only. The best guess for the next position is the last one, which ignores that the robot is moving. The root-mean-square error is $0.122$ m: about one step of travel, $v\,\Delta t = 0.117$ m.
2. Predict from the last two positions. The difference of the last two positions is an estimate of the velocity. Extrapolating with it, $\hat{x}_t = 2x_{t-1} - x_{t-2}$, gives an error of 0.0034 m, 36 times smaller.
3. Predict from position and speed. With the true speed in the state, the error is 0.0028 m, hardly better than the two-position predictor, which has already recovered the speed from the history.
4. The verdict. Adding one earlier position shrank the error by a factor of 36, so the position alone is not a complete state: the past still matters, through the speed. The cure is to add the speed to the state, and then the history is no longer needed (the third predictor). This is why the constant-velocity filter of module 7 has the state (position, velocity).

import math
from robotprob import Rng

rng = Rng(14)
dt, n = 0.1, 2000
x, v = 0.0, 1.0
xs, vs = [], []
for _ in range(n):
    v += rng.gauss(0.0, 0.02)                 # the speed drifts slowly
    x += v * dt + rng.gauss(0.0, 0.002)       # the position follows the speed, plus a little noise
    xs.append(x)
    vs.append(v)

def rms(e):
    return math.sqrt(sum(a * a for a in e) / len(e))

e_last = [xs[t] - xs[t - 1] for t in range(2, n)]                      # predict x_t = x_{t-1}
e_vel = [xs[t] - (2 * xs[t - 1] - xs[t - 2]) for t in range(2, n)]     # extrapolate with the last step
e_state = [xs[t] - (xs[t - 1] + vs[t - 1] * dt) for t in range(2, n)]  # use position and speed
print('prediction error of the next position (rms, metres):')
print('  from the last position only        :', round(rms(e_last), 4))
print('  from the last two positions        :', round(rms(e_vel), 4))
print('  from position and the true speed   :', round(rms(e_state), 4))
print('mean speed', round(sum(vs) / n, 3), ' so the first number is about speed * dt =', round(sum(vs) / n * dt, 4))

prediction error of the next position (rms, metres):
  from the last position only        : 0.122
  from the last two positions        : 0.0034
  from position and the true speed   : 0.0028
mean speed 1.174  so the first number is about speed * dt = 0.1174

In robotics

Choosing the state is the first design step of a filter

Writing a localizer starts with a list: which quantities does the next pose depend on, and which of them are not directly measured? An omnidirectional base that can change velocity instantly can use the pose alone. A heavy delivery robot with wheel-speed controllers has dynamics (acceleration limits, slip) that a velocity belongs in the state to capture. A drone's attitude estimate needs the gyroscope biases as states, because they would otherwise appear as an unexplained slow drift. The UAV course derives such a state in Error-State Kalman Filter and PX4 state estimation and EKF2.

Controls are not exact

The control in the motion model is what the robot is believed to have done, with noise. Many robots use the wheel-encoder increments from the last step as the “control” (the odometry motion model of M5-T2: Odometry and Velocity Motion Models), because they are a better description of the motion than the commanded velocity. A commanded velocity is not what the wheels did: slip, acceleration limits and latency all intervene. Treating either as exact makes the filter overconfident.

Where the assumption fails in practice

• Unmodelled dynamics and latency. A command that takes 100 ms to act means the state at time t depends on the control at time t − 3: the past still matters unless the delay is modelled (state augmentation).
• Correlated sensor errors. If the error of a GNSS fix persists for seconds, the measurement at time t depends on earlier readings beyond the state, as in M3-T3: Independence and Conditional Independence. Add a slowly varying error term (a bias) to the state.
• Dynamic environments. A person walking through the scan makes the measurement depend on something outside the state. Treat it as an outlier component of the measurement model, or track the person as part of the state.
• Map errors. A localizer that treats the map as given is Markov only if the map is correct. SLAM adds the map to the state to remove this assumption.

More state is not free

Each added variable costs computation (the cost of a Kalman update grows as the cube of the number of states) and needs to be observable, meaning the measurements must contain information about it. An added state that no measurement can see just drifts; module 7 discusses observability. The aim is the smallest state that makes the past irrelevant.

Common misconceptions

Key takeaways

1. The state is what the robot needs to know to predict the future (hidden); the controls are its actions or odometry (known, noisy); the measurements are the sensor data, which depend on the state.
2. A robot run is described by a prior p(x₀) and, per step, a motion model p(xₜ | xₜ₋₁, uₜ) and a measurement model p(zₜ | xₜ).
3. The Markov assumption: given the current state, the past adds nothing. It turns the joint distribution into p(x₀) Π p(x_k | x_k−1, u_k) p(z_k | x_k) and makes the filter recursive.
4. A state is complete when predicting from its past does not improve with more history. Test it by comparing predictors that use one and two past values.
5. An incomplete state is repaired by adding variables (speed, biases, delays, the map). Each addition costs computation and must be observable.

References and further reading

Each source is marked free or paid. Free to read does not mean free to reuse: the course resources page lists every source with its licence.

• S. Thrun, W. Burgard and D. Fox, Probabilistic Robotics, MIT Press, 2005, sections 2.3 and 2.4 (state, environment interaction, the generative laws and the Markov assumption). Paid book.
• T. D. Barfoot, State Estimation for Robotics, 2nd edition, Cambridge University Press, 2024 , chapters “Linear-Gaussian Estimation” (the motion and observation models). Free to read as the author’s PDF; the book is copyrighted.
• C. Stachniss, “Bayes Filter” (video lecture) , the graphical model and the Markov assumption. Free to watch.
• S. Särkkä and L. Svensson, Bayesian Filtering and Smoothing, 2nd edition, Cambridge University Press, 2023 , chapters 1 and 5 (state-space models). Free to read for personal use; no redistribution or derivative works.

Knowledge check

Three questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

With the structure fixed, the next lesson builds the first of the two conditional distributions: the motion model, in its two standard forms, with the noise that makes the uncertainty of a dead-reckoned pose grow.

Related content

Nothing below is required to finish this lesson.

Other courses on this site treat neighbouring topics from their own angle:

• SLAM M1-T5: Odometry and Motion Models
• SLAM: Motion and Observation Models
• Robot Foundations 05: Where Am I?
• UAV M3-T7: IMU noise and bias modelling