Occupancy grid mapping explained

How a robot builds an occupancy grid map from range readings: the inverse sensor model, log odds, binary grids and frontier exploration, with four live Python demos on a simulated robot that show what goes wrong with noise and a drifting gyro.

Guidefree, runs in your browser

An occupancy grid is a map made of squares. The floor is cut into small cells, and each cell holds one number: how likely it is that something is in the way there. A robot builds the map from its range sensor, one beam at a time, and a planner reads it to find where the robot can go. Many robot vacuum cleaners that show a floor plan in their app keep one, and so does the ROS navigation stack. On this page a small robot on a 2 metre mat builds a map with its depth sensor, and each demo below is a real program you can change and run.

In the overhead view of each demo, light blue squares are cells the map says are free, black squares are cells it says are occupied, and anywhere still the colour of the mat is unknown: no beam has been there yet. The simulator draws the real obstacles underneath, so you can see where the map is right and where it is not. The chart under most demos shows how much of the mat the map knows about, as a percentage.

The robot's depth sensor reads a fan of 8 beams, about 40 degrees wide, and scan() returns each one as an angle and a distance. To see the whole room the robot turns. Every demo on this page takes the robot's position and heading from the simulator (in the lab this is an overhead camera), because building a map is much easier when you know exactly where you are. What happens when you do not is the third demo.

The idea in one loop

every cell starts at 0: unknown
each tick:
    find the pose: where the robot is, which way it faces
    for each beam in the scan:
        cells the beam passed through: a bit more likely free
        the cell where it stopped:     a bit more likely occupied

That is the whole of occupancy grid mapping with a known pose. Hans Moravec and Alberto Elfes described it in the mid 1980s, for a robot with sonar sensors, and it has hardly changed since. Two pieces need explaining: how one beam turns into evidence about cells (the inverse sensor model), and how the evidence from thousands of beams is added up (log odds).

The inverse sensor model

A range reading looks like one number. It says two things:

1. Something is there. The beam stopped at 100 cm, so the cell 100 cm away along the beam is occupied.
2. Nothing is in the way before it. The beam got that far, so every cell it passed through is free.

The second statement covers about 20 cells of 5 cm and the first covers one, which is why a grid fills in quickly. A mapper that only marked the hits would draw the outline of the walls and know nothing about the floor, and the floor is what a planner needs.

In code, for one beam at angle a from a robot at (x, y) facing h:

th = math.radians(h + a)       # the beam's direction
sx, sy = math.sin(th), math.cos(th)
r = 0.0
while r < d - CELL:            # every cell it passed
    add(x + r * sx, y + r * sy, L_FREE)
    r += CELL / 2
add(x + d * sx, y + d * sy, L_OCC)   # where it stopped

• Sine for x, cosine for y. This robot measures its heading clockwise from straight up the mat, like a compass. Swap them and the map comes out mirrored.
• Step half a cell at a time. Whole cell steps along a slanting beam jump over cells and leave the free space speckled. The standard way to visit exactly the cells a line crosses is Bresenham's line algorithm.
• Stop one cell short of the hit. Otherwise the free marking and the hit fight over the same cell.
• A reading that found nothing is not a wall. A depth sensor that sees nothing in range returns its maximum. The programs here only mark a hit when the reading is under FAR (170 cm), and use longer readings as free space up to 170 cm.

It is called inverse because it runs backwards from the reading to the world. The forward model runs the other way: given a map and a pose, what should the sensor read? That is the model a particle filter uses to find a robot on a map.

Log odds

Each cell should hold a probability p that it is occupied. Mappers store the log odds instead:

l = ln( p / (1 - p) )        and back:   p = 1 / (1 + e^-l)

The reason is that combining independent evidence with Bayes' rule, which with probabilities means multiplying and rescaling, becomes plain addition in log odds:

l = l + L_OCC      # a beam stopped in this cell
l = l + L_FREE     # a beam passed through it

• An empty map is all zeros, which is exactly "unknown".
• L_OCC = 0.85 says one hit makes a cell 70 % likely to be occupied. L_FREE = -0.4 says one pass-through makes it 60 % likely to be free. Both are timid on purpose: one reading is often wrong, and twenty that agree should settle it.
• Hits count for more than passes because a beam can slip past a thin chair leg, but a beam that comes back did hit something.
• Every cell is clamped, here between -8 and +8 (p from 0.0003 to 0.9997). Without a clamp a cell the robot stares at for a minute becomes so certain that, when the thing in it moves, it takes another minute of readings to change its mind. The second demo shows the numbers.

A map from one spot

The robot stands in the middle of the mat. There is a post 30 cm to its right and a shelf 50 cm ahead, over to the left. It turns on the spot for 13 seconds, a little over one full turn, and puts every scan into a grid of 5 cm cells, 40 by 40. A cell counts as known once its log odds is past 1 either way (p above 0.73 or below 0.27).

The chart has a second line, wrong walls %: the share of black cells that are more than one cell away from anything real. The program knows where the post and shelf are only to draw that line; the map never sees it.

from bugbot import *
import math
connect()

# change these numbers and press Run
CELL = 5          # cm per cell (5 to 20)
L_OCC = 0.85      # a beam stopped here
L_FREE = -0.4     # a beam passed through
DRIFT = 0         # degrees per second the gyro drifts

W = int(200 / CELL)          # cells across the mat
START = (100, 100)           # where the robot starts
FAR = 170                    # trust readings to here
grid = [0.0] * (W * W)       # log odds, 0 = unknown
# the truth, only for the chart: post and shelf
REAL = [(130, 70, 8, 70), (40, 150, 70, 8)]

def add(x, y, amount):
    # add evidence to the cell at (x, y) cm
    c, r = int(x / CELL), int(y / CELL)
    if 0 <= c < W and 0 <= r < W:
        l = grid[r * W + c] + amount
        grid[r * W + c] = max(-8, min(8, l))

def update():
    # the inverse sensor model, for every beam
    px, py = position()
    x, y = START[0] + px, START[1] + py
    h = heading() + DRIFT * clock()
    for a, d in scan():
        th = math.radians(h + a)
        sx, sy = math.sin(th), math.cos(th)
        r = 0.0
        while r < min(d, FAR) - CELL:   # free
            add(x + r * sx, y + r * sy, L_FREE)
            r += CELL / 2
        if d < FAR:                     # the hit
            add(x + d * sx, y + d * sy, L_OCC)

def real(x, y):
    # is (x, y) within a cell of a real wall?
    if min(x, y, 200 - x, 200 - y) < CELL:
        return True             # the mat edge
    for rx, ry, w, h in REAL:
        if (rx - CELL < x < rx + w + CELL and
                ry - CELL < y < ry + h + CELL):
            return True
    return False

def show():
    free, occ = [], []
    for i, l in enumerate(grid):
        c, r = i % W, i // W
        p = (c * CELL + CELL / 2, r * CELL + CELL / 2)
        if l < -1: free.append(p)
        if l > 1: occ.append(p)
    draw("free", free, "#9ecae1", "squares", CELL)
    draw("occupied", occ, "black", "squares", CELL)
    plot("known %", 100 * (len(free) + len(occ))
         / len(grid))
    wrong = [p for p in occ if not real(*p)]
    plot("wrong walls %", 100 * len(wrong)
         / max(1, len(occ)))
    return len(free), len(occ)

drive(0, 0, 30)              # turn on the spot
for tick in range(130):      # for 13 seconds
    update()
    if tick % 5 == 0:
        show()
    wait(0.1)
stop()
free, occ = show()
print("free cells:", free, " occupied:", occ)

Watch the known line.

1. Slow at first. For the first 3 seconds the sensor faces the shelf and then the post, both close, so each scan adds only a few cells. At 3 s the map knows 12 % of the mat.
2. Fast. Then the fan sweeps across the open mat, and every scan paints a long wedge of free cells ending in a line of black along the mat's edge. By 8.5 s the map knows 62 %.
3. Flat. The second time round adds almost nothing, and it ends at 63.5 %: 901 free cells and 115 occupied out of 1600. From one spot, that is all there is to see.

The unknown patches that are left are shadows: the space behind the post and behind the shelf, where no beam can reach from here. No amount of turning fills them in. The robot has to move, which is what the last demo does.

Try L_FREE = 0, so a beam passing through a cell counts for nothing. The map keeps only the hits: 139 occupied cells, no free ones, and it knows 8.7 % of the mat. It has the outline of the post and the shelf and says nothing about the floor between them, which is no use to a planner that needs to know where it is safe to drive.

Try CELL = 20. The grid is now 10 by 10, 100 cells, and 70 of them end up known. The post, 8 cm wide, comes out as a block 20 cm wide. Bigger cells are faster and fill in with fewer readings, but a gap narrower than two cells can close up. The rule of thumb is a cell a good deal smaller than the smallest gap the robot must fit through, and no smaller than the sensor's error. On this mat, 5 cm.

Adding up the evidence

Now four single cells, watched while the robot drives about 50 cm straight at a wall that runs across the mat at y = 150. The chart shows the log odds of each:

• floor (blue), open floor 25 to 30 cm in front of the wall,
• in front (orange), the last 5 cm of floor before the wall's face,
• wall (red), the cell the wall's face is in,
• behind (purple), a cell behind the wall that no beam can reach.

from bugbot import *
import math
connect()

# change these numbers and press Run
L_OCC = 0.85      # a beam stopped here
L_FREE = -0.4     # a beam passed through
L_MAX = 8         # no cell gets surer than this

CELL, W = 5, 40
START = (100, 40)            # where the robot starts
FAR = 170                    # trust readings to here
grid = [0.0] * (W * W)       # log odds, 0 = unknown
# four cells to watch: their centres on the mat, cm
WATCH = {"floor": (102.5, 122.5),
         "in front": (102.5, 147.5),   # wall face: 150
         "wall": (102.5, 152.5),
         "behind": (102.5, 177.5)}

def add(x, y, amount):
    c, r = int(x / CELL), int(y / CELL)
    if 0 <= c < W and 0 <= r < W:
        l = grid[r * W + c] + amount
        grid[r * W + c] = max(-L_MAX, min(L_MAX, l))

def update():
    px, py = position()
    x, y = START[0] + px, START[1] + py
    h = heading()
    for a, d in scan():
        th = math.radians(h + a)
        sx, sy = math.sin(th), math.cos(th)
        r = 0.0
        while r < min(d, FAR) - CELL:   # free
            add(x + r * sx, y + r * sy, L_FREE)
            r += CELL / 2
        if d < FAR:                     # the hit
            add(x + d * sx, y + d * sy, L_OCC)

def cell(x, y):
    # the log odds of the cell at (x, y)
    return grid[int(y / CELL) * W + int(x / CELL)]

colours = ["blue", "orange", "red", "purple"]
for name, colour in zip(WATCH, colours):
    draw(name, [WATCH[name]], colour, "squares", CELL)

forward(50)                  # drive at the wall
for tick in range(100):      # for 10 seconds
    if position()[1] > 50:
        stop()
    update()
    for name in WATCH:
        plot(name, cell(*WATCH[name]))
    wait(0.1)
stop()
for name in WATCH:
    l = cell(*WATCH[name])
    p = 1 / (1 + math.exp(-l))
    print(name, " log odds", round(l, 2),
          " p", round(p, 4))

The floor cell loses 0.8 every tick and reaches the clamp at -8 by 0.9 s. The wall cell gets its first hit at 0.7 s and reaches +8 at 2.2 s. The cell behind the wall stays at exactly 0 for the whole run: unknown, and the map says so. A map that could only say "free" or "occupied" would have to guess.

The orange cell is the interesting one. It is floor, but it ends at +7.25, so the map is sure it is wall. The readings here wobble by about 2 cm, so a reading that comes back 1 or 2 cm short puts its hit in this cell, while the free marking stops a cell short of every hit and hardly ever reaches it. For the first 1.3 s it goes up and down between -0.4 and +0.5, then the hits win. This is why walls in an occupancy grid come out about one cell thicker, on the side the robot saw them from. You can see it on the post in the first demo: patches of black just to its left.

Try L_MAX = 100 to take the clamp almost away. By the end the floor cell is at -86.8 and still falling, and the wall cell is at +22.95. If a box were now put on that floor cell, it would take 103 hits in a row just to get it back to "unknown". With the clamp at 8 it takes 10. The clamp is what lets a map keep up with a world where doors open and chairs move.

Try L_FREE = -0.85, so a pass counts as much as a hit. The orange cell spends much of the first 3.5 s at or below zero, but once the robot is closer the hits win, and it ends at +4.25: still occupied.

A wrong pose makes a wrong map

The first demo again, with one change: DRIFT = 3. The heading the program uses to place each beam is now out by 3 degrees more every second, as a cheap gyro's might be.

from bugbot import *
import math
connect()

# change these numbers and press Run
CELL = 5          # cm per cell (5 to 20)
L_OCC = 0.85      # a beam stopped here
L_FREE = -0.4     # a beam passed through
DRIFT = 3         # degrees per second the gyro drifts

W = int(200 / CELL)          # cells across the mat
START = (100, 100)           # where the robot starts
FAR = 170                    # trust readings to here
grid = [0.0] * (W * W)       # log odds, 0 = unknown
# the truth, only for the chart: post and shelf
REAL = [(130, 70, 8, 70), (40, 150, 70, 8)]

def add(x, y, amount):
    # add evidence to the cell at (x, y) cm
    c, r = int(x / CELL), int(y / CELL)
    if 0 <= c < W and 0 <= r < W:
        l = grid[r * W + c] + amount
        grid[r * W + c] = max(-8, min(8, l))

def update():
    # the inverse sensor model, for every beam
    px, py = position()
    x, y = START[0] + px, START[1] + py
    h = heading() + DRIFT * clock()
    for a, d in scan():
        th = math.radians(h + a)
        sx, sy = math.sin(th), math.cos(th)
        r = 0.0
        while r < min(d, FAR) - CELL:   # free
            add(x + r * sx, y + r * sy, L_FREE)
            r += CELL / 2
        if d < FAR:                     # the hit
            add(x + d * sx, y + d * sy, L_OCC)

def real(x, y):
    # is (x, y) within a cell of a real wall?
    if min(x, y, 200 - x, 200 - y) < CELL:
        return True             # the mat edge
    for rx, ry, w, h in REAL:
        if (rx - CELL < x < rx + w + CELL and
                ry - CELL < y < ry + h + CELL):
            return True
    return False

def show():
    free, occ = [], []
    for i, l in enumerate(grid):
        c, r = i % W, i // W
        p = (c * CELL + CELL / 2, r * CELL + CELL / 2)
        if l < -1: free.append(p)
        if l > 1: occ.append(p)
    draw("free", free, "#9ecae1", "squares", CELL)
    draw("occupied", occ, "black", "squares", CELL)
    plot("known %", 100 * (len(free) + len(occ))
         / len(grid))
    wrong = [p for p in occ if not real(*p)]
    plot("wrong walls %", 100 * len(wrong)
         / max(1, len(occ)))
    return len(free), len(occ)

drive(0, 0, 30)              # turn on the spot
for tick in range(130):      # for 13 seconds
    update()
    if tick % 5 == 0:
        show()
    wait(0.1)
stop()
free, occ = show()
print("free cells:", free, " occupied:", occ)

For the first 2 seconds almost every black cell is in the right place. By 5.5 s about a fifth of the black cells are in the wrong place, and by the end 46 %. On the second time round the beams land about 29 degrees away from where they landed the first time, so they draw a second set of walls at a different angle, and their free marking paints blue over the first set. Most of the shelf is rubbed out. The known line reaches 69.5 %, higher than the true map's 63.5 %: the map claims to have seen more than the robot could.

Try DRIFT = 1: about 21 % of the black cells end up in the wrong place. Try DRIFT = 0.2, which is about what this robot's own gyro drifted by in the same 13 s turn, measured through odometry(): the map is as good as the true one, with no wrong walls.

This is the hard part of real mapping. The grid update is a few lines; the difficulty is knowing the pose. A robot with only its own wheels and gyro to go on (dead reckoning) drifts further the longer it runs, and every drift smears the map. The answer is SLAM, simultaneous localisation and mapping: work out the pose from the map while building the map from the pose. GMapping does it with a particle filter in which every particle carries its own occupancy grid; Cartographer and slam_toolbox, both used with ROS, match each new scan against the map built so far.

Binary maps and frontiers

A binary occupancy grid holds one bit per cell: occupied or free. It is what you get when you threshold a probability grid, and it is what most planners read, because a search such as A* only needs to know whether it can step into a cell. In practice two thresholds are used, giving three states: occupied above one probability, free below another, and unknown in between. ROS map files work this way, with occupied_thresh (often 0.65) and free_thresh, and store the map as an image in black, white and grey. A strictly binary grid has no way to say "unknown", so a cell nobody has looked at has to be called free or occupied, and either guess can mislead a planner.

The unknown cells are what let a robot explore on purpose. A frontier cell is a free cell next to an unknown one: a place the robot can reach, on the edge of what it has not seen. Brian Yamauchi described frontier-based exploration in 1997:

1. Find every frontier cell.
2. Group touching frontier cells into regions (a flood fill, the same search as in BFS and DFS).
3. Ignore regions too small to matter.
4. Drive to the best region, look round, and repeat until no frontier is left.

Here the mat has a wall right across it at y = 120, with a doorway 20 cm wide in the middle. The robot starts below the wall. It sweeps, then picks the nearest cell in a frontier region of at least MIN_REGION cells that it can drive to in a straight line, 6 cm clear of anything the map says is occupied. It drives there and sweeps again. Yellow squares are frontier cells, and the red dot is where it chose to go. This robot can drive sideways, so the program steers straight at the goal whichever way it happens to be facing.

from bugbot import *
import math
connect()

# change these numbers and press Run
MIN_REGION = 5    # smallest frontier worth a trip
OCC_P = 0.65      # p above this: occupied
FREE_P = 0.35     # p below this: free

CELL, W = 5, 40              # 40 by 40 cells of 5 cm
L_OCC, L_FREE = 0.85, -0.4
START = (100, 25)            # where the robot starts
FAR = 170                    # trust readings to here
grid = [0.0] * (W * W)       # log odds, 0 = unknown
OCC_L = math.log(OCC_P / (1 - OCC_P))
FREE_L = math.log(FREE_P / (1 - FREE_P))

def add(x, y, amount):
    c, r = int(x / CELL), int(y / CELL)
    if 0 <= c < W and 0 <= r < W:
        l = grid[r * W + c] + amount
        grid[r * W + c] = max(-8, min(8, l))

def where():
    px, py = position()
    return START[0] + px, START[1] + py

def update():
    x, y = where()
    h = heading()
    for a, d in scan():
        th = math.radians(h + a)
        sx, sy = math.sin(th), math.cos(th)
        r = 0.0
        while r < min(d, FAR) - CELL:   # free
            add(x + r * sx, y + r * sy, L_FREE)
            r += CELL / 2
        if d < FAR:                     # the hit
            add(x + d * sx, y + d * sy, L_OCC)

def centre(i):
    return ((i % W) * CELL + CELL / 2,
            (i // W) * CELL + CELL / 2)

def near(i):
    # the four cells that share a side with cell i
    c, r = i % W, i // W
    if c > 0: yield i - 1
    if c < W - 1: yield i + 1
    if r > 0: yield i - W
    if r < W - 1: yield i + W

def frontiers():
    # free cells with an unknown neighbour,
    # grouped into regions that touch
    unknown = [FREE_L <= l <= OCC_L for l in grid]
    edge = set(i for i in range(W * W)
               if grid[i] < FREE_L
               and any(unknown[j] for j in near(i)))
    regions = []
    while edge:
        todo = [edge.pop()]
        region = []
        while todo:
            i = todo.pop()
            region.append(i)
            for j in near(i):
                if j in edge:
                    edge.remove(j)
                    todo.append(j)
        regions.append(region)
    return regions

def show():
    free = [centre(i) for i in range(W * W)
            if grid[i] < FREE_L]
    occ = [centre(i) for i in range(W * W)
           if grid[i] > OCC_L]
    edge = [centre(i) for r in frontiers() for i in r]
    draw("free", free, "#9ecae1", "squares", CELL)
    draw("occupied", occ, "black", "squares", CELL)
    draw("frontier", edge, "yellow", "squares", CELL)
    known = len(free) + len(occ)
    plot("known %", 100 * known / (W * W))
    plot("frontier cells", len(edge))

def sweep(seconds):
    # turn on the spot, mapping as it goes
    drive(0, 0, 30)
    for tick in range(int(seconds * 10)):
        update()
        if tick % 5 == 0:
            show()
        wait(0.1)
    stop()
    show()

def clear(tx, ty):
    # is the straight line from the robot to
    # (tx, ty) 6 cm clear of every occupied cell?
    x, y = where()
    steps = int(math.hypot(tx - x, ty - y) / 2.5) + 1
    for k in range(steps + 1):
        px = x + (tx - x) * k / steps
        py = y + (ty - y) * k / steps
        for ox in (-6, 0, 6):
            for oy in (-6, 0, 6):
                c = int((px + ox) / CELL)
                r = int((py + oy) / CELL)
                if not (0 <= c < W and 0 <= r < W):
                    return False
                if grid[r * W + c] > OCC_L:
                    return False
    return True

def go_to(tx, ty):
    # drive straight at (tx, ty) whichever way
    # the robot faces, mapping on the way
    tick = 0
    while True:
        x, y = where()
        dx, dy = tx - x, ty - y
        d = math.hypot(dx, dy)
        if d < 3:
            break
        v = min(90, 20 + 3 * d) / d
        h = math.radians(heading())
        s, c = math.sin(h), math.cos(h)
        drive(v * (dx * s + dy * c),
              v * (dx * c - dy * s), 0)
        update()
        tick += 1
        if tick % 5 == 0:
            show()
        wait(0.1)
    stop()

def pick():
    # the nearest cell in a big enough frontier
    # region that the robot can drive straight to
    x, y = where()
    regions = frontiers()
    big = [r for r in regions if len(r) >= MIN_REGION]
    print("frontier regions:", len(regions),
          " big enough:", len(big))
    cells = [centre(i) for r in big for i in r]
    cells.sort(key=lambda p: math.hypot(p[0] - x,
                                        p[1] - y))
    for p in cells:
        if clear(*p):
            return p
    return None

sweep(10)                    # 1. look round
goal = pick()                # 2. choose a frontier
if goal:
    print("going to", goal)
    draw("goal", [goal], "red", size=4)
    go_to(*goal)             # 3. go there
    sweep(8)                 # 4. look again
    pick()

After the first sweep the map knows 66 % of the mat and has 22 frontier regions. 15 of them are single cells and 4 are pairs: slivers along the walls where the gaps between beams left a cell unseen. The only 3 with 5 or more cells are the edges of the strip of free space the beams cut through the doorway. The nearest cell the robot can reach in a straight line is at the top of that strip, (97.5, 187.5), so it drives through the doorway, sweeps again, and the map ends at 98.4 % known. 32 frontier regions are left, none of them as big as 5 cells, so by this rule the map is finished. The chart's frontier line falls from 97 cells to 36.

Try MIN_REGION = 1, so every sliver counts. The nearest one the robot can reach is a pair of cells just below the wall, beside the doorway, at (87.5, 112.5). It drives there, sweeps, and learns little: the map ends at 76.4 %. Real explorers throw away small regions for this reason, and weigh how much new space a region might show against how far away it is.

Try OCC_P = 0.95, so a cell needs much more evidence to count as wall. The gaps in the wall row become unknown, 7 regions are now big enough, and the robot again goes to (87.5, 112.5) and ends at 74.6 %.

Questions

What is occupancy grid mapping?

It is a way for a robot to build a map from range readings. The floor is divided into equal square cells, and each cell holds the probability that something is in the way there. Every beam from a laser scanner, sonar or depth sensor lowers that probability in the cells it passes through and raises it in the cell where it stops. The finished grid says, for every cell, free, occupied or not yet seen.

How does the occupancy grid mapping algorithm work?

Every cell starts at log odds 0, meaning unknown. Each time the robot takes a scan, it looks up its own pose, and for each beam it works out which cells the beam crossed and adds a small negative number to each of them, then adds a larger positive number to the cell where the beam stopped. The totals are clamped so no cell becomes completely certain. Repeated over thousands of beams from different places, free space sinks, walls rise and cells no beam reached stay at 0.

What is the inverse sensor model?

It is the rule that turns one sensor reading into evidence about cells: given the reading, what does it say about the world? For a range sensor it says the cells before the reading are probably free and the cell at the reading is probably occupied, with a reading that found nothing treated as free space only. It is called inverse because the forward sensor model goes the other way, predicting the reading from a known map, which is what localisers such as particle filters use.

What are log odds in an occupancy grid?

Log odds are ln(p / (1 - p)), where p is the probability that the cell is occupied. Storing them instead of p turns the Bayes update into addition, so each reading adds a fixed amount such as +0.85 for a hit or -0.4 for a pass. An unknown cell is exactly 0, the numbers never get stuck at 0 or 1, and you convert back with p = 1 / (1 + e^-l) only when you want to draw or threshold the map.

Why clamp the log odds?

So that the map can change its mind. Without a clamp, a cell seen as free for a long time can reach a log odds of -80 or more, and if something is then put there it takes over 100 hits to undo. Clamping at about ±8 (p between 0.0003 and 0.9997) keeps every cell within about 10 readings of changing.

What is a binary occupancy grid?

A grid where each cell is one bit: occupied or free. It is usually made by thresholding a probability grid, and it is the simplest form for a path planner to read. Most real systems keep a third state, unknown, with two thresholds (occupied above about 0.65, free below a lower value), because a strictly binary grid has to call cells it has never seen either free or occupied.

How big should the cells be?

A good deal smaller than the smallest gap the robot has to fit through, and no smaller than the sensor's error. Halving the cell size makes four times as many cells in 2D, each needing its own readings. On the 2 metre mat on this page, 5 cm cells give 1,600 cells; 20 cm cells give 100, and an 8 cm post comes out 20 cm wide. Large 3D maps use a tree of cells instead of a flat array, the best known being OctoMap.

How are frontiers used to explore?

A frontier cell is a free cell next to an unknown one. The robot finds all the frontier cells, groups the touching ones into regions, throws away regions too small to be worth a trip, and drives to the best one, often the nearest. There it scans again, which turns some unknown cells into known ones and moves the frontier. When no frontier region is left, the robot has seen everything it can reach and the map is finished.

What is the difference between occupancy grid mapping and SLAM?

Occupancy grid mapping assumes the robot knows its pose and builds the map. SLAM, simultaneous localisation and mapping, has to work out the pose and the map together, because the robot's own estimate of where it is drifts. Many SLAM systems, such as GMapping, Cartographer and slam_toolbox, produce an occupancy grid as their map, so the grid update on this page sits inside them.

Why are the walls in my occupancy grid thick or doubled?

Thick walls, one cell deeper than they should be, come from sensor noise: readings that come back a little short put hits in the cell in front of the wall, and the free marking never reaches that cell to take them away. Doubled or smeared walls come from pose error: the robot saw the same wall twice and thought it was in a different place each time. Check the heading first, since a few degrees of heading error moves a wall 2 metres away by about 10 cm.

How do you make an occupancy grid map in Python?

Keep a flat list of floats, grid = [0.0] * (W * W), with cell (col, row) at row * W + col. For each beam, step along it half a cell at a time adding L_FREE to each cell, add L_OCC to the cell at the reading, and clamp each value. To draw it, call cells below -1 free and above +1 occupied. The first demo on this page is a complete mapper in about 70 lines; with NumPy you would use a 2D array and Bresenham's line algorithm to find the cells.

Is occupancy grid mapping on the GCSE or A level syllabus?

Not by name. None of the OCR, AQA or Edexcel/Eduqas Computer Science specifications, at GCSE or A level, mention occupancy grids. The pieces are there: two-dimensional arrays are in all of them, and logarithms and conditional probability are in A level Maths. It would suit an A level Computer Science programming project, since it needs 2D arrays, a flood fill and a clear test of whether the result is right.

Learn it step by step

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

1. U8.1 A map of cells Mapping, University
2. U8.2 The inverse sensor model Mapping, University
3. U8.3 Log odds Mapping, University
4. U8.4 Building a grid Mapping, University
5. U8.6 Frontiers Mapping, University
6. U8.7 Project: map the mat Mapping, University