How Does a Robot Know Where It Is?

Blind

Drive the robot to the gate five or six times (press Start again each time) with the real path shown.

• a.How far off was it on the best trip? On the worst?
• b.Watch Off by now while it drives. Does it grow at a steady speed, or slowly at first and then faster?
• c.The robot’s dashed line is the same perfect route every time. Why can’t it tell that anything is wrong?

With landmarks

Now set Landmarks to A post every 25 m. Each post is a stake at a place the robot has on its map; when the robot reaches it, its camera reads where it is and which way it is facing. Drive to the gate a few times.

Counting your way

Finding where you are from where you started, how far you went and which way, is called dead reckoning. A robot does it by counting wheel turns, which is called odometry. If a wheel is 30 cm round, 10 turns is 3 m. If the left wheel turns more than the right, the robot curves to the right, and the difference says by how much.

You do it yourself in the dark at home: so many steps from your bed, turn left, and the door should be there.

Dead reckoning needs nothing outside the robot, so it always works. Its weakness is that it can only add up. Every small mistake stays in the sum.

Why the error grows faster and faster

Pilots have a rule of thumb for this, the 1 in 60 rule: fly 1° off course, and after 60 km you are about 1 km to the side. The sideways miss grows with the distance flown after the mistake.

Now think of the robot. A slip of 1° in the first meter steers all 199 meters after it. The same slip near the end steers only a meter or two. And the slips add up: the robot’s heading wanders a little each meter, one way or the other, like the ant in How far does a wandering ant get?. So two things grow together as it drives: how far off its heading is, and how far it has to go with that heading. That is why Off by now creeps at first and then runs.

Landmarks

A landmark is something the robot can recognize whose place it already knows: a post, a sticker on the floor, a doorway, a mountain, a star. Seeing one gives a fix: where it really is, from outside itself, with no error carried over from before.

A fix alone isn’t enough: landmarks are seen only now and then, and in between the robot still has to move. So every robot mixes the two. It counts between landmarks, and lets each landmark wipe out what the counting got wrong. The error can then grow only for the short stretch since the last fix.

With blocks

The turtle is the robot here. First it draws its plan, a dashed line 480 steps long, and comes back to the start. Then it drives the line for real: every 10 steps the ground turns it a little, by a random number of degrees from −2 to 2.

Now give it posts. This program has a post every 120 steps. A new variable, drift, adds up the slips, which is how far the robot has really turned, though the robot itself can’t know it. At each post, it learns that.

In Python (from Grade 8)

Step 1: one robot, driving blind

The robot drives 100 m along a straight line, one meter at a time. Each meter, it slips by a random amount from −1° to 1°, and the slips add up in heading. Two functions you will meet in Grade 10 maths, math.cos and math.sin, split one meter of driving at an angle into how far it goes along the line and how far to the side; here, just use them. (They take the angle in radians, which math.radians turns degrees into.) A positive side distance is to the left.

import mathimport random random.seed(6)x = 0.0          # where the robot really is, in metersy = 0.0heading = 0.0    # which way it really points: 0 is along the linecounted = 0      # the meters its wheels have counted for meter in range(100):    heading = heading + random.uniform(-1, 1)    # a slip it doesn't feel    x = x + math.cos(math.radians(heading))    y = y + math.sin(math.radians(heading))    counted = counted + 1 off = math.sqrt((x - counted) ** 2 + y ** 2)print('Its wheels counted', counted, 'm, so it thinks it is 100 m along the line.')print('It is really', round(x, 1), 'm along and', round(y, 1), 'm to the left.')print('Off by', round(off, 1), 'm, facing', round(heading, 1), 'degrees off the line.')

Its wheels counted 100 m, so it thinks it is 100 m along the line.It is really 99.9 m along and 4.7 m to the left.Off by 4.7 m, facing 2.4 degrees off the line.

random.uniform(-1, 1) gives a random number with decimals from −1 to 1. random.seed(6) makes your run match this one; change the 6 for another robot.

Step 2: a thousand robots, four distances

One robot is luck. Put the trip in a function and send a thousand robots, for trips of 25, 50, 100, 200 and 400 m.

import mathimport random def drive(meters):    # one robot drives blind; gives back how far off its count is    x = 0.0    y = 0.0    heading = 0.0    for meter in range(meters):        heading = heading + random.uniform(-1, 1)        x = x + math.cos(math.radians(heading))        y = y + math.sin(math.radians(heading))    return math.sqrt((x - meters) ** 2 + y ** 2) random.seed(1)last = 0for meters in [25, 50, 100, 200, 400]:    total = 0    for robot in range(1000):        total = total + drive(meters)    average = total / 1000    line = str(meters) + ' m: off by ' + str(round(average, 1)) + ' m on average'    if last > 0:        line = line + ', ' + str(round(average / last, 1)) + ' times as much'    print(line)    last = average

25 m: off by 0.6 m on average50 m: off by 1.7 m on average, 2.9 times as much100 m: off by 4.8 m on average, 2.8 times as much200 m: off by 12.9 m on average, 2.7 times as much400 m: off by 36.6 m on average, 2.8 times as much

Step 3: landmarks

Now the robot steers. Each meter it aims back towards the line from where it thinks it is (aim), and the slips are added to that. Where it thinks it is moves along aim alone. Every every meters it passes a landmark, which tells it where it really is and which way it really faces, so its slips start again from zero. The function gives back the most the robot was ever off during a 400 m trip.

import mathimport random def drive(meters, every):    # a robot that sees a landmark every so many meters (0: never);    # gives back the most its idea of where it is was ever off    x = 0.0              # where it really is    y = 0.0    think_x = 0.0        # where it thinks it is    think_y = 0.0    slip = 0.0           # how far it has turned without knowing    worst = 0.0    for meter in range(1, meters + 1):        aim = -2 * think_y                   # steer back towards the line        slip = slip + random.uniform(-1, 1)        x = x + math.cos(math.radians(aim + slip))        y = y + math.sin(math.radians(aim + slip))        think_x = think_x + math.cos(math.radians(aim))        think_y = think_y + math.sin(math.radians(aim))        off = math.sqrt((x - think_x) ** 2 + (y - think_y) ** 2)        if off > worst:            worst = off        if every > 0 and meter % every == 0:            think_x = x                      # the landmark says where it is            think_y = y            slip = 0.0                       # and which way it really faces    return worst random.seed(1)for every in [0, 100, 50, 25]:    total = 0    for robot in range(300):        total = total + drive(400, every)    if every == 0:        print('No landmarks:', end=' ')    else:        print('A landmark every', every, 'm:', end=' ')    print('at worst', round(total / 300, 1), 'm off')

No landmarks: at worst 37.5 m offA landmark every 100 m: at worst 8.7 m offA landmark every 50 m: at worst 3.7 m offA landmark every 25 m: at worst 1.5 m off

(aim = -2 * think_y turns the robot 2° back towards the line for every meter it thinks it is to the side, so it closes most of the gap within a few tens of meters.)

Step 4: fifteen robots from above

A picture shows the shape. This program drives 15 robots 200 m each, blind and then with a landmark every 50 m, and draws where they really went, one square for every 2 m along and every meter to the side (so the sideways drift looks twice as big as it is). The gray row is the planned line. show_grid is part of the page’s own pixels module; on your own computer you would draw with a library such as Pillow.

import mathimport randomfrom pixels import show_grid WIDTH = 101      # one square every 2 m along: 0 to 200 mMID = 20         # the planned line is row 20; one row a meter to the side def paths(every):    picture = []    for row in range(2 * MID + 1):        picture.append([0] * WIDTH)    for col in range(WIDTH):        picture[MID][col] = 1                # the planned line    for robot in range(15):        x = 0.0        y = 0.0        think_y = 0.0        slip = 0.0        for meter in range(1, 201):            aim = -2 * think_y            slip = slip + random.uniform(-1, 1)            x = x + math.cos(math.radians(aim + slip))            y = y + math.sin(math.radians(aim + slip))            think_y = think_y + math.sin(math.radians(aim))            if every > 0 and meter % every == 0:                think_y = y                  # a landmark                slip = 0.0            row = MID - round(y)             # left of the line is up            col = round(x / 2)            if 0 <= row <= 2 * MID and col < WIDTH:                picture[row][col] = 2    return picture random.seed(5)show_grid(paths(0), ['white', 'silver', 'navy'])show_grid(paths(50), ['white', 'silver', 'navy'])

Picture

• Twice as far, nearly three times as lost. Each time the trip doubled, the average error grew about 2.8 times: 0.6 m after 25 m, 4.8 m after 100 m, 36.6 m after 400 m. The robot that is off by 5% of its trip at 100 m is off by 9% at 400 m.
• Twice as many landmarks, about 2.5 times closer. With no landmarks the worst error on a 400 m trip was 37.5 m on average; a landmark every 100 m cut it to 8.7 m, every 50 m to 3.7 m, every 25 m to 1.5 m.
• The picture shows both at once: the blind robots spread like a trumpet, and the others stay in a narrow band, which widens a little before each landmark and narrows after it.

Why about 2.8? Doubling the trip doubles how far a robot drives with a wrong heading, and the heading itself has wandered further: like the ant’s distance, it grows as the square root of the meters, so about 1.4 times as much (1.4 × 1.4 = 2). 2 × 1.4 is 2.8. Landmarks turn the same rule round: halve the stretch the robot drives blind, and its worst error drops too, about 2.5 times in your program (a little less than 2.8, because with more, shorter stretches there are more chances for one of them to go badly).

That is why robots don’t rely on counting alone, nor only on landmarks, which are seen only now and then. The warehouse robots, the Mars rovers and the surveyor in the stories below all did the same: count between fixes, and fix as often as they could.

A wheel that is a little small. Real wheels wear: a wheel 1% smaller than the robot thinks covers 99 cm for every meter it counts. Add that to Step 2’s drive (both wheels, so it doesn’t turn the robot). Does it change the 2.8?

Landmarks that say only one thing. The blocks’ posts told the robot only which way it faces; Step 3’s told it everything. Change Step 3 so a landmark gives only the heading (slip = 0.0, not the position). How much worse is it?

The open question. A robot in a new place has no map of landmarks. Can it draw the map while it uses it to find itself? This is called SLAM (simultaneous localization and mapping). Making it work reliably in big, changing places, a crowded street or a forest in the wind, is still being worked on.

★ Where does it think it is? (blocks)

A robot drives along a school corridor with a sticker on the floor every few meters. Its wheel goes 30 cm with every turn. Finish the program so that it says where the robot thinks it is, in centimeters along the corridor, from the last sticker it read and its wheel turns since then. Then press Test.

★★ The robot’s own map (Python, from Grade 8)

A robot keeps a log of what it did. ['F', 5] means forward 5 m, ['L'] and ['R'] a quarter turn left or right, and ['P', 3, 4] that it passed a post saying it is at x = 3, y = 4 (it still faces the same way). It starts at x = 0, y = 0, facing north (the way y grows; east is the way x grows). Write dead_reckon(log) that gives back where it thinks it is at the end, as [x, y].

def dead_reckon(log):    # log is a list of moves; give back [x, y] at the end    return [0, 0] print(dead_reckon([['F', 5], ['R'], ['F', 3]]))

★★★ Where am I, from two posts? (Python, from Grade 8)

A robot is somewhere on a field 30 m wide (x from 0 to 30) and 20 m deep (y from 0 to 20). There are posts at two corners, at (0, 0) and (30, 0). The robot can’t see where it is, but it can measure its distance to each post: d1 to the first, d2 to the second. Write where_am_i(d1, d2) that gives back [x, y], each rounded to one decimal place (round(x, 1)).

def where_am_i(d1, d2):    # the distances to posts at (0, 0) and (30, 0)    return [0, 0] print(where_am_i(15.0, 20.12))

• Grade 8, Physical Computing: the sensors a robot can use to look outside itself.
• Grade 10, Computers in the World: how GPS finds you from the satellites’ signals.
• How far does a wandering ant get? The random walk that the robot’s heading takes.
• Can a robot get out of any maze? A robot that finds its way with one rule and a sense of touch.
• How does a heater or a drone hold steady? Correcting a mistake as it happens, a little at a time.