I’ve been playing with some artificial intelligence algorithms. In particular I implemented a neural network algorithm that supports networks with perceptrons and sigmoids. Using the standard back propagation algorithm I was able to train them to learn some simple tasks. That was fun because I tried implemented the same system from the same source material (Machine Learning by Tom Mitchell) while in grad school. I tried doing it in C++ and could never make it work. I spend a couple weeks working on it. When I tried again, it took about 5 hours for me to implement a working C version. Sigh.
Anyhoo, I’ve been playing with some simple 2d graphics, in this case, a computer controlled object that follows another object (computer or human controlled). I wrote a simple A.I. that manages to do a pretty good job. However I thought it might be fun to try and have a neural network controlled one.
This raises some interesting issues. In particular I don’t really have good training data to use. I could create some simple situations and teach it to do the right thing, but there is little flexibility and the odds are it won’t do to well in general situations. So I thought I’d try another A.I, technique, a genetic algorithms.
Genetic algorithms are kinda cool. You start with a set of random values, test how good they are then select a percentage of the set to maintain (with some preference to the most fit). You then replace the rest of the set by “mating” pairs of values together. In addition throw in a couple mutations to create new solutions. In then end G.A. tend to find good, but not great solutions. In my experimentation, you often end up stuck in locally optimal solutions, instead of globally optimal solution.
The nice thing about G.A. is that you don’t have to train them. Instead you test them to see how the perform, then rank them based on their performance. Thus can I can just stick them into the simulation and breed up some solutions. Of course nothing is quite that easy.
I started simple. The N.N. was stationary, and the other object traveled in a circle around the N.N. All The N.N. needed to do was point towards the circling object. It was able to learn this task really successfully. Almost surprisingly so. It was able to track the circling object with about 97% accuracy. On screen it looks perfect. Just to be clear, the circling object is not moving at a constant pace. It start off at speed zero, then accelerates to a max speed, maintains that for a little bit, then it slows down until it is circling in the opposite direction. The N.N. performed better than I expected. It is a really simple network as well. As input it takes the x, y coordinates of the other object, with the N.N. as the origin. It has one layer of 3 sigmoid units and a second layer of 3 perceptron units. The 3 outputs toggle a rotate left/right accelerator and an rotational damper.
The next step is to allow the N.N. controlled object to move. More on that to come…