Tikalon Header

Computer Ants

August 3, 2020

Scientists, who are always eager to push back the frontiers of their discipline, hit the laboratory floor running as they start their new work day. As the day progresses, we experience a midday slump like many other workers. The usual fix for this is another cup of coffee, or a caffeinated soft drink. Since caffeine merely masks a person's low energy, the benefit of a sugary soft drink is that it gives you an energy boost.

The corporate campus at which I spent most of my career had about 2,000 employees at its peak. It was large enough to be serviced by a vending machine company that sited a dispensing machine for nicely chilled soft drinks a few steps from my office. I realized that I finally had a decent job when I calculated that I made enough money in the two minute walk to and from this vending machine to pay for the soft drink it dispensed.

Lab Rat Cola

(Modified Wikimedia Commons image by CoolKid1993)


One disadvantage of having a drink on your office desk is the possibility of spills. At one time I spilled a sugary soft drink onto my computer keyboard. This was in the early days of computing when keyboards were contained in huge metal cases. The keyboard still functioned, but there was a reservoir of sugary liquid that lingered at the bottom of the case; and, one morning, my keyboard was infested with ants.

As it turned out, spilling soft drinks into keyboards has been a chronic problem for computer programmers. I had read in a computer magazine that a thorough rinse with de-ionized water, followed by a long drying time, would flush out the sugar without damaging the keyboard. One advantage of having a laboratory is that there's a lot of deionized water available; so, I tried this, and it worked.

There's another way to have ants in your computer. That's with a method called Ant Colony Optimization (ACO), a biomimetic technique invented in 1996 for finding optimum paths on graphs.[1] ACO performs just as ants do when they create a path between their colony and a food source. Some applications of ACO are the venerable traveling salesman problem, and routing of traces on a printed circuit board.

When ants search for food, they wander aimlessly at first. When an ant finds food and returns to the ant colony, it lays down a trail of a pheromone that other ants can follow. As more and more ants follow the trail, the intensity of the pheromone signal increases. The path choice is optimized becuse the pheromone evaporates, short paths are favored, and a locally optimal solution, such as going the too long way around a large rock, is less likely. This method has its own website (aco-metaheuristic.org),[2] and a review article by Marco Dorigo of the Université Libre de Bruxelles (Brussels, Belgium) appears online at Scholarpedia.[3]

This food-seeking chemical trail is one among other pheromone types that include the come-hither sex pheromones and the flight alarm signal pheromones that are used by some flying insects. A recent study by an interdisciplinary team from the University of Bristol (Bristol, UK) Faculties of Engineering and Faculties of Life Sciences have discovered a more efficient exploratory process in a species of ants, Temnothorax albipennis, known as rock ants. This species lays down a chemical that signals places to be avoided, thereby reducing unnecessary search. As the lead author of the study, Edmund Hunt, says,
"This would be a reversal of the Hansel and Gretel story – instead of following each other's trails, they would avoid them in order to explore collectively."

Rock ants, which build simple nests in cracks in rocks, are found in Europe. They cover the cracks with a wall built with small pebbles and sand. These ants have a left turn bias in their travels. There's also a difference between the ants' left and right eyes. it's speculated that this is an evolutionary advantage from the fact that consistent left-turning (or, right turning) is a sure way to search and exit simple mazes without getting lost.

Figure caption

A rock ant.

The scientific classification of the rock ant, determined in 1854, is Kingdom: Animalia; Phylum: Arthropoda; Class: Insecta; Order: Hymenoptera; Family: Formicidae; Subfamily: Myrmicinae; Genus: Temnothorax; and, Species: T. albipennis. The binomial name is Temnothorax albipennis.

(Specimen casent0173192, as photographed by April Nobile and uploaded by the California Academy of Sciences to AntWeb.org. Licensed under the Creative Commons Attribution License 4.0, via Wikimedia Commons.)


Ants aren't the only organism that uses chemical markers for navigation. As I wrote in two previous articles (Slimy Computation, September 15, 2011 and Marco Polo Physarum, October 1, 2012), this behavior is also found in the slime mold, Physarum polycephalum. An optimized search strategy is important, since the search is a matter of life and death when the objective is food. Ants are dispatched from a central place, their colony, so there's a problem of their repeatedly searching the same places.[4] foraging would be optimized by coordinating movement such that each ant visits different places.[4]

As an experiment, the research team had ants explore an empty area one-by-one. Two conditions were tried. In one, the area was cleaned between each session, and in the other it wasn't. In the second condition, without cleaning, the ants demonstrated a better search strategy. The conjecture is that the ants leave chemical markers through pheromones, or by chemicals on their footprints, to mark explored space.[4]

Experimental results of ant exploration

The experimentally determined ant exploration trajectories for the two treatments in 36 trials. This demonstrates a wider search domain when the chemical trails are kept intact. (Portion of fig. 1 from ref. 4, licensed under a Creative Commons Attribution License.)


This information can be used to improve computer optimization algorithms, and the research team has developed a Markov chain Monte Carlo algorithm that's substantially enhanced with little additional computational cost.[4] Markov chain Monte Carlo methods suffer from the same problem of revisiting the same areas of probability space.[4-5] As lead author, Edmund Hunt, explains,
"We predicted that we could simulate the approach adopted by the ants in the mathematical sampling problem, by leaving behind a 'negative trail' of where has already been sampled. We found that our ant-inspired sampling method was more efficient (faster) than a standard method which does not leave a memory of where has already been sampled... Our ant-inspired sampling method may be useful in many domains, such as computational biology, for speeding up the analysis of complex problems."[5]

References:

  1. M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system: optimization by a colony of cooperating agents," IEEE Transactions on Systems, Man, and Cybernetics," vol. 26 (Part B), no. 1 (February, 1996), pp. 29-41. A PDF file can be found here.
  2. Ant Colony Optimization Website.
  3. Marco Dorigo, "Ant colony optimization," Scholarpedia, vol.2, no. 3, Article no. 1461, doi:10.4249/scholarpedia.1461.
  4. Edmund R. Hunt, Nigel R. Franks, and Roland J. Baddeley, "The Bayesian superorganism: externalized memories facilitate distributed sampling," J. R. Soc. Interface, vol. 17 (June 17, 2020), Article no. 20190848, http://dx.doi.org/10.1098/rsif.2019.0848. This is an open access article with a PDF file here.
  5. An ant-inspired approach to mathematical sampling, University of Bristol Press Release, June 19, 2020.