TY - GEN

T1 - Forming tile shapes with simple robots

AU - Gmyr, Robert

AU - Hinnenthal, Kristian

AU - Kostitsyna, Irina

AU - Kuhn, Fabian

AU - Rudolph, Dorian

AU - Scheideler, Christian

AU - Strothmann, Thim

PY - 2018

Y1 - 2018

N2 - Motivated by the problem of manipulating nanoscale materials, we investigate the problem of reconfiguring a set of tiles into certain shapes by robots with limited computational capabilities. As a first step towards developing a general framework for these problems, we consider the problem of rearranging a connected set of hexagonal tiles by a single deterministic finite automaton. After investigating some limitations of a single-robot system, we show that a feasible approach to build a particular shape is to first rearrange the tiles into an intermediate structure by performing very simple tile movements. We introduce three types of such intermediate structures, each having certain advantages and disadvantages. Each of these structures can be built in asymptotically optimal O(n2) rounds, where n is the number of tiles. As a proof of concept, we give an algorithm for reconfiguring a set of tiles into an equilateral triangle through one of the intermediate structures. Finally, we experimentally show that the algorithm for building the simplest of the three intermediate structures can be modified to be executed by multiple robots in a distributed manner, achieving an almost linear speedup in the case where the number of robots is reasonably small.

AB - Motivated by the problem of manipulating nanoscale materials, we investigate the problem of reconfiguring a set of tiles into certain shapes by robots with limited computational capabilities. As a first step towards developing a general framework for these problems, we consider the problem of rearranging a connected set of hexagonal tiles by a single deterministic finite automaton. After investigating some limitations of a single-robot system, we show that a feasible approach to build a particular shape is to first rearrange the tiles into an intermediate structure by performing very simple tile movements. We introduce three types of such intermediate structures, each having certain advantages and disadvantages. Each of these structures can be built in asymptotically optimal O(n2) rounds, where n is the number of tiles. As a proof of concept, we give an algorithm for reconfiguring a set of tiles into an equilateral triangle through one of the intermediate structures. Finally, we experimentally show that the algorithm for building the simplest of the three intermediate structures can be modified to be executed by multiple robots in a distributed manner, achieving an almost linear speedup in the case where the number of robots is reasonably small.

KW - Finite automata

KW - Reconfiguration

KW - Shape formation

KW - Tiles

UR - http://www.scopus.com/inward/record.url?scp=85054887058&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-00030-1_8

DO - 10.1007/978-3-030-00030-1_8

M3 - Conference contribution

SN - 978-3-030-00029-5

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 122

EP - 138

BT - DNA Computing and Molecular Programming - 24th International Conference, DNA 24, 2018, Proceedings

A2 - Doty, David

A2 - Dietz, Hendrik

PB - Springer

CY - Cham

T2 - International Conference on DNA Computing and Molecular Programming

Y2 - 8 October 2018 through 12 October 2018

ER -