A5.9 Project: plan the route, then drive it worksheet

Choose and justify a route planner, build the mat's graph, find the shortest route with Dijkstra's algorithm and drive it.

Questions 5 marks in all

[1 mark]On the project's map, why would breadth-first search choose the wrong route from S to G?

AIt finds the route with the fewest roads, which is not the shortest distance when roads have different lengths
BIt cannot search undirected graphs
CIt always walks into dead ends
DIt needs a heuristic

[1 mark]Why can a greedy rule, always driving to the nearest next waypoint, fail?

AIt only looks one road ahead, so it can take a short road into a dead end
BIt is too slow on small maps
CIt always takes the longest road
DIt needs the roads sorted first

[1 mark]What is the length in cm of the shortest route from S to G on the project's map?

[1 mark]What does this print? It builds part of the project's graph.

import math
WAYPOINTS = {"S": (10, 10), "C": (35, 10), "D": (35, 35)}
ROADS = [("S", "C"), ("C", "D")]
graph = {w: {} for w in WAYPOINTS}
for a, b in ROADS:
    graph[a][b] = graph[b][a] = math.dist(WAYPOINTS[a], WAYPOINTS[b])
print(graph["C"])

[1 mark]Trying every possible order of visiting n waypoints grows as n!. Which statement is right?

AIt quickly becomes impractical, while Dijkstra's algorithm stays polynomial
BIt is O(n²), like bubble sort
CIt is O(log n)
DIt is faster than Dijkstra's algorithm for large n

The task: plan the route, then drive it

The starter has the map and the go_to helper. Write the rest: - Build an undirected weighted graph from WAYPOINTS and ROADS, where each road's weight is its length in cm (use math.dist; do not type the lengths). - Write dijkstra(graph, start) and use it to find the shortest route from S to G. The program must find the route: do not type it. - Print route: <waypoints joined with ->, such as route: S-X-Y-G, and length: <n> cm, with n a whole number. - Drive the route by calling go_to for each waypoint after S, in order. Stay on the roads: do not go near waypoints that are not on your route, and do not touch a wall. - When the robot reaches G, turn the LED green.

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

import math
import heapq

WAYPOINTS = {"S": (10, 10), "A": (10, 90), "B": (90, 90), "C": (35, 10), "D": (35, 35),
             "E": (65, 35), "F": (65, 60), "G": (90, 60), "J": (80, 35)}
ROADS = [("S", "A"), ("A", "B"), ("B", "G"), ("S", "C"), ("C", "D"),
         ("D", "E"), ("E", "F"), ("F", "G"), ("E", "J")]
START = WAYPOINTS["S"]              # the robot starts at S

def go_to(x, y):
    """Drive to the mat point (x, y): along y, then along x, twice so the second pass corrects any drift."""
    for attempt in range(2):
        px, py = position()
        dy = y - (START[1] + py)
        if dy > 1:
            forward(60, distance=dy)
        elif dy < -1:
            backward(60, distance=-dy)
        px, py = position()
        dx = x - (START[0] + px)
        if dx > 1:
            right(60, distance=dx)
        elif dx < -1:
            left(60, distance=-dx)

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

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

Challenges

The road from E to F is closed for repairs. Remove it from ROADS and plan again. What route and length do you get, and would the robot hit a wall driving it?

Add A\* with straight-line distance as the heuristic, and count how many waypoints each algorithm expands before G.

Add a second destination and use the distances from one run of dijkstra to decide which destination is nearer, without planning twice.

What this lesson is about

Questions 5 marks in all

The task: plan the route, then drive it

Challenges