Chris Porcelli
-and-
Patrick Pan
The genetic programming package GPJPP, written in Java, served as the motivation and starting point for this project. We were curious as to its extension and application in exploring problems in genetic programming. The particular problem we applied this package to was one which has probably held the attention of people since childhood and has been spoken about since ancient times in Greek myths, helping to imprison a mythical creature known as the minotaur in an island known as Crete. This artifice is more commonly referred to as a maze.
Mazes in themselves are fascinating creations of their own right, destined to forever confound minds, challenge mankind's spatial authority, serve as exercises in navigation and ultimately test one's patience (after one's navigational prowess and tolerance is at an ebb). However, we were not interested in mazes, scintillating though they may be. On the contrary, we were more concerned with their solution. After all, when all is said and done, and one has studied a maze and gazed into its depths in awe of its intricate beauty, praising the ingenuity of its craft and its labyrinthine paths, when one has finally exhausted his supply of goodwill and diplomacy, when one's patience has finally run out, all that one wishes to do at that point is to solve the blasted thing!
Solutions to mazes that vex one's patience and general solutions that promise liberation from captivity represent a heavenly gift to those who have sought a trapdoor out of the labyrinthine madness in which they find themselves ensconced. Our ambitions in such an undertaking were quite a bit more modest, as were our expectations. We were aware of the "right hand" rule of searching mazes, which is to basically place one's right hand upon the wall and follow the wall to its eventual exit. However, it does not provide the solution when applied to disconnected mazes (mazes in which the exit is not connected to the borders of the outer wall).
Our approach was to attempt to generate a general solution for searching mazes (or certain types of mazes), with the aid of the GPJPP genetic programming package mentioned above. We followed the tree-structure of program statements, using the Symbolic Regression program as an example of the format such program statements must take. To this end, the programming "language" we devised made use of similar structures such as functions and terminals. There are eight different expressions, four of which are functions and four of which are terminals. They are:
"N?" - Predicate function determining whether north wall is open "S?" - Predicate function determining whether south wall is open "E?" - Predicate function determining whether east wall is open "W?" - Predicate function determining whether west wall is open "N" - Move north. "S" - Move south. "E" - Move east. "W" - Move west.
We took advantage of the program tree structure to specify that the left branch of any predicate function specified the command(or another function) that would be evaluated if the the predicate was true, while the right branch would be evaluated if the predicate turned out to be false.
For instance, the following program:
N?
/ \
N S
Would mean: if there wasn't a wall to the north, move north. Otherwise, move south.
In such a way, a tree could be constructed that would provide an algorithm for navigating through a maze. We also stipulated that the program that was making its way through a maze would self-destruct if it ever ran into a wall. This would force the program trees to be more "intelligent", rather than simply bouncing against every wall it ran up against. There was another problem in the actual evaluation of a program: whether or not it actually found the exit. If we were to assume that every program that was generated/evolved would be guaranteed to find a solution eventually, there would no longer be a problem of solving a maze! However, in reality, there are programs which will not find a solution, and would run forever as long as it avoided running into walls. In order to prevent this from occurring, we specified that a program would have a "time-to-live" value, which is the number of turns it is allowed to take before self-destructing. Every program statement, that is, predicate functions and terminal commands, takes exactly 1 turn to evaluate. In this sense, there is a time limit in which a program must find an exit or be destroyed. After these specifications the final matter left was the maze. We had to specify the format of the maze, its generation, and the evaluation of the program in the maze. We decided to actually specify the maze and other constraints in a file that would be loaded up by the program. The mazes themselves were generated by hand, since we wanted to know the solution of the maze beforehand. Also, the solution to the maze was included in the file as well, in the form of a matrix of fitness values.
The exact format of the file is as follows:
MAZE_DIMENSIONS(W H) START(X Y) END(X Y) TIME-TO-LIVE ----------- Actual Maze ----------- -------------- Fitness Matrix --------------
The two mazes we trained the GP on are as follows:
10 10 1 0 9 4 80 X XXXXXXXX X X X XX X X X X X X X XX X X XXX X X X XXXX X XXX XX X X X X X X X XX XXXXXXXXXX -1 6 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 -1 4 -1 2 1 1 -1 -1 -1 5 -1 4 -1 2 -1 1 1 -1 -1 5 5 5 -1 2 -1 -1 1 -1 -1 5 -1 -1 -1 2 2 -1 1 0 -1 5 4 5 -1 2 -1 -1 -1 -1 -1 5 -1 -1 -1 2 -1 -1 4 -1 -1 5 4 4 -1 3 -1 3 4 -1 -1 5 -1 3 3 3 3 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
8 8 0 4 3 4 80 XXXXXXXX X X X XXXX X X XX X X X X X XXXX X X X XXXXXXXX -1 -1 -1 -1 -1 -1 -1 -1 -1 4 4 4 3 3 3 -1 -1 5 -1 -1 -1 -1 3 -1 -1 5 -1 -1 1 2 2 -1 6 5 -1 0 1 -1 3 -1 -1 5 -1 -1 -1 -1 3 -1 -1 5 4 4 4 3 3 -1 -1 -1 -1 -1 -1 -1 -1 -1
There was some initial difficulty in debugging the Java code we had written from scratch for program evaluation and loading, but apart from those technicalities, we did not encounter any other unexpected difficulties.
The following program trees were generated from several runs, with a population of 50 programs traversing a maze. Fitness is measured by the location of a program when it terminates.
We selected two research papers for reading. Due to the time constraints, we were unable to find anything closely related to the topic we chose to investigate.
The first paper is entitled "Automatic Programming of a Time-Optimal Robot Controller and an Analog Electrical Circuit to Implement the Robot Controller by Means of Genetic Programming", by Koza, Bennett, Keane, and Andre. In this paper, the authors discuss a gp-created program to control a robot to arrive at a destination while minimizing the time spent. While this paper is somewhat related in topic to our project, they are more concerned with physical models of robots and use circular coordinate systems to represent robotic navigation (rather than our more simplified view of ordinates). Their evaluation of a program features a more complex set of arithmetic and trigonometric operators to minimize time.
The second paper is entitled "Future Work and Practical Applications of Genetic Programming", and is written by John Koza. This paper is actually a chapter of a volume, Handbook of Evolutionary Computation. It is a description of future areas for research and application of Genetic Programming. The summaries and descriptions of other promising areas are rather brief, but the section concerning the handling of complex data structures can be applied to our problem.
After evolving several generations of algorithms, we noticed a trend in the data: the best fitness value seemed to stabilize at a certain point. We believe this is because of the time allotted for program evaluation. The programs are actually dying before they are able to completely search the maze. Experiments in lengthening the time-to-live to a large number could prove to be fruitful in the future.
The "default" maze, which could be solved by the right-hand rule, produced quite a few surprising programs that were able to venture far into the maze. The circular maze, on the other hand, seemed to create fragments of programs that had a "right-hand" rule strategy and simply got the program close to the exit, sometimes even using a "left-hand" rule! Part of what may have affected the results and evolution is the choice of fitness values. The matrix was generated by hand, and values were suggested based upon their proximity to the exit. The result may not have been an accurate measurement of the effectiveness of the program in navigation. Another thing was the small number of sample mazes we evolved the programs upon. We only used two mostly due to time constraints (plus those mazes were annoying to create). There seem to be rich avenues of exploration in this problem for future work as well.
PopulationSize = 500 NumberOfGenerations = 51 CrossoverProbability = 90.0 CreationProbability = 0.0 CreationType = RampedHalf MaximumDepthForCreation = 9 MaximumDepthForCrossover = 26 MaximumComplexity = 300 SelectionType = Probabilistic TournamentSize = 7 DemeSize = 100 DemeticMigProbability = 100.0 SwapMutationProbability = 0.0 ShrinkMutationProbability = 0.0 TerminationFitness = 0.3 GoodRuns = 5 DemeticGrouping = false AddBestToNewPopulation = true SteadyState = false PrintDetails = false PrintPopulation = false PrintExpression = true PrintTree = true TreeFontSize = 12 UseADFs = false TestDiversity = true ComplexityAffectsFitness = true CheckpointGens = 0
import java.io.*;
import gpjpp.*;
// Maze class
class Maze {
boolean[][] maze;
int[][] fitness;
int rows, cols;
pos start, end;
int ttl;
Maze(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.maze = new boolean[cols][rows];
this.fitness = new int[cols][rows];
start = new pos(0, 0);
end = new pos(0, 0);
}
public boolean isNopen(pos location) {
if (location.y == 0) { return false; }
return this.maze[location.x][location.y - 1];
}
public boolean isSopen(pos location) {
if (location.y == this.rows - 1) { return false; }
return this.maze[location.x][location.y + 1];
}
public boolean isEopen(pos location) {
if (location.x == this.cols - 1) { return false; }
return this.maze[location.x + 1][location.y];
}
public boolean isWopen(pos location) {
if (location.x == 0) { return false; }
return this.maze[location.x - 1][location.y];
}
public pos moveN(pos location) {
if ((location.y > 0) &&
(this.isNopen(location))) { location.y -= 1; }
return location;
}
public pos moveS(pos location) {
if ((location.y < this.rows - 1) &&
(this.isSopen(location))) { location.y += 1; }
return location;
}
public pos moveE(pos location) {
if ((location.x < this.cols - 1) &&
(this.isEopen(location))) { location.x += 1; }
return location;
}
public pos moveW(pos location) {
if ((location.x > 0) &&
(this.isWopen(location))) { location.x -= 1; }
return location;
}
}
// X, Y coordinate positions
class pos {
int x, y;
pos(int x, int y) {
this.x = x;
this.y = y;
}
}
//=====================================================================
// GP maze search tree
class GPMaze extends GPRun {
// must override GPRun.createNodeSet to return
// initialized set of functions & terminals
public static Maze maze;
protected GPAdfNodeSet createNodeSet(GPVariables cfg) {
GPAdfNodeSet adfNs = new GPAdfNodeSet();
adfNs.reserveSpace(1);
GPNodeSet ns0 = new GPNodeSet(8);
adfNs.put(0, ns0);
ns0.putNode(new GPNode(0, "N?", 2));
ns0.putNode(new GPNode(1, "S?", 2));
ns0.putNode(new GPNode(2, "E?", 2));
ns0.putNode(new GPNode(3, "W?", 2));
ns0.putNode(new GPNode(4, "N"));
ns0.putNode(new GPNode(5, "S"));
ns0.putNode(new GPNode(6, "E"));
ns0.putNode(new GPNode(7, "W"));
// The following is a possible addition (time permitting)
// ns0.putNode(new GPNode(8, "BACK1");
// ns0.putNode(new GPNode(9, "BACK2");
// ns0.putNode(new GPNode(10, "BACK3");
// ns0.putNode(new GPNode(11, "BACK4");
return adfNs;
}
// must override GPRun.createPopulation to return
// GPMaze-specific population
protected GPPopulation createPopulation(GPVariables cfg,
GPAdfNodeSet adfNs)
{
return new GPMazePopulation(cfg, adfNs);
}
// maze loader
protected void loadMaze(String mazeName) throws IOException {
InputStream in = new FileInputStream(mazeName);
StreamTokenizer st = new StreamTokenizer(in);
int tokenType, rows, cols;
Maze m;
// read in header info
st.nextToken(); rows = (int)st.nval;
st.nextToken(); cols = (int)st.nval;
m = new Maze(rows, cols);
st.nextToken(); m.start.x = (int)st.nval;
st.nextToken(); m.start.y = (int)st.nval;
st.nextToken(); m.end.x = (int)st.nval;
st.nextToken(); m.end.y = (int)st.nval;
st.nextToken(); m.ttl = (int)st.nval;
// read in maze
// disable whitespace parsing
st.ordinaryChar(' '); st.wordChars(' ', ' ');
for (int j = 0; j < cols; j++) {
// read in a line of the maze
st.nextToken();
for (int i = 0; i < rows; i++) {
if (st.sval.charAt(i) == 'X') {
m.maze[i][j] = false;
}
else {
m.maze[i][j] = true;
}
}
}
// re-enable whitespace parsing
st.ordinaryChar(' '); st.whitespaceChars(' ', ' ');
// read in fitness values
for (int j = 0; j < cols; j++) {
for (int i = 0; i < rows; i++) {
st.nextToken(); m.fitness[i][j] = (int)st.nval;
}
}
// Verbose debugging info
System.out.println("ROWS: " + m.rows);
System.out.println("COLS: " + m.cols);
System.out.println("Start: (" + m.start.x + ", " + m.start.y + ")");
System.out.println("End: (" + m.end.x + ", " + m.end.y + ")");
System.out.println("TTL: " + m.ttl);
in.close();
this.maze = m;
}
// construct this test case
GPMaze(String mazeName, String baseName) throws IOException {
super(baseName, true);
// load in maze
loadMaze(mazeName);
}
// main application function
public static void main(String[] args) throws IOException {
// compute base file name from command line parameter
String baseName, mazeName;
switch (args.length) {
case 2:
mazeName = args[0];
baseName = args[1];
break;
case 1:
mazeName = args[0];
baseName = "gpmaze";
break;
default:
mazeName = "default.dat";
baseName = "gpmaze";
}
// construct the test case
GPMaze test = new GPMaze(mazeName, baseName);
// run the test
test.run();
// make sure all threads are killed
System.exit(0);
}
}
//=====================================================================
// extend GPGene to evaluate program
class GPMazeGene extends GPGene {
// public null constructor required during stream loading only
// this constructor called when new genes are created
GPMazeGene(GPNode gpo) { super(gpo); }
// this constructor called when genes are cloned during reproduction
GPMazeGene(GPMazeGene gpo) { super(gpo); }
// called when genes are cloned during reproduction
protected Object clone() { return new GPMazeGene(this); }
// ID routine isA() required only for streams
// must override GPGene.createChild to create GPMaze instances
public GPGene createChild(GPNode gpo) { return new GPMazeGene(gpo); }
/* Code is now useless...
// protected divide, here protected by IEEE floating point standards
double divide(double x, double y) {
// return NaN or INF if y = 0
return x/y;
}
*/
// called by GPMazeGP.evaluate() with a given maze
pos evaluate(GPMazeGene root, Maze m, pos location, int ttl)
{
int branch;
// Check for terminal conditions:
if ((location.x == m.end.x) &&
(location.y == m.end.y))
{ // program has found the exit: end.
return location;
}
if (ttl <= 0) { // running time is up: end.
return location;
}
// run the maze-searching program on the given maze
// for ttl turns
if (isFunction()) { // this node contains a branch predicate
switch (node.value()) {
case 0: // N? - Is it possible to go north?
if (m.isNopen(location)) { // yes: execute left prg branch
branch = 0;
}
else { // no: execute right prg branch
branch = 1;
}
break;
case 1: // S? - Is it possible to go south?
if (m.isSopen(location)) {
branch = 0;
}
else {
branch = 1;
}
break;
case 2: // E? - Is it possible to go east?
if (m.isEopen(location)) {
branch = 0;
}
else {
branch = 1;
}
break;
case 3: // W? - Is it possible to go west?
if (m.isWopen(location)) {
branch = 0;
}
else {
branch = 1;
}
break;
default:
throw new RuntimeException("Undefined function type " +
node.value());
}
location = ((GPMazeGene)get(branch)).evaluate(root,
m,
location,
ttl - 1);
} else { // an actual movement command
switch (node.value()) {
case 4: // move North
if (! m.isNopen(location)) { ttl = 0; }
location = m.moveN(location); break;
case 5: // move South
if (! m.isSopen(location)) { ttl = 0; }
location = m.moveS(location); break;
case 6: // move East
if (! m.isEopen(location)) { ttl = 0; }
location = m.moveE(location); break;
case 7: // move West
if (! m.isWopen(location)) { ttl = 0; }
location = m.moveW(location); break;
default:
throw new RuntimeException("Undefined terminal type " +
node.value());
}
// Go back to root of tree
location = root.evaluate(root, m, location, ttl - 1);
}
return location;
}
}
//=====================================================================
class GPMazeGP extends GP {
//this constructor called when new GPs are created
GPMazeGP(int genes) { super(genes); }
//this constructor called when GPs are cloned during reproduction
GPMazeGP(GPMazeGP gpo) { super(gpo); }
//called when GPs are cloned during reproduction
protected Object clone() { return new GPMazeGP(this); }
//must override GP.createGene to create GPMazeGene instances
public GPGene createGene(GPNode gpo) { return new GPMazeGene(gpo); }
//must override GP.evaluate to return standard fitness
public double evaluate(GPVariables cfg) {
double rawFitness;
pos location = new pos(GPMaze.maze.start.x, GPMaze.maze.start.y);
location = ((GPMazeGene)get(0)).evaluate((GPMazeGene)get(0),
GPMaze.maze,
location,
GPMaze.maze.ttl);
rawFitness = (double)GPMaze.maze.fitness[location.x][location.y] / 10.0;
if (rawFitness < 0.0) {
System.out.println("Fitness: " + rawFitness + "(" +
location.x + ", " + location.y + ")");
}
double stdF = Math.abs(rawFitness);
if (cfg.ComplexityAffectsFitness)
// add 0.1 for optimum length (10)
stdF += (double)length()/100.0;
return stdF;
}
}
//=====================================================================
// extend GPPopulation to create Maze GP trees
class GPMazePopulation extends GPPopulation {
//this constructor called when new populations are created
GPMazePopulation(GPVariables gpVar, GPAdfNodeSet adfNs) {
super(gpVar, adfNs);
}
//populations are not cloned in standard runs
//GPMazePopulation(GPMazePopulation gpo) { super(gpo); }
//protected Object clone() { return new GPMazePopulation(this); }
//must override GPPopulation.createGP to create GPMaze instances
public GP createGP(int numOfGenes) { return new GPMazeGP(numOfGenes); }
}