Distributed Transformations of Hamiltonian Shapes based on Line Moves

2021/08/20 by Almethen, Abdullah, Michail, Othon, Potapov, Igor
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #Robotics (cs.RO) #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.2108.08953

Abstract

We consider a discrete system of n simple indistinguishable devices, called agents, forming a connected shape S_I 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 directions in a single time-step. We study the problem of transforming an initial shape S_I into a given target shape S_F 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. Our main contribution is the first distributed connectivity-preserving transformation that exploits line moves within a total of O(n log₂ n) moves, which is asymptotically equivalent to that of the best-known centralised transformations. The algorithm solves the line formation problem that allows agents to form a final straight line S_L, starting from any shape S_I , whose associated graph contains a Hamiltonian path.

Related

• On Efficient Connectivity-Preserving Transformations in a Grid
• Pushing Lines Helps: Efficient Universal Centralised Transformations for\n Programmable Matter
• On the Transformation Capability of Feasible Mechanisms for Programmable\n Matter
• Efficient Distributed Algorithms for Shape Reduction via Reconfigurable Circuits
• Centralised Connectivity-Preserving Transformations for Programmable Matter: A Minimal Seed Approach