Posted by ljmacphee on June 23, 2008 under source code | 
The SantaFe Trail is a textbook beginner’s problem in genetic programming. The ants are allowed to turn right or left or to move forward. Ants can see food if it is directly in front of them. The Trail is the one in the image above and it is also in the source code.
Ants follow two finite state machines, one if it sees food, another if it does not see food. Optimally the see food machine would only have move forward. But we let nature decide that.
Ants are created, given a random set of instructions and move one instruction each cycle. Then entire swarm moves a given number of cycles, then a new generation is born. The top half of the food finders in the generation mate. One mate contributes the ’see food’ states, one the ‘doesn’t see food states’ and one move is randomly changed in each string of moves. The population is kept at a constant number.
Source Code:
Santa Fe Ants ( Java )
Papers:
Cartesian Genetic Programming (pdf )
Selection in massively Parallel Genetic Algorithms
Ant Algorithms for Discrete Optimization
See also:
Evolutionary AI
Posted by ljmacphee on March 6, 2008 under cool open source ai projects, source code |
Polyworld is an evolutionary environment with simulated physics that allows you create creatures that will evolve. The creatures are free form neural networks. It was created by Larry Yaeger. They will learn to find food, become or hunt prey and mate and have children. It is open source, code is available at Source Forge ( link below ) and it does have versions for Windows, Linux and OSX.
Although we have had great success solving toy problems in artificial environments evolved creatures in virtual environments haven’t found great success in solving real world problems yet.
PolyWorld is a computational ecology that I developed to explore issues in Artificial Life. Simulated organisms reproduce sexually, fight and kill and eat each other, eat the food that grows throughout the world, and either develop successful strategies for survival or die. An organism’s entire behavioral suite (move, turn, attack, eat, mate, light) is controlled by its neural network “brain”. Each brain’s architecture–it’s neural wiring diagram–is determined from its genetic code, in terms of number, size, and composition of neural clusters (excitatory and inhibitory neurons) and the types of connections between those clusters (connection density and topological mapping). Synaptic efficacy is modulated via Hebbian learning, so, in principle, the organisms have the ability to learn during the course of their lifetimes. The organisms perceive their world through a sense of vision, provided by a computer graphic rendering of the world from each organism’s point of view. The organisms’ physiologies are also encoded genetically, so both brain and body, and thus all components of behavior, evolve over multiple generations. A variety of “species”, with varying individual and group survival strategies have emerged in various simulations, displaying such complex ethological behaviors as swarming/flocking, foraging, and attack avoidance.” ( introduction to PolyWorld: Life in a new context ( link below ))
More information:
Poly’s world
Download source code for PolyWorld
Papers:
Polyworld, Yaeger ( pdf)
Computational Genetics, Physiology, Metabolism, Neural Systems, Vision and Behavior or PolyWorld: Life in a new context ( pdf)
You Tube:
PolyWorld: Google Tech Talks
Posted by ljmacphee on February 27, 2008 under game ai, source code |
I am finishing up my reading of ‘The Magic Machine: A Handbook of Computer Sorcery
‘ and there were only two programs left to write. I thought I’d wipe the first one out in a day. Heh, it took three.
In a chapter of the book the author discusses early attempts at genetically evolving artificial life. He gives a rough algorithm and states he had all kinds of critters running around in just a few hundred generations. I loosely wrote a program based on his algorithm. 150,000+ cycles, and 36 hours on my computer later, no evolution. I don’t know how he did it? I couldn’t get the algorithm in the book to produce any interesting results.
I did today get a program that has bugs that learn to stay on and follow food lines drawn in the window. It takes about 1500 days ( cycles ) for them to achieve this universally. The source code is linked to below.
Here’s what I learned in my attempts at a very simple genetic program.
If you place food randomly there is nothing to learn. You just end up with a population of stupid bugs. Adjusting the food nutrient content worked better than adjusting the amount of food for controlling population levels and for evolution. Creating more food to meet the population just created lots of stupid bugs. ( I wonder if there is a real life lesson in that? )
If you adjust the bugs DNA when they find food, not just their energy levels they learn much faster.
I hope to do some more complex and interesting evolution programs soon.
Source Code:
Bugs.java
See also
Evolutionary AI for more information and several useful links and papers to get you started.
SantaFe Ants
Posted by ljmacphee on February 13, 2008 under source code |
I’ve covered a fair bit of simulations of people in news stories and recently read a chapter on people simulations in ‘ The Magic Machine: A Handbook of Computer Sorcery‘ and thought it was time to try a simple simulation.
This source code simulates 3 groups at a party. One group has a personal comfort zone of 1 foot, one group a zone of two feet and one a zone of three feet. Each group is a different color. The people start in random locations. As the party progresses and people move about they try to keep other people at their personal comfort zone. Each person moves to the square nearest himself that maximizes the comfort zone for himself. If that is not possible the person moves to a random spot ( mingles ).
If you deduct happiness from a person when they are crowded or lonely they move more than if no happiness points are deducted. They mingle more, deducting no points the crowd is more likely to form groups.
The code is heavily commented and should be easy to follow, source code is in Java.
party.tar.gz
Posted by ljmacphee on January 21, 2008 under source code, topics in artificial intelligence |
Synthetic psychology is a field where biological behavior is synthesized rather than analyzed. The father of such behavior Valentino Braitenberg ( home page ) did some interesting work with toy vehicles in the 1986 book “Vehicles: Experiments in Synthetic Psychology
“.
The Braitenberg vehicles were simple toy cars with light sensors as headlights. In some cars the wire for each headlight went to the real wheel directly behind it, in some the wires went to the opposite back wheel. The headlight receptors were aimed slightly off to the outside. The more light received by a receptor the faster the wheel wired to that receptor would turn.
Each vehicle exhibited realistic behavior when placed in a plane with several randomly placed light sources. A vehicle wired straight back when placed near a light source will then rush towards the light veering off as it gets closer to the light. As it gets more distant from the light sources the vehicle slows down. The reason is the wheel receiving the most light spins fastest turning the car away from the light source.
The vehicle with the crossed wires will turn and drive towards the brightest light in its field of view. The closer it gets, the faster it goes eventually running into the light.
Pretty interesting behavior from a very simple machine. But what if we add in a neurode to each wire and instead of a plain wire we use a wire that inhibits signals? Neurodes are set to only fire if they receive signals over a certain threshold. In this case zero is to be our threshold. So now our cars send signals to the wheels if there is no light, and do not send a signal if there is a light. Now the vehicle with the wires straight back moves toward a light and slows as it approaches, facing the light. The second vehicle now avoids light sources, speeding off to the darkest corner it can find.
So what has this all to do with current artificial intelligence? Some of our best stuff right now came from earlier work that was done and stopped. Some of our best mathematical algorithms come from extremely early math. And to remind you ( and me ) that simple rules can create very complex behavior in game characters and artificial life forms.
Four neurode versions of these vehicles have been built and they will exhibit more complex, non-linear behavior. “The question of whether a computer can think is no more interesting than the question of whether a submarine can swim.” (Edsger Dijkstra) At what point does the behavior become realist enough to be considered a life form?
Source Code:
Java simulation of Braitenberg Vehicles
More information:
Braitenberg Vehicles ( Java and Lisp simulators here )
Another simulation and pseudocode code here
Papers:
Robotics as an educational tool ( CiteSeer )
Swarm modelling. The use of Swarm Intelligence to generate architectural form. ( pdf)