License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2023.27
URN: urn:nbn:de:0030-drops-191533
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19153/
Go to the corresponding LIPIcs Volume Portal

Kostitsyna, Irina ; Peters, Tom ; Speckmann, Bettina

Fast Reconfiguration for Programmable Matter

pdf-format:
LIPIcs-DISC-2023-27.pdf (14 MB)

Abstract

The concept of programmable matter envisions a very large number of tiny and simple robot particles forming a smart material. Even though the particles are restricted to local communication, local movement, and simple computation, their actions can nevertheless result in the global change of the material’s physical properties and geometry.
A fundamental algorithmic task for programmable matter is to achieve global shape reconfiguration by specifying local behavior of the particles. In this paper we describe a new approach for shape reconfiguration in the amoebot model. The amoebot model is a distributed model which significantly restricts memory, computing, and communication capacity of the individual particles. Thus the challenge lies in coordinating the actions of particles to produce the desired behavior of the global system.
Our reconfiguration algorithm is the first algorithm that does not use a canonical intermediate configuration when transforming between arbitrary shapes. We introduce new geometric primitives for amoebots and show how to reconfigure particle systems, using these primitives, in a linear number of activation rounds in the worst case. In practice, our method exploits the geometry of the symmetric difference between input and output shape: it minimizes unnecessary disassembly and reassembly of the particle system when the symmetric difference between the initial and the target shapes is small. Furthermore, our reconfiguration algorithm moves the particles over as many parallel shortest paths as the problem instance allows.

BibTeX - Entry

@InProceedings{kostitsyna_et_al:LIPIcs.DISC.2023.27,
  author =	{Kostitsyna, Irina and Peters, Tom and Speckmann, Bettina},
  title =	{{Fast Reconfiguration for Programmable Matter}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{27:1--27:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19153},
  URN =		{urn:nbn:de:0030-drops-191533},
  doi =		{10.4230/LIPIcs.DISC.2023.27},
  annote =	{Keywords: Programmable matter, amoebot model, shape reconfiguration}
}

Keywords: Programmable matter, amoebot model, shape reconfiguration
Collection: 37th International Symposium on Distributed Computing (DISC 2023)
Issue Date: 2023
Date of publication: 05.10.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI