Evolving Coordination in Multi-Agent Systems

This work is centering around a simple artificial world, where I want to study the complexity that arises from the interaction between agents and their environment. I don't believe that an agent needs to be complex in order for it to exhibit an interesting behavior. Nor do I believe that interesting behavior stems from a complex environment. But it's the interaction between the two - where the agents are able to effect the environment as well as react to changes in the environment. If one creates a model with a sufficiently rich enviroment, the behavior of the individuals in it becomes interesting very quickly. This view was inspired by Herb Simon's ant on the beach in his book The Sciences of the Artificial and Valentino Braitenberg's Vehicles.

The work has taken on several versions - I'll try and keep this updated to reflect the status of my work. What follows here is a chronological listing of my research where I'll share with you what motivated me from step to step...

A heterogeneous model
This was my first attempt. I was trying to explore the origins of language for a natural language processing course I was enrolled in. What was it in the world that could have served as motivation for language? I figured that food and danger were the esential parts of the environment and created a model world with exactly that. In the simulated world, there are generic good areas (which increase an agent's life) and generic bad ares (decrease the agent's life). I've picked up the habint of referring to these as food and fire. Of course, the world also has the agents themselves.

I started with agents whose genetic encoding was randomly generated, in the hopes that the population would converge upon a successful set of behaviors. This didn't happen. With the randomly generated populations, there was too much noise in the environment and al the signals generated by the populations did not contain any information.

A homogeneous model
Inspired by animal societies, I generated a model that used homogeneous populations. In animal societies, the communicating agents were closely related and acting on either instinct or habits learned at a very young age from the elders they had direct contact with. The society did not converge upon a solution during their own lifetime, the solution was evolved. Also, their behavior involved more than one type of call or signal - so now I had some ideas for the types of behavior to look for. Notice that says look for - not design...it's something that I'm trying to stick to, where I only design the world - not the behavior within it. And then study the types of behavior that are generated or successful within the model world.

So I re-worked the genetic algorithm. Fitness was now the average lifespan of a homogeneous population of agents in the artificial world - group selection. This model developed a foraging call, but no other useful calls. Since the alarm calls were quite popular in the animal societies, something in their environment was motivating it. The enviroment was just not threatening enough for an alarm call to be useful. I added a hardwired predator object to the world. It could see better and was a little faster - giving it an advantage over the agents. If the agents didn't behave intelligently, they would die out rather quickly.

The predators motivated several new types of group behavior. The first was a general recruitment call. A signal was emitted whenever food was found or a predator was seen. The response to the signal was to orient towards it. This doesn't seem to make sense in the case of the predator, but since the predators are so simple minded, they are easy to confuse. If there are several agents for a predator to choose from, it has difficulty tracking a particular agent. Indeed, this happens in nature as well and is referred to as the "confusion effect". Fish school and animals flock/herd for these reasons. Only when an individual leaves the pack does it become easy to track. In the model, what happens often is that the predator gets lured to the edge of the pack and then loses the pack entirely. Another advantage to this behavior is that the damage that a predator would inflict upon an agent would get distributed amoung the agents in the flock.

Another behavior separates the two situations (food and predator) into two different signals. Where the predator signal is oriented away from. This can provide a small advantage in survival rates. What is more interesting was that there was a behavior set found that propogated the alarm call (if it is heard, start emitting it). This served as a way of spreading the signal out even further, providing a better warning. The sensitivity of this system to the population density and the auditory range is currently being studied.

This model is available in an online Java applet. Use the button below to bring up the artificial world. Right now, there are only demos available. I hope to open up the model for you to explore more thoroughly in the future - just that if I have to choose between tweaking the program for my own research or messing around with the user interface for the general public, well, I'm a little selfish. Soon though, soon. Soon is almost here.

Each demo button is meant to display an interesting behavior -

Smart Random Walk
These agents don't communicate - they just do a random walk but are smart enough to stop once they find a good spot. And to turn when they see a bad spot. It's not too successful, since they pretty much have to find the food by using blind luck.
The agents now use a call when they find food. They will orient towards the signal if they hear it. This really helps them find food and extend their lifetime.
Here are the predators that I introduced to the world. I've put in some stationary agents so you can see how effective the predators are.
Foraging II
The foraging model, but with mobile predators.
Here, the agents are responding to the predators. When the agents encounter a predator, they emit the same signal that they emit when food is found. This sounds odd, but watch it in action.
Alarm calls
Now the agents use two different calls to distinguish between the food and the predators. They orient towards the food calls and away from the predator calls.
Here, the alarm calls are propogated (if you hear one, emit one).