Go To The Ant

This talk summarizes material from:

H. Van Dyke Parunak. ``Go to the Ant'': Engineering Principles from Natural Agent Systems. [1] Annals of Operation Research,(75):69--101, 1997.

This paper presents ideas for building MASs. The ideas have a biological inspiration. This work should be contrasted with the economic techniques such as auctions and bargaining.
As software engineering has progressed, more and more control has become localized. Before, the decision of what exactly a piece of code should do was mostly determined by outside influences (e.g., the programmer, parameters, function calls).

Increasing Software Localization
	Monolithic Program	Structured Programming	Object-Oriented Programming	Agent-Oriented Programming
How does a unit behave?	External	Local	Local	Local
What does a unit do when it runs?	External	External	Local	Local
When does a unit run?	External	External (called)	External (message)	Local

Agents localize code, data, and invocation.
The number of system behaviors possible is an exponential of the number of individual agent behaviors. The problem, however, is how to engineering the simple agent behaviors so that they achieve the required system behavior.

CS and AI use different models of the world from Physics and Biology.

Model	Discrete-Event Dynamical Systems	Time-Based Dynamical Systems
State	Discrete (symbols)	Continuous (real numbers)
Processing	Symbol manipulation.e.g. Rewrite rules Transition tables	Partial differential equations or difference equations.
Progress	Discrete; event-based	Discrete (integer time) or continuous (real time)
Time & State	Independent (clock speed)	Coupled (physical laws)
Communities	Computer Science, AI	Physics, Mathematical Ecology

System Behavior: Ants build minimum spanning trees that connect nests to food.
Responsibilities:
1. Avoid obstacles
2. Wander randomly, or towards the general direction of nearby pheromones if any.
3. If holding food, drop pheromone at constant rate.
4. If food and not holding any then pick it up.
5. If at nest and holding food then drop it.
Integration: The ants will find the food because of the random walk. The pheromones trail lead to/from a food source. The initial path will not be straight but, since the ants wander a bit, some of them will find shortcuts. Because pheromone paths have some breadth, they tend to merge together into a trace that becomes straighter the more its used.

System Behavior: An and hill houses larvae, eggs, cocoons, and food. The ant colony keeps all of them separate.
Responsibilities:
1. Wander randomly.
2. Sense nearby objects and maintain a short memory.
3. If object found and not carrying object then decide stochastically whether to pick it up. The probability of a pickup decreases if the ant has recently encountered similar objects.
4. If carrying something then decide stochastically whether to drop it. The probability of dropping increases if the ant has recently encountered similar object.
Integration: As concentration grows, the likelihood that they will get bigger increases. The put-down probability must be bigger than the pick-up, otherwise clusters will disperse faster than they form. The memory cannot be too long.

System Behavior: Tropical termites construct mounds that can exceed five meters in height and ten tons in mass, without central control.
Responsibilities:
1. Metabolize bodily waste, which contains pheromones. The mounds are constructed from this material
2. Wander randomly, preferring the strongest pheromone concentration.
3. At each time step, decide stochastically whether to deposit the current load of waste. The probability increases with pheromone intensity and the amount of waste the termite is carrying.
Integration: Initial deposits will tend to attract termites and become bigger. Because pheromones decay and aggregate, the most recent deposits at the center of the pile are the strongest, so a tower is built.

System Behavior: Mature Polistes wasps in a nest divide into three groups, a single Chief, a group of Foragers who hunt for food, and a group of Nurses who care for the brood. The wasps are all genetically identical.
Responsibilities: Each wasps maintains two parameters: a Force parameter that determines how mobile it is, and a Foraging Threshold that determines how likely the wasp is to go seek food. The brood maintains a Demand for food.
1. When to wasps meet, they face off. The winner is determined so that the wasp with the highest Force is more likely to win. A quantum of force is moved from the loser to the winner.
2. When the brood receives food, this reduces the Demand
3. When a was is near a brood, it determines whether or not to forage. The more Demand and lower Foraging Threshold, the more likely it is to go. If it does, its Foraging Threshold is decreased.
Integration: The ones with low threshold and low force become nurses, those with low threshold and high force become foragers. The chief has high force and high threshold and serves to ground the force and threshold scales and balances them across the population.

System Behavior:Flocks of birds stay together even while managing turns.
Responsibilities:
1. Maintain a minimum distance to the nearest object.
2. Match velocity to nearby birds.
3. Stay close to the center of the flock.
Integration: Birds stay close, but not too close, and swerve to avoid obstacles.

System Behavior: A single wolf cannot kill a moose. A pack has to coordinate its attack.
Responsibilities: Move to the cell that minimizes the distance to the moose and maximizes the distance to the nearest wolf.
Integration: The attraction and repulsion forces need to be properly balanced. When they are, the wolf's will properly surround their prey.

Traditionally, we tend to think of the components of a software system as "functions".
In a multiagent system, "functions" are often the emergent property of the agents' interactions (e.g., players interacting to score a goal).
One should not start by implementing all the desired functions into an agent. They should emerge from simpler agent behaviors.

Small in mass.
- Ants are small but plentiful.
- Large programs are hard to write.
- Favor specialized agents over general one.
Small in time (forgetful).
- Wasps forget. Pheromones evaporate.
- It is an important supplement to agent learning.
Small in scope (local sensing and action).
- Ants are constrained by physics.
- Avoid broadcasting messages, try to target them instead.
- Complex systems with many inter-connections are unpredictable, those with too few are boring (stable), those in between exhibit organization (life emerges at the edge of chaos).

A central agent is a single point of failure.
It can become a bottleneck.
It tends to attract functionality and code as the system develops.
Designers often confuse a class of agents with an individual agents.

Diversity is related to size. Two otherwise identical agents could be at different places, thereby adding diversity.
Natural populations usually have a minimum size they need to be before the emergent properties arise. For example, you need enough ants to form a trail.
Having extra agents makes a system withstand unexpected environmental changes.
Randomness and repulsion are effective ways of achieving spatial diversity.

Agents need to share information.
- Between agents.
- Between agent and environment.
- Across generations of agents.
- Between agent and community.
Agents should plan and execute concurrently.
- Changes in the environment require reactivity.
- Natural systems only react.

Go To The Ant

1 Introduction

2 Modeling State and Process

3 Ants Path Planning

4 Ants: Brood Sorting

5 Termites: Nest Building

6 Wasps: Task Differentiation

7 Birds and Fish: Flocking

8 Wolves: Surrounding Prey

9 Agents Things, not Functions

10 Keep Agents Small

11 Decentralize System Control

12 Support Agent Diversity

URLs

Go To The Ant

1 Introduction

2 Modeling State and Process

3 Ants Path Planning

4 Ants: Brood Sorting

5 Termites: Nest Building

6 Wasps: Task Differentiation

7 Birds and Fish: Flocking

8 Wolves: Surrounding Prey

9 Agents Things, not Functions

10 Keep Agents Small

11 Decentralize System Control

12 Support Agent Diversity

13 Share Information. Plan and Execute Concurrently

URLs