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.
Forming tile shapes with simple robots
2020-06-01
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
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
DDC: | 629 |
Industrial robots in clay roof tile transport system
British Library Online Contents | 1997
Cold roll forming heavy shapes
Tema Archiv | 1989
Cold roll forming heavy shapes
Tema Archiv | 1989
Drag of cylinders of simple shapes
Engineering Index Backfile | 1938
|Forming Powders in Complex Shapes
British Library Conference Proceedings | 1998
|