Making a robot collie

In the last post I built a sheepdog out of two rules from a paper. This time I wanted to see if a dog could work the rules out for itself. Not the usual way, with a pile of data and gradient descent: there’s no data (nobody has recorded what a perfect sheepdog does), and you can’t take a gradient through a flock of sheep. Real collies got good at it by the ones that could do the job having puppies. So I did that, in a simulation.

The dog is a small neural network. It gets told where things are and it says which way to run and how fast. It doesn’t know the two rules or what a pen is, and nobody tells it when it’s done well. Every generation I run a batch of them, keep the ones that got the most sheep in, mix their brains with a few random changes, and go again.

What the dog gets

The same body as the hand-written collie: it can’t run faster, it can’t turn faster (about a third of a turn a second), and it can’t get closer than two sheep-widths to a sheep. Those are done by the world. Everything else it has to learn from what it can see, which is seventeen numbers, all measured from where it’s standing.

Those go through ten neurons and come out as a direction and a speed. Two hundred weights, and the weights are the whole dog.

// 17 inputs → 10 hidden → 3 outputs.
h = tanh(W1 · inputs);
[dx, dy, speed] = W2 · [h, 1];
run(normalise(dx, dy), sigmoid(speed));

A dog’s score on a flock is sheep penned, plus a bonus for finishing quickly, plus a bit for how close the loose ones got, so that early on, when nobody gets any in, the dogs that at least push the flock the right way come out ahead. Every generation gets fresh flocks, the same ones for every dog.

Basic evolution

Thirty-two dogs with random brains (sixteen on a phone, which has to do all of this itself), evolved in your browser. Pick how many generations, press Evolve, and it runs them and stops. The field shows the best dog of the latest generation on a fixed flock; the chart is the best score and the batch average, and 1 is every sheep in.

The first few generations are the good bit. Dogs run in circles, sit in a corner, or push the flock the wrong way. Then one of them gets behind the flock by accident, the score jumps, and the batch fills up with its descendants.

Fifty generations usually gets you a dog that pens the lot. Start again gives you a new batch, and they don’t all find the same trick.

The fastest dog found

The best one I got, evolved properly on a machine: three batches of forty-eight, a hundred and fifty generations, finalists re-tested on thirty flocks none of them had seen. The buttons are the robot collie, the paper’s two-rule dog exactly as published, and you.

Over sixty fresh flocks it penned the lot every time, median 10.5 seconds and worst 14.5, against 16.1 and 32.3 for the paper’s dog and 12.5 and 17.6 for the collie I wrote by hand last time. (Sixty flocks flatters it a little: on four hundred more it lost one and took over twenty seconds on three, so call it one in a hundred that goes wrong.) It stays behind the flock, runs flat out and never fetches a straggler. On this field, pushing from behind in line with the pen is enough.

Away from home

The same dog on the two harder fields from last time, against my hand-written collie (the one with flanking and the third rule, not the paper’s dog). I’ve taken the old ewes out of the awkward flock for this post: they’re a party trick for a dog with a rule for them. So the first flock has leaders, loners and flighty sheep, and the second field has the pond, the wall and the trees.

Forty-one full pens out of sixty on the awkward flock, and what beats it is the leader: it takes a few sheep off, and this dog never goes after anyone. The obstacle field it mostly copes with, 55 out of 60, because the sheep flow round the pond and the wall on their own and a dog pushing from behind gets carried round with them. When it fails there, it’s pressed against the wall with the flock on the other side, which is what the paper’s dog did with the pond last time.

Training it on the harder fields

The fix is the one that made real collies: put the harder fields in the training. This dog was evolved on the awkward flock and the obstacle field, turn and turn about, two hundred generations, and never saw the open field. Then the farm, which neither dog has seen: sixty awkward sheep and all the obstacles. The buttons are the retrained dog (“farm dog”), the open-field dog, my collie and you.

On the obstacle field it’s as good as the collie now: sixty out of sixty. On the awkward flock it goes from forty-one to fifty-six, a couple of seconds behind the collie. The farm it gets thirty-six times out of sixty, with fifty of the sixty sheep in on average, where the open-field dog managed nine. Not the collie, but a working dog.

What it’s thinking

The paper’s dog tells you what it’s doing: the status line says COLLECT or DRIVE. The robot collie doesn’t have those words, it has ten neurons and a direction coming out. So this shows you the lot while it runs: what it can see, the ten neurons, and the direction and speed it chose. The line under the field is my attempt to read it in the paper’s terms. If the direction it picked points at the spot the paper’s dog would run to for COLLECT, it says COLLECT; for DRIVE, DRIVE; and if it’s going somewhere the paper’s dog wouldn’t, neither.

A third of the time it isn’t doing either of the paper’s rules. It reads as DRIVE and COLLECT about a third of the time each, and the rest it’s going wide round the side of the flock, which is how it gets behind them without cutting across the front. Tick “workings” and you can see it: C and D are the two spots the paper’s dog would be running to, and the white line is where this dog is going.

The neurons are worth watching too. Three of the ten sit pinned at 1 or −1 the whole run. The heading mostly comes from h7, which has the biggest weights on the output, and if you watch it against “nearest d” you can more or less see the rule: keep the nearest sheep at the distance it likes, and go.

The numbers

Everything here is from the script in the repo, on the same code as the demos, with seeded flocks. A score over 2 is every sheep in and fast.

Three batches of forty-eight on the open field. One had a dog that penned a whole flock by generation 2, one by 17, and one not until 114. That’s what this kind of evolution is like: once a batch has one dog that gets behind the flock, its descendants take over in a few generations, and until then nothing much happens.

”Behind the flock” is the share of the run spent on the far side of the flock from the pen; “near a sheep” is the share within three sheep-widths of one. The robot collie is fastest on the median and on the worst case.

Switching off one thing it can see at a time, and re-running it on thirty flocks, says the same thing:

Switch off where the pen is, the furthest sheep, how spread out the flock is, or how fast anything is moving, and it still pens thirty out of thirty. Switch off how far the nearest sheep is and it’s useless. (The obstacle input reads a constant on a field with no obstacles, and the dog uses it as a second bias.) So on the open field this is a one-input dog: keep the nearest sheep at the distance it likes and run. The pen is dead weight, because on this field the pen is always to the right.

The retrained dog is a different animal: it’s useless without the nearest sheep’s distance, like the first, but also without the flock centre or the pen, and it drops a fair bit without the two speed inputs. What it still doesn’t use is the furthest sheep, which is the paper’s collect rule, or the obstacle inputs. It gets round the pond the way the first dog does, by following the sheep round.

The paper’s dog reads as one of its own two rules 99% of the time, which is the check that the reading works. The retrained robot is “neither” about half the time on both its fields. It isn’t doing the paper’s job in the paper’s order; the two rules describe about half of what it does.

How to make it the best dog

Everything up to here was the first go. Then I gave myself an hour of compute to make the best dog I could without changing what a dog is. It got two more things to see (the sheep left furthest behind, and which way the flock is drifting), it was trained on all four fields at once, and it started from the retrained dog rather than from scratch, with the new inputs wired to zero so it began exactly as good as it was.

Here it is thinking next to one of the earlier dogs, on the same flock. The menus change the field and the other dog.

The fastest dog on the open field and the obstacle field, level with my collie on the awkward flock, and on the farm it pens fifty out of sixty to the collie’s sixty, at about the same speed. It ignores both of the new inputs. Switch off the sheep-left-behind and it does fractionally better. Everything it gained came from training on all four fields and starting from a dog that worked. It’s also the first dog you can’t break by taking one input away: every earlier dog collapsed without the nearest sheep’s distance, and this one only dips, whichever one you remove.

What I took from it

Five dogs, in the order they turned up:

• The paper’s dog. Two rules, written down by people who watched a real one. Slowest of the lot, and the only one you can explain at a sheepdog show.
• My collie. The paper’s dog plus flanking, manners and a rule for obstacles, written by hand last time. Still the only dog that pens everything, everywhere.
• The open-field dog. Evolved on one field. Faster than either hand-written dog there, uses one input, and falls apart anywhere else.
• The retrained dog. Evolved on the awkward flock and the obstacle field. A working dog on both, and a long way off on the farm.
• The best dog. The retrained dog carried on across all four fields at once. As good as my collie or better on three of them, and it ignored the two extra inputs I gave it.

The lesson is the same one three times: it learns the fields it’s given, and the way to get a general dog is to give it general fields, not cleverer eyes.

The sheep, the fields and the hand-written collie are from the last post, which has the sources. The robot collie is a plain neural network evolved with a genetic algorithm (tournament selection, uniform crossover, Gaussian mutation, two elites), the sort of thing in Floreano D. & Mattiussi C. (2008), Bio-Inspired Artificial Intelligence, MIT Press. Robot collie code · experiment script.