Home

Ant intelligence

And, termite intelligence.

Building a termite nest

How termites do it:

• use pheromones
• metabolize bodily waste, which contains pheromones; this waste is what the mound is constructed of
• wander randomly, but prefer the direction of the strongest local pheromone concentration
• at each step, decide stochastically whether to deposit the current load of waste
• the probability of deposit increases with the local pheromone density and the amount of waste it is carrying
• a full termite will drop its waste even if there is no deposit nearby
• a termite that senses very high local concentration of pheromones will deposit whatever waste it is carrying (even a small amount)

Ants finding food

How ants do it:

• five rules
• avoid obstacles (ants will not aimlessly push against a wall)
• wander randomly, in the general direction of nearby pheromones
• if no pheromones are sensed, execute Brownian motion (uniform distribution of choices)
• if holding food, drop pheromone at constant rate as it walks
• maybe follow a “nest beacon”
• if not holding food and finds food, pick it up
• if holding food and finds nest, drop food

The initial path will not be straight, but the tendency of ants to wander even in the presence of pheromones will generate short-cuts across initial meanders. Because pheromone paths have some breadth, they tend to merge together into a trace that becomes straighter the more it is used.

Ants sorting things in a nest

This model is described in the article “Go to the ant”: Engineering principles from natural multi-agent systems (PDF) by Parunak (1997).

This is the description from the article:

System Behavior An ant hill houses different kinds of things, including larvae, eggs, cocoons, and food. The ant colony keeps these entities sorted by kind. For example, when an egg hatches, the larva does not stay with other eggs, but is moved to the area for larvae. Computer scientists have developed a number of algorithms for sorting things, but no ant in the ant hill is executing a sorting algorithm.

Responsibilities The individual ant algorithm that yields system-level sorting behavior contains some behaviors similar to those in the path-planning problem.

1. Wander randomly around the nest.
2. Sense nearby objects, and maintain a short memory (about ten steps) of what has been seen.
3. If an ant is not carrying anything when it encounters an object, decide stochastically whether or not to pick up the object. The probability of picking up an object decreases if the ant has recently encountered similar objects.

In the emulation, the probability of picking up an object is P = (K+ /(K+ + F))^2 where F is the fraction of positions in short-term memory occupied by objects of the same type as the object sensed and K+ is a constant. As F becomes small compared with K+, the probability that the ant will pick up the object approaches certainty.

4. If an ant is carrying something, at each time step decide stochastically whether or not to drop it, where the probability of dropping a carried object increases if the ant has recently encountered similar items in the environment. In the emulation, P = (F / (K- + F))^2 where F is the fraction of positions in short-term memory occupied by objects of the same type as the object carried, and K- is another constant. As F becomes large compared with K-, the probability that the carried object will be put down approaches certainty.

Integration As in path planning, the Brownian walk eventually brings the wandering ants to examine all objects in the nest. Even a random scattering of different items in the nest will yield local concentrations of similar items that stimulate ants to drop other similar items. As concentrations grow, they tend to retain current members and attract new ones. The stochastic nature of the pick-up and drop behaviors enables multiple concentrations to merge, since ants occasionally pick up items from one existing concentration and transport them to another.

The put-down constant K- must be stronger than the pick-up constant K+, or else clusters will dissolve faster than they form. Typically, K+ is about 1 and K- is about 3. The length of short-term memory and the length of the ant’s step in each time period determine the radius within which the ant compares objects. If the memory is too long, the ant sees the entire nest as a single location, and sorting will not take place.

Principles for designing agent-based solutions

• agents not functions (not functional decomposition)
• keep agents small in size

The motivation for this principle derives not from our theory of multi-agent systems, but from the experience of software engineers that the difficulty of designing, implementing, and launching computer-based systems increases exponentially with the size of the system. Small individual agents are easier to construct and understand than large monolithic systems, and the impact of the failure of any single agent will be minimal. In addition, a large population of agents gives the system a richer overall space of possible behaviors, thus providing for a wider scope of emergent behavior. Very roughly, the number of agents is a multiplicative factor in determining the implementation effort, but an exponent in determining the size of the overall system state space. The effort to code $$100$$ agents with $$10$$ behaviors each is on the order of $$100*10 = 10^3$$, but the resulting state space is on the order of $$10^{100}$$.

• keep agents small in time (forgetful)

Naturally occurring agent systems can forget. Pheromones evaporate, and as a result obsolete paths leading to depleted food sources disappear rather than misleading members of the colony. The probability that a wasp will forage decreases as it successfully resists stimulation. Even the death of unsuccessful organisms in an ecosystem is an important mechanism for freeing up resources so that better adapted organisms can flourish.

• keep agents small in scope (local sensing and action)

Software engineering offers another argument for local agent communications. [Dijkstra 1968] warned of the dangers of the Fortran GOTO statement, which gave the programmer the ability to jump from anywhere to anywhere in a program. This powerful tool led to tangled mazes of spaghetti code that were easy to break and almost impossible to correct and maintain. More disciplined structures proved to have the same expressive power, while supporting modularity and restricted interfaces that limited the propagation of faults. Global data reference has the same kind of engineering implications that global transfer of control does. In both cases, direct remote interactions are difficult for humans to understand, maintain, and control. In both cases, global effects can be obtained by propagation of local influences, much more robustly than by providing global influences.

• decentralizd system control
• avoids single points of failure
• avoids performance bottlenecks
• can grow more
• support agent diversity
• diverse agents cover more of the environment and provide better performance
• provide an entropy leak

Natural agent-based systems do organize themselves with striking efficiency. A common explanation is that a system can become more organized if energy is added to it from the outside (for example, by the metabolism of the food gathered by an insect hive). The addition of energy is necessary for self-organization, but hardly sufficient. Gasoline in construction equipment can erect a building, but the same gasoline in a terrorist’s bomb can destroy it.

In natural systems, agents can organize themselves at the macro level because their actions are coupled to a dissipative or disorganizing process at a micro level. The system can reduce entropy at the macro level by generating more than enough entropy at the micro level to pay its second-law debt. To adopt another metaphor, it provides an entropy leak to drain disorder away from the macro level (where useful work is done) to the micro level (where it won’t interfere with the system’s function).

Emergence (Radiolab, August 14, 2007)

CSE 630 material by Joshua Eckroth is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License. Source code for this website available at GitHub.