Skip to the lesson
FixTheRobot Explore Robotics / Navigation / M3 Global Planning: Graph Search / M3-T1

Navigation · Theory · M3

M3-T1 — Search Problems on Grids and Graphs

Before any algorithm, the question: what is the thing being searched, and how big is it?

  • Lesson 1 of 7
  • Module 3: Global Planning: Graph Search
  • Theory
  • About 9 minutes to read

Scout needs to get from the lobby to the pharmacy. A person sees corridors and doors. A planner sees a set of places, a list of moves from each, and a price for every move. Writing the problem down in those terms is the first step of every planner in this module, and the choices made here, how the places are laid out and which moves are allowed, decide how long the path is and how long the search takes.

Learning objectives

After this lesson, you should be able to:

  • Define a search problem with states, actions, a transition, step costs and a goal test.
  • Turn an occupancy or cost grid into a graph, and say what its nodes and edges are.
  • Compare 4- and 8-connected grids by path length, number of edges and heading choices.
  • Estimate the size of a search space and say when a plain grid is too big.

The intuition

Think of a floor plan with a pin in every square. A search problem is a game played on those pins: you stand on one pin, you may move to a neighbouring pin, each move costs something, and you win when you stand on the goal pin. Nothing else matters to the search. It does not know about corridors, doors or paint; those only show up as which pins exist and which moves between them are allowed.

That is why one idea, “find the cheapest sequence of moves”, covers a delivery robot on a grid, a train on a rail network and a character in a game. The robot-specific work is in building the pins and the prices. Make the pins close together and the answer is more accurate and there are more of them to search. Allow diagonal moves and the paths are shorter and the search has more choices at every step.

Four- and eight-connected neighbourhoodsLeft: a cell with four straight neighbours. Middle: a cell with eight neighbours, four straight and four diagonal. Right: the same walk from the start to a goal ten columns right and six rows up, drawn as a staircase on a four-connected grid, which costs 16 steps, and as six diagonals plus four straights on an eight-connected grid, which costs 12.49.4-connected4 moves, cost 1 each 8-connected8 moves: 1 or √2 staircase: 16 steps diagonals: 12.49
Allowed moves decide what a path looks like. The same trip is 16 steps on a four-connected grid and 12.49 on an eight-connected one; the straight-line distance is 11.66.

The mathematics

A search problem

A search problem has five parts. Everything the later lessons do, breadth-first search, Dijkstra, A*, replanning, is a way of solving this one problem.

S
the set of states: here the cells of the grid, written (row, column).
s₀
the start state, a cell.
A(s)
the actions available in state s: the moves to neighbouring free cells.
c(s, s′)
the step cost of moving from s to s′. It must not be negative, and a planner needs it to be at least some ε > 0 to avoid endless zero-cost cycles.
G(s)
the goal test: true for the goal cell (or for any cell within a tolerance of it).

A solution is a sequence of states s₀, s₁, …, sₙ with sₙ passing the goal test and every step a legal move. Its cost is the sum of the step costs. An optimal solution has the least cost.

Path cost
cost⁡(path)=c(s0, s1)+c(s1, s2)+…+c(sn−1, sn)\operatorname{cost}(\text{path})=c(s_{0},\,s_{1})+c(s_{1},\,s_{2})+\ldots +c(s_{n-1},\,s_{n})

From a grid to a graph

A grid is a graph that is never stored. Each free cell is a node; each legal move between two cells is an edge with a cost. The neighbours of a cell are computed when the search needs them, so a 600 × 400 map does not need an edge list. Free space is where nodes exist: obstacle cells, and for a costmap the cells whose cost is 253 or more, are simply not nodes.

NeighbourhoodMovesStep costsWorst-case path vs straight line
4-connected4 (up, down, left, right)1 each41% longer (at 45°, 2 steps for 1.414)
8-connected8 (adds the diagonals)1 straight, √2 diagonal8.2% longer (at 22.5°)
16-connected16 (adds knight-like moves)lengths of the movesabout 2.7% longer

The percentages come from geometry. On an 8-connected grid a displacement of (dx, dy) with dx ≥ dy costs dx + (√2 − 1)·dy, while the straight line is √(dx² + dy²). Their ratio is largest at an angle of 22.5° and equals 1/cos(22.5°) = 1.0824.

How big is the search?

The number of states is the number of free cells. The number of edges is about 2 per cell for a 4-connected grid and 4 per cell for an 8-connected one, counting each undirected edge once. If the state also includes a heading, as it will in the lessons on kinodynamic planning (module M4), the count multiplies by the number of headings.

Size of a grid graph
states=rows×columns(free cells)\text{states}=\text{rows}\times \text{columns}\text{(free cells)}
edges4=(cols−1)⋅rows+(rows−1)⋅cols\mathrm{edges}_{4}=(\text{cols}-1)\cdot \text{rows}+(\text{rows}-1)\cdot \text{cols}
edges8=edges4+2⋅(cols−1)⋅(rows−1)\mathrm{edges}_{8}=\mathrm{edges}_{4}+2\cdot (\text{cols}-1)\cdot (\text{rows}-1)

A worked example

One floor of Meridian General. The ground floor is 60 m × 40 m. On a 0.1 m grid that is 600 × 400 cells.

Floor size
states=600×400=240, 000\text{states}=600\times 400=240,\,000
edges4=599⋅400+399⋅600=479, 000\mathrm{edges}_{4}=599\cdot 400+399\cdot 600=479,\,000
edges8=479, 000+2⋅599⋅399=957, 002\mathrm{edges}_{8}=479,\,000+2\cdot 599\cdot 399=957,\,002

A planner that visits every cell once, with a cost of a few microseconds per cell, takes about a second. That is fine for one plan and too slow if the plan is redone each second for a fleet. A coarser 0.2 m grid has a quarter of the cells, and doors that are 0.9 m wide are still four cells wide; at 0.5 m a 0.9 m door is only one or two cells and may vanish (lesson M2-T1).

Ten columns right, six rows up. Scout is 10 cells from the goal in the x direction and 6 in the y direction.

Path lengths
4−connected: 10+6=16 steps4-\text{connected}:\,10+6=16\,\text{steps}
8−connected:8-\text{connected}:
6 diagonals+4 straights=6⋅1.4142+4=12.4856\,\text{diagonals}+4\,\text{straights}=6\cdot 1.4142+4=12.485
straight line
102+62=11.662\sqrt{10^{2}+6^{2}}=11.662
ratios
1611.662=1.372\frac{16}{11.662}=1.372
12.48511.662=1.0706\frac{12.485}{11.662}=1.0706

The 4-connected path is 37% longer than the straight line and is not unique: every staircase with 10 rights and 6 ups costs 16, so there are C(16, 6) = 8,008 of them. The 8-connected path is only 7% longer, but it still has a fixed length for a huge number of different shapes, which is why an optimal grid path can zig-zag even though a straight one of similar cost exists (lesson M3-T5).

The cost is a modelling choice. If the cell values of the costmap are part of the step cost, the problem changes: the “cheapest” path is no longer the shortest one. The search problem is the same five parts; only c(s, s′) differs (lesson M3-T7).

Engineering implications and limitations

Choose the problem, then the algorithm

Most planning mistakes are not in the algorithm. They are in the problem: a diagonal that cuts a wall corner is legal on the graph and a collision in the world; a start cell inside the inflated band has no legal moves; a goal on a wall cell is not a node. Check that the start and the goal are nodes before searching, and say what the planner should do when they are not (lab M3-L3).

Resolution is a performance and a safety parameter

Halving the cell size multiplies the number of states by four and the search time by about four or more. It also changes the inflation arithmetic and which doors exist at all. Most robots plan on a 0.05 to 0.1 m grid and accept the cost, or plan on a coarse grid and refine the path locally (module M5).

The graph does not know the robot turns slowly

A grid planner treats a turn of 90° as free. The path it returns is a list of cells, not a drivable trajectory. The robot's motion model, from module M1, comes back when the path is smoothed and followed (module M5), and in module M4 when the heading becomes part of the state.

Implicit and explicit graphs

A grid is implicit: neighbours come from arithmetic. A roadmap of lanes (lesson M2-T5) is explicit: nodes and edges are stored, and the search is the same. The planners in this module work on both.

Common misconceptions

“8-connected search finds the shortest path in the plane.”

It finds the shortest path on the grid graph, which can be up to 8% longer than the true shortest path. A truly shortest path needs any-angle search (lesson M3-T5).

“A diagonal move is always allowed if the target cell is free.”

It is only safe if the two cells it squeezes between are free as well; otherwise the path passes through a wall corner. The corner rule is part of the problem definition (lab M3-L3).

“Zero-cost moves are harmless.”

They make cycles free, so a search can loop without progress, and they break guarantees that rely on positive costs. Give every move a small positive cost.

“A finer grid always gives a better plan.”

Beyond the accuracy of the map and the robot, extra cells only add search time. Resolution should match the narrowest passage and the localisation error.

Engineering takeaways

  1. A search problem is states, a start, actions, non-negative step costs and a goal test.
  2. A grid is a graph that is not stored: free cells are nodes and legal moves are edges.
  3. 4-connected paths can be 41% longer than a straight line, 8-connected paths at most 8.2% longer.
  4. The size of the search is the number of free cells, multiplied by headings if heading is part of the state.
  5. Corners, start cells, goal cells and resolution belong to the problem definition, not to the algorithm.

References and further reading

Standard textbooks for search problems and for planning on grids.

  • S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed., Pearson, 2020, chapter 3 (“Solving Problems by Searching”).
  • S. M. LaValle, Planning Algorithms, Cambridge University Press, 2006, chapters 2 and 5.
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, MIT Press, graph representations and shortest paths chapters.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

Question 1

How many edges does a 4-connected grid of 5 rows and 8 columns have, counting each undirected edge once?

Explanation

(8 − 1)·5 + (5 − 1)·8 = 35 + 32 = 67 edges, among 40 cells.

Question 2

Scout is 7 cells right and 3 cells up from its goal on an 8-connected grid. What is the cheapest path cost on an empty grid, and how does it compare with the straight line?

Explanation

Three diagonals and four straights: 3 × 1.4142 + 4 = 8.243. The straight line is √(49 + 9) = 7.616, so the grid path is about 8.2% longer.

Question 3

Why must step costs not be negative for the search methods of the next lessons?

Explanation

A negative cost lets a path get cheaper by going further, so a cell that was finished cheaply can later be reached more cheaply and the guarantees of Dijkstra and A* no longer hold.

What’s next

Next: the first algorithms, breadth-first search and Dijkstra, and why a priority queue is what makes the second one work.

Next lesson

M3-T2 — Breadth-First Search and Dijkstra

Trace Dijkstra with a priority queue and explain why it returns shortest paths on non-negative costs.

Nothing below is required to finish this lesson.