Drones and self-driving basicsMiddleLesson 2856 min read

Seeing obstacles

Sensors fill a grid map with free, blocked and unknown squares. Then we grow every obstacle by a safety margin, so the robot's body never scrapes past.

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

Speed

Lesson in motion

In 60 seconds

Seeing obstacles

Sensors fill a grid map with free, blocked and unknown squares. Then we grow every obstacle by a safety margin, so the robot's body never scrapes past.

1/4

In simple words

When you carry a big box through a crowded room, you do not walk right next to the chairs. You keep a gap, because the box is wider than you. Robots do the same. They draw a thick line around every obstacle on their map, as wide as their body plus a bit extra, and then never cross that line.

A path planner needs a map that says which places are free. A robot builds this map from its sensors, usually as an occupancy grid: every square holds how likely it is to be occupied.

Building an occupancy grid

A lidar or depth sensor sends out a beam. Where it hits something, that square is probably occupied.
The squares the beam passed through on the way are probably free.
Squares no beam has reached are unknown. A careful robot treats unknown like blocked, or slows down.
One reading is not trusted fully. Each new reading nudges a square's probability up or down, so a single noisy reading does not create or erase a wall.

Python: updating one square from several readingspython

import math

# Log-odds: a handy way to add up evidence. 0 means 50/50.
def to_prob(log_odds):
    return 1 / (1 + math.exp(-log_odds))

HIT, MISS = 0.85, -0.4    # how much one "hit" or one "passed through" changes our belief
cell = 0.0                # start unknown: 50%

readings = ["hit", "hit", "miss", "hit", "hit", "miss", "hit"]
for i, r in enumerate(readings, 1):
    cell += HIT if r == "hit" else MISS
    print(f"reading {i} ({r:4}): chance occupied = {to_prob(cell):.2f}")

Moving obstacles

Walls stay put, but people, dogs, cycles and cows move. A grid built slowly over many readings is good for walls, but it may leave a "ghost" where a person used to stand, or miss someone who just walked in. Real systems often keep the still map and the moving objects separately, and predict where moving things will be a moment later.

Safety margins: inflating obstacles

A planner treats the robot as a single point moving from square to square. But a real robot has a body. If the point passes one square away from a wall, the body may hit it. The fix is simple: inflate every obstacle by the robot's radius plus a safety margin. Now any path the point planner finds is safe for the whole body.

Without inflation

The path hugs walls and corners
The robot's side scrapes the wall
A small position error causes a crash

With inflation

The path keeps a gap from every obstacle
The whole body fits through
There is room for sensor and position error

The margin is a trade-off. Too small, and position errors or a gust of wind cause collisions. Too big, and narrow doorways and gaps disappear from the map, so the robot finds no path at all. Many systems use a hard inner margin that must never be crossed, and a soft outer zone where paths are allowed but cost more.

Margin should grow when	Because
The robot moves faster	It needs more distance to stop
Position is less certain	GPS or dead reckoning may be off by more
It is windy (for drones)	Wind can push the drone sideways
People or animals are near	They move unpredictably, and a collision can hurt them

Real example

A college team in Bengaluru tests a small indoor drone in their lab. Their first grid has no margin, and the planner happily sends the drone through a 40 cm gap between two shelves. The drone is 35 cm wide, and it clips a shelf. They inflate obstacles by half the drone's width plus a margin. Now the planner goes around, which is slower but safe.

Watch out

Obstacle detection can fail: thin wires, glass, smoke, bright sun into a camera, or objects below a sensor's view. A safe design never relies on one sensor for safety, and slows down or stops when it is unsure.

Try this. In the log-odds code, add three more "miss" readings at the end. How many misses does it take to drop below 50%?

Watch and read more

Lab

An inflate() function that grows obstacles by a safety margin on a grid, without changing the original map.

~25 min

The problem

This runs in your browser.

Finish inflate(grid, radius). Return a new list of strings. A free cell becomes # if any obstacle is within radius cells of it in every direction, including diagonals (the rows apart and the columns apart are both at most radius). Do not change the input grid.
Run it with radius 1 and 2 and look at the printed maps. Which gaps close?
Write two sentences: for a drone 30 cm wide, with grid squares of 10 cm, what radius would you choose, and why?

Practice lab

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

Ctrl + Enter to run

Output

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

You are done when

inflate returns a new grid and leaves the original unchanged
Diagonal neighbours are included, so obstacles grow as squares
Obstacles at the edge of the grid grow without errors
The radius chosen for the 30 cm drone covers half its width plus an extra margin, with a reason

Hard questions

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

Q1You inflate by radius 2 and the planner finds no path through the only doorway. What are your honest options?Reveal

Check the numbers first: maybe the margin is larger than needed, or the grid squares are too coarse, so a real gap looks smaller than it is. A finer grid can help. You can also use a hard inner margin plus a soft, costly outer zone, so the robot may pass through the doorway slowly and centred. What you should not do is quietly shrink the margin below the robot's real size plus its position error.

Q2Why is square inflation (including diagonals) slightly different from a real round robot, and does it matter?Reveal

A square grows obstacles a little further along the diagonals than a circle would, so it is slightly more cautious in corners. For most small robots this extra caution is fine. When space is tight, planners can use a round shape, by checking the real distance to the nearest obstacle instead of rows and columns.

Please sign in to continue.

Questions people ask

Why use log-odds and not just probabilities?

With log-odds, each new reading is just added. It avoids repeated multiplying, and keeps numbers stable when a square is almost certainly free or blocked. You can turn it back into a probability whenever you need one.

How big should a grid square be?

Small squares show more detail but use more memory and make planning slower. A common approach is to choose squares a little smaller than the smallest gap you care about. Drones in open fields can use much bigger squares than robots inside a house.

Is inflating obstacles the same as a configuration space?

Yes, for a round robot. Growing obstacles by the robot's radius turns "does the body fit?" into "is this point free?". This idea is called planning in configuration space. For long or odd-shaped robots, the direction the robot faces also matters, which makes it more complex.

What should a robot do when a gap is too narrow after inflation?

Plan another route, slow down and look more carefully, or stop and ask a human. It should not quietly shrink its own safety margin just to get through.

Lesson test

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