Project: mission control

A mission read from a file into a circular queue, moves looked up in a dictionary, position tracked as a vector, and an undo stack to bring the robot home.

A3.9Data structuresA level30 min

Covers OCR H446 1.4.2 Data Structures · AQA 7517 4.2.1.1 Data structures · AQA 7517 4.2.1.4 Abstract data types/data structures · Eduqas A500QS 1.1 Data structures

Print it: worksheet (PDF) · answers (PDF) · as a web page

A real robot is sent a mission, carries it out step by step, keeps track of where it is, and must be able to abandon the mission and come home safely if something goes wrong. Every part of that is a data structure from this module. In this project BugBot reads its mission from a file into a queue, looks up each move in a dictionary, tracks its position as a vector, and records every move on a stack so an abort can undo them.

The brief

The robot reads mission.txt, one command per line, into a circular queue. It takes commands off the front in order. For each move it looks up the move's direction vector in a dictionary, drives it, adds it to its position vector, and pushes the move onto a stack. When it reaches abort, it reports how many commands were never run, then pops its moves one at a time and reverses each, until it is back where it started.

The mission file

forward,30
right,30
forward,25
abort,0
left,20
forward,10

Plan

Choosing the structure is the design decision; the code follows from it. Notice what would go wrong with the wrong choice: undo the moves from a queue and the robot reverses them in the order it made them. Here the reversed moves still add up to home, because adding vectors in a different order gives the same total, but the robot comes back by a different path, one nobody has checked is clear. The stack sends it back exactly the way it came.

Step 1: the mission into a queue

The queue is a fixed array with front, rear and count, exactly as in lesson A3.3. Everything is loaded before the robot moves, so a mission that does not fit is found before anything happens.

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

SIZE = 8
queue = [None] * SIZE
front, rear, count = 0, -1, 0

def enqueue(item):
    global rear, count
    if count == SIZE:
        return False
    rear = (rear + 1) % SIZE
    queue[rear] = item
    count = count + 1
    return True

with open("mission.txt") as f:
    for line in f.read().splitlines():
        word, cm = line.split(",")
        if not enqueue((word, int(cm))):
            print("mission too long: dropped", line)

print(count, "commands queued, front =", front, "rear =", rear)
print(queue)

Run this in the simulator

Step 2: moves as vectors

Each direction word maps to a unit vector: [1, 0] is right, [0, 1] is forward. A move of cm centimetres is that vector scaled by cm, and the new position is the old position plus the move. Undoing a move is adding the same vector scaled by -1.

DIRECTION = {"forward": [0, 1], "backward": [0, -1], "left": [-1, 0], "right": [1, 0]}

def add(a, b):
    return [a[0] + b[0], a[1] + b[1]]

def scale(k, a):
    return [k * a[0], k * a[1]]

pos = [0, 0]
for word, cm in [("forward", 30), ("right", 30), ("backward", 10)]:
    step = scale(cm, DIRECTION[word])
    pos = add(pos, step)
    print(word, cm, "is the vector", step, "so the robot is at", pos)
print("undo the last move:", add(pos, scale(-10, DIRECTION["backward"])))

Run this in the simulator

The program never asks the robot where it is. It works its position out from what it was told to do, which is called dead reckoning. On the real mat the wheels slip a little, so the worked-out position and the true one drift apart over a long mission (lesson 2.5 of the robotics course measures exactly that).

Step 3: put it together

Combine the queue, the dictionary, the vectors and the stack from lesson A3.2. Test the parts separately first: print the queue after loading, and print the stack after each push. Then edit mission.txt above and run again with a mission of your own, including one longer than 8 commands to see what the queue does.

Task: mission control

Build the program from the brief. slide(v) is given: it drives the displacement vector v = [x, y] in cm (x to the right, y forward). Use fixed-size arrays with pointers for the queue and the stack, not the list's own append, pop or insert, and do not call position().

1. Read every line of mission.txt (<word>,<cm>, where <word> is forward, backward, left, right or abort, and <cm> is a whole number) into a circular queue of size 8, wrapping the pointers with %, before the robot moves.
2. Keep a stack of size 8 with a top pointer, a dictionary DIRECTION from each direction word to its unit vector, and a position vector pos starting at [0, 0]. Do not compare the word with each direction name.
3. While the queue is not empty, dequeue a command:
   • A move: drive it with slide, push (word, cm), add the move to pos, and print at <pos>, for example at [0, 30].
   • abort: print abort: <n> commands left in the queue, where n is the number still in the queue. Then, until the stack is empty, pop a move, drive it in reverse, update pos, and print undo <word> <cm>, for example undo forward 25. Then stop taking commands.
4. Finally print home at <pos>.

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

def slide(v):
    """Drive by the displacement vector v = [x, y] in cm: x is sideways (right positive), y is forward."""
    if v[0] > 0:
        right(50, distance=v[0])
    if v[0] < 0:
        left(50, distance=-v[0])
    if v[1] > 0:
        forward(50, distance=v[1])
    if v[1] < 0:
        backward(50, distance=-v[1])

Challenges

1. Give each command a priority in the file, so an abort jumps the queue as soon as it is read. Which kind of queue do you need?
2. Store every position the robot reaches in a dictionary from (x, y) tuple to the step number, and report if the mission ever visits the same place twice.
3. The stack and queue are both size 8. What should happen if a mission has 9 moves before its abort? Change the program so it refuses to start rather than failing half way.