Section 3.5 Glossary

Occupancy Grid

🔗

A map representation that divides space into a 2D matrix of uniform cells marked as free, occupied, or unknown.

🔗

Grid Connectivity (4-Connected / 8-Connected)

🔗

The set of neighboring cells a robot may step to from its current cell: orthogonal-only (4-connected) or orthogonal plus diagonal (8-connected).

🔗

Node

🔗

A graph element representing a state or location that a search algorithm can visit, such as a traversable grid cell.

🔗

Path Planning

🔗

The process of computing a feasible and efficient route from a start location to a goal.

🔗

A* (A-Star)

🔗

An informed graph-search algorithm that ranks candidates by \(f(n)=g(n)+h(n)\text{.}\)

🔗

\(g(n)\) Cost

🔗

The exact accumulated path cost from the start node to node \(n\text{.}\)

🔗

\(h(n)\) Heuristic

🔗

An estimate of the remaining cost from node \(n\) to the goal.

🔗

Manhattan Distance

🔗

A grid-based heuristic for 4-connected movement, computed as \(h(n) = |x_n - x_{\text{goal}}| + |y_n - y_{\text{goal}}|\text{.}\)

🔗

Euclidean Distance

🔗

A straight-line heuristic for movement in any continuous direction, computed as \(h(n) = \sqrt{(x_n - x_{\text{goal}})^2 + (y_n - y_{\text{goal}})^2}\text{.}\)

🔗

Open List

🔗

The set of discovered but not yet processed nodes that A* selects its next expansion from, ordered by lowest \(f(n)\text{.}\)

🔗

Closed List

🔗

The set of nodes A* has already expanded and will not revisit.

🔗