A4.8 Project: plan the route worksheet

Model the mat as a graph, find the shortest route with breadth-first search, and drive it.

Questions 5 marks in all

[1 mark]The robot must reach a square in the fewest moves, and every move costs the same. Why use breadth-first rather than depth-first search?

ABreadth-first finds a shortest path in an unweighted graph; depth-first may not
BDepth-first cannot find any route at all
CBreadth-first uses less memory
DDepth-first only works on trees

[1 mark]Why is an adjacency list a good choice for a grid of squares?

AEach square has at most four neighbours, so the graph is sparse
BA grid is a dense graph
CAn adjacency matrix cannot store a grid
DAdjacency lists answer 'are these two squares joined?' in one look

[1 mark]A 5 by 5 grid of squares has no blocked squares. Each square is joined to the squares directly above, below, left and right of it. How many edges does the graph have?

[1 mark]What does this program print?

from collections import deque
GRAPH = {"S": ["A", "B"], "A": ["S", "C"], "B": ["S", "D"], "C": ["A", "G"], "D": ["B"], "G": ["C"]}
parent = {"S": None}
queue = deque(["S"])
while queue:
    v = queue.popleft()
    for n in GRAPH[v]:
        if n not in parent:
            parent[n] = v
            queue.append(n)
route = []
v = "G"
while v is not None:
    route.append(v)
    v = parent[v]
print(" ".join(reversed(route)))

[1 mark]After a breadth-first search records each vertex's parent, what shape do the parent links form?

AA tree rooted at the start vertex
BA cycle through every vertex
CA complete graph
DA queue

The task: plan the route

GRID is the mat from the brief, with row 0 at the far end of the mat and column 0 on the left, and NAMES gives the letters in reading order. The robot starts in the centre of square A facing up the mat, and square centres are 25 cm apart. Build an adjacency list for the free squares. Print vertices: and the number of free squares, then edges: and the number of edges. Find the route from A to O with the fewest moves, using a breadth-first search that takes squares from the front of a queue with popleft() or pop(0). Print route: followed by the letters of the squares from A to O separated by single spaces, and then moves: followed by the number of moves. Finally drive the route square by square, without touching a blocked square, finishing in O.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

from collections import deque

GRID = ["....",
        ".##.",
        "..#.",
        "#..."]
NAMES = "ABCDEFGHIJKLMNOP"

graph = {}

Plan your program here, then type it in and press Run.

Do it on the robot
www.bugbotlab.com/learn/a4-8-project-plan-the-route/
The simulator checks it and tells you when it passes. Nothing to install, no account.

Challenges

Make the program print no route instead of crashing when the goal cannot be reached. Test it by blocking N and P.

Suppose a sideways move takes the robot twice as long as a forward or backward move. What does "shortest" mean now, and why can breadth-first search no longer find it?

Replace the breadth-first search with a depth-first one and print the route it finds. How many moves does it take, and does that depend on the order you try the neighbours in?

What this lesson is about

Questions 5 marks in all

The task: plan the route

Challenges