Competition 2003: Emergent Behavior

 

Results are now in! Click HERE

 

The theme for this year’s competition is Emergent Behavior. The winner will receive a hot-off-the-press copy of AI Game Programming Wisdom 2.

Emergent behavior is behavior that looks complex and/or purposeful to the observer but is actually derived spontaneously from fairly simple rules. The lower level entities following the rules have no idea of the bigger picture, they are only aware of themselves and maybe a few of their neighbors. Emergent behavior can be found everywhere, from the shoaling habits of fish and ant foraging behavior to the ebbs and flows of traffic tailbacks and the growth of animal societies. You can find descriptions of a couple of examples of emergent behavior immediately after the rules.

Rules

1. A Win32 executable must be submitted by October 31st.  The theme of your program must be “Emergent Behavior”.  Your program can run in either a windowed application, a DOS like console or a Java applet. Please first email your intent to enter the competition and your submissions to: emergence_at_ai-junkie.com.

2. Your program can be written in any language you desire but you must submit the source along with the executable and you must submit a write-up giving a description of the rules/techniques you have used consisting of not less than 250 words.

3. You are allowed to use any third party libraries or APIs you like.

4. There must be a minimum of three entrants for the competition to be judged. 

5. Each submission will be judged by each competitor. Judging will take place from the 1st Nov to the 30th Nov. Marks will be awarded for originality, technique, ‘entertainment value’ and presentation. If a competitor fails to do his/her judging duty, he/she will forfeit their entry. In the event of a tie, I get to choose the winner.

6. The winner will be announced in the week ending 7th Dec. The winner will be sent, by post,  a copy of AI Game Programming Wisdom 2 as soon as this is in print (I’ve been told that will be sometime in December).

7. The losers shall gaze upon the winning entry and writhe around in eternal torment and jealousy.

You can discuss these rules and any aspect of the competition at the ai-junkie forum, which you can find here.

 

Examples of Emergent Behavior

Following are the descriptions of two different mechanisms that produce emergent behavior. The first describes behavior arising from groups of entities that have awareness of one another. The second describes emergent behavior arising from groups of entities that have no awareness of any others in the group.

Flocking

Flocking is a beautiful demonstration of emergent behavior. Amongst the programming community it’s also probably the best know. It was discovered by Craig Reynolds, a researcher presently working for Sony’s R&D dept. Craig was interested in the way birds flock together and discovered that you can obtain very similar behavior with virtual ‘Boids’ if they followed these three simple rules:

Separation is a rule that steers a Boid away from those in its neighborhood region. When applied to a number of Boids they will spread out trying to maximize their distance from every other Boid. (In the same way that people spread out on a beach).

Alignment attempts to keep a Boid’s heading aligned with its neighbors.

Cohesion acts to keep a group of Boids together. A sheep running after its flock is demonstrating cohesive behavior

The figure below  illustrates each behavior. The grey circle represents the white Boid’s ‘neighborhood region’. This is effectively it’s perceptive horizon, and it will only consider the Boids laying within this area when applying each rule.

 

 

I have created a program, Big_Shoal, which you can download and play with. It shows a large shoal of 300 ‘fish’ being wary of a larger wandering ‘shark’. It allows you to adjust the magnitudes of each rule so you can see how they affect the shoal’s behavior. (Please note that the ‘fear’ of the shark is produced by another of Craig Reynolds’ rules: Evade. This does not have any effect on the flocking behavior, but it sure makes the demo a lot more fun to watch!)

 

Frisbee Clustering

Another good example of emergence is an experiment undertaken by Chris Melhuish and Owen Holland at the University of the West of England. Melhuish & Holland are interested in stigmergy, the field of science partly occupied with emergent behavior in social insects like ants, termites and bees. They became interested in the way ants gather their dead, eggs and other material into piles, and specifically the ant Leptothorax, because it lives amongst the cracks in rocks and operates, for all intents and purposes, in 2D… just like a wheeled robot. When observing Leptothorax in their laboratory, bustling about in their simulated crack -- two sheets of glass,  they noticed the ants had a tendency to push small granules of rock-material together into clusters, and wondered if he could design robots capable of doing the same.

After a little sweat and toil they managed to create robots operating on very simple rules, capable of gathering randomly scattered frisbees into clusters. The robots had no knowledge of each other and didn’t know what a cluster, or even a frisbee, was. They couldn’t even see the frisbees. They could only  push frisbees using a U shaped arm situated in front of them.

So how does the clustering behavior happen? Well, when the robots are switched on, they wander about until they bump into a frisbee. A single frisbee doesn’t change a robot’s behavior. However, when a frisbee pushing robot bumps into a second frisbee, it immediately leaves the two frisbees where they are, backs up a little, rotates by a random amount and then wanders off again. Using just these simple rules and a little time, a few robots will push all the frisbees into several large clusters. Just like the ants pushing rock granules into piles.

 


 

Home