Pathfinding GA

The college I attended for undergrad requires an 8 credit senior project to be completed before graduating.  Myself and another student, Steven Turner, decided to develop a genetic algorithm for pathfinding to allow a robot to navigate around obstacles.  Our original intent was to demonstrate predator-prey dynamics among multiple robots in an environment.  I mostly developed the genetic algorithm while my partner worked with the robotics platform and its vision and movement software.

For those of you unfamiliar with genetic algorithms, they are algorithms that borrow from the biological ideas of natural selection and evolution.  The algorithm creates “generations” of solutions from the most “fit” (optimal) solutions of the former parent generation by crossover and mutation functions.  The crossover function, like its biological cousin, takes two solutions (“genes”) and chooses a point to swap information between them to create offspring genes based on the originals.  The mutation function can then pick a point in a gene and change a single point of information.  All of the genes are then tested for “fitness” (how optimal of a solution they are) and the cycle continues.  All of this is done in hopes that an optimal, or very nearly optimal, solution will be found after some number of generations.

Our hope is that the genetic algorithm approach will significantly reduce the runtime and space complexity of traditional A* path planning techniques.  The trade off is that our paths will most likely not be optimal, but this will also lend to a more “organic” feeling path.  Further reduction of runtime comes from how we implement the genetic algorithm.  Because the world in which the PreyBot lives is dynamic, it would be silly to plot one path and go about its business.  By only using the genetic algorithm to pathfind for a short distance and constantly updating the path, we hope to further reduce runtime while also making the robots actions smarter and more natural.

Above is a screenshot from a visual version of the genetic algorithm I created in C.  I used OpenGL to visualize the movements the robots would take, allowing me to change and debug the path planning code without interference from the robotics half of the project.  After realizing my algorithm could not fit on the extremely limited space of our chip, I used SWIG to generate wrapper code with which my C code could be compiled into a DLL to by called from within Python.  I then wrote a front-end in Python which used pySerial to communicate with the robot via an emulated serial port across USB.  The Python code could import and use the AI code contained in the C DLL to perform the pathfinding calculations.

Because of time constraints we then decided to use the OPEN-ROBOT kit which provides a complete robotics package containing the functionality we desired.  The kit is nearly what we had hoped to build ourselves but just did not have the time to actually do so.  The OPEN-ROBOT also comes with open source C# code for communicating with the robot, so I ported all of my AI C code and front-end python code to C#.

In the end, the task of fine-tuning the robot vision and movement was harder than we had anticipated.  The pathfinding algorithm I developed successfully generates optimal, or nearly so, paths which the robot can then execute.  The main problems stem from localizing the robot in its environment and accurate vision and movement.  After several paths have been followed, noise from the robots vision coupled with problems with localization cause the robot to “get lost” in the environment.  Although the code and paper have been turned in and several presentations given, we are planning to continue work on this project in hope of meeting the original goals.  My final paper for the project can be found here, while our poster for one of the presentations can be found here.