28Maps, and knowing where you are on one

You wake in a hotel corridor with the floor plan in your hand. A wall close on each side: you are in a corridor, and the plan has three of those. So you walk. A doorway slides past on your left, and now only two of the plan's corridors fit. A few more steps, another doorway comes too soon for one of the two, and that settles it: you know where you are without seeing a room number. This module is how a robot does the same, and it answers the one thing the rover in the module about odometry could not do.

What that rover was missing

That rover counted its wheel turns and added them up; its belief drifted a little on a clean floor, a meter after one slip, and nothing on board could pull it back. It was missing two things. The first is a map: what a robot carries of the place it works in, most often a grid of small cells each marked wall or floor, so that from any spot on it the robot can work out what its sensors ought to see. A map can be drawn from a building's plans, or made by driving the robot round once with its sensors on. The second thing is a habit: checking the belief against the world, over and over, instead of trusting the sum.

Working out where you are on a map you already have, from what your sensors report, and keeping that answer right as you move, is localization. The word to hold onto this time is checking. Dead reckoning only adds, so an error, once made, stays. Localization compares, so an error that has crept in shows up as a mismatch between what the sensors see and what the map says they should, and gets corrected.

Why one reading is not enough

The rover's five rangefinders each report one number, the distance along a line to the nearest wall. Suppose the ones pointing left and right both report half a meter. That says "I am in the middle of something a meter wide": a corridor, or a gap between two boxes. A rangefinder reading is a clue, not an address. So are five: from a spot in a corridor, all five fit every other spot along that corridor, and a mirror-image spot in it facing the other way.

So the robot cannot read off where it is. It has to reason: "if I were here, facing this way, my five rangefinders would report these numbers; do they?" The map makes that question answerable: a ray on the map is the module about distance sensors' beam done on paper, from the spot across the cells to the first wall. The trick is to check thousands of spots at once.

A crowd of guesses

A particle filter localizes with a crowd of guesses about where the robot is. Each guess is a pretend rover: a spot on the map and a facing. To start, the guesses are thrown down everywhere the robot could be, facing every way, because the robot knows nothing but the map. Then, many times a second, three things happen to the crowd.

First, every guess moves as the wheels say the robot moved. If the wheel counts say ten centimeters forward, every guess steps ten centimeters along its own facing. Not exactly ten, though: each guess adds a little error of its own, a centimeter more or less, a degree of turn one way or the other, because wheels lie, and a crowd that moved exactly as the wheels said would carry every slip with it for ever. The little errors spread the crowd out slightly with every move: dead reckoning's drift, built in on purpose.

Second, whenever the rangefinders report, every guess is weighed. The map says what the five rangefinders ought to read from that guess's spot and facing; the robot compares those five numbers with the five it actually got. A guess whose five numbers match keeps its full weight; one whose numbers are off loses weight, more the further off they are, until a guess that says "wall at half a meter" where the real reading says "nothing in range" weighs nearly nothing. A reading a few centimeters out still counts, because real rangefinders are a few centimeters out.

Third, the crowd is redrawn. A new crowd of the same size is made by copying guesses from the old one, each guess copied in proportion to its weight: a heavy guess is copied several times, a light one once or not at all. Guesses that fit the world multiply; guesses that do not, die. The crowd piles up wherever the readings and the map agree. To give one answer, the robot cuts the map into squares of twenty centimeters, finds the most crowded square, and averages the guesses in it and its neighbors: the middle of the biggest pile. How tight the crowd is around it says how sure the robot is.

Two things make this more than a lottery. Every round, a few guesses are thrown down at random anywhere on the map, so a crowd piled up on the wrong spot can still find the right one. And the robot can tell when not one guess explains the readings, because at the weighing even its best guess comes out far off on most of the five rays; then it throws down a great many more, a quarter of the crowd, because a crowd that is wrong everywhere has nothing to copy from. That is what lets it recover from being picked up and carried across the house.

Look-alikes

Now go back to the corridor. Every guess along it, facing the right way, sees two walls half a meter apart and nothing ahead, and so does every guess in the mirror-image spot facing the other way, so after a few rounds the crowd is a pile at every place that looks like the robot's. That is not a failure but the honest answer, "one of these," and the map cannot say more until the robot moves.

Then it moves, and the piles are tested against a story, not a snapshot. A doorway passes on the robot's left. The pile at a spot with a doorway coming up on the left survives; the pile at a spot with a plain wall there does not. A second doorway comes soon after, and because the doorways in this house are unevenly spaced, only one pile on the map has two doorways that far apart in that order. Moving is what tells look-alikes apart, and a robot unsure where it is does well to drive on a little.

The box

The box below is a map of a small house, seen from above, four meters by two and a half: a corridor across the middle, three rooms above it and two below, each with a doorway onto the corridor. The rover is the blue rectangle at the left end of the corridor, with its five rangefinder beams drawn in faint blue to what they report, and it drives the corridor end to end and back, turning round at each end. The orange strokes are the guesses, each pointing the way it faces, two thousand of them. The dashed orange outline is the crowd's answer, the middle of its biggest pile, and the dashed ring round it is drawn so that nine in ten guesses fall inside it: a small ring is a sure crowd. The line under the map says how far the crowd's answer is from where the rover really is, which only you can know, and the ring's size in centimeters; when no guess fits the readings, it says so, and that fresh guesses are being thrown down.

The rangefinders report with a couple of centimeters of error, and the guesses move with a little error, as real wheels do. A switch labeled Use the rangefinders turns the weighing off, so the crowd is only moved. Kidnap the rover picks the rover up and puts it down somewhere else along the corridor, facing whichever way, without telling the crowd, and it drives on from there. Scatter the guesses throws all two thousand down at random again. Reset does that too, and puts the rover back at the left end.

ResetPlaySlowLabels

Use the rangefindersKidnap the roverScatter the guesses

Waiting for the first frame…

This is easier on a larger screen, but it works here too.

Let it drive on, and the line under the map says the center stays within a few centimeters of the rover, with nine in ten guesses within about ten centimeters of it, twenty at most as it turns round at the end. Nothing drifts.

What you saw

At the first weighing the rooms emptied, because a guess in a room sees walls at the wrong distances: a rangefinder pointing at a far wall where the rover's sees a near one is a mismatch of a meter, and a guess like that weighs nothing next to one in the corridor. What it could not do is choose along the corridor, where the five readings fit every other spot, and the crowd said so by staying spread along it in a few clumps. Then the rover drove past a doorway, and the clumps with no doorway coming up on that side died. Either way, the crowd was on the rover within a few seconds, and it stayed there, round the turn and back, to within a few centimeters. That is the whole difference from the module about odometry: every reading was a chance to correct, so the errors never had time to pile up.

The kidnap showed the same machinery recovering from the worst case. With the rangefinders switched off you saw it with the checking removed: the crowd still moved with the wheels, so it followed the rover, but with nothing to weigh the guesses against, the little errors added up unchecked and the crowd smeared out. That is dead reckoning, and the smear is its drift, drawn. Switching the rangefinders back on let one weighing throw away every guess that had wandered off.

What this is for

This is how a robot vacuum knows which room it is in and, with a bigger map and more rays, how a self-driving car places itself on a road to a few centimeters: a map, a comparison, and a crowd of guesses rather than one answer, so that being unsure is something it can say. Two thousand guesses checked along five rays ten times a second is cheap; a real robot with a lidar checks hundreds of rays against a map it usually built itself.

What the simulation leaves out

The map here is exact, the walls are flat and nothing in the house moves. A real map was built by a robot and is a little wrong in places; a chair is moved, a door is closed, a person walks through, and the robot must decide which readings to trust. And this rover never leaves its corridor, so the crowd only ever has to tell one corridor spot from another. A house with two corridors that look alike, or a long corridor with no doorways, would keep it guessing longer: in a long empty corridor a robot knows how far it is from the walls and little else until something distinctive comes into view.