Kalman Filter, Live
Lesson 2 · Dead reckoning

Dead reckoning: adding up moves makes the estimate drift

Lesson 1 ended with two thermometers in a room that stood still. Now the thing we measure moves. Picture walking from your front door to the kitchen with your eyes closed, counting steps. Each step is a little longer or shorter than you think, and those small errors add up. A robot with only a wheel encoder does the same: each step the encoder reports how far the robot moved, u[n] (read "u at step n"; the square brackets give the step number), and the robot adds up those moves. That is called dead reckoning. Its estimate slowly drifts away from the true position, and nothing pulls it back.

Lesson 2 · slide 1Dead reckoning
x̂[n] = x̂[n−1] + u[n]    P[n] = P[n−1] + Q    after n steps from a known start (P = 0): P = n·Q
Key ideas
  1. Words first: u[n] = the move the encoder reports at step n. x̂[n] = our estimate of the position after step n. P = how unsure we are (the variance of that estimate). Q = the variance one noisy move adds each step.
  2. Dead reckoning: start at a known spot and keep adding the measured moves: x̂[n] = x̂[n−1] + u[n].
  3. Each step adds a fresh error, and the errors accumulate instead of cancelling.
  4. The variance P grows by Q every step, so P = n·Q and σ grows like √n.
  5. With no position sensor, nothing ever shrinks P. The estimate drifts.

Walking with your eyes closed

Stand at your front door, close your eyes and walk to the kitchen by counting steps. The first few steps go fine. But each step is a bit longer or shorter than you think. After twenty steps you bump into a wall that "should not be there". You did nothing wrong. The small errors just added up.

A robot with only a wheel encoder has the same problem.

The encoder and dead reckoning

An encoder is a sensor on the wheel that counts how far it turns. u[n] is the move the encoder reports for step n, in metres: the true move plus some noise.

Dead reckoning means: start at a known position, then keep adding the measured moves.

x̂[n] = x̂[n−1] + u[n]

The hat on x̂ means "our estimate of x", not the true value. The [n] is the step number. We add u[n], the move the encoder reports, because the true move is unknown. A quick example: the robot starts at 2 m and the encoder reports moves of 0.6, 0.4 and 0.5 m.

x̂[1] = 2 + 0.6 = 2.6 m  →  x̂[2] = 2.6 + 0.4 = 3.0 m  →  x̂[3] = 3.0 + 0.5 = 3.5 m

Why the errors pile up

Each encoder reading u[n] is the true move plus noise. Call the noise's standard deviation σ_enc, so its variance is Q = σ_enc² per step. We will call Q the process noise (noise in the motion itself): the uncertainty we add every time the robot moves without looking.

The estimate's own uncertainty is its variance P. Each step adds an independent error, and variances of independent errors add (lesson 1):

P[n] = P[n−1] + Q
start known exactly (P = 0)  →  after n steps, P = n·Q  and  σ = √n · σ_enc

For example, with σ_enc = 0.5 m we get Q = 0.25:

after 1 step: P = 0.25, σ = 0.5 m    after 4 steps: P = 1, σ = 1 m    after 16 steps: P = 4, σ = 2 m
A robot that moves 1 m per step, with Q = 0.25. The bell of "where it might be" slides along and gets lower and wider: σ is 0.5 m, then 1 m, then 2 m.

Notice the square root. Four times as many steps only doubles σ. That is the good news. The bad news: σ never stops growing. There is no step that makes P smaller, because the robot never checks where it actually is.

Drift

So the estimate drifts: it wanders off the true path and stays off. Here is a robot whose speed changes a little, with σ_enc = 0.5 m (Q = 0.25). The picture shows steps 0 to 29. The lab below runs all 79 steps, so its band ends wider.

Dashed: where the robot really is. Blue: dead reckoning, with its ±2σ band. The band fans out like a trumpet, and by step 29 the estimate is about 4 m too far.

The band is ±2σ, and σ = √P. At step 29, P = 29 · 0.25 = 7.25, so σ ≈ 2.69 m and the band is about ±5.4 m. The error you actually get depends on luck. Run the same robot four times, with four different sets of encoder noise:

Four runs of the same encoder. Each line starts at the truth and wanders off in its own direction. Nothing ever brings them back.

A bigger example: five steps, one by one

A robot starts at exactly 0 m (P = 0) and really moves 1.0 m every step. Its encoder has σ_enc = 0.2 m, so Q = 0.04. The encoder reports 1.2, 0.9, 1.3, 1.1 and 0.8 m.

step 1: x̂ = 1.2 m, truth 1 m, error +0.2    P = 0.04, σ = 0.2 m
step 2: x̂ = 2.1 m, truth 2 m, error +0.1    P = 0.08, σ ≈ 0.28 m
step 3: x̂ = 3.4 m, truth 3 m, error +0.4    P = 0.12, σ ≈ 0.35 m
step 4: x̂ = 4.5 m, truth 4 m, error +0.5    P = 0.16, σ = 0.4 m
step 5: x̂ = 5.3 m, truth 5 m, error +0.3    P = 0.20, σ ≈ 0.45 m

Each reading is only 0.1 to 0.3 m off, but the error of the estimate is the sum of all of them so far. It never resets. A real robot runs thousands of steps, and the sum keeps growing.

Where this shows up

Your phone does dead reckoning in a tunnel, using its step counter and compass (a sensor that tells which way is north) until GPS comes back. Submarines navigate this way under water. Warehouse robots count wheel turns between floor markers. In every case the fix is the same: every so often, look at a position sensor.

Reading the lab code

In the code, v is the true move per step and u is what the encoder reports. Python counts from 0, so u[0] holds the move for step 1, u[1] the move for step 2, and so on. The same goes for v. As in lesson 1, dashed(...) draws a dashed line (the truth). New here: line(...) draws a solid line. band= gives σ at each step, and the picture shades ±2σ around the line. Hint for the exercise: the final σ is √79 · enc_std.

Next: a sensor that measures the position itself, the GPS. It never drifts, but it has a problem of its own.

Examples

Example 1 · How fast the band grows

The encoder noise is σ_enc = 0.5 m per step, so Q = 0.5² = 0.25. The start is known exactly (P = 0).

Show solutionHide solution
after 4 steps: P = 4 · 0.25 = 1  →  σ = 1 m
after 100 steps: P = 100 · 0.25 = 25  →  σ = 5 m, so ±2σ = ±10 m

25 times as many steps, only 5 times the σ. But 10 m either way is already useless for a robot in a corridor.

Example 2 · One estimate, step by step

A robot starts at exactly 10 m (P = 0). Here the encoder reports speed, not distance, so each move is u = speed · Δt, where Δt ("delta t") is the time between steps: Δt = 0.5 s. The speeds are 2.1, 1.9 and 2.0 m/s over three steps. Each step adds Q = 0.04 m².

Show solutionHide solution
moves: 2.1·0.5 + 1.9·0.5 + 2.0·0.5 = 1.05 + 0.95 + 1.0 = 3.0 m
x̂ = 10 + 3.0 = 13.0 m
P = 3 · 0.04 = 0.12  →  σ ≈ 0.35 m

The estimate is a clean number. The variance tells you not to trust it too much.

Example 3 · Even a good encoder drifts

A careful encoder has σ_enc = 0.02 m per step, so Q = 0.0004. A delivery robot runs 10,000 steps down long aisles.

Show solutionHide solution
P = 10,000 · 0.0004 = 4  →  σ = 2 m, so ±2σ = ±4 m

A sensor 25 times better than one with σ_enc = 0.5 m still loses the robot over a long enough run. Better hardware slows the drift. It never stops it.

Example 4

An encoder has σ_enc = 0.3 m per step. The start is known exactly. Find P, σ and the ±2σ band after 25 steps.

Show solutionHide solution

Q = 0.3² = 0.09. After 25 steps, P = 25 · 0.09 = 2.25.

σ = √2.25 = 1.5 m, so the ±2σ band is ±3 m.

Example 5

A robot starts at 5 m with P = 1. The encoder reports moves of 1.2, 0.8, 1.0 and 1.0 m over four steps, with Q = 0.5 per step. Find the estimate and its variance after four steps.

Show solutionHide solution

Position: 5 + 1.2 + 0.8 + 1.0 + 1.0 = 9.0 m.

Variance: the starting P = 1 carries over, plus 4 · 0.5 = 2, so P = 3 (σ ≈ 1.73 m). Dead reckoning never forgets its starting doubt. It only adds to it.

Exercise Spec the encoder. Lower enc_std until the final ±2σ band is no wider than ±2 m (final σ ≤ 1 m). How small does it have to be? Edit the code and press Run.
slide_1.py Loading Python…
1
Output · Ctrl+Enter runs
Press Run to execute this slide's code. Ctrl+Enter works too.

Enjoying lesson 2? Get the full course: all 4 lessons through the matrix filter and the EKF, your progress saved lesson by lesson, every solution and 5 extra problems per lesson. $20 once, yours for life.

Questions and comments

Stuck on something, or found a mistake? Ask here and I'll answer. You sign in with GitHub.

The full course

From noisy sensors to the EKF, by running it

Lessons 1 and 2 are free. Finish all four and you will be able to:

You get: all 4 lessons with Python labs · every worked example and solution · 5 extra problems per lesson · your progress tracked · Steppe, your AI tutor inside every lesson, day or night · every future update.

$20 once · lifetime access · 14-day money-back guarantee
Continue to checkout →

Already a member? Log in to the course