Numerosity-driven phase transitions

· 1169 words · 6 minute read

This post discusses the intersection of some of my recent and forthcoming work in probability theory with studies of programmable matter and ant colonies.

Context 🔗

Programmable matter 🔗

The amoebot model is an abstract model of identical, programmable elements which have limited sensory and computational resources but which can nevertheless exhibit useful collective behaviors.1 For example, they can be programmed to form shapes, coat objects, compress, and form bridges.2 The key idea is that desirable collective behavior can be encoded in the stationary distribution of a Markov chain, which the amoebot can reach by following the dynamics dictated by the Metropolis-Hastings algorithm.3 Recently, Li et al. programmed a robot swarm to form an aggregate that can collectively transport objects, using an algorithm they designed with the amoebot model.4

An important detail is that, by design, under the Li et al. algorithm, the amoebots transition from a dispersed phase to an aggregated phase in the same way that spins in the Ising model transition from a paramagnetic phase to a ferromagnetic one. This work demonstrates that a phase transition in a lattice model of interacting elements can be used to program a robot swarm. Hence, identifying new kinds of phase transitions in lattice models can lead to new functionality for programmable matter. The work I will discuss below concerns a model that exhibits a remarkable phase transition, which is qualitatively similar to one observed in ant colonies.5

Takeaway: A phase transition in a lattice model can be translated into a function of programmable matter.

Ant colonies 🔗

Colonies of social insects exhibit different collective behaviors as the number of their constituents—in other words, their numerosity—varies.6 As Franks observed: “The solitary army ant is behaviorally one of the least sophisticated insects imaginable. Even in quite large numbers army ants may demonstrate behavior that is essentially aberrant. . . . In extremely high numbers, however, it is a different story.”7 A natural question is: For a behavior exhibited by sufficiently numerous colonies, how many ants are necessary?

This question has been answered for collective behaviors in at least two species of ants. Beekman, Sumpter, and Ratnieks found that colonies of more than around 600 Pharaoh’s ants exhibit organized foraging, in the sense of sustaining a pheromone trail to a food source, while smaller colonies do not.8 Acromyrmex versicolor leafcutter ants cultivate a fungus which serves as their primary food source. Clark and Fewell found that colonies of around 89 or more such ants have a stable growth relationship with this fungus, while smaller colonies do not.9

Takeaway: Colonies of ants exhibit a numerosity-driven “phase transition” in their behavior which is mediated by the presence or absence of relatively few ants.

A lattice model which exhibits a numerosity-driven phase transition 🔗

The preceding takeaways suggest that it may be possible to impart a function to programmable matter which is mediated exclusively by the number of elements.10 In other words, $n$ elements exhibit one collective behavior, while $n+1$ or more elements exhibit another. The first step is to identify a lattice model which has a numerosity-driven phase transition. Two of my recent papers describe such a model, called harmonic activation and transport (HAT).11

In fact, if there were no further requirements, it would be easy to describe a lattice model with a numerosity-driven phase transition. For example, you could dictate that no elements move unless there are at least $n+1$ of them, in which case they do. The two collective behaviors are simply “not moving” and “moving.” However, this dynamics could not be directly implemented by amoebots, because it requires that each amoebot knows how many amoebots there are, but it can only sense its local environment.

HAT is a random process which rearranges an $n$-element subset of the $d$-dimensional Euclidean lattice, $\mathbb{Z}^d$. The elements of this set are like the elements of programmable matter, and HAT describes their motion. Informally, the main result is that, above a certain dimension and up to a certain number of elements, HAT reaches a steady state in which the elements tend to remain in one large cluster. However, if even one element is added, the elements organize into small clusters which grow increasingly separated.

For concreteness, this provably occurs in five or more dimensions, and the transition between the two behaviors occurs when the number of elements increases from three to four. In forthcoming work, I will show that, by generalizing the HAT dynamics, this transition can be made to occur at any odd number of elements greater than two.

There are two limitations. First, the HAT phase transition does not occur in two dimensions, which is the dimension of the lattice underlying the amoebot model. However, I believe it should be possible to further tweak the HAT dynamics to produce the same transitions in three dimensions. Second, even if it is possible to implement the dynamics with the amoebot model, it may not be easily realized in an experimental robot swarm.

Takeaway: There is a non-trivial lattice model which provably exhibits a numerosity-driven phase transition, and which has the potential to inspire related functionality in programmable matter.

  1. Zahra Derakhshandeh, Shlomi Dolev, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. Amoebot - a new model for programmable matter. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ‘14, pages 220–222, New York, NY, USA, 2014. Association for Computing Machinery. ↩︎

  2. Joshua J. Daymude, Kristian Hinnenthal, Andréa W. Richa W. Richa, and Christian Scheideler. Computing by programmable particles. In Distributed Computing by Mobile Entities: Current Research in Moving and Computing, pages 615–681. Springer, Cham, January 2019. ↩︎

  3. Sarah Cannon, Joshua J. Daymude, Dana Randall, and Andréa W. Richa A Markov chain algorithm for compression in self-organizing particle systems. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC ‘16, pages 279–288, New York, NY, USA, 2016. Association for Computing Machinery. ↩︎

  4. Shengkai Li, Bahnisikha Dutta, Sarah Cannon, Joshua J. Daymude, Ram Avinery, Enes Aydin, Andréa W. Richa, Daniel I. Goldman, and Dana Randall. Programming active cohesive granular matter with mechanically induced phase changes. Science Advances, 7(17):eabe8494, 2021. ↩︎

  5. Here, “phase transition” is broadly construed. ↩︎

  6. Eric Bonabeau, Guy Theraulaz, Jean-Louls Deneubourg, Serge Aron, and Scott Camazine. Self-organization in social insects. Trends in Ecology & Evolution, 12(5):188–193, 1997. ↩︎

  7. Nigel R. Franks. Army ants: A collective intelligence. American Scientist, 77(2):138–145, 1989. ↩︎

  8. Madeleine Beekman, David J. T. Sumpter, and Francis L. W. Ratnieks. Phase transition between disordered and ordered foraging in Pharaoh’s ants. Proceedings of the National Academy of Sciences, 98(17):9703–9706, 2001. ↩︎

  9. Rebecca M. Clark and Jennifer H. Fewell. Transitioning from unstable to stable colony growth in the desert leafcutter ant Acromyrmex versicolor. Behavioral Ecology and Sociobiology, 68(1):163–171, 2014. ↩︎

  10. And not, say, by the strength of the interaction between the elements, which is the case in the Li et al. work. ↩︎

  11. The two papers are:

     ↩︎
probability ant colonies programmable matter paper highlights numerosity