Path Finding AI using Genetic Algorithm in Unity - Tutorial Part 2

In Part 1, we created a Neural Network model. That model is filled with random values and needs to be trained before it can behave correctly. In this part, we will implement the genetic algorithm to train it.

Introduction to Genetic algorithm

The genetic algorithm is a heuristic algorithm based on the theory of natural evolution. The concept of selection, crossover, and mutation is applied in this method. It consists of four phases.

Initialization

In this phase, a population of creatures is created and introduced to the system. In the first generation, creatures are created with random values covering the entire range of possible values. These values make chromosomes based on which a creature's behaviour is determined.

Selection

Creatures performing best in the system are selected to produce offspring for the next generation. To measure the performance(score) of the creature, we will use the fitness function. We will be using time creature survived without colliding wall as the fitness function. Also, the creature scores a huge point when it reaches its goal.

Crossover

The chromosomes from parents are taken and mixed to create new offspring. Gene of these creatures is taken and mixed to get chromosomes for offspring inheriting the parent's character. Various techniques are available for crossovers such as one-point crossover, two-point crossover, and uniform crossover. One-point crossover and two-point crossover slices chromosomes and swap them to create children. Uniform crossover picks random genes from either parent to create a gene for children. We will be using uniform crossover for path-finding AI.

Mutation

A random gene of a chromosome is randomized to add unique characteristics in children. It allows offsprings to explore other possible solution that was not explored by the previous generation. The number of genes altered is determined by mutation chance. The lower mutation causes the finding of a solution long time. Higher mutation chance causes a drastic change in the behaviour of children compared to parents thus losing traits of parent. So, it is important to choose a good mutation chance.

After completing all of the above phases, a cycle of generation is completed. A new population of creatures is generated using chromosomes obtained and are introduced to the system. The cycle of selection, crossover, the mutation are repeated until the termination condition is met.

Creating general creature class

Let's first create a Creatures class that acts as an interface for interacting creatures from the GA system. We will inherit from this class to create path finding creatures. The advantage of having a parent Creatures class is that it provides an abstraction to the GA system so that, various types of creatures can be created, not just path finding AI.

A base creature requires a NN model we will call it brain . An id will be assigned to each creature so that they can be recognized. To maintain a state of a creature, isInitialized and isRunning will be used. isInitialized will keep track of all required setups done and isRunning will keep track of whether a creature is idle or being simulated.

To initialize a creature's brain,  number of inputs, hiddenLayer, output are required. This can vary from type of creature but should be identical for all same type of creature.

using UnityEngine;
using UnityEngine.Events;

public class Creatures: MonoBehaviour {

  public int id;
  private NeuralNetwork brain;
  private bool isInialized;
  protected bool isRunning;

  [SerializeField]
  private int inputs, hiddenLayers, outputs;

  public void InitializeCreature() {
    if (isInialized) return;

    brain = new NeuralNetwork(inputs, outputs, hiddenLayers);
    isInialized = true;
  }
  
  //start simulation in environment
  public void StartCreature() {
    isRunning = true;
  }

  //stop simulation
  public void StopCreature() {
    isRunning = false;
  }
}

Next, create getters and setters for manipulating chromosomes in a creature's brain. Also, create methods for sending and receiving signals from the brain. When the message is received from the brain, GotResultFromBrain will be called. This method needs to be overridden to act according to the received output.

protected void SendInputToBrain(float[] inputSignals) {
  if (!isInialized) return;
  GotResultFromBrain(brain.ProcessInput(inputSignals));
}

//Get creature chromosome
public float[] GetBrainData() {
  if (!isInialized) return null;
  return brain.GetGeneSequence();
}

//Set creature's chromosome
public void SetBrainData(float[] gene) {
  if (!isInialized) return;
  brain.SetValues(gene);
}

//called when action is received after sending input to brain
protected virtual void GotResultFromBrain(float[] output) {
}

Now, let's create events so that other systems monitoring creatures can know what is happening. We will create onGoalReached  and onFailed event to broadcast the success or failure of the creature. Two methods will be created so that child class can inform failure and success.

public UnityEvent < int > onGoalReached = new UnityEvent < int > ();
public UnityEvent < int > onFailed = new UnityEvent < int > ();

protected void GoalReached() {
  onGoalReached.Invoke(id);
}

protected void OnFailed() {
  onFailed.Invoke(id);
}

Implementing Genetic algorithm

To implement the genetic algorithm, let us first create GeneticAlgorithm class. It consists of GetOffsprings method that can be used to get chromosomes for the next generation. This method will take 5 parameters as follows:

1. parents - Chromosomes of all parents of the previous generation.
2. scores - Score received by each parent. The score must be in the same order as parents, score at ith index is a score of parents[i]
3. selectionChance - Chance of best parent be used for crossover. It will be in the order of best parent at 0th index to least good parent at last index. Its length will determine the number of parents that will be chosen for crossover.
4. mutationChance - Chance of gene to be mutated. It must be chosen carefully as too high or too low value can cause a less efficient learning system. We can experiment with different mutation chances to find the right mutation value.
5. offspringCount - Number of offspring to generate.

Now, we can implement the process of selection, crossover and mutation.

using UnityEngine;

public static class GeneticAlgorithm {
  public static float[][] GetOffsprings(float[][] parents, float[] scores, float[] selectionChance, float mutationChance, int offspringsCount) {
    int selectedParentCount = selectionChance.Length;

    //Selection
    int[] bestCreatureIndexes = GetBestScoreIndex(selectedParentCount, scores);
    float[][] bestParents = new float[selectedParentCount][];
    for (int i = 0; i < bestCreatureIndexes.Length; i++) {
      bestParents[i] = parents[bestCreatureIndexes[i]];
    }

    float total = 0;
    for (int i = 0; i < selectedParentCount; i++) {
      total += selectionChance[i];
    }

    //creating offsprings
    float[][] offsprings = new float[offspringsCount][];
    for (int i = 0; i < offspringsCount; i++) {
      //crossover
      float rand = Random.Range(0 f, total);
      float selectionPoint = selectionChance[0];

      //find parent 1
      float[] parent1 = bestParents[0];
      int parent1Index = 0;
      for (int j = 0; j < selectedParentCount; j++) {
        if (rand <= selectionPoint) {
          parent1 = bestParents[j];
          parent1Index = j;
          break;
        }

        if (j == selectedParentCount - 1)
          parent1 = bestParents[selectedParentCount - 1];
        else
          selectionPoint += selectionChance[j + 1];
      }

      //find parent 2
      rand = Random.Range(0 f, total);
      selectionPoint = selectionChance[0];
      float[] parent2 = bestParents[0];

      for (int j = 0; j < selectedParentCount; j++) {
        if (j == parent1Index && j != selectedParentCount - 1) continue; //avoid previous parent
        if (rand <= selectionPoint) {
          parent2 = bestParents[j];
          break;
        }

        if (j == selectedParentCount - 1)
          parent2 = bestParents[selectedParentCount - 1];
        else
          selectionPoint += selectionChance[j + 1];
      }

      //create chromosome for offspring
      float[] offspring = new float[parent1.Length];
      for (int j = 0; j < offspring.Length; j++) {
        //select gene from parent 1 or 2
        offspring[j] = Random.Range(0 f, 1 f) > 0.5 f ? parent1[j] : parent2[j];

        //mutation
        if (Random.Range(0 f, 1 f) < mutationChance) {
          //mutating from -10 to 10. You can add mutation range to pass variable mutation range
          offspring[j] = Random.Range(-10 f, 10 f);
        }
      }

      offsprings[i] = offspring;
    }

    return offsprings;
  }

  //finds index of highest scores. Returns best score's index in descending order
  private static int[] GetBestScoreIndex(int bestPickCount, float[] creatureScore) {
    int[] bestCreatureIndex = new int[bestPickCount];
    float[] bestCreatureScores = new float[bestPickCount];

    for (int i = 0; i < creatureScore.Length; i++) {
      float score = creatureScore[i];
      for (int j = 0; j < bestPickCount; j++) {
        if (score > bestCreatureScores[j]) {
          float replacingScore = score;
          int replacingIndex = i;

          for (int k = j; k < bestPickCount; k++) {
            float tempFloat = bestCreatureScores[k];
            int tempIndex = bestCreatureIndex[k];

            bestCreatureScores[k] = replacingScore;
            bestCreatureIndex[k] = replacingIndex;

            replacingScore = tempFloat;
            replacingIndex = tempIndex;
          }
          break;
        }
      }
    }
    return bestCreatureIndex;
  }
}