skip to main content

Explore Research Products in the NSF-PAR

Title: Full Tilt: Universal Constructors for General Shapes with Uniform External Forces
We investigate the problem of assembling general shapes and patterns in a model in which particles move based on uniform external forces until they encounter an obstacle. In this model, corresponding particles may bond when adjacent with one another. Succinctly, this model considers a 2D grid of “open” and “blocked” spaces, along with a set of slidable polyominoes placed at open locations on the board. The board may be tilted in any of the 4 cardinal directions, causing all slidable polyominoes to move maximally in the specified direction until blocked. By successively applying a sequence of such tilts, along with allowing different polyominoes to stick when adjacent, tilt sequences provide a method to reconfigure an initial board configuration so as to assemble a collection of previous separate polyominoes into a larger shape. While previous work within this model of assembly has focused on designing a specific board configuration for the assembly of a specific given shape, we propose the problem of designing universal configurations that are capable of constructing a large class of shapes and patterns. For these constructions, we present the notions of weak and strong universality which indicate the presence of “excess” polyominoes after the shape is constructed. In particular, for given integers h, w, we show that there exists a weakly universal configuration with O(hw) 1 × 1 slidable particles that can be reconfigured to build any h × w patterned rectangle. We then expand this result to show that there exists a weakly universal configuration that can build any h × w-bounded size connected shape. Following these results, which require an admittedly relaxed assembly definition, we go on to show the existence of a strongly universal configuration (no excess particles) which can assemble any shape within a previously studied “drop” class, while using quadratically less space than previous results. Finally, we include a study of the complexity of deciding if a particle within a configuration may be relocated to another position, and deciding if a given configuration may be transformed into a second given configuration. We show both problems to be PSPACE-complete even when no particles stick to one another and movable particles are restricted to 1 × 1 tiles and a single 2 × 2 polyomino.  more » « less
Award ID(s):
1817602
NSF-PAR ID:
10099120
Author(s) / Creator(s):
; ; ; ; ; ; ;
Date Published:
Journal Name:
Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms
ISSN:
1557-9468
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; ; ; ; ; ( , ACM-SIAM Symposium on Discrete Algorithms)
    Advances in technology have given us the ability to create and manipulate robots for numerous applications at the molecular scale. At this size, fabrication tool limitations motivate the use of simple robots. The individual control of these simple objects can be infeasible. We investigate a model of robot motion planning, based on global external signals, known as the tilt model. Given a board and initial placement of polyominoes, the board may be tilted in any of the 4 cardinal directions, causing all slidable polyominoes to move maximally in the specified direction until blocked.We propose a new hierarchy of shapes and design a single configuration that is strongly universal for any w×h bounded shape within this hierarchy (it can be reconfigured to construct any w×h bounded shape in the hierarchy). This class of shapes constitutes the most general set of buildable shapes in the literature, with most previous work consisting of just the first-level of our hierarchy. We accompany this result with a O(n4logn)-time algorithm for deciding if a given hole-free shape is a member of the hierarchy. For our second result, we resolve a long-standing open problem within the field: We show that deciding if a given position may be covered by a tile for a given initial board configuration is PSPACE-complete, even when all movable pieces are 1×1 tiles with no glues. We achieve this result by a reduction from Non-deterministic Constraint Logic for a one-player unbounded game. 
    more » « less
  2. ; ; ; ; ; ; ( , Algorithmica)
    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. 
    more » « less
  3. ; ; ; ; ( , Natural Computing)
    We investigate algorithmic control of a large swarm of mobile particles (such as robots, sensors, or building material) that move in a 2D workspace using a global input signal (such as gravity or a magnetic field). Upon activation of the field, each particle moves maximally in the same direction until forward progress is blocked by a stationary obstacle or another stationary particle. In an open workspace, this system model is of limited use because it has only two controllable degrees of freedom—all particles receive the same inputs and move uniformly. We show that adding a maze of obstacles to the environment can make the system drastically more complex but also more useful. We provide a wide range of results for a wide range of questions. These can be subdivided into external algorithmic problems, in which particle configurations serve as input for computations that are performed elsewhere, and internal logic problems, in which the particle configurations themselves are used for carrying out computations. For external algorithms, we give both negative and positive results. If we are given a set of stationary obstacles, we prove that it is NP-hard to decide whether a given initial configuration of unit-sized particles can be transformed into a desired target configuration. Moreover, we show that finding a control sequence of minimum length is PSPACE-complete. We also work on the inverse problem, providing constructive algorithms to design workspaces that efficiently implement arbitrary permutations between different configurations. For internal logic, we investigate how arbitrary computations can be implemented. We demonstrate how to encode dual-rail logic to build a universal logic gate that concurrently evaluates AND, NAND, NOR, and OR operations. Using many of these gates and appropriate interconnects, we can evaluate any logical expression. However, we establish that simulating the full range of complex interactions present in arbitrary digital circuits encounters a fundamental difficulty: a FAN-OUT gate cannot be generated. We resolve this missing component with the help of 2 9 1 particles, which can create FAN-OUT gates that produce multiple copies of the inputs. Using these gates we provide rules for replicating arbitrary digital circuits. 
    more » « less
  4. ; ; ; ; ; ; ( , The 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games, JCDCGGG)
    We study a model where particles exist within a board and move single units based on uniform external forces. We investigate the complexity of deciding whether a single particle can be relocated to another position in the board, and whether a board configuration can be transformed into another configuration. We prove that the problems are NP-complete with 1× 1 particles even when only allowed to move in 2 or 3 directions. 
    more » « less
  5. ; ; ( , 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS))
    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. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email