Meteor Shower

Problem Description

The goal of this project was to design an environment where little red squares (envisioned as spaceships in space) learn to avoid little grey squares (envisioned as meteors). Below is a demonstration of the best individual after 20 generations of training:

Below are snapshots of the whole population every fifth generation as well as the best individual of that generation:

Generation 0

Generation 5

Generation 10

Generation 15

Generation 20

How It Works

The red squares die if they are hit by one of the grey squares. However, the red squares can “see” a certain distance around themselves:

If a grey square overlaps with one of the blue points, the red square will know that and will be able to decide where to move based on that. The red square will also know if one of the blue points is outside the bounds of the map. To be able to make decisions the red square is equipped with a neural network that takes the state of the blue points as inputs and outputs a decision:

The outputs can either be -1, 0 or 1. The numbers correspond to whether to decrease, leave unchanged or increase a coordinate. Output 1 controls the x-coordinate and output 2 the y-coordinate. If for example both outputs are ones, then the red square will move towards north east. The red squares are rewarded based on how long they survive. When all the red squares die, the current generation ends and the squares that survived the longest are chosen as parents for the next generation. The weights of the parents’ neural networks are combined to produce new networks for the next generation.

Over many generations the red squares evolve through the process of artificial natural selection to eventually avoid the grey squares. In the end they become much better than a human at achieving the given task.

By adjusting the reward function, network topology and the genetic algorithm, the squares can learn to solve other problems as well, such as chasing the grey squares (could be envisioned as food), navigating a track and many more.