Dead reckoning and odometry explained

How dead reckoning and robot odometry work: the formula, why odometry drifts (noise, scale, gyro bias), how calibration and landmark fixes correct it, and dead reckoning vs GPS, with live Python demos of a robot you can change and run.

Guidefree, runs in your browser

Dead reckoning works out where you are from where you started, which way you went, how fast and for how long. Nothing outside tells you the answer: you add up your own movements. Odometry is a robot doing this with its own sensors, such as wheel encoders, or the optical flow sensor and gyro on the robot on this page. Sailors navigated this way for centuries, aircraft and submarines still do between fixes, and a robot vacuum does it between one landmark and the next. Its weakness is that every small error in a measurement is added in too, so the estimate drifts, and the further you go the further out it gets. On this page a small robot dead reckons its way round a square on a 2 metre mat, and each demo below is a real program you can change and run.

In the overhead view of each demo, the green line is where the robot went and the red line is where it thinks it went. The chart shows the error: how far apart the two are, in cm. The simulator knows the robot's true position, and uses that only to draw the green line and the chart. The robot's own estimate never sees it.

The idea in one line

position = position + velocity × time step

Read the speed, multiply by the time since the last reading, add it on, and do it again. In a program that is a loop with a running total. In maths it is integration: position is the integral of velocity, and the loop adds up thin strips of the area under a velocity-time graph.

A robot on a floor needs a direction as well as a distance. Its sensors measure how it moves in its own frame (vx to its right, vy straight ahead, and a turn rate from the gyro), so each step has to be turned into the frame of the mat before it is added on:

heading = heading + turn rate × dt
x = x + ( vx × cos(heading) + vy × sin(heading)) × dt
y = y + (-vx × sin(heading) + vy × cos(heading)) × dt

Here heading 0 faces up the mat and angles go clockwise. Facing 90 degrees and driving forwards, sin(90) = 1 and cos(90) = 0, so the forward speed all goes into x. The two lines in the middle are a rotation matrix, the same one used to turn any vector through an angle.

That is the whole of dead reckoning: these three lines, run many times a second. The programs below use the heading half way through each step (h + 0.5 × rate × dt), which removes a small error that always leans the same way when the robot turns while it moves.

Odometry from wheel encoders

Most robots measure their motion with wheels instead. An encoder counts how far each wheel has turned, so a wheel's distance is counts ÷ counts per turn × π × wheel diameter. For a robot with a wheel on each side, a distance dL on the left and dR on the right in one step means:

distance forward = (dL + dR) / 2
rotation (radians, clockwise) = (dL - dR) / wheelbase

and those go into the same three lines. The robot on this page has an optical flow sensor underneath instead, which works like the sensor in a computer mouse: it watches the mat slide past and reports the speed in cm/s. It measures how the robot actually moved, so it keeps working when a wheel would slip or, as here, when there are no wheels at all.

Odometry round a square

The robot starts at the bottom left and drives a 1 metre square, steering only by its own estimate: to reach each corner, it works out the direction from where it thinks it is, turns that direction into its own frame, and drives that way. When it thinks it has reached the last corner, it stops.

from bugbot import *
import math
connect()

# change these numbers and press Run
SIDE = 100     # cm along each side of the square
SPEED = 100    # percent: 100 is 20 cm/s

START = (40, 40)   # where the robot starts on the mat
DT = 0.1           # seconds between updates
x = y = h = 0.0    # where the robot thinks it is
mine = [START]     # the path it thinks it took
real = [START]     # the path it really took

def update():
    # one step of dead reckoning
    global x, y, h
    vx, vy = flow()     # cm/s to its right, forward
    rate = imu()[1]     # deg/s, clockwise
    a = math.radians(h + 0.5 * rate * DT)
    x += (vx * math.cos(a) + vy * math.sin(a)) * DT
    y += (-vx * math.sin(a) + vy * math.cos(a)) * DT
    h += rate * DT
    wait(DT)
    show()

def show():
    # the truth, from the simulator: only to check
    px, py = position()
    mine.append((START[0] + x, START[1] + y))
    real.append((START[0] + px, START[1] + py))
    if len(mine) % 5 == 0:
        draw("real", real, "green", "line")
        draw("mine", mine, "red", "line")
    plot("error cm", math.hypot(x - px, y - py))

def go_to(tx, ty):
    # head for (tx, ty) using only the estimate
    while math.hypot(tx - x, ty - y) > 2:
        if clock() > 60:
            break
        # the way to go, in the robot's own frame
        dx, dy = tx - x, ty - y
        a = math.radians(h)
        fwd = dx * math.sin(a) + dy * math.cos(a)
        lat = dx * math.cos(a) - dy * math.sin(a)
        n = math.hypot(fwd, lat)
        drive(SPEED * fwd / n, SPEED * lat / n, 0)
        update()

SQUARE = [(0, SIDE), (SIDE, SIDE), (SIDE, 0), (0, 0)]
for corner in SQUARE:
    go_to(*corner)
stop()
for i in range(5):     # let it coast to a stop
    update()
draw("real", real, "green", "line")
draw("mine", mine, "red", "line")
print("it thinks it is at", round(x, 1), round(y, 1),
      "facing", round((h + 180) % 360 - 180, 1))
print("it is really at", position(),
      "facing", round((heading() + 180) % 360 - 180, 1))

It works, roughly. After 24 seconds and 4 metres the red square and the green one are close, the error never goes above 7.2 cm, and the robot stops 3.9 cm from where it thinks it is: about 1 percent of the distance it drove. That is good odometry. It is also not zero, and nothing in the program can find the error and take it out.

The BugBot can drive sideways, so it never turns on purpose here. It still ends facing 10.7 degrees to the left: the vibration motors twist it a little as it goes. The gyro follows the twist, and the rotation in the formula turns each step to match. Change the line a = math.radians(...) in update() to a = 0.0, so the steps are never rotated, and the robot stops 15.5 cm from where it thinks it is instead of 3.9. The gyro is not quite right about the twist, though. The robot thinks it is facing 14.7 degrees to the left, 4 degrees more than it is.

Try SPEED = 50. The same square takes 48 seconds instead of 24, the heading ends 9 degrees out instead of 4, and the robot stops 8.2 cm from where it thinks it is. Same distance, about twice the time, about twice the heading error: that part of the error grows with time, not with distance. The next section says why.

Why dead reckoning drifts

Every reading is a little wrong, and dead reckoning adds up every reading, so it adds up every error as well. What matters is the kind of error, because the kinds grow at different rates.

A heading error is the expensive one, because it turns everything after it. Drive a distance d with a heading error of e radians and you end up about d × e to one side: 3 degrees is 0.052 radians, so 3 degrees out over 10 metres puts you 52 cm to the side, and the same 3 degrees costs nothing if you stand still.

This demo gives the robot perfect sensors with set_noise(0), and then spoils the readings on purpose, one kind of error at a time. It drives the same square.

from bugbot import *
import math, random
connect()
random.seed(1)
set_noise(0)    # perfect sensors, spoilt below

# change these numbers and press Run
BIAS = 1.0      # deg/s the gyro reads when still
SCALE = 1.0     # 1.1 reads every speed 10 % high
NOISE = 0.0     # cm/s of random error on each reading

SIDE = 100
SPEED = 100
START = (40, 40)
DT = 0.1
x = y = h = 0.0
mine = [START]
real = [START]

def update():
    global x, y, h
    vx, vy = flow()
    rate = imu()[1]
    # spoil the perfect readings
    vx = vx * SCALE + random.gauss(0, NOISE)
    vy = vy * SCALE + random.gauss(0, NOISE)
    rate = rate + BIAS
    a = math.radians(h + 0.5 * rate * DT)
    x += (vx * math.cos(a) + vy * math.sin(a)) * DT
    y += (-vx * math.sin(a) + vy * math.cos(a)) * DT
    h += rate * DT
    wait(DT)
    show()

def show():
    px, py = position()
    mine.append((START[0] + x, START[1] + y))
    real.append((START[0] + px, START[1] + py))
    if len(mine) % 5 == 0:
        draw("real", real, "green", "line")
        draw("mine", mine, "red", "line")
    plot("error cm", math.hypot(x - px, y - py))

def go_to(tx, ty):
    while math.hypot(tx - x, ty - y) > 2:
        if clock() > 60:
            break
        dx, dy = tx - x, ty - y
        a = math.radians(h)
        fwd = dx * math.sin(a) + dy * math.cos(a)
        lat = dx * math.cos(a) - dy * math.sin(a)
        n = math.hypot(fwd, lat)
        drive(SPEED * fwd / n, SPEED * lat / n, 0)
        update()

SQUARE = [(0, SIDE), (SIDE, SIDE), (SIDE, 0), (0, 0)]
for corner in SQUARE:
    go_to(*corner)
stop()
for i in range(5):
    update()
draw("real", real, "green", "line")
draw("mine", mine, "red", "line")
print("it thinks it is at", round(x, 1), round(y, 1))
print("it is really at", position())

Bias. The gyro says the robot is turning right at 1 degree a second when it is not turning at all. By the end of the lap the robot believes it is facing 25 degrees further right than it is, so each side it drives is rotated further left than the one before. The error is 3 cm after 4 seconds, 10 cm after 10 seconds and 33 cm after 25: it grows faster and faster, because the heading error behind it keeps growing. Try BIAS = 2: 68 cm. Try BIAS = -1: the green square turns the other way, and it ends 29 cm out.

Scale. Set BIAS = 0 and SCALE = 1.1, so every speed reads 10 percent high. Now the robot thinks it has gone further than it has, and the green square comes out about a tenth smaller than the red one. The error climbs to 13 cm along the first two sides, then falls back to under 1 cm by the end: the sides that were too short on the way out are too short on the way back as well, so a closed loop hides a scale error. A straight line does not.

Noise. Set BIAS = 0 and NOISE = 3. The error wanders up and down instead of climbing smoothly, and ends at 8.5 cm. With NOISE = 10 it ends at 25 cm. Random errors partly cancel: with NOISE = 0.7, about what this robot's own flow sensor has, it ends 2.4 cm out.

Step size. Set all three to zero and the red line still sits about 1 cm off the green. The program reads the speed once every 0.1 seconds and treats it as constant for the whole step, which it is not while the robot speeds up or slows down. Change DT to 0.05 and the gap is about 0.7 cm; at 0.2 it is about 2 cm. It is the least of the four.

The robot in the first demo has a gyro that reads about 0.2 degrees a second when still and a flow sensor that reads about 3 percent high going forwards. On a 24 second lap the bias is worth about 4 degrees of heading. On a 10 minute run it would be worth over 100.

Calibrate what you can

A bias is the same every time, so it can be measured and taken off. The robot stands still for a few seconds before it sets off. A gyro standing still should read 0, so whatever it reads on average is its bias, and the program subtracts that from every reading afterwards.

from bugbot import *
import math
connect()

# change these numbers and press Run
CALIBRATE = True   # measure the gyro bias first
STILL = 4          # seconds standing still to do it

SIDE = 100
SPEED = 100
START = (40, 40)
DT = 0.1
x = y = h = 0.0
bias = 0.0
mine = [START]
real = [START]

def update():
    global x, y, h
    vx, vy = flow()
    rate = imu()[1] - bias     # take the bias off
    a = math.radians(h + 0.5 * rate * DT)
    x += (vx * math.cos(a) + vy * math.sin(a)) * DT
    y += (-vx * math.sin(a) + vy * math.cos(a)) * DT
    h += rate * DT
    wait(DT)
    show()

def show():
    px, py = position()
    mine.append((START[0] + x, START[1] + y))
    real.append((START[0] + px, START[1] + py))
    if len(mine) % 5 == 0:
        draw("real", real, "green", "line")
        draw("mine", mine, "red", "line")
    plot("error cm", math.hypot(x - px, y - py))
    off = (h - heading() + 180) % 360 - 180
    plot("heading error deg", off)

def go_to(tx, ty):
    while math.hypot(tx - x, ty - y) > 2:
        if clock() > 60:
            break
        dx, dy = tx - x, ty - y
        a = math.radians(h)
        fwd = dx * math.sin(a) + dy * math.cos(a)
        lat = dx * math.cos(a) - dy * math.sin(a)
        n = math.hypot(fwd, lat)
        drive(SPEED * fwd / n, SPEED * lat / n, 0)
        update()

if CALIBRATE:
    # standing still, the gyro should read 0:
    # whatever it reads on average is its bias
    rates = []
    for i in range(int(STILL / DT)):
        rates.append(imu()[1])
        wait(DT)
    bias = sum(rates) / len(rates)
    print("gyro bias", round(bias, 2), "deg/s")

SQUARE = [(0, SIDE), (SIDE, SIDE), (SIDE, 0), (0, 0)]
for corner in SQUARE:
    go_to(*corner)
stop()
for i in range(5):
    update()
draw("real", real, "green", "line")
draw("mine", mine, "red", "line")
print("it thinks it is at", round(x, 1), round(y, 1),
      "facing", round((h + 180) % 360 - 180, 1))
print("it is really at", position(),
      "facing", round((heading() + 180) % 360 - 180, 1))

Set CALIBRATE = False to compare: that is the first demo with a heading line added. Without calibration the heading error climbs steadily to 4 degrees; with it, the line stays within 1 degree of zero and ends at 0.3. The position error is smaller too, 4.9 cm at worst instead of 7.2.

The gyro's noise (about 0.8 degrees a second on each reading) is much bigger than its bias, so the average needs enough readings to settle. With STILL = 2 the program measures -0.13 and the heading still ends a degree out; with STILL = 6 it measures -0.19. A few seconds of standing still buys the whole run, which is why phones, drones and aircraft all do it. Better systems do it again every time they know they are still: a foot-mounted step tracker recalibrates each time the foot is flat on the ground, which is called a zero velocity update.

What calibration cannot remove is anything that changes: noise, slip, and a real gyro's bias creeping as it warms up. The flow sensor's scale can be calibrated too, by driving a distance you already know and comparing, but that needs something outside the robot to say what the distance was. That is the idea that stops drift altogether.

A fix from outside

Dead reckoning on its own always drifts, however well calibrated. The only thing that stops it is a fix: a measurement of where you are made against something whose position you already know. A ship's navigator dead reckoned all day and took a star sight at dusk, and threw the day's error away. The error grows between fixes and drops at each one, a saw-tooth.

Here the fix comes from two AprilTags on the far wall. The camera reports how far away each tag is. There is only one place on this side of the wall that is the right distance from both, where the two circles cross, and that is where the robot is. Where tag 11 sits in the picture then gives the way it is facing. To make the drift easy to see, the gyro has an extra bias of 1 degree a second, as in the last demo.

from bugbot import *
import math
connect()
set_cv("apriltag")

# change these numbers and press Run
FIX_EVERY = 3   # seconds between fixes (0: never)
BIAS = 1.0      # extra gyro error in deg/s

# the two tags on the far wall, in cm from the start
TAGS = {11: (0, 145), 12: (80, 145)}
FOCAL = 92.4    # the camera's focal length in pixels

SIDE = 90
SPEED = 100
START = (70, 50)
DT = 0.1
x = y = h = 0.0
last_fix = 0.0
mine = [START]
real = [START]

def fix():
    # where am I, from the distance to each tag?
    global x, y, h, last_fix
    seen = {t[0]: t for t in apriltags()}
    if 11 not in seen or 12 not in seen:
        return
    d1, d2 = seen[11][3], seen[12][3]
    (ax, ay), (bx, by) = TAGS[11], TAGS[12]
    gap = bx - ax
    # the point d1 from tag 11 and d2 from tag 12,
    # on this side of the wall
    x = ax + (d1 ** 2 - d2 ** 2 + gap ** 2) / (2 * gap)
    y = ay - math.sqrt(max(0, d1 ** 2 - (x - ax) ** 2))
    # which way am I facing? tag 11 is this way
    # on the mat, and b degrees right in the picture
    cx = seen[11][1]
    b = math.degrees(math.atan((cx - 160) / FOCAL))
    h = math.degrees(math.atan2(ax - x, ay - y)) - b
    last_fix = clock()

def update():
    global x, y, h
    vx, vy = flow()
    rate = imu()[1] + BIAS
    a = math.radians(h + 0.5 * rate * DT)
    x += (vx * math.cos(a) + vy * math.sin(a)) * DT
    y += (-vx * math.sin(a) + vy * math.cos(a)) * DT
    h += rate * DT
    wait(DT)
    if FIX_EVERY and clock() - last_fix >= FIX_EVERY:
        fix()
    show()

def show():
    px, py = position()
    mine.append((START[0] + x, START[1] + y))
    real.append((START[0] + px, START[1] + py))
    if len(mine) % 5 == 0:
        draw("real", real, "green", "line")
        draw("mine", mine, "red", "line")
    plot("error cm", math.hypot(x - px, y - py))

def go_to(tx, ty):
    while math.hypot(tx - x, ty - y) > 2:
        if clock() > 60:
            break
        dx, dy = tx - x, ty - y
        a = math.radians(h)
        fwd = dx * math.sin(a) + dy * math.cos(a)
        lat = dx * math.cos(a) - dy * math.sin(a)
        n = math.hypot(fwd, lat)
        drive(SPEED * fwd / n, SPEED * lat / n, 0)
        update()

SQUARE = [(0, SIDE), (SIDE, SIDE), (SIDE, 0), (0, 0)]
for corner in SQUARE:
    go_to(*corner)
stop()
for i in range(5):
    update()
draw("real", real, "green", "line")
draw("mine", mine, "red", "line")
print("it thinks it is at", round(x, 1), round(y, 1))
print("it is really at", position())

The fixes come at 3, 6, 9 and 12 seconds, and each one puts the estimate within 0.1 cm and 0.3 degrees of the truth. In between, the bad gyro drags it off again, by up to 1.8 cm, and the chart is a saw-tooth. After 12 seconds the robot is on the right-hand side and the bottom of the square, where the camera cannot see both tags at once, so there are no more fixes, and the error climbs to 8.1 cm by the end.

Set FIX_EVERY = 0 for no fixes at all: the error grows the whole way round and ends at 22 cm. Set BIAS = 0 for this robot as built: with fixes it ends 1.5 cm out, and without them 3.7 cm.

Two things to take from this. A fix bounds the error; calibration only slows it down. And the fix is only as good as your view of the landmarks, so a real robot plans its route, or places its landmarks, so that it gets one often enough.

Replacing the estimate with the fix, as this program does, is right when the fix is much better than the estimate, as it is here, because the simulated tag distances are exact. A real fix has its own error. Blending the two in proportion to how much you trust each, and working out that trust properly as you go, is what a Kalman filter does. A particle filter does the same job with a cloud of guesses, and needs odometry to move them.

Dead reckoning vs GPS

They fail in opposite ways, so they are used together. A car's sat nav keeps the arrow moving through a tunnel on wheel speed and a gyro, then corrects it when the satellites come back. A drone uses its gyros and accelerometers for the fast, smooth part and GPS to stop the drift. That is dead reckoning between fixes again, done continuously.

Questions

What is dead reckoning?

Working out where you are from a known starting point by adding up your own movements: the speed, the direction and the time since the last update. It needs nothing from outside, which is its strength, and every error in the measurements is added up with them, which is its weakness.

What is robot odometry?

Odometry is a robot measuring its own motion and adding it up to estimate where it is. Usually it counts wheel turns with encoders; the robot on this page uses an optical flow sensor that watches the floor, and a gyro for the turns. Odometry is the most common way robots do dead reckoning, and it starts drifting from the moment the robot moves.

What is the formula for dead reckoning?

In a straight line, position = position + velocity × time, repeated every step. In two dimensions, with the robot's own speeds vx (sideways) and vy (forwards) and a heading measured clockwise, heading = heading + turn rate × dt, then x = x + (vx cos(heading) + vy sin(heading)) × dt and y = y + (-vx sin(heading) + vy cos(heading)) × dt. For a robot with two wheels, it moves (dL + dR) / 2 forward and turns (dL - dR) / wheelbase radians each step.

Why does dead reckoning drift?

Because it adds up measurements that are each a little wrong, and nothing ever takes the errors back out. Random noise grows slowly because it partly cancels. A scale error grows with distance. A gyro bias is worst: the heading error grows steadily, and a heading error sends every later step in the wrong direction, so the position error grows faster and faster. On this page, a gyro reading 1 degree a second when still put the robot 33 cm out after one 4 metre lap.

How do you correct odometry drift?

Two ways. Calibrate the errors that stay the same, such as measuring the gyro bias while the robot stands still and subtracting it: on this page that kept the heading within 1 degree instead of drifting to 4. Then take regular fixes from something whose position is known, such as tags, walls, beacons or GPS, and reset or blend the estimate with each one. Only fixes stop the error growing; calibration slows it down.

What is the difference between dead reckoning and GPS?

Dead reckoning works anywhere and is smooth and fast, but its error grows the longer it runs. GPS needs a view of the sky and jumps about by a metre or more, but its error does not grow. Most vehicles use both: dead reckoning between GPS fixes, and GPS to stop the drift, often combined with a Kalman filter.

What is the difference between odometry and dead reckoning?

Dead reckoning is the general method: position from a start point plus measured speed, direction and time, used by ships and aircraft long before robots. Odometry is the robot version, where the movement comes from the robot's own sensors, usually wheel encoders. People often use the two words for the same thing.

How accurate is dead reckoning?

It depends on the sensors and on how long you go without a fix. The robot on this page ended 3.9 cm out after a 4 metre square, about 1 percent of the distance, and 8.2 cm out when the same square took twice as long. Good wheel odometry on a hard floor is often quoted at around 1 to 2 percent of distance travelled, and it gets worse on carpet, gravel or anywhere the wheels slip.

How do you write dead reckoning in Python?

Keep x, y and heading as variables starting at zero. In a loop, read the speeds and the turn rate, add turn rate × dt to the heading, rotate the speeds by the heading with math.cos and math.sin, and add them times dt to x and y. Measure dt with a clock if the loop time can vary. Every demo on this page is a complete program that does this in about ten lines.

What is visual odometry?

Dead reckoning from a camera: the robot tracks how features in the picture move between frames and works out how it must have moved. Mars rovers use it where their wheels slip in sand. It still drifts, like any odometry, because each small error is added to the last.

Is dead reckoning on the GCSE or A level syllabus?

Not by name, but the maths behind it is. Finding the distance travelled from the area under a velocity-time graph is in GCSE Physics (AQA, OCR, Edexcel and Eduqas) and A level Physics. Integrating velocity to get displacement, vectors and the trapezium rule are in A level Maths for every board (AQA, OCR, Edexcel), and rotation matrices are in A level Further Maths.

Learn it step by step

These lessons build the same ideas one at a time, each with tasks the simulator marks.

1. 2.5 Drift and correction Sensing, Robot club
2. U3.1 Integrating velocity Odometry and drift, University
3. U3.2 Write your own odometry Odometry and drift, University
4. U3.3 How the error grows Odometry and drift, University
5. U3.4 Calibration Odometry and drift, University
6. U3.5 A fix from a landmark Odometry and drift, University
7. U3.6 An error budget Odometry and drift, University
8. U3.7 Project: the long lap Odometry and drift, University