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(n 2 ) 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, and explain how the algorithm can be used to construct a triangle distributedly.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Forming tile shapes with simple robots


    Beteiligte:

    Erscheinungsdatum :

    2020-06-01


    Anmerkungen:

    Gmyr , R , Hinnenthal , K , Kostitsyna , I , Kuhn , F , Rudolph , D , Scheideler , C & Strothmann , T 2020 , ' Forming tile shapes with simple robots ' , Natural Computing , vol. 19 , no. 2 , pp. 375-390 . https://doi.org/10.1007/s11047-019-09774-2



    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    629



    Industrial robots in clay roof tile transport system

    British Library Online Contents | 1997




    Drag of cylinders of simple shapes

    Lindsey, W.F. | Engineering Index Backfile | 1938


    Forming Powders in Complex Shapes

    Trapp, W. | British Library Conference Proceedings | 1998