Algorithmic Foundations of Programmable Matter

We introduce the self-replication of hierarchical robotic swarms made by robotic swarms. This is accomplished by discretizing their construction from a feedstock of primitive building blocks that are simultaneously simpler than prior reconfigurable robotic modules and can be composed to create a wide range of functionality. The motivating application is the assembly of high-performance (high specific modulus and strength) cellular structures, for which the swarms function as a combined material-robot system. The discretization significantly simplifies the swarm’s navigation, error correction, and coordination. Such a system can build serially, can grow exponentially by building more robots, and can grow hierarchically by building larger robots. We present an algorithm for this novel path-planning problem to compile a shape into a swarm to construct it, show an experimental design of the building block basis set, and model the scaling tradeoffs.

This talk gives a brief overview of three areas in DNA self-assembly, with emphasis on open problems, including:

• $\mathrm{■}$

  Self-assembly for flexible armed tiles, and also geometric tiles for example in the octet truss.

• $\mathrm{■}$

  Identifying reporter strands for verifying experimental results.

• $\mathrm{■}$

  The problems and possibilites of knotted scaffolding strands in DNA origami.

How can a set of identical mobile agents coordinate their motions to transform their arrangement from a given starting to a desired goal configuration? We consider this question in the context of actual physical devices called Catoms, which can perform reconfiguration, but need to maintain connectivity at all times to ensure communication and energy supply. We demonstrate and animate algorithmic results, in particular a proof of hardness, as well as an algorithm that guarantees constant stretch for certain classes of arrangements: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of d, then the total duration of our overall schedule is in O(d), which is optimal up to constant factors.

One of the most fundamental and well-studied problems in Tile Self-Assembly is the Unique Assembly Verification (UAV) problem. This algorithmic problem asks whether a given tile system uniquely assembles a specific assembly. The complexity of this problem in the 2-Handed Assembly Model (2HAM) at a constant temperature is a long-standing open problem since the model was introduced. Previously, only membership in the class coNP was known and that the problem is in P if the temperature is one ($\tau =1$). The problem is known to be hard for many generalizations of the model, such as allowing one step into the third dimension or allowing the temperature of the system to be a variable, but the most fundamental version has remained open.

In this paper, we prove the UAV problem in the 2HAM is hard even with a small constant temperature ($\tau =2$), and finally answer the complexity of this problem (open since 2013). Further, this result proves that UAV in the staged self-assembly model is coNP-complete with a single bin and stage (open since 2007), and that UAV in the q-tile model is also coNP-complete (open since 2004). We reduce from Monotone Planar 3-SAT with Neighboring Variable Pairs, a special case of 3SAT recently proven to be NP-hard. We accompany this reduction with a positive result showing that UAV is solvable in polynomial time with the promise that the given target assembly will have a tree-shaped bond graph, i.e., contains no cycles. We provide a $𝒪(n^5)$ algorithm for UAV on tree-bonded assemblies when the temperature is fixed to $2$, and a $𝒪(n^5\log \tau )$ time algorithm when the temperature is part of the input.

Robots sense, move and act in the physical world. It is therefore natural that understanding the geometry of the problem at hand is often key to devising an effective robotic solution. I will review several problems in robotics and automation in whose solution geometry plays a major role. These include designing optimized 3D printable fixtures, object rearrangement by robot arm manipulators, and efficient coordination of the motion of large teams of robots. As we shall see, exploiting geometric structure can, among other benefits, lead to reducing the dimensionality of the underlying search space and in turn to efficient solutions.

The concept of programmable matter envisions a very large number of tiny and simple robot particles forming a smart material that can change its physical properties and shape based on the outcome of computation and movement performed by the individual particles in a concurrent manner. We use geometric insights to develop a new type of shortest path tree for programmable matter systems. Our feather trees utilize geometry to allow particles and information to traverse the programmable matter structure via shortest paths even in the presence of multiple overlapping trees.

This presentation introduces VisibleSim a behavioral simulator for distributed robots placed in a regular 3D lattice. I first present our programming model and then show a video that introduce VisibleSim, presenting the several robots that can be simulated, with different shapes and capabilities (change color, move from one cell of the lattice to another one…). VisibleSim is a C++ project that allow to observe the effects of running the same program in all the robots, in order to debug, capture picture and video from the simulation. The second part of the presentation shows step by step how to write an application code (BlockCode) for VisibleSim to displace a line of 4 SlidingCubes. Using our online generator which generate a runnable skeleton of the application from a formular, for your application the code that must be added is very limited to get a quick result. Finally in the third part of my presentation, I have presented an application of self-reconfiguration developed with VisibleSim applied on 3D Catoms robots which are placed in a Face Centered Cubic lattice and are able to roll to neighbor to change their position in the grid. We first define meta-modules made of 10 modules, and the basic process to dismantle, transfer and assemble these meta-modules. Using VisibleSim, we evaluate an algorithm that compute a distributed version of the Max-Flow algorithm to compute a set of separated paths between sources (Meta-module that must be removes) and destinations (connected meta-modules that must be added), and finally moves modules along these paths.

For controlling the movement of swarms of robots or drones, the positions of the robotic entities need to be tracked at sub-decimeter level. This entails a number of research challanges, (i) minimizing the overhead for the infrastructure needed to support tracking such as the number of reference anchors (ii) scaling to a large number of densely deployed robotic elements (iii) supporting a high update rate for positions in the order of hundrets to thousands of position fixes per second, and (iv) robustness in harsh environments, for example due to obstacles blocking the line of sight between anchors and robotic elements. In this talk we present two results to address these challanges using Ultra-Wide-Band (UWB) communication. In the first solutions, a single anchor supports localization by exploiting the reflections of the UWB signals from the walls. In the second solution, multiple anchors submit UWB pulses quasi simultaneously to allow robotic entities to localize themselves with just a single UWB message reception operation, thus supporting scaling to an arbitraty number of robotic elements and more than 1000 position updates per second.

In my presentation, I raised a number of open problems for reconfigurable circuit extension of the amoebot model. In this extension, amoebots can set up circuits stretching many amoebots. If at least one amoebots beeps on such a circuit, all amoebots of that circuit will receive it, and otherwise no amoebot will receive a beep. When a beep is received, an amoebot cannot determine the direction it came from or the number of amoebots that beeped.

First, consider the case of rapid shape transformation. We have shown that when performing joint expansions and contractions on top of the circuit model, one can transform a line of n amoebots into a parallelogram in just O(log n) rounds [1]. However, what is the minimum number of joint expansions and contractions to get from one structure to another? Can this be computed efficiently and transformed into a distributed algorithm?

Second, consider the case of rapid energy transfer or, more concretely, the problem of repairing an amoebot structure by moving a collection of amoebots from places where they should be removed to places where they are needed. Both of these problems can be reduced to a fairly elementary problem of establishing a shortest path from one position of the amoebot structure to another (e.g., [2]). Is there a fast algorithm for constructing a circuit between these two positions representing a shortest path in the circuit model?

Third, consider the case of seed-less shape transformation. All amoebot algorithms that transform an arbitrary amoebot structure in a hexagon are based on a seed (e.g., [3]). Can we also come up with an algorithm that does not need a seed or leader to perform the transformation.

Finally, consider the situation of faulty amoebots (e.g., [4]). How can we design algorithms for shape transformation that are resilient to permanent failures of amoebots?

In this open problem presentation, we introduced a method to learn cellular automata (CA) rules to grow and reconfigure optimal structures based on given boundary conditions and objective functions. Now that we have CA local rules to update a voxel state based on only its neighbors’ state, we proposed working on the materialization of this method to be used for the assembly and reconfiguration of structures. We proposed first working on implementing distributed path planning algorithms for the swam assembly and reconfiguration of structures using the learned neural cellular automata (NCA) rules. We also proposed working on understanding the theoretical bounds of the geometries can/cannot be built using these algorithms in order to edit/update/constrain the learned NCA rules.

This open problem is concerned with a (discrete) CRN task referred to as self-stabilizing modular clock. For this task, let $Z_k$ denote the additive cyclic group over the integers modulo $k$. We wish to build a CRN over a species set $\mathrm{\Sigma }\cup \{E\}$ where $E$ is a designated highly reactive external species, associated with a function $\kappa :\mathrm{\Sigma }\to Z_k$ that maps each species $A\in \mathrm{\Sigma }$ to a clock value $\kappa (A)\in Z_k$. A configuration over $\mathrm{\Sigma }$ in which all molecules have the same clock value is said to be synchronized. We are interested in constructing a CRN that satisfies the following properties:

1. 1.

   From any initial configuration, the CRN is guaranteed to stabilize to a halting synchronized configuration.

2. 2.

   The external species $E$ reacts with all species in $\mathrm{\Sigma }$ and is not produced by any reaction.

3. 3.

   If we are in a synchronized halting configuration with clock value $i\in Z_k$ and a “small” number of external molecules (“a drop”) are added to the solution, then the CRN is guaranteed to stabilize to a halting synchronized configuration with clock value $i+1modk$.

It is trivial to design such a CRN operating under a fair scheduler, assuming the “usual” notion of fairness ([1]), however we are interested in the following weaker versions of fairness: (F1) Every reaction which is applicable infinitely often is scheduled infinitely often (that is, no reaction can be “starved” indefinitely). (F2) Every reaction which is applicable infinitely often is either scheduled or becomes inapplicable infinitely often (that is, no reaction can be “starved” continuously and indefinitely).

Does there exist such a CRN? For which values of $k$? Does the task become easier if we omit the requirement of halting configurations? Does the task become easier if we relax the “self-stabilization” requirement so that starting from an (adversarial) initial configuration, the system is guaranteed to go back to “proper operation” after a few rounds of “external species drops”?