The Sample Problem

Date: 2015-10-07; view: 450.

The abstract problem I'll deal with is to develop an intelligent strategy to be used by a simple artificial ant. The ant moves on a 32¥32 grid, and if it moves off one side it returns on the other side. The grid has a winding trail of food on it. The trail begins at the [0,0] origin, which is also the starting position of the ant. Each grid location in the trail can be empty, contain food, or contain an indicator that it is a gap between food locations. The trail must be continuous from the origin. All food must be adjacent to at least one point that has food or a marked gap.

The simple ant has two elements that fully describe its state. The first is its current location on the grid. The second is the direction it is facing, which is either left, right, up, or down. The ant has three possible things it can do. It can turn left, turn right, or move to the square that it is facing. It has only one sensor for its environment: a function called FacingFood which will tell it if there is food in the square that it is facing.

When an ant moves to a square that contains food, it removes the food from the grid and increments the total food it has gathered. When it moves or turns, it increments the number of steps it has taken to gather its food.

The problem is to create an ant that will make an intelligent series of moves and turns based on its FacingFood function. An example would be:

This would work fine for trails whose turns are always to the right. The practical problem is to use GP to create a program that will walk an arbitrary trail of food and gaps most efficiently.