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.

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 2 log 2 n ) time, O ( n 2 ) time, or O ( n log 2 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.

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.

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. For example, in the programmable matter context, which is the focus of this paper, Kostitsyna et al. have utilized shortest path trees to transform one amoebot structure into another [DISC, 2023]. We consider the reconfigurable circuit extension of the model where this amoebot structure is able to interconnect amoebots by so-called circuits. These circuits permit the instantaneous transmission of simple signals between connected amoebots.

Abstract The 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.