Fast Reconfiguration for Programmable Matter

Tom Peters, Irina Kostitsyna, Bettina Speckmann

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
Titel37th International Symposium on Distributed Computing, DISC 2023
RedacteurenRotem Oshman
Pagina's27:1-27:21
ISBN van elektronische versie9783959773010
DOI's
StatusGepubliceerd - okt. 2023

Publicatie series

NaamLeibniz International Proceedings in Informatics, LIPIcs
Volume281
ISSN van geprinte versie1868-8969

Vingerafdruk

Duik in de onderzoeksthema's van 'Fast Reconfiguration for Programmable Matter'. Samen vormen ze een unieke vingerafdruk.

Citeer dit