Irina Kostitsyna

David Kirkpatrick, Irina Kostitsyna, Alfredo Navarra et al.

Among fundamental problems in the context of distributed computing by autonomous mobile entities, one of the most representative and well studied is {\sc Point Convergence}: given an arbitrary initial configuration of identical entities, disposed in the Euclidean plane, move in such a way that, for all $\eps>0$, a configuration in which the separation between all entities is at most $\eps$ is eventually reached and maintained. The problem has been previously studied in a variety of settings, including full visibility, exact measurements (like distances and angles), and synchronous activation of entities. Our study concerns the minimal assumptions under which entities, moving asynchronously with limited and unknown visibility range and subject to limited imprecision in measurements, can be guaranteed to converge in this way. We present an algorithm that solves {\sc Point Convergence}, for entities in the plane, in such a setting, provided the degree of asynchrony is bounded: while any one entity is active, any other entity can be activated at most $k$ times, for some arbitrarily large but fixed $k$. This provides a strong positive answer to a decade old open question posed by Katreniak. We also prove that in a comparable setting that permits unbounded asynchrony, {\sc Point Convergence} in the plane is impossible, contingent on the natural assumption that algorithms maintain the (visible) connectivity among entities present in the initial configuration. This variant, that we call {\sc Cohesive Convergence}, serves to distinguish the power of bounded and unbounded asynchrony in the control of autonomous mobile entities, settling at the same time a long-standing question whether in the Euclidean plane synchronously scheduled entities are more powerful than asynchronously scheduled entities.

Hugo A. Akitaya, Erik D. Demaine, Matias Korman et al.

A well-established theoretical model for modular robots in two dimensions are edge-connected configurations of square modules, which can reconfigure through so-called sliding moves. Dumitrescu and Pach [Graphs and Combinatorics, 2006] proved that it is always possible to reconfigure one edge-connected configuration of $n$ squares into any other using at most $O(n^2)$ sliding moves, while keeping the configuration connected at all times. For certain pairs of configurations, reconfiguration may require $Ω(n^2)$ sliding moves. However, significantly fewer moves may be sufficient. We prove that it is NP-hard to minimize the number of sliding moves for a given pair of edge-connected configurations. On the positive side we present Gather&Compact, an input-sensitive in-place algorithm that requires only $O(\bar{P} n)$ sliding moves to transform one configuration into the other, where $\bar{P}$ is the maximum perimeter of the two bounding boxes. The squares move within the bounding boxes only, with the exception of at most one square at a time which may move through the positions adjacent to the bounding boxes. The $O(\bar{P} n)$ bound never exceeds $O(n^2)$, and is optimal (up to constant factors) among all bounds parameterized by just $n$ and $\bar{P}$. Our algorithm is built on the basic principle that well-connected components of modular robots can be transformed efficiently. Hence we iteratively increase the connectivity within a configuration, to finally arrive at a single solid $xy$-monotone component. We implemented Gather&Compact and compared it experimentally to the in-place modification by Moreno and Sacristán [EuroCG 2020] of the Dumitrescu and Pach algorithm (MSDP). Our experiments show that Gather&Compact consistently outperforms MSDP by a significant margin, on all types of square configurations.

Irina Kostitsyna, Cai Wood, Damien Woods

Molecular robotics is challenging, so it seems best to keep it simple. We consider an abstract molecular robotics model based on simple folding instructions that execute asynchronously. Turning Machines are a simple 1D to 2D folding model, also easily generalisable to 2D to 3D folding. A Turning Machine starts out as a line of connected monomers in the discrete plane, each with an associated turning number. A monomer turns relative to its neighbours, executing a unit-distance translation that drags other monomers along with it, and through collective motion the initial set of monomers eventually folds into a programmed shape. We provide a suite of tools for reasoning about Turning Machines by fully characterising their ability to execute line rotations: executing an almost-full line rotation of $5π/3$ radians is possible, yet a full $2π$ rotation is impossible. Furthermore, line rotations up to $5π/3$ are executed efficiently, in $O(\log n)$ expected time in our continuous time Markov chain time model. We then show that such line-rotations represent a fundamental primitive in the model, by using them to efficiently and asynchronously fold shapes. In particular, arbitrarily large zig-zag-rastered squares and zig-zag paths are foldable, as are $y$-monotone shapes albeit with error (bounded by perimeter length). Finally, we give shapes that despite having paths that traverse all their points, are in fact impossible to fold, as well as techniques for folding certain classes of (scaled) shapes without error. Our approach relies on careful geometric-based analyses of the feats possible and impossible by a very simple robotic system, and pushes conceptional hardness towards mathematical analysis and away from molecular implementation.

Allan Costa, Benjamin Jenett, Irina Kostitsyna et al.

Assembly of large scale structural systems in space is understood as critical to serving applications that cannot be deployed from a single launch. Recent literature proposes the use of discrete modular structures for in-space assembly and relatively small scale robotics that are able to modify and traverse the structure. This paper addresses the algorithmic problems in scaling reconfigurable space structures built through robotic construction, where reconfiguration is defined as the problem of transforming an initial structure into a different goal configuration. We analyze different algorithmic paradigms and present corresponding abstractions and graph formulations, examining specialized algorithms that consider discretized space and time steps. We then discuss fundamental design trades for different computational architectures, such as centralized versus distributed, and present two representative algorithms as concrete examples for comparison. We analyze how those algorithms achieve different objective functions and goals, such as minimization of total distance traveled, maximization of fault-tolerance, or minimization of total time spent in assembly. This is meant to offer an impression of algorithmic constraints on scalability of corresponding structural and robotic design. From this study, a set of recommendations is developed on where and when to use each paradigm, as well as implications for physical robotic and structural system design.

Joshua J. Daymude, Robert Gmyr, Kristian Hinnenthal et al.

We envision programmable matter as a system of nano-scale agents (called particles) with very limited computational capabilities that move and compute collectively to achieve a desired goal. We use the geometric amoebot model as our computational framework, which assumes particles move on the triangular lattice. Motivated by the problem of sealing an object using minimal resources, we show how a particle system can self-organize to form an object's convex hull. We give a distributed, local algorithm for convex hull formation and prove that it runs in $\mathcal{O}(B)$ asynchronous rounds, where $B$ is the length of the object's boundary. Within the same asymptotic runtime, this algorithm can be extended to also form the object's (weak) $\mathcal{O}$-hull, which uses the same number of particles but minimizes the area enclosed by the hull. Our algorithms are the first to compute convex hulls with distributed entities that have strictly local sensing, constant-size memory, and no shared sense of orientation or coordinates. Ours is also the first distributed approach to computing restricted-orientation convex hulls. This approach involves coordinating particles as distributed memory; thus, as a supporting but independent result, we present and analyze an algorithm for organizing particles with constant-size memory as distributed binary counters that efficiently support increments, decrements, and zero-tests --- even as the particles move.

Kevin Buchin, Anne Driemel, Joachim Gudmundsson et al.

The Euclidean $k$-center problem is a classical problem that has been extensively studied in computer science. Given a set $\mathcal{G}$ of $n$ points in Euclidean space, the problem is to determine a set $\mathcal{C}$ of $k$ centers (not necessarily part of $\mathcal{G}$) such that the maximum distance between a point in $\mathcal{G}$ and its nearest neighbor in $\mathcal{C}$ is minimized. In this paper we study the corresponding $(k,\ell)$-center problem for polygonal curves under the Fréchet distance, that is, given a set $\mathcal{G}$ of $n$ polygonal curves in $\mathbb{R}^d$, each of complexity $m$, determine a set $\mathcal{C}$ of $k$ polygonal curves in $\mathbb{R}^d$, each of complexity $\ell$, such that the maximum Fréchet distance of a curve in $\mathcal{G}$ to its closest curve in $\mathcal{C}$ is minimized. In this paper, we substantially extend and improve the known approximation bounds for curves in dimension $2$ and higher. We show that, if $\ell$ is part of the input, then there is no polynomial-time approximation scheme unless $\mathsf{P}=\mathsf{NP}$. Our constructions yield different bounds for one and two-dimensional curves and the discrete and continuous Fréchet distance. In the case of the discrete Fréchet distance on two-dimensional curves, we show hardness of approximation within a factor close to $2.598$. This result also holds when $k=1$, and the $\mathsf{NP}$-hardness extends to the case that $\ell=\infty$, i.e., for the problem of computing the minimum-enclosing ball under the Fréchet distance. Finally, we observe that a careful adaptation of Gonzalez' algorithm in combination with a curve simplification yields a $3$-approximation in any dimension, provided that an optimal simplification can be computed exactly. We conclude that our approximation bounds are close to being tight.