Ant Inspired Computation in 1988

Late last year I chanced upon the title of a 1988 paper by Moyson and Manderick: The Collective Behaviour of Ants: An Example of Self-Organization in Massive Parallelism. Recently I was able to get an electronic copy.

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.

So what? Well the paper was published in early 1988, and references Probabilistic Behaviour of Ants: A Strategy of Errors. The same paper referenced by the seminal work of Dorigo, Maniezzo and Colorni on Ant System, three years later. Whereas the later paper has been referenced by almost every major work in the field to date (57 according to citeseer), Moyson and Manderick’s paper has received only one citation by Koza in a non-ant-inspired computation paper. As Prof. Julius Sumner Miller would say “Why is it so?”