Forming tile shapes with simple robots

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

11 Citations (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.
Original languageEnglish
Title of host publicationDNA Computing and Molecular Programming - 24th International Conference, DNA 24, 2018, Proceedings
EditorsDavid Doty, Hendrik Dietz
Place of PublicationCham
Number of pages17
ISBN (Electronic)978-3-030-00030-1
ISBN (Print)978-3-030-00029-5
Publication statusPublished - 2018
EventInternational Conference on DNA Computing and Molecular Programming - Jinan, China
Duration: 8 Oct 201812 Oct 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11145 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference on DNA Computing and Molecular Programming
Abbreviated titleDNA


  • Finite automata
  • Reconfiguration
  • Shape formation
  • Tiles


Dive into the research topics of 'Forming tile shapes with simple robots'. Together they form a unique fingerprint.

Cite this