Skip to main content
Contents Index
Search Book
Search Results:
No results.
Read aloud Readability settings Prev Up Next Scratch ActiveCode Profile title here \(\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section 3.1 Representing Space: Grid Maps and Graphs
Before a robot can plan a route from start to finish, it needs a way to store the world in memory. Physical environments are continuous, but computers process information best when space is broken down into discrete chunks.
Imagine a rectangular room with a single rectangular obstacle sitting inside it. To store that continuous floor plan in memory, we overlay it with a uniform grid of square cells and mark each cell with a single number:
0 where the floor is clear, and
1 wherever the cell overlaps the obstacle.
Subsection 3.1.1 Occupancy Grid Maps
An
Occupancy Grid Map divides the robot’s environment into a 2D matrix of uniform square cells.
Free Space (0): Safe for the robot to drive through.
Occupied Space (1): Represents walls, furniture, or obstacles.
Unknown Space (-1 or 0.5): Areas the robot’s sensors haven’t scanned yet.
Figure 3.1.1. An occupancy grid converts a continuous environment into discrete cells labeled as free space or obstacles.
Subsection 3.1.2 Grid Connectivity: 4-Way vs. 8-Way
When moving between cells, we define how a robot can step:
4-Connected Neighborhood: The robot moves only up, down, left, or right (orthogonally) — its North, South, East, and West neighbors.
8-Connected Neighborhood: The robot can also move diagonally, adding the Northeast, Northwest, Southeast, and Southwest neighbors to the four orthogonal ones.
Figure 3.1.2. Four-connected movement uses orthogonal neighbors, while eight-connected movement also permits diagonal neighbors.
Subsection 3.1.3 Section 3.1 Interactive Exercises
Subsubsection 3.1.3.1 Exercise 3.1.2: CodeLens Trace — Neighbor Generation
Step through the code to trace how a robot finds its valid, unblocked 4-connected neighbors on a 2D grid.
Reading Questions 3.1.4 Reading Questions
1. Exercise 3.1.1: Map Grid Indexing Conceptual Check.
Given a 2D occupancy grid represented in Python as:
grid = [[0, 0, 0], [0, 0, 1], [0, 1, 0]]
What is located at
grid[1][2] (row 1, column 2)?
Free space, because grid[1][2] contains a 0.
Incorrect. Remember that 1 represents an occupied cell (obstacle).
Obstacle, because grid[1][2] contains a 1.
Correct! grid[1] is the second row [0, 0, 1], and index 2 selects the value 1 (Obstacle).
Unknown space, because grid[1][2] is out of bounds.
Incorrect. Row 1, Column 2 is well within bounds of a 3x3 grid.
Free space, because 1 means clear path.
Incorrect. By standard convention in occupancy grids, 1 represents an obstacle.
You have attempted
of
activities on this page.
