Abstraction and models

Representational abstraction, generalisation, problem reduction, and a grid model of the mat that differs from reality.

A2.4Recursion and computational thinkingA level20 min

At GCSE, abstraction meant removing unnecessary detail (F4.4). At A level you need to say more precisely what kind of abstraction is being used, why it is needed, and where the model and reality part company. This lesson is about abstraction as a way of thinking, and about building an abstract model of the robot's world.

What abstraction is, and why it is needed

Abstraction is removing the details of a problem that do not matter for the purpose in hand, so that what is left can be understood and solved. The details that are kept depend on the purpose: a map for a walker keeps footpaths and hills, a map for a train driver keeps signals and gradients.

It is needed because:

• real situations have far too much detail to reason about, or to store and process;
• a simpler model can be solved with an algorithm, where the full situation cannot;
• the same model can be reused for many situations that share the same important features.

Representational abstraction

A representational abstraction is a representation arrived at by removing unnecessary details. The London Underground map is the classic example: it keeps which stations are on which lines and in what order, and throws away distances, bends and the streets above. It is useless for walking and ideal for planning a journey by train.

The robot's mat can be represented the same way. The real mat has obstacles of any shape at any position. A grid model splits the mat into cells and records only whether each cell is blocked:

The model is small (25 true or false values), it is easy to search, and the robot's route planning can treat each free cell as a place to stand. In the task you will build it.

Abstraction and reality

A model is only useful if its differences from reality do not matter for the purpose. Look at the post in the figure. It is 8 cm wide and stands between cell centres, so no cell centre lies inside it. The grid model says every cell around it is free, and a robot planning from the model could drive straight into it.

def corridor(cell_cm):
    """A 100 cm corridor with a thin post from 41 to 44 cm, sampled at the centre of each cell."""
    cells = ""
    centre = cell_cm / 2
    while centre < 100:
        cells = cells + ("#" if 41 <= centre <= 44 else ".")
        centre = centre + cell_cm
    return cells

for size in [20, 10, 5]:
    print(str(size).rjust(2), "cm cells:", corridor(size))

Run this in the simulator

With 20 cm or 10 cm cells the post vanishes; with 5 cm cells it appears. A finer model is closer to reality but bigger and slower to search. Choosing the level of detail is a design decision, and the question to ask is always: what could go wrong because of what this model leaves out? Common answers are a lost obstacle, a rounded measurement, a straight line where the robot really drifts, or a delay that the model assumes is zero.

Abstraction by generalisation

Abstraction by generalisation (or categorisation) groups things by what they have in common, giving a hierarchy of "is a kind of" relationships. A time-of-flight sensor is a kind of distance sensor, which is a kind of sensor. Anything true of every sensor (it has a reading, it can fail) is written once at the top, and only the differences are added lower down. You met the same idea in object-oriented programming, where a subclass inherits from a more general class.

kinds = {
    "sensor": None,
    "distance sensor": "sensor",
    "time-of-flight sensor": "distance sensor",
    "ultrasonic sensor": "distance sensor",
    "camera": "sensor",
}

def chain(kind):
    """Follow the 'is a kind of' links to the top of the hierarchy."""
    names = []
    while kind is not None:
        names.append(kind)
        kind = kinds[kind]
    return " is a kind of ".join(names)

print(chain("time-of-flight sensor"))
print(chain("camera"))

Run this in the simulator

Problem abstraction and reduction

Problem abstraction, or reduction, removes details until the problem is represented in a way that is possible to solve, because it has become a problem that has already been solved.

In 1736 Euler was asked whether you could walk round the city of Königsberg crossing each of its seven bridges exactly once. He removed everything except the land masses (as points) and the bridges (as lines joining them). The question became one about the graph, which could be answered by counting how many lines meet at each point: the walk was impossible.

The robot does the same. "Get across this cluttered room to the charger" becomes "find a path from one free cell to another in a grid", which is a graph search, and graph searches such as breadth-first search are solved problems you will meet in module A4. Once a problem has been reduced, the known algorithm does the rest.

To devise an abstract model for a situation:

1. state the purpose: what question must the model answer?
2. list what matters for that purpose, and leave out the rest;
3. choose a representation: a grid, a graph, a table of records, a set of equations;
4. check the differences from reality, and whether any of them could make the answer wrong.

Task: a grid model of the mat

The mat is 100 cm by 100 cm, with (0, 0) in the bottom left corner. The four obstacles in the figure are these rectangles, each (x, y, width, height) in cm, where (x, y) is the rectangle's bottom left corner:

(25, 64, 40, 10), (72, 5, 8, 50), (5, 22, 30, 16) and (84, 40, 12, 60)

Build the 5 by 5 grid model with 20 cm cells.

• Write a function blocked(cx, cy) that returns True if the point (cx, cy) is inside any rectangle (a point exactly on an edge counts as inside) and False otherwise.
• A cell is blocked if its centre is blocked. Row 0 is the top row of the mat and column 0 the left, so the cell in row 0, column 0 has its centre at (10, 90).
• Print the five rows, row 0 first, each as a string of five characters: # for a blocked cell and . for a free one.
• Then print blocked: <n>, the number of blocked cells.

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

obstacles = [(25, 64, 40, 10), (72, 5, 8, 50), (5, 22, 30, 16), (84, 40, 12, 60)]

def blocked(cx, cy):
    return False

Challenges

1. Change your model to 10 cm cells (10 rows of 10). Does the post appear now? What has it cost?
2. Instead of testing only the centre, mark a cell blocked if any part of a rectangle overlaps it. Which model is safer for the robot, and which wastes more space?
3. Draw an abstract model of your school's corridors that a delivery robot could plan with. What have you left out, and could any of it matter?