CADbots: Algorithmic Aspects of Manipulating Programmable Matter with Finite Automata
- PDF / 1,292,672 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 32 Downloads / 184 Views
CADbots: Algorithmic Aspects of Manipulating Programmable Matter with Finite Automata Sándor P. Fekete1 · Robert Gmyr2 · Sabrina Hugo1 · Phillip Keldenich1 · Christian Scheffer1 · Arne Schmidt1 Received: 9 July 2019 / Accepted: 17 August 2020 © The Author(s) 2020
Abstract We contribute results for a set of fundamental problems in the context of programmable matter by presenting algorithmic methods for evaluating and manipulating a collective of particles by a finite automaton that can neither store significant amounts of data, nor perform complex computations, and is limited to a handful of possible physical operations. We provide a toolbox for carrying out fundamental tasks on a given arrangement of particles, using the arrangement itself as a storage device, similar to a higher-dimensional Turing machine with geometric properties. Specific results include time- and space-efficient procedures for bounding, counting, copying, reflecting, rotating or scaling a complex given shape. Keywords Programmable matter · Finite automata · Robots · Geometry · Turing machines · CAD operations
* Sándor P. Fekete [email protected]‑bs.de Robert Gmyr [email protected] Sabrina Hugo [email protected]‑bs.de Phillip Keldenich [email protected]‑bs.de Christian Scheffer [email protected]‑bs.de Arne Schmidt [email protected]‑bs.de 1
Department of Computer Science, TU Braunschweig, Braunschweig, Germany
2
Department of Computer Science, University of Paderborn, Paderborn, Germany
13
Vol.:(0123456789)
Algorithmica
1 Introduction When dealing with classic challenges of robotics, such as exploration, evaluation and manipulation of objects, traditional robot models are based on relatively powerful capabilities, such as the ability (1) to collect and store significant amounts of data, (2) perform intricate computations, and (3) execute complex physical operations. With the ongoing progress in miniaturization of devices, new possibilities emerge for exploration, evaluation and manipulation. However, dealing with small dimensions (as present in the context of micro-robots and even programmable matter) or large dimensions (as in the construction of large-scale structures in space) introduces a vast spectrum of new difficulties and constraints. These include significant limitations to all three of the mentioned capabilities; challenges get even more pronounced in the context of complex small-scale or far-away systems, where there is a significant threshold between “internal” objects and sensors, and “external” control entities [2]. that can evaluate gathered data, extract important information, and provide guidance. In this paper, we present algorithmic methods for evaluating and manipulating a collective of particles by agents of the most basic possible type: finite automata that can neither store significant amounts of data, nor perform complex computations, and are limited to a handful of possible physical operations. The objective is to provide a toolbox for carrying out fundamental tasks on a given arrangement of particles, such
Data Loading...
