Coding Club: Genetic Algorithms

The robot problem discussed in this challenge is found in the book Complexity: A Guided Tour by Melanie Mitchell. It’s also included in her excellent introductory course on Complexity.

This coding club session will deal with us writing robot control software causing the robot to peruse a grid picking up virtual cans. We start out with a warmup exercise that encourages you to write whatever algorithm you can devise for your robot to pick up the most cans while avoiding the most peril. We then will use a genetic algorithmic approach to have the system optimize a best strategy through random cross breeding and mutation.

Warmup

You are tasked to write control software for a robot. this robot will operate in a two dimensional grid that has cans randomly interspersed throughout the grid. The robot is able to see the squares that are just north, south, east, and west of his current location as well as his current location.

For example, in the following grid, the robot ‘c’ can see the five shaded areas and see that there is a can just west of where it is.

robot vision

At any given iteration, the robot can perform only one of the following actions:

• try to pick up a can
• move in a random direction horizontally or vertically
• move west
• move east
• move north
• move south
• do nothing

You will score the performance of the robot with the following rules:

• 10 points for every can successfully picked up
• -1 point for trying to pick up a can that isn’t there
• -5 points for trying to move out of the grid (i.e. hitting a wall)

For your control program assume you are passed a two dimensional char array that has ‘’ for blank squares and ‘C’ for squares that have a can.

The problem

Now that you have a personalized strategy for the robot playing the game, let’s evolve an optimal strategy by creating a genetic algorithm.

The most difficult part of a genetic algorithm is transforming the parameters of your problem domain into the structures and forms of genetic algorithms. The basic steps of a genetically algorithmic iteration are:

• start with a population P of different randomly generated strategies. a strategy is defined as “for every possible scenario, pick what action should be taken”
• run each individual in P[] through your problem domain to see how it performs. it’s performance is measured by a “fitness function (fitnessFunction)
• keep a low percentage of your highest performing strategies unchanged for the next population (often between .1 and .2, but make it configurable). we’ll call this the elite population.
• fill up the rest of your population by crossbreeding and mutating based on the current top performers.
• to crossbreed, take the top x performers of this iteration and breed them together two at a time. for each breeding, pick a random location to split the scenario parameters taking the first part of the split from one partner and the second part of the split from the other partner to produce a child. keep doing this until you are at max population.
• to mutate, take the crossbred population and iterate through each scenario parameter testing it for a low chance of random mutation (usually between .005 and .01 but make it configurable)
• once the population is full from cross breeding and mutation, run the new strategies against the problem again and keep iterating. keep iterating until you have performed a configurable amount of iterations or until you have evolved the optimal strategy.

Hints for setting up the problem

• focus first on what information you have at each iteration. in our case, we can see 5 squares (north, south, east, west, and current) and each square has 3 different possibilities of what it can contain (can, empty, wall). this means that there are 3^5=243 different possible scenarios you can find yourself in at any given iteration. your solution should have a way to account for all of these scenarios:

numbered scenarios

Think about what structure you would use to store these 243 different scenarios and the actions that you will perform?

• assuming a population of 20, once you have the 243 scenarios defined, create 20 different strategies by randomly selecting what action you would take for each of the 243 different scenarios.

A solution

The simplest way to represent the data is to have an int array of size 243 where the index into the array corresponds with a specific scenario and the value at that index corresponds to an action.

First, let’s create an action lookup by assigning a number to each of the different actions:

• 0 — stay
• 1 — move random
• 2 — move north
• 3 — move south
• 4 — move east
• 5 — try pick

So your int array would then look like so:

strategy array

This array is ideal when you need to crossbreed and mutate, but your fitnessFunction would need to contain a lot of data about the meaning of each of those scenarios (NOTE: pseudo code):

float fitnessFunction( int[] strategy, 
             ArrayList<RobotMaps> testRobotMaps) {
  //returns the average score of running 
  //strategy against these testRobotMaps
  float ret = 0;
  for( int idx=0; idx<testRobotMaps.size(); idx++) {
    ret += testRobotMaps.get(idx).scoreStrategy( strategy);
  }
  return ret/(float)testRobotMaps.size();
}
public class RobotMaps {
  private char[MAP_SIZE][MAP_SIZE] map;
  public int scoreStrategy( int[] strategy) {
    int score = 0;
    //get robot current location
    x,y = this.getRobotLocation();
    //check neighbors for scenario
    // '.'=empty, 'c'=can, 'w'=wall . 
    //these conditions match scenario 0 above
    if( map[x-1] [y] == '.' && map[x+1][y] == '.' 
        && map [x][y-1] == 'c' 
        && map[x][y+1] == '.' && map[x][y] == '.') {
      score += performAction(strategy[0]);
    } 
    //else if( conditions that match scenario 1) { score+=performAction(strategy[1]);}
    //else if( conditions that match scenario 1) { score+=performAction(strategy[2]);}
    //do this a total of 243 times
    return score;
  }
  private int performAction( int action) {
    if( action==0) {return 0;}
    else if( action==1) {
      //move random
      //if random move results in hitting a wall dont move and return -5
      //else return 0
    } //more movement else statements like above for actions 2-5
    else if (action==6) {//try pickup
      x,y = this.getRobotLocation();
      if(map[x][y] == 'c'){ return 10;}
      else{ return -1}
    }
  }
}

After you’ve tested every strategy and identified your genetic candidates, you’ll need to crossbreed and mutate:

int[] breed( int[] partnerOne, int[] partnerTwo) {
  Random rnd = new Random(SEED);
  int[] ret = new int[partnerOne.length];
  int split = rnd.nextInt(partnerOne.length);
  for(int i=0; i<=split; i++){ 
    ret[i]=(rnd.nextFloat()>.05?partnerOne[i]:rnd.nextInt(7));
  }
  for(int i=split; i<ret.length; i++){
    ret[i]=(rnd.nextFloat()>.05?partnerTwo[i]:rnd.nextInt(7));
  }
  return ret;  
}