SAND

SAND 2013: The Art Beyond Technology

"The Potential Growth of Emergent Behaviour from an Ant Foraging Algorithm"

http://nunbrums.com/thesandlecture
Rubrum Nuncios

Friday 15th November at 15.50

Rubrum Nuncios

This lecture script is intended to accompany the lecture demonstration available on:-
www. http://nunbrums.com/thesandlecture
The page numbers in this script highlighted in orange refer to the page numbers of the lecture demonstration which can be found on the bottom strap line on the far right of the Unity player screen.



Of Interest to:-

Game developers, visual effects designers, technical directors and procedural animation/motion designers.


Abstract:

Emergent behaviour is that which arises from simple rules followed by individuals but does not involve any central coordination.   In 1992 Henry Lutman wrote a computer programme in LISP that would simulate the activities of leaf cutting ants for the primary role of reproducing insect crowd scenes for TV and Film use.   It's first use was in generating a title sequence for a natural history programme in the "The Natural World" series called "The Little Creatures who Run the World" aired on the BBC on 28th February 1993.   A modified version was later used in a Channel 4 production about extra-terrestrial life forms which was a great success and demonstrated the power of procedural animation over more traditional methods and hinted at the possibilities of emergent behaviour.
Since then the algorithm has been refined and has revealed some interesting side effects which focus on social issues.   It has now been put to work in the promotion of domestic recycling in the form of a web based interactive game.
This lecture reveals the background, to the project, the problems encountered and the benefits of playing god over a lower order of synthetic species and how they may help with our future.




Contents:

Supporting Material and if you want to have a go.
Introduction.
Historical context and why ants?
The Forage Programme Core Function
Time to Think and what Walt Disney said.
Fetch and Carry Flow Chart.
The Collision Flow Chart.
The Imminent Collision Flow Chart.
The Collision Avoidance Theory.
The first evidence of emergent behaviour.
Pheromone Trails
. Pheromone Trails with obstructions.
Pheromone Trails and more strange behaviour
Fetch and Carry Flow Chart
Fetch and Carry: Obstinacy and Group Inefficiency
Fetch and Carry: A Flexible Approach
Fetch and Carry: The Reservation Method




Supporting Material and if you want to have a go.

If you want to have a go yourself with the "unity" demonstrations displayed in this lecture then you can by going to the following website www. http://nunbrums.com/thesandlecture.   Unfortunately they are only available on a Web browser and not available on ipads or Android devices yet.   By interactively changing the position of the pheromone trail markers, leaves or nest locations, you can run unique tests for yourself to find new emergent behaviours of your own.
You can also view the lecture script on this site.   For these demonstrations, Unity is used as a real time renderer and programming environment.   The ant acting animation is not powered by Unity but by look up tables written in Unity JavaScript.



Introduction.

Emergent behaviour is that which arises from simple rules followed by individuals but does not involve any central coordination.
Emergent behaviour is where complex global behaviour can arise from the interaction of simple local rules.
One individual on its own doesn't show much promise. Put a hundred individuals together and things can happen that can go beyond just the sum of the component parts.




A Flock of Birds

A common example of emergent behaviour is the Flocking or Swarming of birds where the flock forms an ordered and seemingly coordinated flight pattern without any obvious explanation.
Emergent behaviour can NOT always be easily explained or easily predicted from the rules imposed on its participating individuals.
Emergent behaviour can be mistaken for that brought about by a supervisory or management system.
A large flock of birds seem to coordinate their flight when they swoop and circle in the sky.  Is there one bird in charge of the rest, like squadron leader, one bird that controls the choreography of their flight?   Well according to experts, there isn't.   Each bird is of equal status but follows a simple set of rules.
Today we are not looking at emergent behaviour from flocks of birds but a terrestrial creature that has been around in its present form for 100 million years. The ant.   (Humans have only been around 2.4 million years)   We are not going look at just any species of ant but one that has been around for just 23 years.   It is a synthetic species called "Rubrum Nuncii" (Latin for the "Red Messengers") and they were developed for my own amusement and research.
The "Forage Algorithm" is my name for an ant behaviour simulator which I devised some years ago and will show you today.
Part of this lecture is about the quest for "Emergent Behaviour" from this ant simulator and because I don't want you to think that I am cheating, I want you to understand the basic way the "forage algorithm" works so that if behaviour does emerge for which there is no or easy explanation, then you know that it has not been contrived through sleight of hand or programming trickery.
Later on we will be looking at ways in which ants behaviour actually helps solve logistical, management and communication problems in our complex technological world.



Historical Context and Why Ants?

GO TO PAGE 1 Waiting for Action

In the 1990s I was working on a 3D computer system called "Symbolics".  This system had a LISP based operating system (derived from "LISt Processing"), which, at that time, had a very unique object orientated operating system which meant that it was accessible to reprogramming or programme extensions without the need for a large depth of knowledge, compilers or other complicated tools.
One of the software developers who were responsible for creating the "Symbolics" was Craig Reynolds, who advocated the possibilities that LISP offered.   In 1986, Craig wrote a programme in LISP to simulate the flocking behaviour of birds in flight and it was regarded as a milestone in procedural animation technique.   He called it Boids, a Distributed Behavioural Model.  With his inspiration and hungry for power over my very own species for whom there would be only one god I decided I would attempt a Behavioural Model of my own.

Why ants? They are easy to study and the ones I see even come into the kitchen and run around on the work tops therefore yielding easy access to their busy activities.   When I first wrote this forage programme I did not devise any rules to start with.   The primary activity of an ant is to fetch and carry.   Like an Eddie Stobart lorry, the ant was primarily concerned with picking up a load and delivering it somewhere then picking up another load and carrying that somewhere and doing the same thing over and over again.



The Forage Programme Core Function. We will now explore the "Forage Algorithm" and find out how it works.

GO TO PAGE 2 Finding a Goal by Navigation, Steering and Locomotion

This first demo shows goal seeking in its raw form.   Every now and again the ant will try to work out the distance and bearing of the desired goal.  From these calculations it will attempt to steer towards it.   It breaks down into three distinct parts.

Allocate a Goal (depending on the Task.)
then "Think" about how to reach the goal. "Think" is about navigation.
then "Proceed" towards the goal.

Allocate a Goal (depending on the Task).
The foraging programme relies on allocating a task to each insect, (the insect's "Current Task")
Depending on what this "Current Task" is defines what type of goal is allocated to the ant.   Types of goal include food particles, a nest locations, or pheromone trail markers. The final choice of goal is usually made by the insect choosing the nearest one to its own proximity. Once a goal is allocated then the insect will think about where the goal is, then proceed towards it. In this example the goal is fixed.

"Think" about how to reach the goal. "Think" is about navigation.
Make calculations on how to reach the goal.
This is done by calculating a new required bearing.
AND calculating a new required distance to reach the goal.
Once these simple calculations have been achieved then the insect can proceed.
Think involves calculating a new "Required Bearing".
Think involves calculating a new "Required Distance".

"Proceed" towards the goal.
The insect will rotate incrementally towards the "Required Bearing" and move in a forward direction incrementally until the "Required Distance" has been achieved.
If the Current Bearing equals the Required Bearing you are going in the right direction.
If the Required Distance is zero then you might have arrived.
"Proceed" is continually repeated (looped through) until the Current Bearing equals the Required Bearing and the Required Distance reaches zero.

GO TO PAGE 3 The Forage Programme Core Function - PROCEED = Steering and Locomotion

GO TO PAGE 4 The Forage Programme Core Function - THINKING = Navigation

The flow cycle is then repeated (looped through), starting back with "Think" until the goal is reached within an acceptable margin of error.



Time to Think and What Walt Disney Said.

GO TO PAGE 5 Time to Think (Doing Nothing)

Walt Disney said, "In most instances, the driving forces behind the action are the mood, the personality, the attitude of the character-or all three.   Therefore, the mind is the pilot.  We think of things before the body does them."
With that in mind each time the insect makes a navigational calculation about where it can find its goal ("Think"), I inject a pause in insects movement.   This gives the impression that it is thinking about where to go next, thus projecting the Disney theory that thinking before an action helps to project a living character.  This particular demo uses a random thinking time of between 250 and 500 milliseconds.   I must point out that this is the only piece of contrived behaviour imposed on this programme.

When we introduce more than one creature it becomes clear that we must stop them running through each other.   Real ants don't intersect so my synthetic ones shouldn't either.



When we introduce more than one creature it becomes clear that we must stop them running through each other.   Real ants don't intersect so my synthetic ones shouldn't either.

GO TO PAGE 6 The Collision Flow Chart

The Collision Flow Chart:

I use three strategies to stop ant intersection (three ways to stop collisions).
The first is when an ant comes head to head with an obstruction, usually another ant.   When this happens the ant will stop locomotion.   It will stand still and wait to see if the blockage clears.   If, after waiting, there is no longer a blockage then the ant can proceed on its intended path to goal.   If, after waiting there is still a blockage then it instigates its second strategy which is to take evasive active by choosing a new bearing to avoid the obstruction.   There is also a third strategy explained in the next section.



GO TO PAGE 7 The Imminent Collision Flow Chart

The Imminent Collision Flow Chart:

The third strategy is to try and avoid bumping in to things in the first place.   I call this "Avoiding Imminent Collision".   If there is an obstacle in front of you then gently steer away from it so that you can keep out of trouble.
Later I will be talking about the ants following pheromone trials and when they do then the "Imminent Collision" detection is turned off and only the first two strategies are used.
Both "Collision" and "Imminent Collision" detection are embedded in the "Proceed" part of the "Forage Programme Core Function"



GO TO PAGE 8 The Collision Avoidance Theory

The Collision Avoidance Theory:

Here you can see the collision mechanisms in action.
Close collision currently uses a current Field of Vision setting of around 100 degrees and any obstruction within 2.5 units (two and a half ants) distance is detected and an avoidance angle calculated.
Imminent collision currently uses a current Field of Vision of just 40 degree and any obstruction within 6 units (six ants) distance is detected and an avoidance angle calculated.



GO TO PAGE 9 The first evidence of emergent behaviour.

The First Evidence of Emergent Behaviour.

As you can see, this really complicates things for the ants as they now have to spend time trying not to bump in to each other.   If we keep the leaf goal still for a reasonable time, the ants will gather almost uniformly around the goal.   There is nothing written in the programme to say that the ants should do this when sharing a goal.
At this moment we are only employing the "Forage Programme Core Function" with the addition of the three anti-collision strategies placed within the "Proceed" part of the programme.

I have not explained to them the concept of "Gathering Round".
The decision to walk around the outside of the circle until a suitable space is available to reach the leaf is an emergent behaviour.   I haven't told them to do that, but it is caused the anti-collision strategies imposed on each of these individuals.

Let us now try and find some other emergent behaviour.



Pheromone Trails.

Real ants use pheromone trials for communication in number of ways.   One reason they down a pheromone trial is so that other ants can follow it.   My experimental ants do not lay trails yet but they do follow them.

GO TO PAGE 10 Pheromone Trails.Twelve is a Crowd.

I use a series of numbered markers to represent the pheromone trail.   The ant treats each one as a goal and must visit each one in turn.   This example uses a trail which is circular and the ants are forever locked in an everlasting route which is never ending.  This example uses a team of twelve ants which gives the impression that the trail is over-crowded.

GO TO PAGE 11 Pheromone Trails. Changing Search Tolerance.

Revealing the markers you may notice that some are bigger than others.   Each marker has an individual tolerance which is a radius (or perimeter) which the ant must reach.   A marker with a tolerance of 0.1, means that an ant must visit almost the very centre of the marker before going on to the next.   A marker with a larger tolerance of for example 6 units only requires the ant to reach within 6 units of the centre before going on to the next.
In this eight ant example, the markers at the back are set to 6 units and the ones to the front are set to 2.
As you can gather, the ants are perfectly happy going round even through the tight sections.
Notice how the ants eventually find an equilibrium and become reasonably spaced around the circle even though they started on the trail all bunched together. Is this more evidence of emergent behaviour?



Pheromone Trails with Obstructions.

GO TO PAGE 12 Pheromone Trails with obstructions.

In this example there are two dead ants which are in the way of the others.   There is a little bit of tension building up.   Please note that at marker three the ants always go to the inside even though there is more space on the outside.   At marker nine, however, the ants go either side. I would not have predicted this before running the test.



Pheromone Trails. A cause of Frustration.

GO TO PAGE 13 Pheromone Trails with obstructions.

The ants seem to become agitated because of one ant that is slower than the rest.   They seem not to able to overtake the slow ant or at least not very often, but do succeed in overtaking each other.   This is not the result that I expected but thought the fast ants would overtake the slow ant at regular intervals but the fast ants are more interested in overtaking each other.



Fetch and Carry Flow Chart.

GO TO PAGE 14 Fetch and Carry Flow Chart.

This is the flow chart of the "fetch and Carry" programme.   It is this part of the programme that is responsible for choosing the next ant goal and is the programme that oversees the "Forage Programme Core Function".   When I originally wrote this in LISP, this programme flow and the "Forage Programme Core Function" was all there was apart from the acting subroutines.   By "acting" I mean the leg motions and other body functions that are added to the character.
You can see form this flow chart that there are only five possible outcomes which makes this flow simple.   If there is nothing doing (nothing to find or nothing pick up or put down) then "Do End Behaviour" which can be a number of things.   I used to give them random directions and random distances so that they would look busy and eventually run out of view.   In this set of demonstrations their End Behaviour is to go to their individual muster points and wait patiently, for ever.   If an ant is not carrying food then it must either be looking for some, or it has found a piece and is ready to pick it up.   Equally, if an ant is currently carrying food, then it must either be looking for a place to put it (a nest location) or it has found a nest location and is ready to put the food down.

As you can probably see for yourself, a single ant is happy to fetch and carry.
Introduce more than one ant and we immediately introduce new problems that have to be addressed by looking at issues of ownership of both food and nest locations.



Fetch and Carry: Obstinacy and Group Inefficiency

GO TO PAGE 15 The fetch and Carry: Works well when goals or not in contention.

By looking just at two ants, we can examine their relationship with each other and the other elements.   You can see that as well as food represented by these leaves, the ants also have nest locations represented by these crosses which I normally keep hidden.   These nest locations are where the ant is required to deposit its food.
Each ant chooses a food goal nearest too them, picks it up and then travels to the nearest nest location.   At the location the ant puts down the food.
This works is fine as long as each ant has chosen a different goal.   In this example the ants initially choose different leaf goals and then, in turn, choose different nest location goals but this is pure chance.

Incidentally, the red crosses are "muster" points where each ant is required to go when its task is finished. (the "End Behaviour")

GO TO PAGE 16 The fetch and Carry: Obstinacy and Group Inefficiency.

The problem comes when they both choose the same goal.   This produces an inefficient work flow but a very interesting "Emergent Behaviour" which I identify as anti-social.

GO TO PAGE 17 The fetch and Carry: The fetch and Carry: Obstinacy and Group Inefficiency are amplified when the Team of Eight use this flow

We can illustrate this by using the same programme flow with our eight ant community.
How do we stop this terrible turmoil and agitation?
A more flexible solution to the fetch and Carry task is needed.
The solution lies in the looping structure of the Basic Forage Programme Model.
In the last example, the code loops through from "Think" through to "Proceed" without ever visiting the "Allocate Goal" until arrival at the current goal has been achieved. Only then is a new goal selected.



Fetch and Carry: A Flexible Approach

GO TO PAGE 18 The fetch and Carry: Review your goal every think cycle

In the next example when at the end of "Proceed" and the code is due to loop back to "Think" it is actually looped all the way back to "Allocate a Goal" thus allowing the ant to renew its choice of goal if its original choice has now been taken by another ant or if there is another goal that is now nearer to travel to.   This sounds an obvious solution but after this example we will look at a method that shelves the notion of goal review.
By making this simple alteration to allow allocation of goals to be reviewed in every thinking cycle, we are freeing the ants to choose a new goal if necessary at every thinking opportunity.   Instead of relentlessly sticking to their goals they now can choose a new goal if the one they were after has been taken by another ant, or if the opportunity arises when an alternative goal is nearer to get to.
This freedom, as you can see, allows the ants to carry out their fetch and carry task with great efficiency even though there is potential for conflict.   If you look at the beginning of this test, the ants move towards the same piece of leaf until one actually picks it up and takes ownership.   At that point the others will lose interest and select alterative goals.   This still leaves room for potential conflict as ants continually head for the same goals.
When we let the eight ant community do its work you see marked difference in their progress.

GO TO PAGE 19 The fetch and Carry: The Eight Review their goals every think cycle

Take a note of the time it took the ants to do their job of moving the 28 pieces of leaf.  We will need that figure in a moment.

Can we try a system where we can eliminate potential conflict altogether?



Fetch and Carry: The Reservation Method.

GO TO PAGE 20 The fetch and Carry: The Reservation Method

In this next demo I restore the loop structure of the Basic Forage Programme Model back to how it was in the first fetch and carry demo.   Once a goal is chosen, the ant is not at liberty to change it until it has been reached.   To stop the chaos ensuing again however, I change the definition of what constitutes goal ownership.   In the next demo when a goal is chosen by an ant it is immediately prevented from being chosen by any other ant.   It is rather like all the ants in the group pre-agreeing to choose different goals thus eliminating all goal conflict.
You will notice that the ants head for a different choice of goal and different nests.

I said at the beginning of this talk that I would be looking at ways in which ants behaviour actually helps solve logistical, management and communication problems in our complex technological world.   There a numerous examples where the study of real ants has solved the insolvable mainly in logistics where complex systems can be analysed by laying down virtual pheromone trails but the example I have chosen concerns Southwest Airlines.   This company had a problem with their aircraft seat bookings.   Traditionally they had always allowed their customers to board their aircraft and sit where they want on a first come first served basis.   Some customers were evidently unhappy about his arrangement and so Southwest Airlines decided to investigate different ways of getting passengers onto the plane and to try and find the fastest way of getting passengers aboard without too much conflict.   After using many types of computer simulations they eventually employed a computer programme that was based on the behaviour of ants.   Ants, after all are used to getting in and out of tight spaces. Using this programme they compared the difference in the speed in boarding a Boeing 737 between pre booked seats and a free for all first come first served system using an ant simulator.
You remember the last test we ran using the team of eight? You can regard that test as loosely being the equivalent of a free for all, first come first served simulation of boarding a 737 except our simulation is shifting leaves and not passengers.   Do you remember the time it took for them to do their job?   We are now going to run the "reservation method" which removes all conflict and relies on goal agreement across the team.   Will this prove that shifting leaves is more efficient if the opportunity for conflict is removed?   Will this prove that loading a 737 is quicker and more efficient using seat reservations?

GO TO PAGE 21 The fetch and Carry: The Eight use the Reservation Method

You can see by the timer that the result is almost the same as the previous "free for all" test.

After running their the ant simulations, Southwest Airlines also concluded that actually, there was no discernible difference in the time it took passengers to board a 737, between their methods of seat allocation. "free for all" and "reserved" seats took roughly the same amount of time.

That concludes this lecture and may I remind you that you too can experiment using the "Rubrum Nuncii" on nunbrums.com/thesandlecture.

GO TO PAGE 22 The fetch and Carry: The Eight ask for help

At no time were any ants harmed or treated poorly in the making of this talk.

Henry Lutman 03-11-2013
for SAND 2013 15th November @ 15.50