Simulating the emergent behavior of ant colonies

http://practicingruby.com/articles/ant-colony-simulation

by nithinbekal • 12 years ago

34 9 12 years ago

sandal3• 12 years ago

I run practicingruby.com and wrote this article, happy to answer any questions!

sbspalding• 12 years ago

This is pretty cool, it's one of those "classic" problems in AI/Machine intelligence. I remember working on a slightly less interesting version of this a few (many) years back when I was trying to model a swarm. That was a hardware project, but the basic structure is near identical.

SeoxyS• 12 years ago

The thing I'm most curious about is how to get this working within more "natural" constraints: i.e., ants in real life can't emit pheromones on their entire path history, only their current location. Is there a way to still successfully run this simulation taking that constraint into consideration?

sandal3• 12 years ago

It would definitely be interesting to do that! I had originally started out wanting to do something as natural as possible, but got myself into all sorts of frustrating trouble with ants getting turned around or wandering off forever. I'm fairly sure these were just failures in implementation, but they forced me towards looking at slightly more artificial designs.

The Ruby-based simulator discussed in this article used Rich Hickey's Clojure ant simulator as a starting point: https://gist.github.com/spacemanaki/1093917

Hickey's simulator was perhaps a bit closer to what you are looking for. It only emits one type of pheremone, which it releases on a continuous basis.

In my simulation, I introduced two types of pheremones: one emitted when food was found, and another emitted when the home was found. In retrospect, I possibly could have continuously emitted the "food" pheremone when traveling outbound, and the "home" pheremone when traveling inbound. I can't remember if I tried that and ran into trouble, or just didn't think of the idea at the time I was building this.

I vaguely remember choosing to implement things this way because it eliminated the noise generated by ants wandering in circles endlessly, but I honestly can't remember why I decided to "improve upon" Hickey's simulator.

It's worth pointing out that though the behavior of the world is very artificial (the whole trail gets marked at once after a complete path is run), the behavior of the ants themselves still only relies on their immediate location. And because these ants don't know where "home" is, they're even dumber than real ants that actually do have some sense of direction.

Anyway, refinements on this simulator or links to other simulations that illustrate these ideas are absolutely welcome! I'd definitely update the article if we found a way to improve upon what I've done.

hughlomas2• 12 years ago

I loved reading this because I made something exceedingly similar a few years ago, and I'm similarly fascinated with how complex behavior can emerge from such simple rules.

https://www.youtube.com/watch?v=VsHc91IhzdI

My ants also had no conception of where their home was located, their behavior is entirely pheromone driven. They can "read" pheromones from any adjacent cell.

They leave a pheromone every movement depending on which state they are in, either "find food" or "return food".

In my system, the pheromones have a strength. Whenever an ant touches the nest, his "nest pheromone" is at full strength (255). Each movement decreases the strength by 1. This sets up a natural gradient of nest strength for ants to follow. They also "deteriorate" each round as yours do.

A similar setup is used with food, such that a high food scent is created when they pick up food, and decreases in strength as they return to the nest.

So to find food, they try to move up a food gradient or down the nest gradient (away from the nest), while to return food they move up the nest gradient (towards the nest).

Their searching consists of a random walking into cells that have no nest scent, or following a food trail.

They have an energy cost for moving, and if it's too low they have to eat a piece of food. Returning a piece of food to the hill spawns a new ant. The lines on the right side show the population of each colony and the total food on the board.

From these extremely basic rules, they are very efficient at clearing the "world" of food.

GenerocUsername• 12 years ago

Of course! The same way ants do it! Perhaps ants leave a small trail while exploring, and then upon finding food, follow their own trail home while leaving a stronger trail.

This would cause lots of smaller weaker trails, and the occasional strong trail.

Ants out looking for food would follow trails with chances of deviating from the trail based inversely on the strength of the trail. Meaning food sources would get more attention than the random dead-end trails.

Scaevolus• 12 years ago

SimAnt (Maxis, 1991) follows this strategy extensively. Ants wander around, dropping different pheromones (food, alarm, ...) and exhibiting surprisingly complex behavior for an RTS of the time.

Simulating the emergent behavior of ant colonies

Related Stories