Tikalon Blog is now in archive mode.
An easily printed and saved version of this article, and a link
to a directory of all articles, can be found below: |
This article |
Directory of all articles |
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.
(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.
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]
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:
- 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.
- Ant Colony Optimization Website.
- Marco Dorigo, "Ant colony optimization," Scholarpedia, vol.2, no. 3, Article no. 1461, doi:10.4249/scholarpedia.1461.
- 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.
- An ant-inspired approach to mathematical sampling, University of Bristol Press Release, June 19, 2020.
Linked Keywords: Scientist; frontiers of science; branches of science; discipline; laboratory; workweek; work day; coffee; caffeine; caffeinated; soft drink; energy; sugar; sugary; corporation; corporate; campus; career; employment; employee; vending machine; dispensing machine; cold; chilled; office; job; calculation; calculated; salary; money; Wikimedia Commons; CoolKid1993; probability; possibility; spill; computer keyboard; history of computing hardware; early days of computing; metal; reservoir; liquid; infestation; infested; ant; computer programmer; magazine; rinse; de-ionized water; damage; Ant Colony Optimization (ACO); biomimetics; biomimetic; shortest path problem; optimum paths on graphs; ant colony; food; traveling salesman problem; routing (electronic design automation); routing of traces; printed circuit board; trail; pheromone; amplitude; intensity; evaporation; evaporate; rock (geology); website; aco-metaheuristic.org; Marco Dorigo; Université Libre de Bruxelles (Brussels, Belgium); Scholarpedia; chemical substance; sex pheromone; fight-or-flight response; flight; alarm signal; pterygota; flying insect; interdisciplinarity; interdisciplinary team; University of Bristol (Bristol, UK); Faculties of Engineering; Faculties of Life Sciences; exploration; exploratory process; species; Temnothorax albipennis; author; Edmund Hunt; Hansel and Gretel story; nest; fracture; crack; Europe; wall; pebble; sand; dhirality; left turn bias; relative direction; left; right; eye; speculative reason; speculate; fitness (biology); evolutionary advantage; maze solving algorithm wall follower; maze; taxonomy (biology); scientific classification; Kingdom (biology); Animal; Animalia; Phylum; Arthropod; Arthropoda; Class (biology); Insect; Insecta; Order (biology); Hymenoptera; Family (biology); Formicidae; tTaxonomic rank; subfamily; Myrmicinae; Genus; Temnothorax; species; T. albipennis; binomial nomenclature; binomial name; AntWeb.org; Creative Commons Attribution License 4.0; organism; navigation; Slimy Computation, September 15, 2011; Marco Polo Physarum, October 1, 2012; slime mold; Physarum polycephalum; life and death; foraging; coordination; coordinating; experiment; research; cleaning; clean; footprint; exploration; trajectory; trail; Creative Commons Attribution License; information; Markov chain Monte Carlo; computational resource; computational cost; prediction; predict; computer simulation; simulate; mathematics; mathematical; sampling (statistics); algorithmic efficiency; efficient; memory; computational biology; analysis; complex.