Abstract
We consider a discrete system of n simple indistinguishable devices, called agents, forming a connected shape SI on a two-dimensional square grid. Agents are equipped with a linear-strength mechanism, called a line move, by which an agent can push a whole line of consecutive agents in one of the four cardinal directions in a single time-step. We study the problem of transforming an initial shape SI into a given target shape SF via a finite sequence of line moves in a distributed model, where each agent can observe the states of nearby agents in a Moore neighbourhood. We develop the first distributed connectivity-preserving transformation that exploits line moves. The transformation solves the line formation problem. That is, starting from any shape SI whose associated graph contains a Hamiltonian path known to them, the agents can form a final straight line SL. The complexity of the transformation is O(nlog2n) moves, which is asymptotically equivalent to that of the best-known centralised transformations.
•We study a linear-strength model for programmable matter and mobile robotic systems•A single mechanical operation, line pushing, is allowed for the shape formation•A distributed algorithmic framework is presented for line moves•The first distributed connectivity-preserving transformation that exploits line moves•Achieve running time equivalent to that of the best-known centralised algorithms