Search Results

Documents authored by Padalkin, Andreas

Document
DOI: 10.4230/LIPIcs.DISC.2025.7
On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits

Authors: Matthias Artmann, Andreas Padalkin, and Christian Scheideler

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
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 particle structure. Shape formation problems, where the particles have to reorganize themselves into a desired shape using basic movement abilities, are particularly interesting. In the related shape containment problem, the particles are given the description of a shape S and have to find maximally scaled representations of S within the initial configuration, without movements. For example, if S is a triangle, they have to identify the largest subsets of particles that already form a triangle. While the shape formation problem is being studied extensively, no attention has been given to the shape containment problem, which may have additional uses besides shape formation, such as detecting structural flaws. In this paper, we consider the shape containment problem within the geometric amoebot model for programmable matter, using its reconfigurable circuit extension to enable the instantaneous transmission of primitive signals on connected subsets of particles. We first prove a lower runtime bound of Ω (√n) synchronous rounds for the general problem, where n is the number of particles. Then, we present simple and efficient primitives for identifying subsets that form the desired shape. Using these primitives, we construct a large class of shapes which we call snowflakes. This class contains, among others, all shapes composed of parallelograms and hexagons, and the class of star convex shapes. Let k be the maximum scale of the considered shape in a given amoebot structure. If the shape is star convex, we solve it within 𝒪 (log² k) rounds. If it is a snowflake but not star convex, we solve it within 𝒪 (√n log n) rounds.
Cite as

Matthias Artmann, Andreas Padalkin, and Christian Scheideler. On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{artmann_et_al:LIPIcs.DISC.2025.7,
  author =	{Artmann, Matthias and Padalkin, Andreas and Scheideler, Christian},
  title =	{{On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{7:1--7:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.7},
  URN =		{urn:nbn:de:0030-drops-248240},
  doi =		{10.4230/LIPIcs.DISC.2025.7},
  annote =	{Keywords: Programmable matter, amoebot model, reconfigurable circuits, shape containment}
}
Artifact
Software
DOI: 10.4230/artifacts.23289
AmoebotSim 2.0

Authors: Matthias Artmann, Tobias Maurer, Andreas Padalkin, Daniel Warner, and Christian Scheideler

Abstract
Cite as

Matthias Artmann, Tobias Maurer, Andreas Padalkin, Daniel Warner, Christian Scheideler. AmoebotSim 2.0 (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23289,
   title = {{AmoebotSim 2.0}}, 
   author = {Artmann, Matthias and Maurer, Tobias and Padalkin, Andreas and Warner, Daniel and Scheideler, Christian},
   note = {Software, version 1.8.4., DFG-SCHE 1592/10-1, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:41a83f85a3e7c6c1d5a2fec79533bef04c7ff770;origin=https://github.com/martmannupb/AmoebotSim-2.0;visit=swh:1:snp:8aeb8f3c490d90e04facd9ff0fd699c06b8a2ab6;anchor=swh:1:rev:5873cfc9aa08099e3ebf3b0ce334b8f28cbda75f}{\texttt{swh:1:dir:41a83f85a3e7c6c1d5a2fec79533bef04c7ff770}} (visited on 2025-06-20)},
   url = {https://github.com/martmannupb/AmoebotSim-2.0},
   doi = {10.4230/artifacts.23289},
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2025.81
AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements (Media Exposition)

Authors: Matthias Artmann, Tobias Maurer, Andreas Padalkin, Daniel Warner, and Christian Scheideler

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We present AmoebotSim 2.0, a simulation environment for the geometric amoebot model of programmable matter that supports the reconfigurable circuit and joint movement extensions of the model. In the geometric amoebot model, we consider systems of simple computational entities called amoebots in a regular triangular grid environment. We are interested in distributed algorithms that solve coordination and shape formation problems. The reconfigurable circuit and joint movement extensions of the model allow the amoebots to communicate over greater distances and perform more complex movements, overcoming some limitations of the original model. AmoebotSim 2.0 is an open-source simulation environment that supports these extensions and provides a rich graphical interface, flexible simulation features, an extensive API, and comprehensive documentation.
Cite as

Matthias Artmann, Tobias Maurer, Andreas Padalkin, Daniel Warner, and Christian Scheideler. AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements (Media Exposition). In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 81:1-81:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{artmann_et_al:LIPIcs.SoCG.2025.81,
  author =	{Artmann, Matthias and Maurer, Tobias and Padalkin, Andreas and Warner, Daniel and Scheideler, Christian},
  title =	{{AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{81:1--81:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.81},
  URN =		{urn:nbn:de:0030-drops-232338},
  doi =		{10.4230/LIPIcs.SoCG.2025.81},
  annote =	{Keywords: Programmable matter, amoebot model, reconfigurable circuits, joint movements, simulator}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2025.20
Brief Announcement: Efficient Distributed Algorithms for Shape Reduction via Reconfigurable Circuits

Authors: Nada Almalki, Siddharth Gupta, Othon Michail, and Andreas Padalkin

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
In this paper, we study the problem of efficiently reducing geometric shapes into other such shapes in a distributed setting through size-changing operations. We develop distributed algorithms using the reconfigurable circuit model to enable fast node-to-node communication. Let n denote the number of nodes and k the number of turning points in the initial shape. We show that the system of nodes can reduce itself from any tree to a single node using only shrinking operations in O(k log n) rounds w.h.p. and any tree to its incompressible form in O(log n) rounds given prior knowledge of the incompressible nodes, or O(k log n) without it, w.h.p. We also give an algorithm to transform any tree to a topologically equivalent tree in O(k log n+log² n) rounds w.h.p. using both shrinking and growth operations. On the negative side, we show that one cannot hope for o(log² n)-round transformations for all shapes of Θ(log n) turning points.
Cite as

Nada Almalki, Siddharth Gupta, Othon Michail, and Andreas Padalkin. Brief Announcement: Efficient Distributed Algorithms for Shape Reduction via Reconfigurable Circuits. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 20:1-20:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{almalki_et_al:LIPIcs.SAND.2025.20,
  author =	{Almalki, Nada and Gupta, Siddharth and Michail, Othon and Padalkin, Andreas},
  title =	{{Brief Announcement: Efficient Distributed Algorithms for Shape Reduction via Reconfigurable Circuits}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{20:1--20:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.20},
  URN =		{urn:nbn:de:0030-drops-230730},
  doi =		{10.4230/LIPIcs.SAND.2025.20},
  annote =	{Keywords: growth process, shrinking process, collision avoidance, programmable matter}
}
Document
DOI: 10.4230/LIPIcs.SAND.2024.18
Reconfiguration and Locomotion with Joint Movements in the Amoebot Model

Authors: Andreas Padalkin, Manish Kumar, and Christian Scheideler

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract
We are considering the geometric amoebot model where a set of n amoebots is placed on the triangular grid. An amoebot is able to send information to its neighbors, and to move via expansions and contractions. Since amoebots and information can only travel node by node, most problems have a natural lower bound of Ω(D) where D denotes the diameter of the structure. Inspired by the nervous and muscular system, Feldmann et al. have proposed the reconfigurable circuit extension and the joint movement extension of the amoebot model with the goal of breaking this lower bound. In the joint movement extension, the way amoebots move is altered. Amoebots become able to push and pull other amoebots. Feldmann et al. demonstrated the power of joint movements by transforming a line of amoebots into a rhombus within O(log n) rounds. However, they left the details of the extension open. The goal of this paper is therefore to formalize the joint movement extension. In order to provide a proof of concept for the extension, we consider two fundamental problems of modular robot systems: reconfiguration and locomotion. We approach these problems by defining meta-modules of rhombical and hexagonal shapes, respectively. The meta-modules are capable of movement primitives like sliding, rotating, and tunneling. This allows us to simulate reconfiguration algorithms of various modular robot systems. Finally, we construct three amoebot structures capable of locomotion by rolling, crawling, and walking, respectively.
Cite as

Andreas Padalkin, Manish Kumar, and Christian Scheideler. Reconfiguration and Locomotion with Joint Movements in the Amoebot Model. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{padalkin_et_al:LIPIcs.SAND.2024.18,
  author =	{Padalkin, Andreas and Kumar, Manish and Scheideler, Christian},
  title =	{{Reconfiguration and Locomotion with Joint Movements in the Amoebot Model}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.18},
  URN =		{urn:nbn:de:0030-drops-198963},
  doi =		{10.4230/LIPIcs.SAND.2024.18},
  annote =	{Keywords: programmable matter, modular robot system, reconfiguration, locomotion}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2024.26
Brief Announcement: Collision Detection for Modular Robots - It Is Easy to Cause Collisions and Hard to Avoid Them

Authors: Siddharth Gupta, Marc van Kreveld, Othon Michail, and Andreas Padalkin

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract
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 deciding whether collisions may occur, or can be avoided, if a set of expansion and contraction operations is executed. We study both discrete- and continuous-time models, and allow operations to be coupled into a single parallel group. Our algorithms to decide if a collision may occur run in O(n²log² n) time, O(n²) time, or O(nlog² n) time, depending on the presence and type of coupled operations, in a continuous-time model for a modular robot with n nodes. To decide if collisions can be avoided, we show that a very restricted version is already NP-complete in the discrete-time model, while the same problem is polynomial in the continuous-time model. A less restricted version is NP-hard in the continuous-time model.
Cite as

Siddharth Gupta, Marc van Kreveld, Othon Michail, and Andreas Padalkin. Brief Announcement: Collision Detection for Modular Robots - It Is Easy to Cause Collisions and Hard to Avoid Them. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 26:1-26:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.SAND.2024.26,
  author =	{Gupta, Siddharth and van Kreveld, Marc and Michail, Othon and Padalkin, Andreas},
  title =	{{Brief Announcement: Collision Detection for Modular Robots - It Is Easy to Cause Collisions and Hard to Avoid Them}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{26:1--26:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.26},
  URN =		{urn:nbn:de:0030-drops-199044},
  doi =		{10.4230/LIPIcs.SAND.2024.26},
  annote =	{Keywords: Modular robots, Collision detection, Computational Geometry, Complexity}
}
Document
DOI: 10.4230/LIPIcs.DNA.28.8
The Structural Power of Reconfigurable Circuits in the Amoebot Model

Authors: Andreas Padalkin, Christian Scheideler, and Daniel Warner

Published in: LIPIcs, Volume 238, 28th International Conference on DNA Computing and Molecular Programming (DNA 28) (2022)

Abstract
The amoebot model [Derakhshandeh et al., SPAA 2014] has been proposed as a model for programmable matter consisting of tiny, robotic elements called amoebots. We consider the reconfigurable circuit extension [Feldmann et al., JCB 2022] of the geometric (variant of the) amoebot model that allows the amoebot structure to interconnect amoebots by so-called circuits. A circuit permits the instantaneous transmission of signals between the connected amoebots. In this paper, we examine the structural power of the reconfigurable circuits. We start with some fundamental problems like the stripe computation problem where, given any connected amoebot structure S, an amoebot u in S, and some axis X, all amoebots belonging to axis X through u have to be identified. Second, we consider the global maximum problem, which identifies an amoebot at the highest possible position with respect to some direction in some given amoebot (sub)structure. A solution to this problem can then be used to solve the skeleton problem, where a (not necessarily simple) cycle of amoebots has to be found in the given amoebot structure which contains all boundary amoebots. A canonical solution to that problem can then be used to come up with a canonical path, which provides a unique characterization of the shape of the given amoebot structure. Constructing canonical paths for different directions will then allow the amoebots to set up a spanning tree and to check symmetry properties of the given amoebot structure. The problems are important for a number of applications like rapid shape transformation, energy dissemination, and structural monitoring. Interestingly, the reconfigurable circuit extension allows polylogarithmic-time solutions to all of these problems.
Cite as

Andreas Padalkin, Christian Scheideler, and Daniel Warner. The Structural Power of Reconfigurable Circuits in the Amoebot Model. In 28th International Conference on DNA Computing and Molecular Programming (DNA 28). Leibniz International Proceedings in Informatics (LIPIcs), Volume 238, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{padalkin_et_al:LIPIcs.DNA.28.8,
  author =	{Padalkin, Andreas and Scheideler, Christian and Warner, Daniel},
  title =	{{The Structural Power of Reconfigurable Circuits in the Amoebot Model}},
  booktitle =	{28th International Conference on DNA Computing and Molecular Programming (DNA 28)},
  pages =	{8:1--8:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-253-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{238},
  editor =	{Ouldridge, Thomas E. and Wickham, Shelley F. J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.28.8},
  URN =		{urn:nbn:de:0030-drops-167935},
  doi =		{10.4230/LIPIcs.DNA.28.8},
  annote =	{Keywords: progammable matter, amoebot model, reconfigurable circuits, spanning tree, symmetry detection}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact