Forming tile shapes with simple robots

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

Onderzoeksoutput: Bijdrage aan congresAbstract

76 Downloads (Pure)

Samenvatting

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 a triangle through one of the intermediate structures.
Originele taal-2Engels
StatusGepubliceerd - 2018
Evenement6th Workshop on Biological Distributed Algorithms (BDA 2018) - London, Verenigd Koninkrijk
Duur: 23 jul 201823 jul 2018
Congresnummer: 6
http://www.snl.salk.edu/~navlakha/BDA2018/

Workshop

Workshop6th Workshop on Biological Distributed Algorithms (BDA 2018)
Verkorte titelBDA 2018
LandVerenigd Koninkrijk
StadLondon
Periode23/07/1823/07/18
Internet adres

    Vingerafdruk

Citeer dit

Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Rudolph, D., Scheideler, C., & Strothmann, T. (2018). Forming tile shapes with simple robots. Abstract van 6th Workshop on Biological Distributed Algorithms (BDA 2018), London, Verenigd Koninkrijk.