Evolve a Cleaning Robot

A genetic algorithm optimizes a robot's strategy to clean a littered room. This is based on an example genetic algorithm posed in Dr. Melanie Mitchell's Complexity: A Guided Tour.

Design

The robot can see the 5 squares of its Von Neumann neighborhood, where there are 3 possible values for a square: Clean, Dirty, or a Wall. Because of this, there are 35 = 243 possible states. For each possible state there is a corresponding action (gene) in the strategy (genome).

Robbie looks up which strategy to follow in its genome, then is rewarded (if it picks up a can) or punished (if it hits a wall or bends over where there is no can) to determine the strategy's fitness. This is done on an entire population of strategies comprising the first generation, then the fittest individuals are selected using tournament selection.

Interactive Simulation

Click on Run Evolution below to start evolving an efficient genome for the robot.

Genetic Algorithm Controls

Gen #MeanBest

Individual Simulation

Generation: 0

Step: 0 Fitness: 0

Genetic Algorithm Overview

This is a relatively simple genetic algorithm that uses the basic steps of initialization, fitness determination, selection, crossover, and mutation to search a vast number of possible strategies for a decent learned strategy. In this case, we search 7243 ≅ 2.28×10205 possible genomes for a good strategy.

The basic structure of the algorithm is:

  1. Create a population of random strategies
  2. Get the fitness of each genomes by averaging 50 runs of the following:
    1. Build a world with walls and random litter
    2. Place Robbie in the world with a genome
    3. Reward and punish Robbie according to its performance
  3. Select the fittest individuals for reproduction using tournament selection
  4. Breed children using single-point crossover
  5. Randomly change some genes using uniform mutation
  6. Repeat steps 2 through 5, each repetition corresponding to a generation