Drones and self-driving basicsMiddleLesson 2836 min read

Knowing where you are

Counting your own steps drifts. GPS jumps around. Combine them and you get something better than either. This is localisation.

✦ Ask the tutor 🧪 Lab · 25 min 📝 Lesson test

Speed

Lesson in motion

In 60 seconds

Knowing where you are

Counting your own steps drifts. GPS jumps around. Combine them and you get something better than either. This is localisation.

1/4

In simple words

Walk down a dark corridor counting your steps: "twenty steps, so I am at the classroom door." Each step is a little longer or shorter than you think, so after a hundred steps you are quite far off. Now someone calls out "you are near the water cooler" every few seconds. Their shout is not exact either, but it stops your counting error from growing. Put both together and you know where you are.

Before a machine can plan where to go, it must know where it is. This is called localisation. It sounds simple, but every method has errors, and the errors behave differently.

Dead reckoning: counting your own movement

Dead reckoning means working out your position from your own movement: wheel turns, speed, heading and time. A robot car counts wheel rotations. A drone adds up readings from its IMU. It is smooth and fast, and it works anywhere, even indoors or in a tunnel.

The problem is drift. If a wheel is a little worn, every metre is counted as slightly more or less than a metre. A tiny error per step is added again and again, so the total error grows the farther you go. Wheel slip on sand or mud, and a heading that is off by one degree, make it worse.

Python: how a small wheel error growspython

# A robot thinks each wheel turn moves it 1.00 m.
# In truth the wheel is slightly worn and moves 0.98 m per turn.
believed_per_turn = 1.00
real_per_turn = 0.98

for turns in [10, 100, 1000, 5000]:
    believed = turns * believed_per_turn
    real = turns * real_per_turn
    print(f"after {turns:5d} turns: believes {believed:7.1f} m, really {real:7.1f} m, "
          f"error {believed - real:6.1f} m")

GPS: noisy but does not drift

Satellite navigation gives a position directly. Its error does not grow over time, but each reading can be off by a few metres, it jumps around, it updates only a few times each second, and near tall buildings the signals bounce, which can make it worse. Indoors, under a flyover or in a tunnel it may not work at all.

	Dead reckoning	GPS
Short-term	Smooth and precise	Jumpy, a few metres of noise
Long-term	Error keeps growing (drift)	Error stays about the same
Indoors, tunnels	Still works	Often fails
Update speed	Very fast	A few times a second

Combining them: predict, then correct

The best methods repeat two steps. Predict: move your estimate by the amount dead reckoning says, and admit that you are now a bit less sure. Correct: when a GPS reading arrives, move your estimate part of the way towards it. How far depends on how much you trust each one.

1
Start
An estimate of position, and a number for how unsure you are (the variance).
2
Predict
Add the movement from the wheels or IMU. Uncertainty grows a little.
3
Measure
A GPS reading arrives, with its own uncertainty.
4
Correct
Take a weighted average: trust the less uncertain one more. Uncertainty shrinks.
5
Repeat
Every step. Drift can never build up, and GPS noise is smoothed out.

If both guesses are equally uncertain, the answer is halfway between them. If GPS is very noisy, the answer stays close to the prediction and moves only a little. This weighted average, done step by step, is the heart of the Kalman filter, which is used widely in navigation.

Note

There are other ways to correct drift. A robot can recognise landmarks it has seen before, or match what its lidar or camera sees against a map. Building the map and finding yourself in it at the same time is called SLAM (simultaneous localisation and mapping). Many indoor robots and vacuum cleaners use ideas like this.

Real example

A farm robot in Punjab drives between rows of wheat. In the open field, satellite navigation keeps it on track. When it passes under a row of tall trees, the signal gets poor for a while. Its wheel counting and IMU carry it through, and the error is still small when the signal comes back. Neither method alone would work as well.

Try this. In the code, change the real distance per turn to 1.01. Does the error get smaller over time, or only change direction?

Watch and read more

Lab

A fuse() function that combines dead reckoning and GPS, beating both on made-up data.

~25 min

The problem

This runs in your browser. A robot drives along a straight road. Its wheel reading is 5% too high (drift), and its GPS has about 3 m of noise. All numbers are made up.

Finish fuse(estimate, est_var, measurement, meas_var). Use the weight k = est_var / (est_var + meas_var). The new estimate moves k of the way towards the measurement. The new variance is (1 - k) × est_var.
Run it and compare the three errors. Look at the plot.
Change GPS_VAR to 100 (you trust GPS much less). What happens to the fused line? Write two sentences.

Practice lab

Edit the code and run it. Python runs in your browser — nothing is sent to our server.

Ctrl + Enter to run

import numpy as np
import matplotlib.pyplot as plt

def fuse(estimate, est_var, measurement, meas_var):
    """Combine two noisy guesses of the same position.
    Return (new_estimate, new_var). Trust each guess more when its variance is smaller."""
    # TODO: replace this line. Right now it ignores the GPS completely.
    return estimate, est_var

rng = np.random.default_rng(3)
steps = 120
true_pos = np.arange(1, steps + 1) * 1.0            # the robot really moves 1 m each second
wheel = 1.05 + rng.normal(0, 0.05, steps)           # wheels say about 1.05 m: 5% too high
gps = true_pos + rng.normal(0, 3.0, steps)          # GPS: about 3 m of noise
GPS_VAR = 9.0        # 3 m squared
STEP_VAR = 0.1       # how much uncertainty each step of wheel counting adds

dead_reckoning = np.cumsum(wheel)
est, var = 0.0, 1.0
fused = []
for i in range(steps):
    est, var = est + wheel[i], var + STEP_VAR       # predict
    est, var = fuse(est, var, gps[i], GPS_VAR)      # correct
    fused.append(est)
fused = np.array(fused)

def rms(err):
    return float(np.sqrt(np.mean(np.square(err))))

print("error, dead reckoning:", round(rms(dead_reckoning - true_pos), 2), "m")
print("error, GPS alone:     ", round(rms(gps - true_pos), 2), "m")
print("error, fused:         ", round(rms(fused - true_pos), 2), "m")

plt.plot(dead_reckoning - true_pos, label="dead reckoning error")
plt.plot(gps - true_pos, ".", alpha=0.4, label="GPS error")
plt.plot(fused - true_pos, label="fused error")
plt.axhline(0, color="k", linewidth=0.8)
plt.xlabel("seconds"); plt.ylabel("metres off"); plt.legend(); plt.show()

Output

No output. Add print(...) to see values.

You are done when

fuse() lands halfway for equal variances and moves only a little towards a very noisy measurement
The fused error is clearly lower than both dead reckoning and GPS alone
The plot shows dead reckoning drifting away while the fused line stays near zero
The GPS_VAR experiment is explained: trusting GPS less makes the fused line smoother but slower to correct drift

Hard questions

Try to answer before you reveal. If you can answer these, you understood the lesson.

Q1The wheel reading is biased (5% too high), but the filter assumes only random error. Why does fusion still work well?Reveal

GPS keeps pulling the estimate back, so the bias cannot build up without limit. The fused estimate ends up a small, steady distance ahead of the truth instead of drifting further and further away. A better filter could also estimate the bias itself, by adding it to the things it tracks, and then correct the wheel readings.

Q2What would happen to the fused estimate if GPS were lost for 30 seconds?Reveal

During the outage, only the predict step runs. The estimate follows dead reckoning and drifts, and the variance grows each step. When GPS comes back, the large variance means the filter trusts the first new GPS reading a lot and jumps back towards it. Good systems also check that the returning reading is sensible before trusting it.

Please sign in to continue.

Questions people ask

Why is it called dead reckoning?

It is an old term from ship navigation, where sailors worked out their position from speed, heading and time. The exact origin of the name is not certain. The idea is the same in robots today.

How accurate can satellite navigation get?

An ordinary phone or drone receiver is often a few metres off in open sky, and worse in cities. Special setups that use correction signals from a nearby base station can reach centimetre-level accuracy. These are used in surveying and precision farming. Check current equipment before promising a number.

Does the Kalman filter need GPS?

No. It combines any prediction with any measurement: wheel counts with a camera, IMU with a barometer, and so on. GPS is just the most common example.

What happens if the GPS reading is badly wrong?

A single wild reading can pull the estimate off. Good systems check each reading against the prediction and ignore ones that are far too different. This is called outlier rejection or gating.

Lesson test

5 questions. Get 3 right (60%) to pass and complete this lesson.

Knowing where you are

Knowing where you are

Dead reckoning: counting your own movement

GPS: noisy but does not drift

Combining them: predict, then correct

Start

Predict

Measure

Correct

Repeat

Watch and read more

The problem

Practice lab

You are done when

Hard questions

Questions people ask