Artificial Ant Problem Genetic Programming Example

Artificial Ant Problem

This page provides an example of using the OakGP genetic programming Java framework to evolve suitable candidates for the "artificial ant problem" (also known as the Santa Fe Trail problem).
For an overview of OakGP please read the getting started with OakGP guide.

Problem Description
Approach
Configuration
   Return Type
   Variable Set
   Function Set
Java Source Code
Output

Problem Description

The artificial ant problem (also known as the Santa Fe Trail problem) is often used as a GP benchmark. The challenge is to develop a solution that will navigate an artificial ant along a twisting trail on a two-dimensional grid.

Approach

The MutableState class is used to represent the grid and the ant's position within it.

The following functions are used to help the ant navigate around the grid:

Right - turn the ant to the right.
Left - turn the ant to the left.
Forward - move the ant forward one square.
IsFoodAhead - returns true if the square the ant is facing contains food, else false.
BiSequence - executes two nodes in sequence.
TriSequence - executes three nodes in sequence.

The genetic programming run is configured in ArtificialAntExample using a org.oakgp.util.RunBuilder.

Configuration

Return Type

Type	Description
`void`	The program does not return anything. The program works by mutating the `MutableState` object passed as an argument.

Variable Set

ID	Type	Description
`v0`	`state`	An instance of `MutableState` representing the grid and the ant's position within it.

Function Set

Class:	`org.oakgp.examples.ant.AntMovement`
Symbol:	`forward`
Return Type:	`void`
Arguments:	`state`

Class:	`org.oakgp.examples.ant.AntMovement`
Symbol:	`left`
Return Type:	`void`
Arguments:	`state`

Class:	`org.oakgp.examples.ant.AntMovement`
Symbol:	`right`
Return Type:	`void`
Arguments:	`state`

Class:	`org.oakgp.examples.ant.IsFoodAhead`
Symbol:	`foodahead?`
Return Type:	`boolean`
Arguments:	`state`

Class:	`org.oakgp.examples.ant.BiSequence`
Symbol:	`bisequence`
Return Type:	`void`
Arguments:	`void, void`

Class:	`org.oakgp.examples.ant.TriSequence`
Symbol:	`trisequence`
Return Type:	`void`
Arguments:	`void, void, void`

Class:	`org.oakgp.function.choice.If`
Symbol:	`if`
Return Type:	`void`
Arguments:	`boolean, void, void`

Java Source Code

org/oakgp/examples/ant/MutableState.java

package org.oakgp.examples.ant;

import org.oakgp.Type;

/** Represents the grid and the ant's position within it. */
class MutableState {
    static final Type STATE_TYPE = Type.type("state");

    private boolean[][] grid;
    private int incX = 0;
    private int incY = 1;
    private int[] currentPosition = new int[2];
    private int foodEaten;
    private int movesTaken;

    MutableState(boolean[][] grid) {
       this.grid = grid;
    }

    /** Returns the number of cells visited that have contained food. */
    int getFoodEaten() {
       return foodEaten;
    }

    /** Returns the total number of moves (left, right and forward) that have already been applied to this object. */
    int getMovesTaken() {
       return movesTaken;
    }

    /** Returns {@code true} if the cell directly ahead of the ant contains food. */
    boolean isFoodAhead() {
       return isFood(getCoordsAhead());
    }

    /** Turns the ant to the left. */
    void left() {
       movesTaken++;

       int oldIncX = incX;
       incX = incY;
       incY = 0 - oldIncX;
    }

    /** Turns the ant to the right. */
    void right() {
       movesTaken++;

       int oldIncX = incX;
       incX = 0 - incY;
       incY = oldIncX;
    }

    /** Moves the ant forward one cell. */
    void forward() {
       movesTaken++;

       currentPosition = getCoordsAhead();
       if (isFood(currentPosition)) {
          eatFood(currentPosition);
       }
    }

    private int[] getCoordsAhead() {
       int[] newPosition = new int[2];
       newPosition[0] = update(currentPosition[0], incX);
       newPosition[1] = update(currentPosition[1], incY);
       return newPosition;
    }

    private int update(int current, int increment) {
       int newValue = current + increment;
       if (newValue == -1) {
          return GridReader.getGridLength() - 1;
       } else if (newValue == GridReader.getGridLength()) {
          return 0;
       } else {
          return newValue;
       }
    }

    private boolean isFood(int[] coords) {
       return grid[coords[0]][coords[1]];
    }

    private void eatFood(int[] coords) {
       grid[coords[0]][coords[1]] = false;
       foodEaten++;
    }
}

org/oakgp/examples/ant/AntMovement.java

package org.oakgp.examples.ant;

import java.util.function.Consumer;

import org.oakgp.Arguments;
import org.oakgp.Assignments;
import org.oakgp.function.Function;
import org.oakgp.function.ImpureFunction;
import org.oakgp.function.Signature;
import org.oakgp.node.FunctionNode;
import org.oakgp.node.Node;
import org.oakgp.node.NodeType;
import org.oakgp.util.Void;

/** Mutates the state of a {@code MutableState} object. */
final class AntMovement implements ImpureFunction {
    /** Move the ant forward one square. */
    static final AntMovement FORWARD = new AntMovement("forward", MutableState::forward);
    /** Turns the ant to the left. */
    static final AntMovement LEFT = new AntMovement("left", MutableState::left);
    /** Turns the ant to the right. */
    static final AntMovement RIGHT = new AntMovement("right", MutableState::right);

    private final String displayName;
    private final Consumer<MutableState> movement;

    private AntMovement(String displayName, Consumer<MutableState> movement) {
       this.displayName = displayName;
       this.movement = movement;
    }

    @Override
    public Signature getSignature() {
       return Signature.createSignature(Void.VOID_TYPE, MutableState.STATE_TYPE);
    }

    @Override
    public Void evaluate(Arguments arguments, Assignments assignments) {
       MutableState state = arguments.firstArg().evaluate(assignments);
       movement.accept(state);
       return Void.VOID;
    }

    @Override
    public String getDisplayName() {
       return displayName;
    }

    static boolean isLeftAndRight(Node firstArg, Node secondArg) {
       Function f1 = getFunction(firstArg);
       Function f2 = getFunction(secondArg);
       if (f1 == LEFT && f2 == RIGHT) {
          return true;
       } else if (f1 == RIGHT && f2 == LEFT) {
          return true;
       } else {
          return false;
       }
    }

    static boolean areAllSame(AntMovement function, Node firstArg, Node secondArg, Node thirdArg) {
       Function f1 = getFunction(firstArg);
       Function f2 = getFunction(secondArg);
       Function f3 = getFunction(thirdArg);
       return f1 == function && f2 == function && f3 == function;
    }

    private static Function getFunction(Node n) {
       if (NodeType.isFunction(n)) {
          return ((FunctionNode) n).getFunction();
       } else {
          throw new IllegalStateException(n.toString());
       }
    }
}

org/oakgp/examples/ant/IsFoodAhead.java

package org.oakgp.examples.ant;

import org.oakgp.Arguments;
import org.oakgp.Assignments;
import org.oakgp.Type;
import org.oakgp.function.ImpureFunction;
import org.oakgp.function.Signature;

/** Returns {@code true} if the square the ant is facing contains food, else {@code false}. */
class IsFoodAhead implements ImpureFunction {
    @Override
    public Signature getSignature() {
       return Signature.createSignature(Type.booleanType(), MutableState.STATE_TYPE);
    }

    @Override
    public Boolean evaluate(Arguments arguments, Assignments assignments) {
       MutableState state = arguments.firstArg().evaluate(assignments);
       return state.isFoodAhead();
    }
}

org/oakgp/examples/ant/BiSequence.java

package org.oakgp.examples.ant;

import static org.oakgp.examples.ant.AntMovement.isLeftAndRight;
import static org.oakgp.util.Void.VOID_CONSTANT;
import static org.oakgp.util.Void.VOID_TYPE;
import static org.oakgp.util.Void.isVoid;

import org.oakgp.Arguments;
import org.oakgp.Assignments;
import org.oakgp.function.ImpureFunction;
import org.oakgp.function.Signature;
import org.oakgp.node.FunctionNode;
import org.oakgp.node.Node;
import org.oakgp.util.Void;

/** Executes two nodes in sequence. */
class BiSequence implements ImpureFunction {
    static final BiSequence BISEQUENCE = new BiSequence();

    private BiSequence() {
    }

    @Override
    public Signature getSignature() {
       return Signature.createSignature(VOID_TYPE, VOID_TYPE, VOID_TYPE);
    }

    @Override
    public Void evaluate(Arguments arguments, Assignments assignments) {
       arguments.firstArg().evaluate(assignments);
       arguments.secondArg().evaluate(assignments);
       return Void.VOID;
    }

    @Override
    public Node simplify(Arguments arguments) {
       Node firstArg = arguments.firstArg();
       Node secondArg = arguments.secondArg();
       if (isVoid(firstArg)) {
          return secondArg;
       } else if (isVoid(secondArg)) {
          return firstArg;
       } else if (isLeftAndRight(firstArg, secondArg)) {
          return VOID_CONSTANT;
       } else if (isBiSequence(firstArg)) {
          Arguments firstArgArgs = ((FunctionNode) firstArg).getArguments();
          return createTriSequence(firstArgArgs.firstArg(), firstArgArgs.secondArg(), secondArg);
       } else if (isBiSequence(secondArg)) {
          Arguments secondArgArgs = ((FunctionNode) secondArg).getArguments();
          return createTriSequence(firstArg, secondArgArgs.firstArg(), secondArgArgs.secondArg());
       } else {
          return null;
       }
    }

    private boolean isBiSequence(Node firstArg) {
       FunctionNode fn = (FunctionNode) firstArg;
       return fn.getFunction() == BISEQUENCE;
    }

    private Node createTriSequence(Node arg1, Node arg2, Node arg3) {
       return new FunctionNode(TriSequence.TRISEQUENCE, arg1, arg2, arg3);
    }
}

org/oakgp/examples/ant/TriSequence.java

package org.oakgp.examples.ant;

import static org.oakgp.examples.ant.AntMovement.LEFT;
import static org.oakgp.examples.ant.AntMovement.RIGHT;
import static org.oakgp.examples.ant.AntMovement.areAllSame;
import static org.oakgp.examples.ant.AntMovement.isLeftAndRight;
import static org.oakgp.util.Void.VOID_TYPE;
import static org.oakgp.util.Void.isVoid;

import org.oakgp.Arguments;
import org.oakgp.Assignments;
import org.oakgp.function.ImpureFunction;
import org.oakgp.function.Signature;
import org.oakgp.node.FunctionNode;
import org.oakgp.node.Node;
import org.oakgp.util.Void;

/** Executes three nodes in sequence. */
class TriSequence implements ImpureFunction {
    static final TriSequence TRISEQUENCE = new TriSequence();

    private TriSequence() {
    }

    @Override
    public Signature getSignature() {
       return Signature.createSignature(VOID_TYPE, VOID_TYPE, VOID_TYPE, VOID_TYPE);
    }

    @Override
    public Void evaluate(Arguments arguments, Assignments assignments) {
       arguments.firstArg().evaluate(assignments);
       arguments.secondArg().evaluate(assignments);
       arguments.thirdArg().evaluate(assignments);
       return Void.VOID;
    }

    @Override
    public Node simplify(Arguments arguments) {
       Node first = arguments.firstArg();
       Node second = arguments.secondArg();
       Node third = arguments.thirdArg();
       if (isVoid(first)) {
          return createBiSequence(second, third);
       } else if (isVoid(second)) {
          return createBiSequence(first, third);
       } else if (isVoid(third)) {
          return createBiSequence(first, second);
       } else if (isLeftAndRight(first, second)) {
          return third;
       } else if (isLeftAndRight(second, third)) {
          return first;
       } else if (areAllSame(LEFT, first, second, third)) {
          return new FunctionNode(RIGHT, ((FunctionNode) first).getArguments());
       } else if (areAllSame(RIGHT, first, second, third)) {
          return new FunctionNode(LEFT, ((FunctionNode) first).getArguments());
       } else {
          return null;
       }
    }

    private Node createBiSequence(Node arg1, Node arg2) {
       return new FunctionNode(BiSequence.BISEQUENCE, arg1, arg2);
    }
}

org/oakgp/examples/ant/ArtificialAntFitnessFunction.java

package org.oakgp.examples.ant;

import org.oakgp.Assignments;
import org.oakgp.node.Node;
import org.oakgp.rank.fitness.FitnessFunction;

/** Calculates the fitness of candidate solutions to navigate an artificial ant around a two-dimensional grid. */
class ArtificialAntFitnessFunction implements FitnessFunction {
    private static final int MAX_MOVES = 600;

    @Override
    public double evaluate(Node candidate) {
       MutableState state = new MutableState(GridReader.copyGrid());
       evaluate(candidate, state);
       return calculateFitness(state);
    }

    /** Keeps evaluating the given candidate using the given state until either the maximum number of moves have been taken or all the food has been eaten. */
    private void evaluate(Node candidate, MutableState state) {
       Assignments assignments = Assignments.createAssignments(state);
       int movesTaken = 0;
       while (movesTaken < MAX_MOVES && isRemainingFood(state)) {
          candidate.evaluate(assignments);

          // if last call to evaluate did not result in the state being updated
          // then exit now to avoid getting stuck in loop when evaluating candidates that do not do anything
          if (movesTaken == state.getMovesTaken()) {
             return;
          }

          movesTaken = state.getMovesTaken();
       }
    }

    /**
     * Calculate fitness of the given state.
     * <p>
     * Any state where all the food has been eaten is better than any state where there is food remaining. The best solution is the one where all the food has
     * been eaten in the quickest time.
     */
    private double calculateFitness(MutableState state) {
       if (isRemainingFood(state)) {
          return Integer.MAX_VALUE - state.getFoodEaten();
       } else {
          return state.getMovesTaken();
       }
    }

    /** Returns {@code true} if the given state contains cells with food that have not yet been visited. */
    private boolean isRemainingFood(MutableState state) {
       return state.getFoodEaten() < GridReader.getNumberOfFoodCells();
    }
}

org/oakgp/examples/ant/ArtificialAntExample.java

package org.oakgp.examples.ant;

import static org.oakgp.examples.ant.AntMovement.FORWARD;
import static org.oakgp.examples.ant.AntMovement.LEFT;
import static org.oakgp.examples.ant.AntMovement.RIGHT;
import static org.oakgp.examples.ant.BiSequence.BISEQUENCE;
import static org.oakgp.examples.ant.MutableState.STATE_TYPE;
import static org.oakgp.examples.ant.TriSequence.TRISEQUENCE;
import static org.oakgp.util.Void.VOID_CONSTANT;
import static org.oakgp.util.Void.VOID_TYPE;

import org.oakgp.function.Function;
import org.oakgp.function.choice.If;
import org.oakgp.node.Node;
import org.oakgp.rank.RankedCandidates;
import org.oakgp.rank.fitness.FitnessFunction;
import org.oakgp.util.RunBuilder;

public class ArtificialAntExample {
    private static final int TARGET_FITNESS = 0;
    private static final int NUM_GENERATIONS = 1000;
    private static final int INITIAL_POPULATION_SIZE = 100;
    private static final int INITIAL_POPULATION_MAX_DEPTH = 4;

    public static void main(String[] args) {
       Function[] functions = { new If(VOID_TYPE), new IsFoodAhead(), FORWARD, LEFT, RIGHT, BISEQUENCE, TRISEQUENCE };
       FitnessFunction fitnessFunction = new ArtificialAntFitnessFunction();

       RankedCandidates output = new RunBuilder().setReturnType(VOID_TYPE).setConstants(VOID_CONSTANT).setVariables(STATE_TYPE).setFunctions(functions)
             .setFitnessFunction(fitnessFunction).setInitialPopulationSize(INITIAL_POPULATION_SIZE).setTreeDepth(INITIAL_POPULATION_MAX_DEPTH)
             .setTargetFitness(TARGET_FITNESS).setMaxGenerations(NUM_GENERATIONS).process();
       Node best = output.best().getNode();
       System.out.println(best);
    }
}

Output

Below is an example of a solution generated by ArtificialAntExample.

Structure of generated solution Demonstration of generated solution

(trisequence
     (if
         (foodahead?
             v0)
         void
         (bisequence
             (right
                 v0)
             (right
                 v0)))
     (if
         (foodahead?
             v0)
         void
         (left
             v0))
     (bisequence
         (forward
             v0)
         (if
             (foodahead?
                 v0)
             void
             (left
                 v0))))