Search for: All records

We investigate motion planning algorithms for the assembly of shapes in the tilt model in which unit-square tiles move in a grid world under the influence of uniform external forces and self-assemble according to certain rules. We provide several heuristics and experimental evaluation of their success rate, solution length, and runtime. Video: https://youtu.be/VU1SZYzeaXw Transcript: This animation shows colored tiles moved by a global signal so they all move in the same direction unless blocked. This simple example is solved using the Greatest Distance heuristic, which finds the shortest path in 21 steps. Each tile has glue on the four sides that only stick to compatible glues. Glue type is denoted by color. The objective is to manipulate the tiles to bond in the shape of the connected polyomino target outlined in red. The Polyomino Assembly Problem is PSPACE-hard, so optimal solutions are difficult to find. This more complicated workspace was solved using the Minimum Move to Polyomino or Target. This approach is not optimal, but is a best-first search that attempts to keep tiles not involved in the present construction step separated from each other. This is done by pruning configurations with undesired subassemblies from the search tree. The solution requires 473 steps. 

In this video, we present theoretical and practical methods for achieving arbitrary reconfiguration of a set of objects, based on the use of external forces, such as a magnetic field or gravity: Upon actuation, each object is pushed in the same direction. This concept can be used for a wide range of applications in which particles do not have their own energy supply or in which they are subject to the same global control commands. A crucial challenge for achieving any desired target configuration is breaking global symmetry in a controlled fashion. Previous work (some of which was presented during SoCG 2015) made use of specifically placed barriers; however, introducing precisely located obstacles into the workspace is impractical for many scenarios. In this paper, we present a different, less intrusive method: making use of the interplay between static friction with a boundary and the external force to achieve arbitrary reconfiguration. Our key contributions are theoretical characterizations of the critical coefficient of friction that is sufficient for rearranging two particles in triangles, convex polygons, and regular polygons; a method for reconfiguring multiple particles in rectangular workspaces, and deriving practical algorithms for these rearrangements. Hardware experiments show the efficacy of these procedures, demonstrating the usefulness of this novel approach. 

We investigate algorithmic approaches for targeted drug delivery in a complex, maze-like environment, such as a vascular system. The basic scenario is given by a large swarm of micro-scale particles ("agents") and a particular target region ("tumor") within a system of passageways. Agents are too small to contain on-board power or computation and are instead controlled by a global external force that acts uniformly on all particles, such as an applied fluidic flow or electromagnetic field. The challenge is to deliver all agents to the target region with a minimum number of actuation steps. We provide a number of results for this challenge. We show that the underlying problem is NP-hard, which explains why previous work did not provide provably efficient algorithms. We also develop a number of algorithmic approaches that greatly improve the worst-case guarantees for the number of required actuation steps. We evaluate our algorithmic approaches by a number of simulations, both for deterministic algorithms and searches supported by deep learning, which show that the performance is practically promising. 

We consider recognition and reconfiguration of lattice-based cellular structures by very simple robots with only basic functionality. The underlying motivation is the construction and modification of space facilities of enormous dimensions, where the combination of new materials with extremely simple robots promises structures of previously unthinkable size and flexibility; this is also closely related to the newly emerging field of programmable matter. Aiming for large-scale scalability, both in terms of the number of the cellular components of a structure, as well as the number of robots that are being deployed for construction requires simple yet robust robots and mechanisms, while also dealing with various basic constraints, such as connectivity of a structure during reconfiguration. To this end, we propose an approach that combines ultra-light, cellular building materials with extremely simple robots. We develop basic algorithmic methods that are able to detect and reconfigure arbitrary cellular structures, based on robots that have only constant-sized memory. As a proof of concept, we demonstrate the feasibility of this approach for specific cellular materials and robots that have been developed at NASA. 

We present algorithmic results for the parallel assembly of many micro-scale objects in two and three dimensions from tiny particles, which has been proposed in the context of programmable matter and self-assembly for building high-yield micro-factories. The underlying model has particles moving under the influence of uniform external forces until they hit an obstacle. Particles bond when forced together with another appropriate particle. Due to the physical and geometric constraints, not all shapes can be built in this manner; this gives rise to the Tilt Assembly Problem (TAP) of deciding constructibility. For simply-connected polyominoes P in 2D consisting of N unit-squares (“tiles”), we prove that TAP can be decided in 𝑂(𝑁log𝑁) time. For the optimization variant MaxTAP (in which the objective is to construct a subshape of maximum possible size), we show polyAPX-hardness: unless P = NP, MaxTAP cannot be approximated within a factor of Ω(𝑁13) ; for tree-shaped structures, we give an Ω(𝑁12) -approximation algorithm. For the efficiency of the assembly process itself, we show that any constructible shape allows pipelined assembly, which produces copies of P in O(1) amortized time, i.e., N copies of P in O(N) time steps. These considerations can be extended to three-dimensional objects: For the class of polycubes P we prove that it is NP-hard to decide whether it is possible to construct a path between two points of P; it is also NP-hard to decide constructibility of a polycube P. Moreover, it is expAPX-hard to maximize a sequentially constructible path from a given start point. 

In this video, we consider recognition and reconfiguration of lattice-based cellular structures by very simple robots with only basic functionality. The underlying motivation is the construction and modification of space facilities of enormous dimensions, where the combination of new materials with extremely simple robots promises structures of previously unthinkable size and flexibility. We present algorithmic methods that are able to detect and reconfigure arbitrary polyominoes, based on finite-state robots, while also preserving connectivity of a structure during reconfiguration. Specific results include methods for determining a bounding box, scaling a given arrangement, and adapting more general algorithms for transforming polyominoes.