@article{65733,
abstract = {{Abstract
In this paper, we study the computation of shortest paths within the
geometric amoebot model
, a commonly used model for programmable matter. Shortest paths are essential for various tasks and therefore have been heavily investigated in many different contexts. We consider the
reconfigurable circuit extension
of the model where the amoebot structure is able to interconnect amoebots by so-called circuits. These circuits permit the instantaneous transmission of simple signals between connected amoebots. We propose distributed algorithms for the
shortest path forest problem
where, given a set of
k
sources and a set of
$$\ell $$
ℓ
destinations, the amoebot structure has to compute a forest that connects each destination to its closest source on a shortest path. Our main results are two algorithms for hole-free structures. The first algorithm constructs a shortest path tree for a single source within
$$O(\log \ell )$$
O
(
log
ℓ
)
rounds, and the second algorithm a shortest path forest for an arbitrary number of sources within
$$O(\log n \log ^2 k)$$
O
(
log
n
log
2
k
)
rounds. The former algorithm also provides an
O
(1) rounds solution for the
single pair shortest path problem
(SPSP) and an
$$O(\log n)$$
O
(
log
n
)
rounds solution for the
single source shortest path problem
(SSSP) since these problems are special cases of the considered problem. Then, we adapt the latter algorithm to an offset version of the problem. This allows us to solve the problem for amoebot structures with holes within
$$O(h \log ^3 n)$$
O
(
h
log
3
n
)
rounds w.h.p. where
h
denotes the number of holes.
}},
author = {{Padalkin, Andreas and Scheideler, Christian}},
issn = {{0178-2770}},
journal = {{Distributed Computing}},
number = {{2}},
publisher = {{Springer Science and Business Media LLC}},
title = {{{Polylogarithmic time algorithms for shortest path forests in programmable matter}}},
doi = {{10.1007/s00446-026-00505-2}},
volume = {{39}},
year = {{2026}},
}
@article{64098,
author = {{Scheideler, Christian and Padalkin, Andreas and Kumar, Manish}},
journal = {{Reconfiguration and locomotion with joint movements in the amoebot model. Auton. Robots 49(3): 22 (2025)}},
title = {{{Reconfiguration and locomotion with joint movements in the amoebot model. Auton. Robots 49(3): 22 (2025)}}},
year = {{2025}},
}
@inproceedings{64094,
author = {{Scheideler, Christian and Artmann, Matthias and Maurer, Tobias and Padalkin, Andreas and Warner, Daniel}},
title = {{{AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements (Media Exposition). }}},
year = {{2025}},
}
@inproceedings{64097,
author = {{Scheideler, Christian and Artmann, Matthias and Padalkin, Andreas}},
title = {{{On the Shape Containment Problem Within the Amoebot Model with Reconfigurable Circuits. }}},
year = {{2025}},
}
@article{55379,
abstract = {{AbstractThe amoebot model (Derakhshandeh et al. in: SPAA ACM, pp 220–222. https://doi.org/10.1145/2612669.2612712, 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. in J Comput Biol 29(4):317–343. https://doi.org/10.1089/cmb.2021.0363, 2022) of the geometric 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 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 be used to solve the skeleton problem, where a cycle of amoebots has to be found in the given amoebot structure which contains all boundary amoebots. A canonical solution to that problem can 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 allows 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.}},
author = {{Padalkin, Andreas and Scheideler, Christian and Warner, Daniel}},
issn = {{1567-7818}},
journal = {{Natural Computing}},
publisher = {{Springer Science and Business Media LLC}},
title = {{{The structural power of reconfigurable circuits in the amoebot model}}},
doi = {{10.1007/s11047-024-09981-6}},
year = {{2024}},
}
@inproceedings{55378,
author = {{Gupta, Siddharth and van Kreveld, Marc J. and Michail, Othon and Padalkin, Andreas}},
booktitle = {{3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece}},
editor = {{Casteigts, Arnaud and Kuhn, Fabian}},
pages = {{26:1–26:5}},
publisher = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
title = {{{Brief Announcement: Collision Detection for Modular Robots - It Is Easy to Cause Collisions and Hard to Avoid Them}}},
doi = {{10.4230/LIPICS.SAND.2024.26}},
volume = {{292}},
year = {{2024}},
}
@inproceedings{55376,
author = {{Padalkin, Andreas and Kumar, Manish and Scheideler, Christian}},
booktitle = {{3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece}},
editor = {{Casteigts, Arnaud and Kuhn, Fabian}},
pages = {{18:1–18:20}},
publisher = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
title = {{{Reconfiguration and Locomotion with Joint Movements in the Amoebot Model}}},
doi = {{10.4230/LIPICS.SAND.2024.18}},
volume = {{292}},
year = {{2024}},
}
@inproceedings{55377,
author = {{Padalkin, Andreas and Scheideler, Christian}},
booktitle = {{Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing}},
publisher = {{ACM}},
title = {{{Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter}}},
doi = {{10.1145/3662158.3662776}},
year = {{2024}},
}
@inproceedings{64103,
author = {{Scheideler, Christian and Padalkin, Andreas}},
pages = {{65 -- 75}},
title = {{{Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter. }}},
year = {{2024}},
}
@article{64100,
author = {{Scheideler, Christian and Padalkin, Andreas and Warner, Daniel}},
journal = {{The structural power of reconfigurable circuits in the amoebot model. Nat. Comput. 23(4): 603-625 (2024)}},
pages = {{603 -- 625}},
title = {{{The structural power of reconfigurable circuits in the amoebot model. }}},
year = {{2024}},
}
@inproceedings{64105,
author = {{Scheideler, Christian and Padalkin, Andreas and Kumar , Manish }},
title = {{{Reconfiguration and Locomotion with Joint Movements in the Amoebot Model. }}},
year = {{2024}},
}
@article{31060,
author = {{Feldmann, Michael and Padalkin, Andreas and Scheideler, Christian and Dolev, Shlomi}},
journal = {{J. Comput. Biol.}},
number = {{4}},
pages = {{317–343}},
title = {{{Coordinating Amoebots via Reconfigurable Circuits}}},
doi = {{10.1089/cmb.2021.0363}},
volume = {{29}},
year = {{2022}},
}
@inproceedings{32602,
author = {{Padalkin, Andreas and Scheideler, Christian and Warner, Daniel}},
booktitle = {{28th International Conference on DNA Computing and Molecular Programming (DNA 28)}},
editor = {{Ouldridge, Thomas E. and Wickham, Shelley F. J.}},
isbn = {{978-3-95977-253-2}},
issn = {{1868-8969}},
pages = {{8:1–8:22}},
publisher = {{Schloss Dagstuhl – Leibniz-Zentrum für Informatik}},
title = {{{The Structural Power of Reconfigurable Circuits in the Amoebot Model}}},
doi = {{10.4230/LIPIcs.DNA.28.8}},
volume = {{238}},
year = {{2022}},
}
@inproceedings{28917,
author = {{Feldmann, Michael and Padalkin, Andreas and Scheideler, Christian and Dolev, Shlomi}},
booktitle = {{Stabilization, Safety, and Security of Distributed Systems - 23rd International Symposium, (SSS) 2021, Virtual Event, November 17-20, 2021, Proceedings}},
editor = {{Johnen, Colette and Michael Schiller, Elad and Schmid, Stefan}},
pages = {{484--488}},
publisher = {{Springer}},
title = {{{Coordinating Amoebots via Reconfigurable Circuits}}},
doi = {{10.1007/978-3-030-91081-5\_34}},
volume = {{13046}},
year = {{2021}},
}
@misc{25130,
author = {{Padalkin, Andreas}},
title = {{{Fire Containment by Back Burning on Grids}}},
year = {{2019}},
}
@misc{25129,
author = {{Padalkin, Andreas}},
title = {{{Modulbasierte Realisierung eines mittels Backpropagation lernenden Neuronalen Netzes auf einem FPGA}}},
year = {{2016}},
}