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

3 Citations (Scopus)

Abstract

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
PublisherSpringer
Pages122-138
Number of pages17
ISBN (Electronic)978-3-030-00030-1
ISBN (Print)978-3-030-00029-5
DOIs
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

Conference

ConferenceInternational Conference on DNA Computing and Molecular Programming
Abbreviated titleDNA
CountryChina
CityJinan
Period8/10/1812/10/18

Keywords

  • Finite automata
  • Reconfiguration
  • Shape formation
  • Tiles

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

  • Cite this

    Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Rudolph, D., Scheideler, C., & Strothmann, T. (2018). Forming tile shapes with simple robots. In D. Doty, & H. Dietz (Eds.), DNA Computing and Molecular Programming - 24th International Conference, DNA 24, 2018, Proceedings (pp. 122-138). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11145 LNCS). Springer. https://doi.org/10.1007/978-3-030-00030-1_8