Ant Inspired Computation in 1988
The paper presents an argument for the use of biological ant colonies as an inspiration for parallel problem solving. The paper discusses the importance of randomness in decision making in conjunction with a chemical trail (pheromone) to direct the ants towards a food source or a nest. The emergent effect of trail formation between food and nest which results from simple local interactions is shown to be of great importance since it can be shown to occur without the specific requirement for a path between food and nest, i.e. there is no reward or cost function associated with forming a trail, it just occurs through the definition of four behaviours (rules).
Each artificial ‘ant’ moves about a grid according to four simple rules. Each ant first checks whether it has found food. If so it reverses direction and starts laying pheromone, looking for more pheromone. If no food has been found the ant checks for the nest and if it is encountered the ant reverses direction and looks for pheromone. If the ant found neither food nor pheromone nor nest it travels in a random way, left, forward or right. If a pheromone is encountered its new direction is determined by this pheromone in any of the three directions: left, forward or right.
The researchers found that these simple rules were enough to allow the ants to create paths between multiple food sources and the nest without an inbuilt requirement for the ants to build a path between a nest and food.
The paper introduces several key concepts taken from biology and replicated in an artificial simulation:
- Self-organisation without the requirement for centralised control.
- Use of randomness in conjunction with directedness in the form of an artificial pheromone to guide decision making.
- Emergent effects (path linking) occurring in the absence of a cost function.
- The requirement for a critical mass of artificial ants before emergent effects are observed.