{\huge A Creepy Model Of Computation}
Local rules can achieve global behavior
\vspace{.25in}
Sarah Cannon is a current PhD student in our Algorithms, Combinatorics, and Optimization program working with Dana Randall. Sarah has a paper with Dana and Joshua Daymude and Andrea Richa entitled, ``A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems.''
Today I would like to discuss the paper, and relate it to some recent results on soft robots.
For starters let's call her 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, $latex {n}&fg=000000$ 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 $latex {O(\sqrt{n})}&fg=000000$.
Soft Robots
While I started to write this post, I discovered that are some neat results on soft robots. As usual, theorists like CDRR think about $latex {n}&fg=000000$ objects. They study the behavior of many simple devices and prove theorems that hold often for large enough $latex {n}&fg=000000$. 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 $latex {O(\sqrt{n})}&fg=000000$.
On the other hand, practical researchers often start by studying the case of $latex {n=1}&fg=000000$. 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.
\includegraphics[width=3in]{poland.png}
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 says:
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 $latex {n>1}&fg=000000$, 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 on 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.
\includegraphics[width=0.8in]{worm.png}
Okay the above is a cartoon. Here are some figures that are more descriptive of how their systems work:
\includegraphics[width=5in]{bot1.png}
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 $latex {a}&fg=000000$ be a node occupied by a contracted worm $latex {P}&fg=000000$ and $latex {b}&fg=000000$ an adjacent empty node. Then let $latex {c}&fg=000000$ and $latex {d}&fg=000000$ be the two nodes adjacent to both $latex {a}&fg=000000$ and $latex {b}&fg=000000$, and let $latex {N_{a,b}}&fg=000000$ include $latex {c}&fg=000000$ and $latex {d}&fg=000000$, the other three nodes adjacent to $latex {a}&fg=000000$, and the other three nodes adjacent to $latex {b}&fg=000000$. The rules in CDRR make it legal for $latex {P}&fg=000000$ to expand into $latex {b}&fg=000000$ and then contract into $latex {b}&fg=000000$ only if:
There are further rules covering possible adjacent expanded worms after $latex {P}&fg=000000$ has expanded, but their effect is to enable treating the nodes concerned as unoccupied, so that Markov chains $latex {M}&fg=000000$ built on these rules need only use states with all worms contracted. Their main $latex {M}&fg=000000$ always executes the move if the number $latex {t_a}&fg=000000$ of triangles the worm was part of on node $latex {a}&fg=000000$ is no greater than the number $latex {t_b}&fg=000000$ of triangles it joins on $latex {b}&fg=000000$, and otherwise happens with probability $latex {\lambda^{t_b - t_a}}&fg=000000$ where $latex {\lambda > 1}&fg=000000$ is a fixed constant. The whole system is asynchronous, but $latex {M}&fg=000000$ 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.
The first rule prevents the move from forming an eye at $latex {a}&fg=000000$. The second and third ensure both that the move preserves connectedness of the whole and that it does not connect islands at $latex {b}&fg=000000$. The third rule also ensures that a path of open nodes through $latex {c,b,d}&fg=000000$ now can go $latex {c,a,d}&fg=000000$. The latter two rules are symmetric and so is the first on the presumption that node $latex {b}&fg=000000$ was not previously an eye. Hence a move back from $latex {b}&fg=000000$ to $latex {a}&fg=000000$ is legal, which makes $latex {M}&fg=000000$ reversible.
Example and Main Theorem
Here is a configuration from their paper in which the only legal moves involve the third rule:
\includegraphics[width=3.5in]{CDRRbotfig2bigger.png}
Here the edges denote adjacent contracted worms, not expanded worms. Suppose the chosen worm is the one midway up the second column at left. It forms a triangle with its two neighbors on the left, so $latex {t_a = 1}&fg=000000$. The node $latex {b}&fg=000000$ above $latex {a}&fg=000000$ is vacant, but moving there would close off a big region below it. The move is prevented by the second rule because $latex {N_{a,b}}&fg=000000$ would comprise three nodes that are not all connected within $latex {N_{a,b}}&fg=000000$. Similarly the node below $latex {a}&fg=000000$ is forbidden. Either node $latex {b'}&fg=000000$ to the right of $latex {a}&fg=000000$ is permitted by rule 3, however. Since $latex {t_{b'} = 2}&fg=000000$ the move will certainly happen if a neighbor $latex {b'}&fg=000000$ not $latex {b}&fg=000000$ 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 $latex {n}&fg=000000$-worm configuration is reachable from any other. This makes the Markov chain $latex {M}&fg=000000$ ergodic. Their main theorem is:
Theorem 1 For all $latex {\alpha > 1}&fg=000000$ and $latex {\lambda > (2 + \sqrt{2})^{\alpha/(\alpha - 1)}}&fg=000000$, and sufficiently large $latex {n}&fg=000000$, when $latex {M}&fg=000000$ is run from any connected, hole-free $latex {n}&fg=000000$-worm configuration, with all but exponentially vanishing probability it reaches and stays among configurations with total perimeter at most $latex {\alpha}&fg=000000$ times the minimum possible perimeter for $latex {n}&fg=000000$ nodes.
They also show a threshold of $latex {\lambda < 2.172033\dots}&fg=000000$ for the opposite behavior: the perimeter stays at size $latex {\Omega(n)}&fg=000000$.
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 as 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 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 $latex {1}&fg=000000$. 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 $latex {P}&fg=000000$ has just activated, it is equally likely that any particle will be the next particle to activate, including particle $latex {P}&fg=000000$. 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 global clocks and other assumptions. The fact that compression is solvable by a weaker model is very neat.