Skip to content

A Creeping Model Of Computation

September 25, 2016

Local rules can achieve global behavior


Sarah Cannon is a current PhD student in our Algorithms, Combinatorics, and Optimization program working with Dana Randall. Sarah has a newly-updated paper with Dana and Joshua Daymude and Andrea Richa entitled, “A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems.” An earlier version was presented at PODC 2016.

Today Ken and I would like to discuss the paper, and relate it to some recent results on soft robots.

For starters let’s call the paper (CDRR)—after the authors last names. Being lazy let me also start by quoting part of their abstract:

We consider programmable matter as a collection of simple computational elements (or particles) with limited (constant-size) memory that self-organize to solve system-wide problems of movement, configuration, and coordination. Here, we focus on the compression problem, in which the particle system gathers as tightly together as possible, as in a sphere or its equivalent in the presence of some underlying geometry. More specifically, we seek fully distributed, local, and asynchronous algorithms that lead the system to converge to a configuration with small perimeter. We present a Markov chain based algorithm that solves the compression problem under the geometric amoebot model, for particle systems that begin in a connected configuration with no holes.

What does this mean? They imagine simple devices that lie on a 2-dimensional lattice. Each device operates in with the same rules: they can decide what to do next based only on their local environment; however, the devices have access to randomness. The goal is that the devices over time should tend, with high probability, to form a tightly grouped system. This is what they call the compression problem. The surprise is that even with only local interactions, {n} such devices can form a configuration that close to as tight a configuration as possible. Roughly they will collapse into a region of perimeter order at most {O(\sqrt{n})}.

Soft Robots

As I started to write this post, I discovered that are some neat results on soft robots. As usual, theorists like CDRR think about {n} objects. They study the behavior of many simple devices and prove theorems that hold often for large enough {n}. Their main one, as a stated above, is that there are devices that can solve the compression problem and get within a region of perimeter order {O(\sqrt{n})}.

On the other hand, practical researchers often start by studying the case of {n=1}. I think both ends of the spectrum are important, and they complement each other. Since I am not a device physicist, I will just point out the highlights of the recent work on soft robots.


The above photo is of a “light-powered micro-robot capable of mimicking the slow, steady crawl of an inchworm or small caterpillar.” See this for more details.

This is research done by a team in Poland led by Piotr Wasylczyk, who writes:

Designing soft robots calls for a completely new paradigm in their mechanics, power supply and control. We are only beginning to learn from nature and shift our design approaches towards these that emerged in natural evolution.

Their soft robot is based on no motors or pneumatic actuators to make it move. Instead it uses a clever liquid crystal elastomer technology: when exposed to light the device moves like a caterpillar. Further the light can be adjusted to make the device move in different ways.

I have no idea if this work can be extended to {n>1}, nor could it be used to implement even small numbers of the devices that CDRR require. I thought you might enjoy hearing about such creepy devices. Let’s turn to the mathematical work on the compression problem.

The Model

CDRR assume that they have a fixed structure, which is an infinite undirected graph. Their devices or particles sit on the vertices of this structure. This, of course, forces the particles to be a discrete system. As you might guess, the usual structures are fixed lattices. These lattices have periodic structure that makes the systems that result at least possible to understand. Even with this regular structure the global behavior of their particles can be quite subtle.

The models of this type have various names; the one they use is called the amoebot model as proposed in this 2014 paper. I like to think of them as soft robots creeping along the lattice.


Okay the above is a cartoon. Here are some more-illustrative figures from the 2014 paper:


Their “particles” reside in a triangular lattice and either sit at one vertex or occupy two adjacent vertices. Figuratively, the worm is either pulled together or is stretched out. They can creep to an adjacent vertex by stretching out and later contracting. They cannot hop as in Chinese checkers.

The Worms Cannot Play Go

We don’t know if the game of Go can be played sensibly on a Chinese checkers board, but anyway these worms cannot play Go. A necessity in Go is forming interior holes called eyes. Although the movement rules crafted by CDRR are entirely local and randomized, the configuration of worms can never make an eye.

Let {a} be a node occupied by a contracted worm {P} and {b} an adjacent empty node. Then let {c} and {d} be the two nodes adjacent to both {a} and {b.} Define the neighborhood {N_{a,b}} to include {c} and {d,}, the other three nodes adjacent to {a}, and the other three nodes adjacent to {b}. Here is an alternate version of the rules in CDRR for it to be legal for {P} to expand into {b} and then contract into {b}:

  1. If both {c,d} are occupied, then all occupied nodes in {N_{a,b}} must be connected within {N_{a,b}} to either {c} or {d} but not both.

  2. If one of {c,d} is occupied, then all occupied nodes in {N_{a,b}} must be connected within {N_{a,b}} to it.

  3. If neither is occupied, then the occupied neighbors of {a} must form one connected component within {N_{a,b}}, and so must the neighbors of {b}.

There are further rules saying initially that no node in {N_{a,b}} may be part of an expanded worm and covering possible adjacent expanded worms after {P} has expanded. However, their effect is to enable treating the nodes concerned as unoccupied, so that Markov chains {M} built on these rules need only use states with all worms contracted. The rules are enforceable by giving each worm a fixed finite local memory that its neighbors can share.

The “not both” in the first rule subsumes their rule that the worm cannot have five occupied neighbors, which would cause an eye upon its moving to {b}. The second and third rules preserve connectedness of the whole and ensure that the move does not connect islands at {b}. The third rule also ensures that a path of open nodes through {c,b,d} now can go {c,a,d}. The rules’ symmetry makes a subsequent move back from {b} to {a} also legal, so that {M} reversible.

Their chain {M} always executes the move if the number {t_a} of triangles the worm was part of on node {a} is no greater than the number {t_b} of triangles it joins on {b}, and otherwise happens with probability {\lambda^{t_b - t_a}} where {\lambda > 1} is a fixed constant. Given the rules, it strikes us that using the difference in neighbor counts as the exponent is equivalent. The whole system is concurrent and asynchronous, but {M} is described by first choosing one worm uniformly at random for a possible move at each step, and then choosing an unoccupied neighbor at random.

Example and Main Theorems

Here is a configuration from their paper in which the only legal moves involve the third rule:


The edges denote adjacent contracted worms, not expanded worms. Suppose the chosen node {a} is the one midway up the second column at left. It forms a triangle with its two neighbors to the left, so {t_a = 1.} The node {b} above {a} is vacant, but moving there would close off a big region below it. The move is prevented by the second rule because {N_{a,b}} would comprise four nodes that are not all connected within {N_{a,b}.} Similarly the node below {a} is forbidden. Either node {b'} to the right of {a} is permitted by rule 3, however. Since {t_{b'} = 2} the move will certainly happen if {b'} is randomly chosen.

This suggests there could be examples where the only legal moves go back and forth, creating cycles as can happen in John Conway’s game of Life. However, CDRR show that every connected hole-free n-worm configuration is reachable from any other. This makes the Markov chain {M} ergodic. Their main theorem is:

Theorem 1 For all {\alpha > 1} and {\lambda > (2 + \sqrt{2})^{\alpha/(\alpha - 1)}}, and sufficiently large {n}, when {M} is run from any connected, hole-free {n}-worm configuration, with all but exponentially vanishing probability it reaches and stays among configurations with total perimeter at most {\alpha} times the minimum possible perimeter for {n} nodes.

The second main theorem shows a threshold of {\lambda < 2.172033\dots} for the opposite behavior: the perimeter stays at size {\Omega(n)}.

The Proof

The researchers CDRR are experts at the analysis of Markov chains. So they view their particles as such a system. Then they need to prove that the resulting Markov system behaves the way they claim: that as time increases they tend to form a tight unit that solves the compression problem.

Luckily there are many analytical tools at their disposal. But regarding the ergodicity alone, they say:

We emphasize the details of this proof are far from trivial, and occupy the next ten pages.

Their particles are pretty simple, but to prove that the system operates as claimed requires quite careful analysis. Take a look at their paper for the details.

I (Dick) will make one last detailed comment. They want their system to operate completely locally. This means that there can be no global clock: each particles operates asynchronously. This requires some clever ideas to make it work: they want each particle to activate in an random manner. They use the trick that random sequences of actions can be approximated using Poisson clocks with mean {1.} The key is:

After each action, a particle then computes another random time drawn from the same distribution and executes again after that amount of time has elapsed. The exponential distribution is unique in that, if particle {P} has just activated, it is equally likely that any particle will be the next particle to activate, including particle {P}. Moreover, the particles update without requiring knowledge of any of the other particles’ clocks. Similar Poisson clocks are commonly used to describe physical systems that perform updates in parallel in continuous time.

Open Problems

After looking at their paper in some depth, we find the result that local independent particles can actually work together to solve a global problem remains intriguing. Yes there are many such results but they usually have global clocks and other assumptions. The fact that compression is achievable by a weaker model is very neat.

4 Comments leave one →
  1. September 25, 2016 7:39 pm

    Reblogged this on Narrowing and commented:
    Programming matter!

  2. September 26, 2016 1:53 am

    How does their model compare to other models such as (probabilistic) cellular automata or self-assembly? In the introduction of their paper, they claim that a difference with cellular automata is that their particles have less computation power (than cells of an automata I guess) though it is not clear to me.

    • Thim permalink
      October 6, 2016 10:36 am

      There are some differences to both mentioned models,to briefly summarize:

      Self-Assembly: The Amoebot particles are active (e.g. they can move) and there number is fixed from the beginning. In (Tile) Self-Assembly nothing can move (or compute) and it is somewhat assumed that you have an infinite supply of each tile.

      Cellular Automata: If I remember correctl, then CAs have a gloabl orientation, whereas the particles only have a local one (i.e., each one of them can distinguish outgoing edges of the lattice). Moreover, in CAs the cells themselves are doing the computation, in the amoebot model, the particles that are on the graph are doing it (and they cannot use the underlying graph for computation).

      I could dive a bit deeper if needed, but I hope that roughly answers the question

  3. Thim permalink
    October 10, 2016 4:05 am

    I just wanted to leave a clarifying comment:

    You are absolutely correct that the CDRR paper forbids holes in the particle structure (i.e., they are not created and the initial structure is not allowed to have holes). However, this is a direct consequence of the fact that the authors use a Markov chain Algorithm to solve the compression problem.

    The original amoebot model allows holes and is able to deal with them.
    In fact, there is even a simple (deterministic) algorithm that solves the compaction problem optimally in linear time (i.e., just build a hexagon) given that you have a leader particle + leader election is solvable in the amoebot model in in (expected) linear time (see the 2015 DNA paper).
    However, the DCRR algorithm is still remarkable, since it is absolutely stateless (and therefore also self-stabilizing). Moreover, it introduces techniques that have not been explored so far and that (potentially) transfer nicely into the real world.

Leave a Reply

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

You are commenting using your 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