Genetic Path Finding was my major project and dissertation I completed within my third year of University. I had an interest in AI and was widening my horizons with this project. The project is essentially a comparison between a genetically created program and A* that each attempt to reach the target location on a randomly generated map. I began by researching into a variety of different areas of AI and I came across Genetic Algorithms. This was only part of my project since I wanted to move a character based on a specific program or set of code generated by the algorithm, this is known as Genetic Programming.
- Language: C++,
- IDE: Visual Studio 2010,
- Graphics API: OpenGL 3.3.
The project began as all projects should; with research. I looked into a wide variety of topics to gain knowledge and an understanding of AI and path finding. The topics researched include; A*, group movement, Neural Networks (and back propagation), Genetic Algorithms (and Genetic Programming) and the main two graphics APIs for the graphical representation section of the program. This led to reading sections of some books, articles and journals written by great authors such as John Koza.
The next logical step was to design the system, I had been given a very basic framework to work with which displayed a basic cube through a application wrapper using OpenGL. This was the initial starting point for the project before developing all the additions that brought the project to completion. The best way to understand my design is to look over the UML diagram created during the design phase of the project.
The classes in the upper-left of the diagram (CGApp, CGAppDelegate and OpenGL) show the basic framework provided while the others show the classes I have either modified or entirely created myself while developing the project. I decided upon a naming convention early in the project which was to name prefix the classes that I had written with the letter 'P' (standing for 'project') since this was my third year project and dissertation.
The first class I wrote was the PController class, this interfaced with the OpenGL class in that there were the standardised Update and Render calls. The design I went with was to call these methods within each of the classes that composed the PController class. An example of this is that the map must be both updated and rendered at each frame interval, this would be done by the placing a call to the controller's update and render functions within the OpenGL class, the controller would then call the corresponding functions within the PMap class and the PMap would then call the corresponding functions within the PGround class resulting in a rendered ground object within the scene. This basic design was mimic for each of the classes that needed to be either updated or rendered within the entire program to create a consistent and easy-to-understand design.
The controller class also acts as a Mediator (design pattern) in that other classes can only gain certain information by asking the PController class. An example of this is that for path finding to work correctly; a simple representation of how the map is laid out is required. The PAIPath class computes the path finding within the project and so would ask the controller class to collect the information from the PMap class. The path finding algorithm used was the A* algorithm, however this was only used to compare against the program created through the evolution processes of genetic programming.
2.1 Genetic Programming
The genetic programming element, and arguably the main part of the project was designed and implemented, and this section explains the design and implementation of the system. A basic genetic programming library was used (originally written by Larry Gritz) with some modifications since it was written purely in C rather than C++. The Genetic Program class provides the interface that is used by the different scenes (the path finding scene and the painted desert scene), however each of the classes that setup a given scene are also responsible for the setup of the GP. This is completed by defining the essential group of elements for the GP, these are:
- Objective: A statement of the problem which we are attempting to solve.
- Terminal Set: The list of terminals which can be included in any symbolic expressions generated by the GP.
- Function Set: The list of functions which can be included in any symbolic expressions generated by the GP.
- Fitness cases: A problem dependant set of test cases which will be used by the fitness function to derive the raw fitness value for each individual.
- Raw fitness: The method by which the fitness function will calculate the raw fitness measure for each individual.
- Standardised fitness: An optional method of conversion between raw fitness and standardised fitness.
- Hits: An auxiliary measure of the number of fitness cases which achieve satisfactory fitness.
- Wrapper: An optional conversion between output values of an evolved symbolic expression and input values needed by the fitness function.
- Parameters: Any of the major or minor parameters which control the GP run.
- Success predicate: An optional condition which may terminate the GP run before the maximum number of iterations.
Once each and every one of these elements have been correctly setup and defined; the genetic program begins to create populations of potential individuals (in this case, collections of functions with terminals as inputs). Once an initial, random, set of individuals are created; they are each tested using the fitness function (defined within the setup). This function returns the fitness score for the individual based on how effective it is at moving the green cube from the starting location in the lower right position of the grid to the end point at the upper left grid position.
It was clear that with the description above alone, it would be hard to visualise what my completed program was doing and so a collection of screenshots along with explanations was pieced together to construct a more clear image of the completed program.
This image shows how the path finding problem was graphically rendered, there is a basic plane showing the grid-layout of the map with black cubes showing the walls. The green cube and path shows the program generated by the genetic program for this problem and the red cube and path shows how it would be solved using the A* algorithm. This was a failed attempt for the genetic program
This image shows how an evolved program can find a solution that almost matches the optimal path computed by the A* algorithm.
Alongside the main program and graphical representation a basic debug console was written within a small class that redirected the output stream. This was used mainly for debug purposes and it was interesting to output the results and the programs generated.
4.0 Implementation and Additional Information