Evolve a Cleaning Robot
Developed by Ben Duncan
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.
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.
Simulate a single genome in a random environment.
Control the evolution of the algorithm.
|Gen #||Mean Fitness||Best Fitness|
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:
- Create a population of random strategies
Get the fitness of each genomes by averaging 50 runs of the following:
- Build a world with walls and random litter
- Place Robbie in the world with a genome
- Reward and punish Robbie according to its performance
- Select the fittest individuals for reproduction using tournament selection
- Breed children using single-point crossover
- Randomly change some genes using uniform mutation
- Repeat steps 2 through 5, each repetition corresponding to a generation