In this subunit, I'm going to go through
a detailed example of a simple genetic algorithm that evolves
control programs for virtual robots.
Well, our virtual robot is called "Robby". He's a very simple robot
who lives in a simulated world.
I described him first in my book, "Complexity: A Guided Tour",
and his job is to go around, collecting empty soda cans.
Robbie was inspired by a real robot, called "Herbert",
which operated in the 1980's, in the MIT Artificial Intelligence Lab.
It went around the lab, on its wheels, going into the different offices,
and collecting empty soda cans, and taking them to the recycle bin.
Herbert was the work of Jonathan Connell, a graduate student at MIT working with
Rod Brooks and Peter Ning, and was a very impressive robot
that used only very simple algorithms to control its behaviour.
Our version of "Herbert" is called "Robby", and he's a virtual robot
who lives this simulated world consists of a 10 by 10 grid of squares
You can think of the squares as sort of "virtual offices",
and each office is either empty or it contains and empty soda can.
So here's an example of a soda can.
And Robby's job is to move around this world, collecting the empty soda cans.
So we have to give Robby a program that tells him what to do at each step.
I could program that myself, but instead I'm going to use a
genetic algorithm to evolve programs to do this task.
So first I need to tell you what Robby can see and what he can do.
He's a very simple robot, and he has very bad vision, so the only thing
he can see are the contents of his own square
and the squares to the north, south east and west.
So his current site, north south, east and west.
In his current state, his current office or room is empty.
To the north there is a wall, to the west there is a wall,
to the south there is an empty square and to the east there is a can.
So that's all he can see.
He uses what he can see to decide which action to take at each time step.
And he has seven possible actions: he can move to the north,
move to the south, move to the east,
move to the west, that's all moving one square.
He can make a random move: choose a random direction to move in.
He can stay where he is and do nothing, or he can try to pick up a can.
And if he tries to pick up a can and there is a can there, he succeeds.
Or he can try to pick up a can mistakenly in an empty square.
And he has certain rewards and penalties that he gets for doing these things.
If he picks up a can, he gets 10 points, that's a good thing to do.
If he tries to pick up a can on an empty site, he gets minus one point,
and if he crashes into a wall, he gets minus five points.
And his overall score as he moves around is the
sum of the rewards and penalties that he gets.
The goal is to use a genetic algorithm to evolve a control program
that is a strategy for Robby.
So let me talk about what a "strategy" is.
The definition that I'm going to use is a set of rules that specifies an action
for every possible situation.
Where the possible situations are the inputs to Robby,
the possible inputs that he can see.
So let's make a list of possible situations that Robby can find himself in.
The possible situations would be what he sees
to the north, south, east, west, his current site.
And a strategy would be for each possible situation an action he would take.
So here's a possible situation-- maybe the simplest one--
everything is empty.
He's in an empty cell and cells in all directions are empty.
That's one possible situation. Here's another possible situation:
everything is empty except in his current site he has a can.
And we could go on and on listing possible situations.
And in a second, we'll figure out how many possible situations there are,
but just to make sure that you are getting all of this, let's stop for a quick quiz.
The quiz has two questions. The first says look at this situation,
and suppose that Robby has a score of zero so far,
and he takes some actions: move east, move east, pick up can,
move east, pick up can, move south.
So he takes those six actions, and you have to answer what his
situation is after those six actions, and what his score is.
And here's to remind you what the scoring process is.