Project: the mission robot

Validate a mission with a regular expression, carry it out with a Mealy machine, and report with sets.

A6.10Theory of computationA level30 min

This project puts the module to work on one robot. BugBot is given a mission: a list of marker ids to visit in order, typed in as text. The robot has to check the mission is well formed, carry it out with a finite state machine, and report what it saw. Each part uses an idea from this module, and the last part of the lesson asks where the limits of computation come in.

The mission language

A mission is one or more marker ids separated by commas, with no spaces: 3,8,5 or 12. As BNF:

<mission> ::= <id> | <id>,<mission>
<id>      ::= <digit> | <digit><id>
<digit>   ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Both rules recurse only at the end, never in the middle, so nothing has to be counted or matched up. That means the language is regular, and a regular expression describes it:

(0|1|2|3|4|5|6|7|8|9)+(,(0|1|2|3|4|5|6|7|8|9)+)*

In Python, with the shorthand for a digit, that is [0-9]+(,[0-9]+)*. The check must use re.fullmatch, so that a valid start such as 3,8 in 3,8x is not enough.

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

import re

MISSION = r"[0-9]+(,[0-9]+)*"
for text in ["3,8,5", "12", "3,,8", "3,8,", ",3", "3 8"]:
    print(repr(text), "valid" if re.fullmatch(MISSION, text) else "invalid")

Run this in the simulator

If missions could contain bracketed sub-missions nested inside each other, a regex would no longer be enough and you would need a grammar and a recursive checker, as in lesson A6.5.

The controller

Each marker is visited by the Mealy machine from lesson A6.2. Its input alphabet is none, far and near, its outputs are spin, drive and halt, and STOP ends the visit.

For a mission with several markers, the machine is simply restarted in SEARCH for each one. The sensing function takes the marker id as a parameter, so the same table serves every marker.

What the robot saw

While it spins and drives, the camera sees other markers too. Collect every id it sees into a set: a marker seen twenty times is still one member. At the end, the markers that were seen but were not part of the mission are a set difference:

seen \ mission

In Python, with seen and mission as sets of whole numbers, that is seen - mission. A report like this is how a patrolling robot would tell you about something new in the room.

Where the limits are

• Tractability. The mission gives the order, so the robot just follows it. If instead the robot were told "visit these ten markers in whatever order is shortest", it would face the travelling salesman problem from lesson A6.7: intractable, so a real robot would use a heuristic such as nearest neighbour.
• Halting. Suppose the mission names a marker that is not on the mat. The SEARCH state spins forever, because no input near or far ever arrives. No checker could, in general, spot every such problem in any program in advance. What a robot can do is what the simulator does: give each state a time limit and treat running out as a failure.

Task: the mission

Carry out a mission typed in by the user.

• Ask for the mission with input("Mission? "). A valid mission matches [0-9]+(,[0-9]+)* exactly (check with re.fullmatch). While it is not valid, print invalid mission and ask again. The input box holds 3,,8 then 3,8,5, so invalid mission is printed exactly once.
• For each id in the mission, in order, run the Mealy machine with a table dictionary like the one in lesson A6.2: keys (state, input), values (next_state, output), start state "SEARCH", stopping at "STOP". Each tick: sense, look up, act, change state, wait(0.1). When it reaches STOP, print reached and the id, for example reached 3.
• sense(target) and act(output, steer) are written for you. sense also returns, as a third value, the list of every marker id in view on that tick.
• Keep a set of every marker id seen during the whole run. At the end, print seen but not in mission: followed by the ids in the set difference, ascending, separated by single spaces, or none if it is empty.
• Do not touch any marker.

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

import re

def bearing_of(cx):
    return (cx - 160) * 120 / 320      # pixels to degrees

def sense(target):
    tags = apriltags()
    ids = [t[0] for t in tags]
    mine = [t for t in tags if t[0] == target]
    if not mine:
        return "none", 0, ids
    if mine[0][3] <= 15:
        return "near", 0, ids
    return "far", bearing_of(mine[0][1]), ids

def act(output, steer):
    if output == "spin":
        turn_right(40)
    elif output == "drive":
        drive(60, 0, steer * 3)
    elif output == "halt":
        stop()

set_cv("apriltag")

Challenges

1. Give every state a time limit: if SEARCH lasts more than 10 seconds, print marker <id> not found and move on to the next id.
2. Reject missions that name the same marker twice. Can a regular expression check that? What can?
3. Let the user type nearest instead of a list, and visit every marker the robot has seen in nearest neighbour order.