Adam DiCarlo's Blog

Robby is a robot who wanders around a grid looking for empty soda cans to pick up. Robby has no memory. At any given time, all he knows is what’s in his current cell, and what’s in each of the adjacent cells to the north, south, east, and west.

Robby’s goal is to pick up as many of the soda cans—which are randomly distributed across a 10×10 grid—as possible, without bumping into the wall bordering the grid. His performance is evaluated by using rewards and punishments:

• +10 points for every soda can picked up
• −5 points for running into a wall
• −1 point for trying to pick up a can where there isn’t one

Robby’s strategy is a finite state machine which describes which action to take for each possible state he can find himself in. Each action is one of these:

• Move north
• Move west
• Move south
• Move east
• Move randomly
• Do nothing
• Try to pick up a soda can in current cell

What should Robby’s strategy be? I programmed three different versions of Robby:

1. Darwin Robby (genetic algorithm)
2. Smart Robby (genetic algorithm plus some extra logic which allows him to avoid punishments)
3. Intelligent Design Robby (hand-crafted strategy)

The genetic algorithms start with completely random genes (which are Robby’s strategy/FSM), and use selection of the fittest, mutation, and crossover to evolve this strategy over many generations.

This was an assignment for Melanie Mitchell’s Artificial Intelligence course at Portland State University.

Code on github.