[Français]
Sponsor List
|
How Ants Find Food
Many species of ants communicate with their nest-mates using chemical scents known as pheromones. Pheromones can be used in many ways by ants and other animals (including humans), but we are most interested in how ants use pheromones to direct each other through their environment---this particular task is closely related to the problem of directing the flow of information through a network.Consider a colony of ants that is searching for food. Casual observation of an ant colony will reveal that ants often walk in a straight line between their anthill and the food source. The concept of an "army" of ants marching in file has permeated popular culture, and most people who live in ant-friendly locations (nearly every human-friendly place in the world) have seen this particular behavior first-hand. Marching in a straight line, which is usually the shortest route, seems like an obvious solution to the problem of efficient food transportation, and we might pass it off as uninteresting.
Photo by Harold Thimbleby --- used without permission
Of course, we humans would do the same thing, and in fact we do march in lines along direct routes when we travel in groups as caravans. When we look down at a line of ants from above, we might simply think "so what?" But we have huge brains compared to ants, along with extraordinarily complicated visual systems (over 25% of the human brain is devoted to vision), and we also have a more elevated view of the terrain. Even with these advantages, efficient route-finding, especially through an environment that is full of obstacles, is not an easy task for us. Given ants' comparatively simpler brains, we cannot pass their collectively intelligent route-finding off as trivial. So how do they do it?
Suppose that an ant colony starts out with no information about the location food in the environment. The human strategy in this case would be to send out a "search party" to comb the surrounding area---the scouts who find food can bring some back to the home-base and inform the others about where the food is. Ants do search for food by walking randomly, which is similar to the human "combing" approach, but two issues prevent ants from implementing a human-style search party directly. First, how can an ant-scout, upon discovering food, find its way back to the nest? Second, even if a scout makes it back to the nest, how can it inform the other ants about the food's location? The answers lie in a clever use of pheromones.
To solve the "finding home" problem, each ant leaves a trail of pheromone as it looks for food. In the following example pictures, the pheromone trail left by each wandering ant is shown in transparent red.
When an ant finds food, it can follow its own pheromone trail back to the nest---this is similar to leaving a trail of bread crumbs through the woods to find your way back home. On the way back to the nest, the ant solves the "telling others" problem by laying down more pheromone, creating a trail with an even stronger scent. In the following picture, ant A reaches the food first and then follows its own trail back to the nest, while the other three ants keep wandering.
When other ants run into a trail of pheromone, they give up their own search and start following the trail. In the following picture, ant D discovers the double-strength trail left by ant A and starts to follow it. Ant C encounters the single-strength trail left by D and follows that trail, which will eventually lead to A's trail as well. Ant B eventually discovers its own route to the food source that is completely disconnected from the routed used by A.
If a pheromone trail leads an ant back to the nest with empty jaws, it turns around and follows the trail in the opposite direction. Once an ant reaches the food, it grabs a piece and turns around, following the same trail back to the nest. On the way back, an ant reinforces the trail by laying down more pheromone. In the following picture, ant C joins A's trail but follows it it the wrong direction, reaching the nest empty-jawed. Ant B follows its own trail back to the nest---it never comes in contact with the more direct trail that the other ants are using. A and D carry food back to the nest along the established route.
Once they reach the food, they grab a piece and turn around, following the same trail back to the nest. On the way back, they reinforce the trail by laying down more pheromone.
We have explained how ants find food in the first place, but how do they find the shortest route to the food? One more detail helps to answer this question: ants prefer to follow the trails with the strongest pheromone scent. Shorter routes between the nest and the food are completed faster by each ant that takes them. For example, if ant X is traveling along a 10-meter path to the food repeatedly, and ant Y is traveling along a different 20-meter path repeatedly, ant X will make twice as many trips in an hour as ant Y. Thus, ant X will lay twice as much pheromone on its trail as ant Y. Given the choice, ants will prefer the strongly-scented 10-meter path over the more weakly-scented 20-meter path. The following picture demonstrates this point. When B deposits food at the nest and sets out for another trip, it discovers the strongly-scented path used by the other ants and abandons its own path. At this point, all four ants are using the path discovered by ant A to carry food between the source and the nest.
Over time, many paths between the nest and the food are explored, but the scent on shortest path is reinforced more than the other paths, so it quickly becomes the most popular path, and soon all of the ants walk in file along it.
Simple Rules
The ant approach to route-finding is quite different from the way humans navigate their environment. We would visually study the environment as a whole and try to "plan" the best route ahead of time. Of course, the ant method has advantages over our "high level" approach. For example, the ant method works fine in complete darkness. When it comes to navigating without visual cues, humans are comparatively helpless.The ant method can be distilled into simple rules followed by each member of the colony:
| Condition: | Action: |
| Not carrying food not on pheromone trail | walk randomly lay pheromone |
| Not carrying food on pheromone trail | follow pheromone trail lay more pheromone |
| Reach home without food on pheromone trail | turn around follow trail in opposite direction |
| Reach food | pick up food turn around follow trail in opposite direction |
| Carrying food | follow trail lay more pheromone |
| Reach home with food | deposit food turn around follow trail in opposite direction |
More About Ants
As we go on to describe MUTE's ant-inspired message routing scheme, we will leave real-world ant behavior behind us. However, there is a wealth of information about natural ants and their behavior online, including:Simplifying Nature
Though the table of "Simple Rules" above is relatively easy to understand, it still contains seven rules, which is not as simple as we might like. Also, there is a bit of sub-optimal behavior lurking: an empty-jawed ant may follow a pheromone trail in the wrong direction, all the way back to the nest. Of course, when an empty-jawed ant reaches the nest, it turns around and eventually makes its way back to the food, but this is still a wasted trip. The problem seems to be the lack of directionality in the trail, and it is certainly difficult to represent direction when all you have to work with are spots of chemical scents.In the world of networking programs, we are not limited to directionless trail markers. By adding direction to the trail markers, we actually get a much simpler set of rules
Suppose that we augment the ants with two types of pheromone instead of just one, and suppose that we give these pheromones directionality. The first pheromone can be thought of as a "this way home" marker, and we will call it a home-finding pheromone. The second pheromone will be the food-finding pheromone, and it points in the direction of the food source. When ants leave the nest in search of food, they walk randomly, leaving trails of home-finding pheromone as they go. When an ant finds food, it picks up a piece and follows its home-finding trail back to the nest, leaving a trail of food-finding pheromone as it goes. If a wandering ant ever encounters a food-finding trail, it follows that trail to the food source, leaving more home-finding pheromone as it goes.
This simple modification reduces the complexity of our rule set:
| Condition: | Walk: | Mark Ground With: |
| Not carrying food | on food-direction trail, or randomly otherwise | home-direction pheromone |
| Carrying food | on home-direction trail | food-direction pheromone |
Painting Arrows in the Forest
This mechanism is similar to the way humans might navigate a forest by painting colored arrow markers on tree trunks. For example, blue arrows might mean "this way to the lake," and yellow arrows might mean "this way to the lodge." If you walk away from the lodge in search of the lake, you can paint backward yellow arrows as you go along. On your way back from the lake, you can follow your yellow arrows home while painting backward blue arrows. The key point here is that you always know how to get to where you are coming from, though you may not know how to get where you are going. If you get to a tree trunk that has already been painted, you simply add your own arrow, even if it contradicts an existing arrow.After many people have traveled between the lodge and the lake using this method, there will be many arrows painted throughout the forest---many trees will bear multiple, contradictory arrows. When trying to find your way back to the lodge, how do you interpret a tree trunk that bears ten yellow arrows? There are many possible strategies, but the simplest might be to just obey the majority of the arrows, since they probably point down the more direct paths (recall that direct paths are faster, so they receive more traffic).
(This navigation technique was presented only as an example and not as a suggestion. Please do not paint arrows in the forest.)
How MUTE Routes Messages
In a network, we do not have ants looking for food or hikers trying to find their way between the lodge and the lake. Instead, we have messages that need to travel from a sender to a recipient. Since MUTE users are anonymous, none of the nodes in the network know exactly where to find a particular recipient (or, more precisely, which computer a particular recipient is using). Like ants that are unaware of the overall environment layout, MUTE messages must be directed through the network using only local clues.Each MUTE node maintains connections to several "neighbors" in the network, and these neighboring connections are used for message passing. Suppose that MUTE node X receives a message from Alice to Bob through node Y, one of its neighbors. X may have no information clues about where Bob is in the network. However, upon receiving this message, node X learns something about Alice: it learns that messages from Alice come through node Y. In the future, if node X ever receives a message to Alice, it can send it back through node Y using this clue.
Regardless of what X learns about Alice, it still has no information about Bob. The best strategy here, using ants as inspiration, is to "send ants in all directions", or to send a copy of the message on to each one of X's neighbors (what we will call "broadcasting" the message). One of the neighbors may have more information about which direction Bob is in. If none of the nodes in the network have clues about Bob's location, they will all broadcast the message to their neighbors. If Bob exists in the network, this technique will eventually find him.
Notice that throughout the search for Bob, the message has been leaving a trail of clues about Alice. If the message reaches Bob, and then Bob sends back a response, the response can follow these clues on a rather direct path back to Alice.
As the response is routed to Alice, it leaves a trail of clues that can be used to route future messages from Alice back to Bob. Other nodes can make use of these clues too. For example, if the owner of node X sends a message to Bob, the message will travel on a rather direct route using the existing clues.
Looking at these example diagrams, we can see that MUTE's routing mechanism is quite similar to the technique of "Painting Arrows in the Forest" presented earlier. Each node can be thought of as a tree, and each neighbor connection can be thought of as a path between neighboring trees. Each node maintains a collection of arrows, and each arrow says something like "To get to Bob, use this path." In these diagrams, we follow the blue arrows backward to find Bob.
We can also think of each message leaving a "scent" as it travels through the network. Messages from Alice leave Alice's scent, and we can follow this scent when sending messages to Alice. The darker arrows in these diagrams represent messages, while the faded arrows can be thought of as the scent left by messages.
For more information about how MUTE implements ant-inspired routing, see the MUTE Technical Details page.