Category: publications

Posted on

Full Tilt: Universal Constructors for General Shapes with Uniform External Forces

Title: Full Tilt: Universal Constructors for General Shapes with Uniform External Forces

Authors: Jose Balanza-Martinez, David Caballero, Angel A. Cantu, Luis Angel Garcia, Austin Luchsinger, Rene Reyes, Robert Schweller, and Tim Wylie

Conference: The 30th ACM-SIAM Symposium on Discrete Algorithms (SODA’19), 2019.

Abstract: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 \emph{universal configurations} that are capable of constructing a large class of shapes and patterns.
For these constructions, we present the notions of \emph{weak} and \emph{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 $\mathcal{O}(hw)$ $1 \times 1$ slidable particles that can be reconfigured to build any $h \times w$ patterned rectangle. We then expand this result to show that there exists a weakly universal configuration that can build any $h \times 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. In both cases, we show this problem to be PSPACE-complete, even when movable particles are restricted to $1\times 1$ and $2\times 2$ polyominoes that do not stick to one another.

URL:

Bibtex:

Accompanying videos related to the paper

Section 3: Pattern and General Shape Builder

Construction of a Pattern:

Construction of a Drop Shape:

Construction of a Non-Drop Shape:

Section 4: Drop Shape Builder

Section 5: Relocation Gadget

Example of Correct Traversal Through our Relocation Gadget:

This video shows the correct sequence of tilts to traverse our robot through the gadget.  Note the closed exit/entrance points of our gadgets do not affect this traversal, and are only there to simplify testing

Example of Incorrect State Traversal Attempt Through our Relocation Gadget:

Here we see the robot trying to traverse our gadget while the gadget is not in the correct state to allow the robot to do so. This is only one of the possible sequences, but no sequence of tilts exists that would allow the robot to traverse through the gadget from this position.

Example of Robot Polyomino Becoming Stuck Through Correct State but Incorrect Traversal Sequence:

Here is an example of the importance of our optimal sequence to traverse through the gadget, although there are many ways to traverse, there are also many ways to enter what we call “stuck” configuration. From these configurations there is no sequence of tilts that would allow the robot to leave the gadget.

Section 6: Reconfiguration Gadget

Example of Correct Traversal Through Our Reconfiguration Gadget:

Example of Moving State Tiles to Reconfiguration Ring:

Here we remove all tiles from the inner section of our gadget and into the “reconfiguration ring”. This property of our gadget is what allows us to achieve a global configuration of our gadgets and classify this problem as a reconfiguration problem.

Example of A System of Reconfiguration Gadgets:

This shows a system of reconfiguration gadgets and the robots traversal through the system. At the end of our traversal we move all our state tiles int the reconfiguration ring and achieve a specific configuration of our entire system.

Example of Traversal Sequences that Preserve Initial State Tile Positions:

The videos here show that we can easily traverse gadgets while maintaining the a small set of positions for our state tiles. We know that from these positions we can traverse the gadget with a sequence that will allow us to keep the positions of our red tiles within this set, while not moving any tiles that started in this set into the reconfiguration ring.

Posted on

Tile Pattern-Building Games on a Grid are PSPACE-complete

Tile Pattern-Building Games on a Grid are PSPACE-complete (Short Abstract).

Angel A. Cantu, Arturo Gonzalez, Cesar Lozano, Austin Luchsinger, Eduardo Medina, Fernando Martinez, Arnoldo Ramirez, and Tim Wylie.
The 21st Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3’18), 2018.

Abstract: In this paper, we investigate a certain class of tile-based pattern games through a simplified version of a recent game titled Nonads. We prove that Nonads is PSPACE-complete with a reduction from bounded 2-player constraint logic (Bounded 2CL) even when both players share the same target and there is only one type of playable tile. This has application to any grid-based pattern building game.

Bibtex:

Posted on

Freezing Simulates Non-freezing Tile Automata

Title: Freezing Simulates Non-freezing Tile Automata

Authors: Cameron Chalk, Austin Luchsinger, Eric Martinez, Robert Schweller, Andrew Winslow, and Tim Wylie
Abstract:

Citation: Proc. of 24th Inter. Conf. on DNA Computing and Molecular Programming (DNA’18)
Bibtex:
PDF:

Posted on

Optimal Staged Self-Assembly of Linear Assemblies

Title: Optimal Staged Self-Assembly of Linear Assemblies
Authors: Cameron Chalk, Eric Martinez, Robert Schweller, Luis Vega, Andrew Winslow, Tim Wylie
Abstract:
We analyze the complexity of building linear assemblies, sets of linear assemblies, and $\mathcal{O}(1)$-scale general shapes in the staged tile assembly model. For systems with at most $b$ bins and $t$ tile types, we prove that the minimum number of stages to uniquely assemble a $1 \times n$ \emph{line} is $\Theta(\log_t{n} + \log_b{\frac{n}{t}} + 1)$. Generalizing to $\BO{1} \times n$ lines, we prove the minimum number of stages is $\BO{\frac{\log{n} – tb – t\log t}{b^2} + \frac{\log \log b}{\log t}}$ and $\Omega(\frac{\log{n} – tb – t\log t}{b^2})$. We also obtain similar upper and lower bounds in a model permitting \emph{flexible glues} using non-diagonal glue functions.

Next, we consider assembling sets of lines and general shapes using $t = \BO{1}$ tile types. We prove that the minimum number of stages needed to assemble a set of $k$ lines of size at most $\BO{1} \times n$ is $\BO{\frac{k\log n}{b^2}+\frac{k\sqrt{\log n}}{b}+\log\log n}$ and $\Omega(\frac{k\log n}{b^2})$. In the case that $b = \BO{\sqrt{k}}$, the minimum number of stages is $\Theta(\log{n})$. The upper bound in this special case is then used to assemble “hefty” shapes of at least logarithmic edge-length-to-edge-count ratio at $\BO{1}$-scale using $\BO{\sqrt{k}}$ bins and optimal $\BO{\log{n}}$ stages.

Citation: Proc. of 17th Inter. Conf. on Unconventional Computation and Natural Computation (UCNC’18)
Bibtex:

Posted on

Self-Assembly of Shapes at Constant Scale using Repulsive Forces

Self-Assembly of Shapes at Constant Scale using Repulsive Forces.
Austin Luchsinger, Robert Schweller, and Tim Wylie. In Natural Computing. 2018.

Link: https://link.springer.com/article/10.1007/s11047-018-9707-9

Abstract:

Bibtex:

 

Conference Version:

Self-Assembly of Shapes at Constant Scale using Repulsive Forces.
Austin Luchsinger, Robert Schweller, and Tim Wylie.
In Proc. of the 16th Inter. Conf. on Unconventional Computation and Natural Computation (UCNC’17), 2017.

Abstract:

Bibtex:

Posted on

Concentration Independent Random Number Generation in Tile Self-Assembly

Title: Concentration Independent Random Number Generation in Tile Self-Assembly
Authors:
In this paper we introduce the robust random number generation problem where the goal is to design an abstract tile assembly system (aTAM system) whose terminal assemblies can be split into n partitions such that a resulting assembly of the system lies within each partition with probability 1/n , regardless of the relative concentration assignment of the tile types in the system. First, we show this is possible for n=2n=2 (a robust fair coin flip ) within the aTAM, and that such systems guarantee a worst case O(1)O(1) space usage. We accompany our primary construction with variants that show trade-offs in space complexity, initial seed size, temperature, tile complexity, bias, and extensibility, and also prove some negative results. As an application, we combine our coin-flip system with a result of Chandran, Gopalkrishnan, and Reif to show that for any positive integer n , there exists a O(log⁡n)O(log⁡n) tile system that assembles a constant-width linear assembly of expected length n for any concentration assignment. We then extend our robust fair coin flip result to solve the problem of robust random number generation in the aTAM for all n. Two variants of robust random bit generation solutions are presented: an unbounded space solution and a bounded space solution which incurs a small bias. Further, we consider the harder scenario where tile concentrations change arbitrarily at each assembly step and show that while this is not possible in the aTAM, the problem can be solved by exotic tile assembly models from the literature.

Bibtex:
PDF:
URL: