Distributed computation in foraging desert ants

For computer scientists, ants are most familiar from ant colony optimization. These algorithms rely on simulating how ants lay, follow, and modify pheromone trails to find efficient paths from their hives to food sources. Hence, it might come as a surprise that this is not a universal feature of ants. The cataglyphis niger desert ant makes its home in the deserts of the middle east where the constantly shifting terrain makes pheromone trails ineffective outside of the nest. As such, all communication is done inside the hive with the ants being almost completely autonomous once they wander into the outside world. This makes them a perfect animal for looking at distributed computing and the problem of coordinating action in a noisy environment with a limited amount of computation.

During the first post-lunch talk of the second day of the 2nd workshop on Natural Algorithms and the Sciences, Ofer Feinerman introduced us to his experimental work with ants. He concentrated on two important parts of foraging: recruitment in the desert ant, and communal load carrying in the yellow crazy ant (I won’t cover the latter in this post). Under normal conditions, desert ants choose to spend their time at rest or moving slowly through the dark interior of their nest. An ant — lets call her Alice — occasionally wanders outside of the nest, and if she bumps into some food — a tasty cricket in Feinerman’s experiments — then she tries to drag it back to the hive. If the food is too heavy — or held immobile with tweezers — then she has to give up and return to the hive to convince other ants to join her and try to drag back the tasty snack. Unfortunately, Alice does not have the vocabulary to describe the delicious treat, and can only convey her excitement by running around quickly and bumping into other ants. The other ants are inherently skeptical and don’t know if they should interpret Alice’s nudges as an intended “I bumped into you because I saw a delicious cricket” or “sorry, I bumped into you because it is dark in here”. From an information theoretic perspective, Alice must transmit at least one bit of information to her comrades to let them know that the bump was not accidental but meant to excite them to leave the hive.

Omg! Omg! Delicious cricket! Cricket!

Feinerman’s goal is to estimate the channel capacity of the ants’ communication. By tagging each ant with a barcode and tracking their motion with an overhead camera, his group is able to collect mass amounts of data on repeated interactions between ants that have seen the cricket and those that need to be convinced of the proximity of a tasty snack. From a careful statistical analysis, the researchers were able to conclude that the relevant observable variable is the ant’s running speed. As such, the experimentalists can look at the speed distribution of the excited ant, and how it affects the speed distribution of the skeptical ants after interaction. From the resulting changes in speed of the skeptical ant, Feinerman was able to estimate the ant’s channel capacity at 0.22 bits. For an engineer, this means that excited Alice must nudge a skeptical Bob around 5 times before he gets the message: a tasty cricket is near! In the above photo you can see a snapshot from Feinerman’s videos where Alice is running around quickly (seen by the length of her position trace) and has managed to convince Bob to take a look outside, and is having a harder time with Charlie.

Although the reluctance of Bob and Charlie to absorb Alice’s excitement might seem counter-productive, it is actually essential for a healthy colony. If excitement was too easily transmit from confident Alice to hesitant Bob then a random unsubstantiated initial excitement would cause all the ants to swarm outside the hive too often, exposing them to the dangers of being outside without a reward. The hesitant ants provide an inertia that is essential for avoiding an undamped drive of over-excitement. Feinerman’s future plans include quantifying the costs in time and energy that ants pay for communicating badly and either over-exciting or not generating enough excitement in their hive.

antTCSnotes

In the closing talk of the workshop, Amos Korman considered a general approach to using theoretical computer science in empirical studies like Feinerman’s ants. The goal is to help biology make connections between parameters by finding lower and upper bounds that are agnostic to the choice of algorithm carried out by individual agents. If we take a simple but realistic model of ants then we can prove theorems about trade-offs between foraging time and individual ant information capacity that hold for any possible foraging algorithms the ants could use. We can then move to an experimental setting and get the actual foraging times of ants, and from that conclude a lower bound on the ants’ information capacity. Since these bounds are based on the best possible algorithm, it means that the ants can’t be doing any better with less communication. Although the ants might store more information that the theoretic lower-bound, it still gives us a starting relationship and proof of memory. Of course, the key point of this approach is that we can apply it outside of foraging in desert ants to build theoretical guarantees on quantities of interest to biology.

Feinerman & Korman (2012) started their theoretical process by building a reasonable abstract model of desert ants and proving distributed computing lower bounds in it. The authors considered a model of k probabilistic distributed agents (i.e. ants) that can only synchronize before the search starts (i.e. in the ant hill) and have to find a cricket placed by an adversary at an unknown distance D in a 2D lattice around their starting location. Note that this model makes minimal assumptions about the agents, nothing about the complexity of their cognition, planning, or sensory abilities, just that they can only coordinate inside the hill and have sensors that can only detect a cricket within some bounded distance (this determines how to discretize real space into cells). The agents have to visit each site inside the radius with high probability (otherwise the adversary can always trick them by placing the cricket in a lower-probability cell), and thus have to spend at least T = \Omega(D + D^2/k) time searching before at least one of them finds the cricket. For any algorithm to achieve a running time of O(T \log^{1 - \epsilon} k) for any (\epsilon > 0), the authors showed that the individual ants would need at least \Omega(\log \log k) bits of memory. Further, all constants hidden in the big-O notation are reasonable. Now it remains for Feinerman’s group to run careful experiments measuring how the foraging behavior of desert ants scales with their numbers and cricket distance, and they will have rigorous lower bounds on the memory capacity of foraging ants! These bounds could then help us to understand the ants better, and work towards understand the exact algorithm they use for finding those delicious crickets.

ResearchBlogging.orgNote: this is the third blogpost of a series (first and second) on the recent workshop on Natural Algorithms and the Sciences at Princeton’s Center for Computational Intractability.
Feinerman, O., & Korman, A. (2012). Memory Lower Bounds for Randomized Collaborative Search and Implications to Biology 26th International Symposium on Distributed Computing (DISC) DOI: 10.1007/978-3-642-33651-5_5

About Artem Kaznatcheev
From the Department of Computer Science at Oxford University and Department of Translational Hematology & Oncology Research at Cleveland Clinic, I marvel at the world through algorithmic lenses. My mind is drawn to evolutionary dynamics, theoretical computer science, mathematical oncology, computational learning theory, and philosophy of science. Previously I was at the Department of Integrated Mathematical Oncology at Moffitt Cancer Center, and the School of Computer Science and Department of Psychology at McGill University. In a past life, I worried about quantum queries at the Institute for Quantum Computing and Department of Combinatorics & Optimization at University of Waterloo and as a visitor to the Centre for Quantum Technologies at National University of Singapore. Meander with me on Google+ and Twitter.

15 Responses to Distributed computation in foraging desert ants

  1. Pingback: Mathematical models of running cockroaches and scale-invariance in cells | Theory, Evolution, and Games Group

  2. Pingback: Microscopic computing in cells and with self-assembling DNA tiles | Theory, Evolution, and Games Group

  3. Pingback: Distributed computation in foraging desert ants | The Connectivist

  4. bdh63 says:

    Interesting idea, that you can calculate the memory capacity of an ant as if it were a SIM card with finite capacity. Sometimes memory in humans seems like a moving target — today it works, and tomorrow it doesn’t — especially as the years pile up. I wonder if ants live long enough that memory functioning becomes more spotty.

  5. Pingback: Distributed computation in foraging desert ants...

  6. Eimhin says:

    I think the team are missing something. Take the brain for example…and the recetn case of reflexivity neurons…neurons that fire for multiple purposes at synchronous and asynchronous timings. When you add refexivity neurons to a situation the computing power goes up, way up, to unlimited at 30% of the total.
    In the colony you take each individual ant as a part/whole, but I’m not sure that there is much point in trying to find an even distribution for computing power among individuated ants. It looks as though the “whole is more than the parts” and to figure this out you would need to establish more about the nature of signal strength and reinforcement of the colony messages by repeated ‘bumps’ at the pheremonical level. Of course its going to involve a kind of puctuated equilibrium with signal strength increasing exponentially at certain numbers of signalling ants…just like with refelxivity neurons.
    Its great research, don’t get me wrong, I like it because it desimplifies some lazy generalizations I’ve come across in popular science about the way ants communicate, yet doing the experiment in these low numbers may have one effect, while increasing the number of ants will have another…if you could find the constant in the proportion you might have the basis with which to measure the rate of ‘information exchange’ against the rate of ‘change/coordinated activity’ in the colony.
    It is clear from our printing press and now the internet that this ‘information exchange’ has its effects…thermodynamically speaking, with an objective perspective on this, we might be able to see how much we need to accomodate the extra energy flow (the information exhcange itself) in our system to stabilize it…though it will happen anyway naturally. Anyway, thats enough from me, Good morning all,
    Eimhin

    • The whole point of their research is to be precise and rigorous, so I think the researchers would not be happy with examples like:

      neurons that fire for multiple purposes at synchronous and asynchronous timings. When you add refexivity neurons to a situation the computing power goes up, way up, to unlimited at 30% of the total.

      Because it is vague and imprecise.

      Also, a lot of the experiments are done with real ant colonies, so the number of desert ants is at naturalistic levels, so there is no reason to really worry about the increase of numbers. Further the whole point of using desert ants is to avoid:

      to figure this out you would need to establish more about the nature of signal strength and reinforcement of the colony messages by repeated ‘bumps’ at the pheremonical level

      As I explained in the intro, the reason these sort of ants are used is because they don’t communicate by pheromones.

  7. Pingback: https://egtheory.wordpress.com/2013/05/26/distributed-computing-in-ants | involuteconduit

  8. Pingback: Machine learning and prediction without understanding | Theory, Evolution, and Games Group

  9. Pingback: Toward an algorithmic theory of biology | Theory, Evolution, and Games Group

  10. asuss30005 says:

    Reblogged this on Oak Leaf Systems, LLC and commented:
    Quite the interesting article !

  11. Pingback: Stats 101: an update on readership | Theory, Evolution, and Games Group

  12. Pingback: Cataloging a year of blogging: the algorithmic world | Theory, Evolution, and Games Group

  13. Pingback: Evolution As Machine Learning | Large Numbers

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.