Nearest neighbour

The simplest classifier, in a dozen lines.

8.3LearningRobot club20 min

The simplest classifier there is: keep every sample you recorded, and when you see something new, answer with the label of the sample it looks most like. No training. A dozen lines.

How alike are two views?

Two lists of 16 numbers. Subtract them column by column, square each difference so that negatives count too, and add up. Small total means alike. This is the four-sample dataset from lesson 8.2:

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

DATA = [
    ([54, 52, 51, 51, 51, 51, 52, 54, 54, 52, 51, 51, 51, 51, 52, 54], 'open'),
    ([16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16], 'wall-ahead'),
    ([36, 47, 46, 46, 46, 16, 16, 16, 36, 47, 46, 46, 46, 16, 16, 16], 'gap-left'),
    ([16, 16, 16, 46, 46, 46, 47, 36, 16, 16, 16, 46, 46, 46, 47, 36], 'gap-right'),
]

def difference(a, b):
    return sum((p - q) ** 2 for p, q in zip(a, b))

level = tof_grid()[16:32]
print("open vs wall-ahead:", difference(DATA[0][0], DATA[1][0]))
for feats, label in DATA:
    print("here vs", label, ":", difference(level, feats))

Run this in the simulator

zip(a, b) walks the two lists side by side. The robot is at the start, in open space, and the open sample is far and away the closest.

The classifier

Loop over the samples, keep the smallest difference, return its label:

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

def level_rows():
    # rows 2 and 3: the 16 readings that look straight ahead
    return tof_grid()[16:32]

def nearest(sample, data):
    # the label of the recorded sample most like this one (smallest sum of squared differences)
    best_label, best_d = None, 1e18
    for feats, label in data:
        d = sum((a - b) ** 2 for a, b in zip(feats, sample))
        if d < best_d:
            best_label, best_d = label, d
    return best_label
DATA = [
    ([54, 52, 51, 51, 51, 51, 52, 54, 54, 52, 51, 51, 51, 51, 52, 54], 'open'),
    ([16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16], 'wall-ahead'),
    ([36, 47, 46, 46, 46, 16, 16, 16, 36, 47, 46, 46, 46, 16, 16, 16], 'gap-left'),
    ([16, 16, 16, 46, 46, 46, 47, 36, 16, 16, 16, 46, 46, 46, 47, 36], 'gap-right'),
]

print("at the start:", nearest(level_rows(), DATA))
# drive forward at 60 (keeps going until the next command)
forward(60)
# do this 8 times (tick counts from 0)
for tick in range(8):
    # pause 0.5 s (the robot keeps doing what it was told)
    wait(0.5)
    # where am I? (cm from where I started)
    x, y = position()
    print("y =", round(y), "->", nearest(level_rows(), DATA))
# all motors off
stop()

Run this in the simulator

nearest is the whole model. It says open while the wall is far, then something else as the wall fills the view.

Where it goes wrong

Look at what it said around y = 25 to 30: gap-left, when the truth is a wall about 30 cm ahead. There is no sample for that. The wall-ahead sample was taken 15 cm from the wall, open 50 cm from it, and a view from in between is closer to gap-left than to either. Nearest neighbour can only answer with a label it has seen, from a place it has seen it.

The cure is not cleverer code, it is more data. Lesson 8.4 uses 34 samples, recorded from many places, and the same nearest function gets the in-between views right.

Task: nearest neighbour

Drive to (0, 15), (0, 40), (-38, 40) and (38, 40) in turn, and print spot <n>: <label> at each, using nearest against DATA.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()
# maths: atan2, hypot, sin, cos, radians
import math

def wrapped(h):
    return (h + 180) % 360 - 180

def go_to(x, y, speed=60):
    # where am I?
    px, py = position()
    a = math.radians(wrapped(math.degrees(math.atan2(x - px, y - py)) - heading()))
    # forward, sideways, rotation: -100 to 100 each, until the next command
    drive(speed * math.cos(a), speed * math.sin(a), wrapped(0 - heading()) * 3)

def near(x, y, cm=4):
    # where am I?
    px, py = position()
    return math.hypot(x - px, y - py) < cm

def drive_to(x, y):
    while not near(x, y):
        go_to(x, y)
        # pause 0.1 s (the robot keeps doing what it was told)
        wait(0.1)
    # all motors off
    stop()
    # pause 0.4 s (the robot keeps doing what it was told)
    wait(0.4)
def level_rows():
    # rows 2 and 3: the 16 readings that look straight ahead
    return tof_grid()[16:32]

def nearest(sample, data):
    # the label of the recorded sample most like this one (smallest sum of squared differences)
    best_label, best_d = None, 1e18
    for feats, label in data:
        d = sum((a - b) ** 2 for a, b in zip(feats, sample))
        if d < best_d:
            best_label, best_d = label, d
    return best_label
DATA = [
    ([54, 52, 51, 51, 51, 51, 52, 54, 54, 52, 51, 51, 51, 51, 52, 54], 'open'),
    ([16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16], 'wall-ahead'),
    ([36, 47, 46, 46, 46, 16, 16, 16, 36, 47, 46, 46, 46, 16, 16, 16], 'gap-left'),
    ([16, 16, 16, 46, 46, 46, 47, 36, 16, 16, 16, 46, 46, 46, 47, 36], 'gap-right'),
]
drive_to(0, 15)
print('spot 1:', nearest(level_rows(), DATA))

Challenges

Make nearest also return the smallest difference, and print unsure when it is above 2000.
Vote: find the three closest samples and answer with the label most of them have.
Add the samples you recorded in lesson 8.2's challenges and see whether the in-between views improve.