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.2 Pathfinding Heuristics: Estimating Distance
When searching a large grid map, how does a robot decide which direction to try first? It uses a
Heuristic function , denoted as
\(h(n)\text{.}\)
A heuristic is an educated guess that estimates the remaining distance from any given cell
\(n\) to the goal cell.
On a 4-connected grid, a path from a start cell
\(S\) to a goal cell
\(G\) must zig-zag along orthogonal grid lines, so its length is the sum of horizontal and vertical steps taken. On an open continuous space, the same trip could instead be measured as one straight diagonal line directly from
\(S\) to
\(G\text{.}\) These two ways of measuring distance, stair-stepped along grid lines versus a direct straight line, correspond to the two most common heuristics used in grid-based pathfinding.
Subsection 3.2.1 Common Distance Metrics
Figure 3.2.1. Manhattan distance follows orthogonal grid steps, while Euclidean distance measures the straight-line path from the start to the goal.
Subsubsection 3.2.1.1 Manhattan Distance (\(h_{\text{manhattan}}\) )
When to use: When the robot can only move in 4 orthogonal directions (up, down, left, right).
Intuition: Sum of absolute horizontal and vertical differences (like walking along city blocks).
Formula:
\begin{equation*}
h(n) = |x_n - x_{\text{goal}}| + |y_n - y_{\text{goal}}|
\end{equation*}
Subsubsection 3.2.1.2 Euclidean Distance (\(h_{\text{euclidean}}\) )
\begin{equation*}
h(n) = \sqrt{(x_n - x_{\text{goal}})^2 + (y_n - y_{\text{goal}})^2}
\end{equation*}
Subsection 3.2.2 Section 3.2 Interactive Exercises
Subsubsection 3.2.2.1 Exercise 3.2.2: Parsons Problem — Manhattan Heuristic Function
Construct a Python function that takes a current cell position
(r1, c1) and goal position
(r2, c2) and calculates the Manhattan distance heuristic.
Checkpoint 3.2.2 .
Arrange the blocks to form a complete function
manhattan_heuristic that computes the Manhattan distance heuristic between a current cell and a goal cell.
def manhattan_heuristic(current, goal):
---
r1, c1 = current
r2, c2 = goal
---
row_diff = abs(r1 - r2)
col_diff = abs(c1 - c2)
---
h_cost = row_diff + col_diff
---
return h_cost
Reading Questions 3.2.3 Reading Questions
1. Exercise 3.2.1: Selecting the Right Heuristic.
A robot is navigating a grid using strict 4-connected movement (no diagonal steps allowed). Which heuristic function is most appropriate for estimating the remaining path cost to the goal?
Manhattan Distance, because movement is constrained to orthogonal grid steps.
Correct! Manhattan distance accurately measures distance along orthogonal grid lines without underestimating or relying on impossible diagonal cuts.
Euclidean Distance, because straight-line distance is always faster to calculate.
Incorrect. Euclidean distance represents straight-line cuts across diagonal cells, which the robot cannot actually take in a 4-connected setup.
Manhattan Distance, because diagonal movement is allowed in 4-connected grids.
Incorrect. 4-connected grids explicitly forbid diagonal moves.
Euclidean Distance, because Manhattan distance underestimates the distance on a grid.
Incorrect. Manhattan distance does not underestimate orthogonal grid paths.
You have attempted
of
activities on this page.
