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.

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.

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 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 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 time searching before at least one of them finds the cricket. For any algorithm to achieve a running time of for any (), the authors showed that the individual ants would need at least 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.

Note: 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