How Hansel, Gretel, and the ants inspire new concepts in computing

A team of researchers is studying an interesting parallel between the exploration problem confronted by ants and the mathematical sampling problem of acquiring information.

Exploring an unfamiliar, changing environment in search of valuable resources such as food or potential nest sites is a challenge for many organisms. A memory of where one has already explored, to avoid revisiting unprofitable locations, is an advantage, but memory is expensive. One way to circumvent the cost of carrying memories internally is to store the information externally in the environment. Use of external markers as memory has been demonstrated in simple organisms, like the slime mould Physarum polycephalum. Markers may be left in the environment to signify the presence or absence of good foraging or nest-making prospects at a given location, so that when an animal returns it can make an appropriate and timely decision about the expenditure of its efforts.

For superorganisms like ants, that seek to maximize their foraging performance at the level of the colony, pheromone signals or cues such as cuticular hydrocarbon footprints may be used to coordinate the movement decisions of their nest-mates (stigmergy) such that an unfamiliar space is quickly explored.

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.

Edmund Hunt, as quoted by EurekAlert!

An analogous problem to animals searching in an unfamiliar environment is that of sampling efficiently from unknown probability distributions. The team has developed a bioinspired trail avoidance method for the purpose of Markov chain Monte Carlo sampling that uses a memory of where the walker has visited to obtain a representative sample more rapidly.

A key challenge for any animal (or sampling technique) is to avoid wasting time by searching for resources (information) in places already found to be unprofitable. In biology, this challenge is particularly strong when the organism is a central place forager—returning to a nest between foraging bouts—because it is destined repeatedly to cover much the same ground. This problem will be particularly acute if many individuals forage from the same central place, as in social insects such as the ants. Foraging (sampling) performance may be greatly enhanced by coordinating movement trajectories such that each ant (walker) visits separate parts of the surrounding (unknown) space. We find experimental evidence for an externalized spatial memory in Temnothorax albipennis ants: chemical markers (either pheromones or cues such as cuticular hydrocarbon footprints) that are used by nest-mates to mark explored space. We show these markers could be used by the ants to scout the space surrounding their nest more efficiently through indirect coordination. We also develop a simple model of this marking behaviour that can be applied in the context of Markov chain Monte Carlo methods (Baddeley et al. 2019 J. R. Soc. Interface16, 20190162 (doi:10.1098/rsif.2019.0162)). This substantially enhances the performance of standard methods like the Metropolis–Hastings algorithm in sampling from sparse probability distributions (such as those confronted by the ants) with only a little additional computational cost. Our Bayesian framework for superorganismal behaviour motivates the evolution of exploratory mechanisms such as trail marking in terms of enhanced collective information processing.

Hunt, Edmund R., Nigel R. Franks, and Roland J. Baddeley. ‘The Bayesian Superorganism: Externalized Memories Facilitate Distributed Sampling’. Journal of The Royal Society Interface 17, no. 167 (24 June 2020): 20190848. https://doi.org/10.1098/rsif.2019.0848.

____________________

Image: Molly Seamans, Cover illustration for “Once Upon an Algorithm: How Stories Explain Computing”, a book by Martin Erwig

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.