Universal Coating for Programmable Matter

Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann.[arXiv] [ScienceDirect] — Journal article in Theoretical Computer Science, pp. 671:56-68, 2017.

Overview

In universal coating, the particle system must coat the surface an arbitrarily shaped object as evenly as possible, using multiple layers if applicable. This paper presents the universal coating algorithm and proves its correctness; a subsequent paper [TODO: link!] proves its runtime bounds.

The algorithm first uses the spanning forest primitive to orient the particle system towards the object. Each particle that is not adjacent to the object then generates a complaint that is passed through the spanning forest until it reaches a particle that can move along the surface. This surface particle consumes the complaint and moves forward once, making room for one more particle to enter the surface. Eventually, this process fills the first layer.

But the particle system immediately encounters two challenges: how do the particles know when the first layer is complete, and how do they know where to start a second layer, if necessary? To solve these problems, the particles use leader election to choose a marker node in the surface layer that denotes the beginning and end of each layer. The marker particle occupying this marker node can then check local conditions to find when its layer is complete. It then triggers the formation of the next layer up, denoting a new marker node for this next layer to use. This general layering primitive continues until all particles have joined the coating.

In the simulation below, the object is a closed, regular hexagon (black particles). The simulation begins with complaint-based coating, which coats the first layer (this occurs very quickly in the demo, but can be seen by pausing at 0:01 and moving the slider). Red particles are super-roots, which move forward when they receive complaints from their followers. Yellow particles are awaiting the election of a marker node, and those on the object’s surface participate in a node-based leader election primitive. The segment colors are the same as in the leader election algorithm. The light grey particle is the elected marker. White particles are followers, which follow their parents to the surface of the coating. Dark grey particles are roots, which move into the current coating layer and become retired when the coating reaches them.

Resources

  • [GitHub] Coming soon!

Press

BibTeX

@article{Derakhshandeh2017,
title = {Universal Coating for Programmable Matter},
author = {Derakhshandeh, Zahra and Gmyr, Robert and Richa, Andr\’ea W. and Scheideler, Christian and Strothmann, Thim},
journal = {Theoretical Computer Science},
volume = {671},
pages = {56–68},
year = {2017} }

Related Publications

This paper subsumes the earlier, unpublished work on Infinite Object Coating (2014), which is a special case of Universal Coating. The runtime for the Universal Coating algorithm is analyzed in the Universal Coating Runtime paper [TODO: link!] (2018).