Distributed transformations of Hamiltonian shapes based on line moves



Almethen, Abdullah, Michail, Othon ORCID: 0000-0002-6234-3960 and Potapov, Igor
(2023) Distributed transformations of Hamiltonian shapes based on line moves. In: ALGOSENSORS, 2021-9-9 - 2021-9-10.

[img] Text
AMP-ALGOSENSORS-21.pdf - Author Accepted Manuscript

Download (584kB) | Preview

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(nlog2⁡n) moves, which is asymptotically equivalent to that of the best-known centralised transformations.

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: Line movement, Discrete transformations, Shape formation, Reconfigurable robotics, Programmable matter, Distributed algorithms
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 02 Sep 2021 08:14
Last Modified: 25 Jan 2023 14:20
DOI: 10.1016/j.tcs.2022.11.029
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3135614