Forming tile shapes with simple robots

Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, Christian Scheideler, Thim Strothmann

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

8 Citaten (Scopus)


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.
Originele taal-2Engels
TitelDNA Computing and Molecular Programming - 24th International Conference, DNA 24, 2018, Proceedings
RedacteurenDavid Doty, Hendrik Dietz
Plaats van productieCham
Aantal pagina's17
ISBN van elektronische versie978-3-030-00030-1
ISBN van geprinte versie978-3-030-00029-5
StatusGepubliceerd - 2018
EvenementInternational Conference on DNA Computing and Molecular Programming - Jinan, China
Duur: 8 okt 201812 okt 2018

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11145 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349


CongresInternational Conference on DNA Computing and Molecular Programming
Verkorte titelDNA


Duik in de onderzoeksthema's van 'Forming tile shapes with simple robots'. Samen vormen ze een unieke vingerafdruk.

Citeer dit