---
created_at: '2016-01-08T22:51:07.000Z'
title: How Ants Find Food (2003)
url: http://mute-net.sourceforge.net/howAnts.shtml
author: ycmbntrthrwaway
points: 53
story_text: 
comment_text: 
num_comments: 5
story_id: 
story_title: 
story_url: 
parent_id: 
created_at_i: 1452293467
_tags:
- story
- author_ycmbntrthrwaway
- story_10868911
objectID: '10868911'

---
[Source](http://mute-net.sourceforge.net/howAnts.shtml "Permalink to MUTE:  Simple, Anonymous File Sharing")

# MUTE:  Simple, Anonymous File Sharing


| ----- |
|  [ ![][1]  
![][2]][3]  
  
[[Français][4]]   
  
[Sponsor List][5]   

| 

|  **MUTE protects your privacy** by avoiding direct connections with your sharing partners in the network. Most other file sharing programs use direct connections to download or upload, making your identity available to spies from the RIAA and other unscrupulous organizations.  
[Read more...][6]  |  
| 

  
  

| ----- |
|  **Ants display collectively intelligent behavior** when foraging for food or fighting off predators. Each ant in the colony acts in a rather simple way, but together they end up doing something clever, like discovering the shortest path between their ant hill and a food source. MUTE's routing mechanism is inspired by ant behavior.  
[Read more...][7]  |  
| 

  
  

| ----- |
|  **MUTE is based on research**, and experiments show that it works quite well. MUTE's ant-inspired routing is light-weight, robust, and adaptive. Results from experiments in real MUTE networks show that the collective behavior of MUTE nodes quickly finds the shortest (or fastest) routing path between two nodes on the network.  
[Read more...][8]  |  
| 

  
  

| ----- |
|  "**The RIAA just started bullying Internet users**, but they've been bullying musicians for decades. By refusing to pay for major label (RIAA) music, we can usher in a more fair music business and keep the Internet free (as in freedom)." 

| \--Holmes Wilson | 

[Read more at Downhill Battle...][9] |  
| ---------------------------------- |  
|  

                                     |  

                                     |  

# 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.  
  
![][10]  
Photo by [Harold Thimbleby][11] \--- 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.   
![][12]   
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.   
![][13]   
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_.   
![][14]   
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.   
![][15]   
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.  
![][16]   
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: 

| ----- |
| 

* [Optimal Behavior of Ants][17]
* [Pheromone Biology][18]
* <http://www.antnest.co.uk>
* [http://www.antcam.com][19]
 | 

# 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.  
  
![][20]   
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.  
  
![][21]   
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_.  
  
![][22]   
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.  
  
![][23]   
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][24] page. 

## Routing Clues and Privacy

In terms of anonymity, the notion of "clues about _Alice_" sounds scary. Keep in mind that all of these "clues" are just local hints that will not enable anyone to directly pinpoint _Alice_ in the network. A node's routing clue essentially tells it, "my neighbor knows more about _Alice_ than I do." Of course, none of the nodes have a good measure of how much they know about _Alice_, so the fact that a particular neighbor knows more gives a node little extra information. For example, none of the nodes along a path between _Alice_ and _Bob_ know enough to conclude that "my neighbor **is** _Alice_."   | 
* * *

| ----- |
|  They say, "DON'T EVER ANTAGONIZE THE HORN."  
Their lips move, but no sound comes out.  
Who really listens to the people on TV?  |  hosted by:  
[ ![SourceForge Logo][25]][26]  | 

[1]: http://mute-net.sourceforge.net/images/logo.png
[2]: http://mute-net.sourceforge.net/images/logoText.png
[3]: http://mute-net.sourceforge.net/index.php
[4]: http://mute-net.sourceforge.net/index.fr.shtml
[5]: http://mute-net.sourceforge.net/sponsors.shtml
[6]: http://mute-net.sourceforge.net/howPrivacy.shtml
[7]: http://mute-net.sourceforge.net/howAnts.shtml
[8]: http://mute-net.sourceforge.net/experiments.shtml
[9]: http://www.downhillbattle.org
[10]: http://mute-net.sourceforge.net/images/ants/antLine.jpg
[11]: http://www.uclic.ucl.ac.uk/harold/
[12]: http://mute-net.sourceforge.net/images/ants/antDiagram1.png
[13]: http://mute-net.sourceforge.net/images/ants/antDiagram2.png
[14]: http://mute-net.sourceforge.net/images/ants/antDiagram3.png
[15]: http://mute-net.sourceforge.net/images/ants/antDiagram4.png
[16]: http://mute-net.sourceforge.net/images/ants/antDiagram5.png
[17]: http://iridia.ulb.ac.be/~mdorigo/ACO/RealAnts.html
[18]: http://users.rcn.com/jkimball.ma.ultranet/BiologyPages/P/Pheromones.html
[19]: http://www.antcam.com/
[20]: http://mute-net.sourceforge.net/images/ants/antRouting1.png
[21]: http://mute-net.sourceforge.net/images/ants/antRouting2.png
[22]: http://mute-net.sourceforge.net/images/ants/antRouting3.png
[23]: http://mute-net.sourceforge.net/images/ants/antRouting4.png
[24]: http://mute-net.sourceforge.net/technicalDetails.shtml
[25]: http://sourceforge.net/sflogo.php?group_id=83030&type=1
[26]: http://sourceforge.net

