A Creeping Model Of Computation

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, 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 .

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 objects. They study the behavior of many simple devices and prove theorems that hold often for large enough . 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 .

On the other hand, practical researchers often start by studying the case of . 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 , 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 be a node occupied by a contracted worm and an adjacent empty node. Then let and be the two nodes adjacent to both and Define the neighborhood to include and , the other three nodes adjacent to , and the other three nodes adjacent to . Here is an alternate version of the rules in CDRR for it to be legal for to expand into and then contract into :

1. If both are occupied, then all occupied nodes in must be connected within to either or but not both.

2. If one of is occupied, then all occupied nodes in must be connected within to it.

3. If neither is occupied, then the occupied neighbors of must form one connected component within , and so must the neighbors of .

There are further rules saying initially that no node in may be part of an expanded worm and covering possible adjacent expanded worms after has expanded. However, their effect is to enable treating the nodes concerned as unoccupied, so that Markov chains 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 . The second and third rules preserve connectedness of the whole and ensure that the move does not connect islands at . The third rule also ensures that a path of open nodes through now can go . The rules’ symmetry makes a subsequent move back from to also legal, so that reversible.

Their chain always executes the move if the number of triangles the worm was part of on node is no greater than the number of triangles it joins on , and otherwise happens with probability where 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 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 is the one midway up the second column at left. It forms a triangle with its two neighbors to the left, so The node above is vacant, but moving there would close off a big region below it. The move is prevented by the second rule because would comprise four nodes that are not all connected within Similarly the node below is forbidden. Either node to the right of is permitted by rule 3, however. Since the move will certainly happen if 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 ergodic. Their main theorem is:

Theorem 1 For all and , and sufficiently large , when is run from any connected, hole-free -worm configuration, with all but exponentially vanishing probability it reaches and stays among configurations with total perimeter at most times the minimum possible perimeter for nodes.

The second main theorem shows a threshold of for the opposite behavior: the perimeter stays at size .

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 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 has just activated, it is equally likely that any particle will be the next particle to activate, including particle . 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.

A Proof Of The Halting Theorem

Toward teaching computability and complexity simultaneously

Large Numbers in Computing source

Wilhelm Ackermann was a mathematician best known for work in constructive aspects of logic. The Ackermann function is named after him. It is used both in complexity theory and in data structure theory. That is a pretty neat combination.

I would like today to talk about a proof of the famous Halting Problem.

How Hard, Really, is SAT?

A new longest computer proof makes us wonder about things from security to the Exponential Time Hypothesis

Marijn Heule, Oliver Kullmann, and Victor Marek are experts in practical SAT solvers. They recently used this ability to solve a longstanding problem popularized by Ron Graham.

Today Ken and I want to discuss their work and ask a question about its ramifications.

Descending Proofs Into Algorithms

A way to make indirect reasoning more palpable

Wikimedia Commons source

Nicholas Saunderson was the fourth Lucasian Professor at Cambridge, two after Isaac Newton. He promoted Newton’s Principia Mathematica in the Cambridge curriculum but channeled his original work into lecture notes and treatises rather than published papers. After his death, most of his work was collected into one book, The Elements of Algebra in Ten Books, whose title recalls Euclid’s Elements. It includes what is often credited as the first “extended” version of Euclid’s algorithm.

Today we raise the idea of using algorithms such as this as the basis for proofs.

A Surprise For Big-Data Analytics

A simple but interesting issue with analyzing high-dimensional data

Peter Landweber, Emanuel Lazar, and Neel Patel are mathematicians. I have never worked with Peter Landweber, but have written papers with Larry and Laura Landweber. Perhaps I can add Peter one day.

Today I want to report on a recent result on the fiber structure of continuous maps.

Do results have a “teach-by-date?”

Teaching automata theory

Noam Chomsky is famous for many many things. He has had a lot to say over his long career, and he wrote over 100 books on topics from linguistics to war and politics.

Today I focus on work that he pioneered sixty years ago.

Yes sixty years ago. The work is usually called the Chomsky hierarchy(CH) and is a hierarchy of classes of formal grammars. It was described by Noam Chomsky in 1956 driven by his interest in linguistics, not war and politics. Some add Marcel-Paul Schützenberger’s name to the hierachry. He played a crucial role in the early development of the theory of formal languages—see his joint
paper with Chomsky from 1962.

The Mathematics Of Dan’s Inferno

A possible error with mathematical ramifications

Non-technical fact-check source

Dan Brown is the bestselling author of the novel The Da Vinci Code. His most recent bestseller, published in 2013, is Inferno. Like two of his earlier blockbusters it has been made into a movie. It stars Tom Hanks and Felicity Jones and is slated for release on October 28.

Today I want to talk about a curious aspect of the book Inferno, since it raises an interesting mathematical question.