Project: the robot's safety logic

From a rule table to a Karnaugh map, a simplified expression, a proof and a robot that stops for the right reasons.

A8.9Boolean algebra and logic circuitsA level30 min

This project takes a real design problem through every stage of the module: a rule written as a list of cases, a truth table, a Karnaugh map, a simplified expression, a proof that the simplification is right, and a robot that obeys the result. It is the process an engineer follows when a safety rule ends up as a few gates on a board, or as one line of firmware that has to be correct.

The brief

BugBot has four signals that affect whether it may drive:

The output is G, go: 1 means the motors may drive.

The safety officer did not write an expression. She wrote down, case by case, every situation in which driving is allowed:

1. Nothing is close, nothing has been knocked, the battery is fine, and it is not docking.
2. It is docking, and nothing else is happening.
3. It is docking with a low battery, and nothing is close or knocked.
4. It is docking with something close (the dock itself), and nothing knocked and the battery fine.
5. It is docking with something close and a low battery, and nothing knocked.

In every other situation, G is 0. This is a complete specification, but as a circuit it would be five four-input AND gates and a five-input OR gate, and as code it would be a line nobody could check by eye.

Stage 1: the truth table

With four inputs there are 2⁴ = 16 rows. Number each row as the binary number CKLD, so row 0 is 0000 and row 15 is 1111. Each of the five cases is exactly one row. For example case 1 is C = 0, K = 0, L = 0, D = 0, row 0, and case 2 is C = 0, K = 0, L = 0, D = 1, row 1.

Work out the other three yourself before reading on. The rows where G = 1 are given in the program below as GO_ROWS, so you can check.

GO_ROWS = [0, 1, 3, 9, 11]

print(" C K L D | G")
for n in range(16):
    c, k, l, d = n >> 3 & 1, n >> 2 & 1, n >> 1 & 1, n & 1
    g = 1 if n in GO_ROWS else 0
    print(f" {c} {k} {l} {d} | {g}")

Run this in the simulator

n >> 3 & 1 shifts the row number three places right and keeps the lowest bit: it picks out bit 3, which is C.

Stage 2: the sum of products

Straight from the table, with one minterm per row where G = 1:

G = (¬C ∧ ¬K ∧ ¬L ∧ ¬D) ∨ (¬C ∧ ¬K ∧ ¬L ∧ D) ∨ (¬C ∧ ¬K ∧ L ∧ D) ∨ (C ∧ ¬K ∧ ¬L ∧ D) ∨ (C ∧ ¬K ∧ L ∧ D)

This is correct and it is what you would build if you stopped here. Twenty literals.

Stage 3: the Karnaugh map

Lay the map out with CK down the side and LD across the top, both in Gray code order:

Take care filling it in. The row labelled 11 is C = 1, K = 1, so it holds rows 12 to 15 of the truth table, and the column labelled 10 is L = 1, D = 0. Row 11 of the truth table (1011) goes at CK = 10, LD = 11.

Then group. Look for the largest group first, and remember that the top and bottom rows of the map are neighbours. There are two groups; one of them has four cells and one has two.

Stage 4: simplify further, and prove it

Reading the groups gives a sum of two products. Both contain the same literal, so distribution can factor it out, and De Morgan may shorten what is left. Aim for an expression with at most six and, or and not operators in Python.

Then prove it. A simplification that has not been checked is a guess, and a wrong safety rule is worse than a slow one. Compare your expression against the original rows on all sixteen combinations, exactly as in lessons A8.3 and A8.6.

Stage 5: wire it to the robot

Finally the expression goes into the control loop. Each time round, read the sensors, turn each into a 0 or 1, and let G decide:

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

def go(c, k, l, d):
    return not c           # a placeholder: only looks at one input

docking = 0
for step in range(60):
    close = 1 if distance() < 20 else 0
    hit = 1 if bumped() else 0
    low = 1 if battery() < 20 else 0
    if go(close, hit, low, docking):
        forward(50)
        wait(0.1)
    else:
        stop()
        print("stopped")
        break

Run this in the simulator

On the mat the battery is fine, nothing is knocked and the robot is not docking, so the full rule and the placeholder happen to agree here and the robot stops at the wall. They do not agree in general: run the placeholder through your proof and see which rows it gets wrong. That is exactly why the proof comes before the drive.

Task: the robot's safety logic

The starter gives GO_ROWS, the truth table rows (numbered 8C + 4K + 2L + D) where G = 1, and draft(c, k, l, d), which takes four bits and returns 1 on those rows and 0 otherwise.

1. Write go(c, k, l, d), taking four bits, as a single return line using at most six of and, or and not in total. It may not use GO_ROWS or call draft. Any true result means drive.
2. Check go against draft on all sixteen combinations, treating a true result as 1 and a false one as 0, and print matches: True if they agree on every one, or matches: False if not.
3. Drive the robot. Set docking = 0. In a loop, read close (1 if distance() is under 20, else 0), hit (1 if bumped(), else 0) and low (1 if battery() is under 20, else 0), and call go(close, hit, low, docking). While it is true, drive forward. When it is false, stop, print one line in exactly the form stopped: C=1 K=0 L=0 D=0 using the values that stopped it, and end the loop. The robot must finish in the band before the wall without touching it.

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

GO_ROWS = [0, 1, 3, 9, 11]

def draft(c, k, l, d):
    return 1 if 8 * c + 4 * k + 2 * l + d in GO_ROWS else 0

def go(c, k, l, d):
    return 0

Challenges

1. Draw the circuit for your go expression using AND, OR and NOT gates. How many gates does it need, compared with the sum of products?
2. Redraw it using only NAND gates.
3. The safety officer adds a sixth case: docking with a low battery and something knocked, but nothing close, is allowed. Add the row, redo the map, and find the new simplest expression.