Up

Simulation of Ant's Emergent Behavior Using StarLogo

This page is about a short personal project of mine to investigate emergent behavior.  To this end, I created a virtual ant colony using a piece of software called StarLogo made by some people at MIT.  The idea is that each ant alone is next to useless for gathering food efficiently, but a bunch of ants each acting on its own simple set of rules together are able to gather food much more efficiently.  This phenomenon where the group ability is greater than the sum of each individual acting alone, can be a form of emergent behavior.  An excellent book on emergent behavior is "EMERGENCE The connected lives of ants, brains, cities, and software" by Steven Johnson.  This book was recommended by a friend and inspired me to do this project.  I'll quote his definition of emergence here, from the inside flap of the book cover:

Emergence is what happens when an interconnected system of relatively simple elements self-organizes to form more intelligent, more adaptive higher-level behavior.  It's a bottom-up model; rather than being engineered by a general or a master planner, emergence begins at the ground level.  Systems that at first glance seem vastly different--ant colonies, human brains, cities, immune systems--all turn out to follow the rules of emergence.  In each of these systems, agents residing on one scale start producing behavior that lies a scale above them: ants create colonies, urbanites create neighborhoods.

Following is a screenshot of my virtual ants gathering food and bringing it back to the nest:

This may look complicated at first, but it's actually pretty simple.  If you want to see this running on your own computer, just follow these easy steps:

  1. download and install the StarLogo software from MIT.  NOTE: My software was written in version 1.2.2 of StarLogo and the current version is 2.0.  My original source was not compatible and a couple kind folks told me they were getting an error message, so I upgraded the source link below to provide a 2.0 compatible version.  I'm not sure if it will work with the 1.2.2 version anymore, so if you have that version and have trouble, I apologize, please try version 2.0.
  2. download my source code.  If this file opens in your browser, just Back up to this page, right-click and "Save Target As..." to save it on your hard disk as "ant_simulation.slogo"
  3. run StarLogo and open the my source code file that you just downloaded.  
  4. For the simplest demonstration, click the "setup" button once, and then click the "execute turn" button.  Then ants will now start running around and soon form a trail to the food.
  5. In exchange for using my source code, I simply ask a few things.  First, feel free to have fun with and make changes to the software.  Second, if you make any improvements you think I might find interesting, email me!  Third, if you think this is really cool AND you are doing interesting AI type work AND you think you could use my help AND you are in a position to hire me or get me hired, email me! :-)  

So, back to what's going on in the picture: 

  • Ant individuals- the red and blue dots are the individual ants.  Red colored ants have come from the nest and are looking for food.  Blue ants have food and are looking for the nest to deposit the food.
  • Scent trails- ants leaving the nest leave a decaying trail of "nest scent", these are the red lines.  When an ant looking for the nest comes upon a trail like this, she (ant workers are female, don't you know?) knows that if she follows it she will eventually end up at the nest.  Same goes for the blue food trails.
  • The nest- the hub of the red nest scent trails is the nest.  Ants come from the nest and return there to deposit food they have collected.
  • The food- the yellowish/green dots are food items.  Each dot has a given amount of "food points", or pieces that an ant can break off of it.  It's kind of hard to see, but the different food dots are actually slightly different in color.  The more green the dot is, the more food points are left in that piece of food.
  • The Great Food Trail- the highway that the ants have created between their nest and the food, note that it's pretty straight.

With this understanding, I'll try to explain what rules the ants follow, then how these simple rules lead to this beautiful example of emergent behavior (the nice straight food trail allowing the ants to more efficiently collect food).  If you haven't already, let me recommend that you install and run the software before continuing.  Although it is a nice screenshot if I do say so myself, it's no substitute for seeing the ants running around and building the trail- it's absolutely fascinating to watch (maybe just for me?) and it will make this coming explanation that much easier to understand.

Since I don't know where to start explaining this, what I'll do is start at the top of the application window and explain what the different buttons, sliders, and info boxes mean.  By the time I get to the bottom, it should be fairly clear what is going on (also, keep in mind the above descriptions of what the graphical display means).

  • "setup" button- this button initializes the application by cleaning up anything left over from a previous run of the application, and creating a new pile of food.  The food is disbursed at a given location with a gaussian spread.  In case "gaussian spread" is Greek to you, imagine what would happen if you dropped a handful of BBs on the ground.  They would be centered around the spot where you dropped them, but some would be further away from that center than others by random chance.  This is how the food is disbursed.  This button also creates a new nest, clears the variables from the last run, and then starts making one ant come out of the nest each second up to the set amount of ants.
  • "execute turn" button- this button tells each ant to take a "turn".  This button loops and keeps telling the ants to take another turn until you click it again and stop them.  A turn might consist of moving a step, picking up food, dropping off food, etc.
  • "debug turn" button- never mind this button, I forget what it does anyway, and it doesn't matter enough to bother trying to remember or looking through the code  :-)
  • "NumWorkers" slider- this is simply the number of ants that you want running around.  You must set this before hitting the "setup" button, i.e. once the simulation is in action you can't add more ants.
  • "NumFood" slider- this is the number of food bits you want there to be.  This also must be set before hitting the "setup" button.
  • "FoodGathered" info box- this is a display of the FoodGathered variable.  This obviously keeps track of the amount of food points the ants have brought back to the nest.  This is the performance metric I use to evaluate the quality/"genetic fitness" of a given ant population.  The "HeadingConsistency" slider and down are the settings that uniquely make an ant population function properly.  If these settings are not good then the population doesn't have a good "genetic fitness" since they can't gather much food.
  • "FoodPointsPerItem" slider- this sets the number of food points that each food piece has.  The purpose of this is to simulate ants grabbing a small piece of a chunk of food.  To put it in terms of a real piece of food, it describes how big each piece of food is and how many chunks can be taken before it is gone.
  • "HeadingConsistency" slider- if you've ever watched an ant walking around, unless they're following a trail they kind of meander about.  You can see what I mean by looking at some of the trails in the above screenshot.  To get this wandering path, every time an ant is going to take a step there is a percent chance that the ant will alter it's heading angle.  This variable is the percent chance that the ant will NOT change heading in a given turn.
  • "HeadingDegreeRandomizer" slider- after the ant uses the "HeadingConsistency" slider above and it has determined that it wants to make a heading change, it then uses this slider to help determine how much change to make.  Basically, it turns a random degree from -"HeadingDegreeRandomizer" to +"HeadingDegreeRandomizer" off its current course.  It might only turn 1 or 2 degrees left or right, or it might turn left or right for the full amount of the slider.
  • "ScentStrengthDecay" slider- when an ant is leaving the nest (or just picked up a piece of food), it drops scent indicating that it just came from the nest (or a piece of food).  As it continues moving, the strength of the scent that it is dropping should decay so that another ant coming upon the trail can tell in which direction the nest lies.  This is easiest to see in the screenshot with the blue trails, you can see that they're brighter nearest the food.  This makes sense in terms of the real behavior of ants, it is good for the strength of the scent dropped to indicate proximity to something.
  • "GroundScentDecay" slider- trails upon the ground in real life get slowly scrubbed away by the elements of wind and water.  This is actually useful to the ants since they don't want to be following old trails to food that is now gone.  So this slider determines how fast trails on the virtual ground decay.  The lower the number, the faster the decay.  This number should be greater than the "ScentStrengthDecay" value so that trails will be stronger nearer the object which they are marking.
  • "SearchDistance" slider- each time an ant takes a step, it looks in front of itself for things of interest.  This slider determines the radius in front of itself the ant can see.  It scans through this radius for -45 to +45 degrees off its current heading.  Depending on whether the ant is looking for food or the nest is what determines what kind of things it's looking for.  If it is looking for food then its first priority to look for is an actual piece of food within its scanning range, if it doesn't see any food there then it looks for a food scent trail.  If it is looking for the nest then its first priority is to look and see if the nest is right in front of it, then if it doesn't see the nest then it looks for a nest scent trail.
  • "FollowProbability" slider- when an ant sees a trail that it might be interested in, then this slider comes into play.  It determines the chance that the ant will follow the trail.  This brings up a point: the ant does not always follow a trail of the type they're looking for.  Again, if you've ever watched ants, sometimes an ant not carrying food will walk right across a trail which lead to some food.  I didn't know why this was, but after I programmed it in it became obvious why it was beneficial to the ants.  Two good reasons, first of which is that sometimes an existing trail to food or the nest is not the shortest path.  So if an ant does not always follow a trail and sometimes even leaves a trail, and then they come upon the trail again- then their trail may be the shortest one!  This is how the ants built that nice direct trail from the nest to the food!  At first the path was very curvy, but by this slider's effect, the ants that left the trail and came back on it later found a shorter path.  Due to the decay of the scent trails, shorter paths are reinforced better and have a stronger scent than a long path.  This brings up the additional factor in following a trail: the probability to follow a given trail is based on this slider AND how strong the trail is.  If it's a weak trail then the ant is less likely to follow it, and if it's a strong trail then the ant is more likely to follow it- both contributing to the building of shorter paths.  The second good reason for not always following a trail is that there may be food somewhere else (other than the current piece that they're grabbing from), and so some ants need to be out looking for another source of food.  Currently, there is no way to drop down new pieces of food, but this is a feature I'd like to add.
  • "evolve" button- this button is the last thing I added.  Since I just set the value of the sliders based on some experimentation to figure out some settings which would allow the ants to gather food in a reasonably efficient way, it's clear that the settings I used are probably not optimal.  What this button does is to run the simulation a couple times for about two minutes each, then take the average of the FoodGathered value to determine the performance of this ant population.  It then changes the "FollowProbability" slider by a small random amount, then runs the simulation two more times.  If the "FoodGathered" is greater than the previous population then it stores this new "FollowProbability" as the best and then makes another small random change and repeats.  This allows the "FollowProbability" to evolve into the best value.  Unfortunately, StarLogo is not a good program for reading and writing data which makes it very difficult to write a good genetic algorithm to modify all the sliders.  Hence the pathetic attempt at evolution which only modifies this one slider and is of course subject to local maximum mistakes.  

At this point, you should have a good idea of how this program works.  If you got this far, hopefully you are interested in playing with it some on your own.  I highly recommend running it and playing with the sliders to see how it affects the ants, note that many setting combinations will completely cripple their ability to gather food in a reasonably efficient manner so if you want to save your changes, you should do so with a new file name so that you can always restart with my settings if you can't get the ants working properly again.

Things I'd Like to Improve

Mostly, I'd like to improve the evolution of the ants from the silly little hack method I used above to evolve the "FollowProbability".  I was hoping that I could somehow have a C (or any programming language with good ability to manipulate data)  program interface with StarLogo.  This would allow the C program to do things like creating genetic trees of the slider settings since I suspect that branching the genetic paths would be necessary to find optimal combinations of settings, since the settings are related and thus there might be local minimums and maximums for a given setting in relation to another.  What I mean by this is that if you just move one setting at a time, you will find a point at which that setting is best, but if you change some other settings then the first setting may no longer be optimal.  This is why I suspect that having various branches on the chain of evolution might help discover the most efficient settings.  A C program could manage this data and make the evolutionary changes and the call the StarLogo program to run a given ant population a few times to measure its ability to gather food, the C program then can read the results and determine if the new population was an improvement or a step in the wrong direction.  

I contacted the people who wrote StarLogo to ask if they had written any hidden interface like this, but they said they had not but that they had thought about it.  This was back in October or so, and I was hoping that they'd come out with a new version including this feature by now, but so far they have not released any new updates to StarLogo since the 1.2.2 version that I got back then.  I suspect the main authors (if not everyone involved) are working on other things now.

Update: maybe StarLogo 2.0 has some provision for communicating with a language more suitable to handling the data sets to run a good evolution algorithm.  I haven't had time to look into this yet, but if anyone knows the answer I'd sure appreciate a tip. :-)

Hit Counter

You are visitor Hit Counter