Software Architecture for Small Robots – Part 2

Doing more than one thing

In Part 1 our conclusion so far seemed to be a top-down approach of implementing a high-level behaviour:

1. Start with the algorithm as the main loop itself.
2. Fill in (implement) all the details, by adding low-level functions to be called from the main loop (these can in turn contain loops).
3. Don’t worry about the “sense (input) → plan → act (output)” separation: reading inputs and sending outputs to actuators can happen anywhere in the code.

It all looks manageable – as long as wall following is the only thing we want. But we’ll probably soon realise that we need quite a lot more, for example:

• Manual control override: stop current behaviour and use remote control
• Switch to a different behaviour (from remote control)
• Record inputs and outputs for debugging later
• Send telemetry for live debugging and monitoring
• Check battery voltage and interrupt current behaviour if power is low
• Other safety checks: stop when bumping into a wall, regardless of what the “clever bit” says!
• Make sounds or add a fancy light show (provide feedback about inputs and outputs)
• And probably even more…

In theory it would be possible to extend our wall follower program to take care of all this, carefully adding extra checks for overrides whenever we’re reading inputs or waiting for something, checks everywhere for collisions or battery voltage, and calling other functions to update lights, to make sounds, etc. But it would quickly become a mess, and the actual wall following logic would become unrecognisable.

Wall following and the above list of tasks are clearly different concerns, and should be kept separate – but we still want to run them together somehow.

If we go back to our initial idea with the single main loop, all this would fit in nicely: it’s just more things around that clever bit (e.g. wall following) in the middle.

while True:
    input = get_sensor_data()
    if check_remote_control_override():
        output = do_remote_control()
    else:
        output = do_the_clever_bit(input)
    # Run any other tasks here that might override output:
    # collision checks, battery voltage check, etc.
    # We can also run anything else that needs to react
    # to current inputs/outputs: update lights, make sounds,
    # log, send telemetry, etc.
    do_actions(output)

This shows why separating the three phases is useful: it’s clearly easy to extend or chain things together.

So it looks like we have two options, but both are bad in different ways:

1. Single main loop with neatly separated phases: makes it easy to add various things – but this structure looks completely unsuitable for implementing a high level behaviour like wall following which has its own loop(s).

2. Top-down: implement wall following, but eventually turn it into a mess by adding other concerns to it that don’t belong there.

Threads?

One of our problems is that we want to do additional things while we’re running our behaviour. They kind of look like activities or tasks that are running concurrently. Using threads sounds like an obvious choice for this.

But threads are better for something that’s truly asynchronous, running something that’s more independent with occasional synchronisation. For example when you’re dealing with the outside world or I/O, where you have to wait for something to happen or react to something.

But our case is different: we’re just looking for a way to organise our high level control code, we’re not dealing with I/O directly at this level. We need to do multiple things but we would very much like to keep it all synchronised all the time, executing everything at a predictable rate.

State machines?

Maybe this is the key: we don’t actually want to run a bunch of tasks independently of each other. What we want is the ability to execute our main behaviour step by step, one iteration at a time, so that we can also do other things before or after each step.

And of course we have a tool for that too: state machines.

We can turn our wall following logic into a state machine, implementing something like the above diagram: it’s really the same as our original example from the book, but in a different form. Here, states like “stopped” or “moving forward” and the transitions between them with conditions need to be made explicit.

The entry point has to be a single step(inputs) function that we can call from the main loop: it would check the inputs it’s given for any conditions to transition to a different state, and return the current output or command accordingly. So it can never wait for a condition on its own and can never block, it can only respond when “nudged” from the outside.

(And of course, this function will need to be able to remember the current state between calls, which you can implement using a closure or a class.)

Turning left and right can be implemented as more state machines or “sub-states”, in a similar way.

So we can imagine that the end result in Python would look significantly different from our initial example from the book. State machines can be a great tool to express certain kinds of logic. But code is usually not as nice as diagrams and in this case it feels like an extra burden to “translate” our nice original description to something that’s longer, harder to read and more fragmented.

Anything else?

Is there a better way? Some sort of magical tool or syntax that would allow us to:

• write code for a complex behaviour as a single block of code on its own, with its own loops
• and execute it one step at a time, from the middle of our main loop?

Coroutines!

What? What are these?!

From Wikipedia:

Coroutines are computer program components that generalize subroutines for non-preemptive multitasking, by allowing execution to be suspended and resumed. Coroutines are well-suited for implementing familiar program components such as cooperative tasks, exceptions, event loops, iterators, infinite lists and pipes.

From the Python docs:

Coroutines are a more generalized form of subroutines. Subroutines are entered at one point and exited at another point. Coroutines can be entered, exited, and resumed at many different points. They can be implemented with the async def statement. See also PEP 492.

These definitions might sound cryptic at first glance – but also promising: “cooperative tasks”, “event loops”, “…can be entered, exited and resumed…” Wikipedia also mentions that coroutines are useful to implement state machines!

The terminology in general (coroutines, generators, continuations) is somewhat confusing, especially in Python! Generators were originally very limited, and were later extended to be “simple coroutines” in PEP-342, then async/await appeared in PEP-492 – if you follow the documentation, you end up reading about async I/O exclusively, and it’s hard to see how that’s relevant to our problem at all!

Generators in Python

Let’s take a step back and look at what generators are in Python. Here is a very simple one:

def generate_behaviour():
    while True:
        yield "move forward"
        yield "turn left"
        yield "turn right"

We can use it like this:

behaviour = generate_behaviour()
while True:
    print(next(behaviour))

…which will output this infinite sequence:

move forward
turn left
turn right
move forward
turn left
turn right
move forward
.
.
.

We can even imagine calling this from our main loop, to make it generate outputs, like we expect from do_the_clever_bit(), but it doesn’t seem terribly useful: it would just mindlessly repeat the same sequence.

But generators have one more feature: they can also take inputs from the outside! So at the same time we ask for the next value, we can also give the generator some input. Instead of using next(generator), we have to use generator.send(input). The choice of different syntax might feel a bit arbitrary but suddenly this seems much more interesting! Our “generator” fits right in the middle!

behaviour = generate_behaviour()
behaviour.send(None)  # extra step needed to initialise
while True:
    input = get_sensor_data()
    # instead of do_the_clever_bit(input):
    output = behaviour.send(input)
    do_actions(output)

OK, but what are we doing with that input we’re sending? Let’s make our generator a bit more interesting:

def generate_behaviour():
    input = yield
    while True:
        if input['right_distance'] < 10:
            output = "turn left"
        elif input['left_distance'] < 10:
            output = "turn right"
        else:
            output = "move forward"
        input = yield output

Yet more variation on the syntax! It turns out that yield can be used both for input and output. It “returns” to the caller, suspending our execution, but when we’re called with send() the next time around, and we continue, it will give us the input!

At this point, generator seems like a terrible name, it really hides the potential. We can think about our behaviour as something that generates a series of outputs, but it’s much more than that. It’s really a function that can be run in steps: it can “return” something in the middle, and when it’s called again, it remembers its local state, and continues where it left off – but with new inputs. Let’s call this a coroutine – because that’s what it really is!

We can also see how this can be used for cooperative multitasking: we can imagine coroutines as tasks: we can have many of these, and we can switch between them, executing one bit from each at a time from a “scheduler” – but it’s the task that decides when to give back control and interrupt itself using yield.

This also shows how coroutines can also be used to implement state machines: in fact they can be equivalent! The state of a state machine can simply be a plain local variable in our coroutine function, or it can just be implicit from its control structure.

(And of course, coroutines are used extensively for asynchronous I/O, but that’s a use case that’s not obviously similar to what we needed.)

Another good thing about them is that they are cheap: switching between generators is much, much faster than the context switching between threads – and they are even faster than using classes with methods and storing state explicitly in attributes.

In the next part, we’ll go back to wall following and see how we can put everything together with coroutines!