9 papers
Logarithmic-Time Geodesically Convex Decomposition in Programmable Matter
Henning Hillebrandt, Andreas Padalkin, Christian Scheideler +2
The decomposition of complex structures into simpler substructures is a powerful technique with a wide range of applications. We study the computation of decompositions in the cont…
Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements
Manish Kumar, Othon Michail, Andreas Padalkin +1
We study centralized reconfiguration problems for geometric amoebot structures. A set of amoebots occupy nodes on the triangular grid and can reconfigure via expansion and cont…
Efficient Distributed Algorithms for Shape Reduction via Reconfigurable Circuits
Nada Almalki, Siddharth Gupta, Othon Michail +1
Autonomous reconfiguration of agent-based systems is a key challenge in the study of programmable matter, distributed robotics, and molecular self-assembly. While substantial prior…
On the Shape Containment Problem within the Amoebot Model with Reconfigurable Circuits
Matthias Artmann, Andreas Padalkin, Christian Scheideler
In programmable matter, we consider a large number of tiny, primitive computational entities called particles that run distributed algorithms to control global properties of the pa…
Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter
Andreas Padalkin, Christian Scheideler
In this paper, we study the computation of shortest paths within the \emph{geometric amoebot model}, a commonly used model for programmable matter. Shortest paths are essential for…
Reconfiguration and Locomotion with Joint Movements in the Amoebot Model
Andreas Padalkin, Manish Kumar, Christian Scheideler
We are considering the geometric amoebot model where a set of amoebots is placed on the triangular grid. An amoebot is able to send information to its neighbors, and to move vi…
Collision Detection for Modular Robots -- it is easy to cause collisions and hard to avoid them
Siddharth Gupta, Marc van Kreveld, Othon Michail +1
We consider geometric collision-detection problems for modular reconfigurable robots. Assuming the nodes (modules) are connected squares on a grid, we investigate the complexity of…
The Structural Power of Reconfigurable Circuits in the Amoebot Model
Andreas Padalkin, Christian Scheideler, Daniel Warner
The amoebot model [Derakhshandeh et al., 2014] has been proposed as a model for programmable matter consisting of tiny, robotic elements called amoebots. We consider the reconfigur…
Accelerating Amoebots via Reconfigurable Circuits
Michael Feldmann, Andreas Padalkin, Christian Scheideler +1
We consider an extension to the geometric amoebot model that allows amoebots to form so-called \emph{circuits}. Given a connected amoebot structure, a circuit is a subgraph formed…