Title: Verification and Computation in Restricted Tile Automata
Authors: David Caballero, Timothy Gomez, Robert Schweller, and Tim Wylie
Conference: The 26th International Conference on DNA Computing and Molecular Programming (DNA’20), 2020
Abstract:
Many models of self-assembly have been shown to be capable of performing computation. Tile Automata was recently introduced combining features of both Celluar Automata and the 2-Handed Model of self-assembly both capable of universal computation. In this work we study the complexity of Tile Automata utilizing features inherited from the two models mentioned above. We first present a construction for simulating Turing Machines that performs both covert and fuel efficient computation. We then explore the capabilities of limited Tile Automata systems such as 1-Dimensional systems (all assemblies are of height $1$) and freezing Systems (tiles may not repeat states). Using these results we provide a connection between the problem of finding the largest uniquely producible assembly using $n$ states and the busy beaver problem for non-freezing systems and provide a freezing system capable of uniquely assembling an assembly whose length is exponential in the number of states of the system. We finish by exploring the complexity of the Unique Assembly Verification problem in Tile Automata with different limitations such as freezing and systems without the power of detachment.
Title: Hierarchical Shape Construction and Complexity for Slidable Polyominos under Uniform External Forces Authors: Jose Balanza-Martinez, David Caballero, Angel A. Cantu, Mauricio Flores, Timothy Gomez, Austin Luchsinger, Rene Reyes, Robert Schweller, and Tim Wylie Conference: The 31st ACM-SIAM Symposium on Discrete Algorithms (SODA’20), 2020.
Abstract: 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 \emph{strongly universal} for any $w \times h$ bounded shape within this hierarchy (it can be reconfigured to construct any $w \times 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(n^4 \log n)$-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 \times 1$ tiles with no glues. We achieve this result by a reduction from Non-deterministic Constraint Logic for a one-player unbounded game.
We show the construction of a strict level 2 polyomino using two tile types following the command sequences described in the paper. This polyomino cannot be built by the level 1 constructor, and requires the use of the level 2 constructor.
NCL Reduction:
Succesful Relocation of 1×1 Tile:
This video shows a solution to an instance of the relocation problem in ful tilt that was generated from a constraint graph. The image below shows the successive states of the the corresponding constraint graph. The target configuration is shown in the rightmost graph.
Unsuccesful Relocation of 1×1 Tile:
This video shows the an attempt at completing the relocation process when the gadgets are not in the correct state, causing a tile to get trapped. The starting and goal configurations are the same as the previous example. The image below shows the successive states of the the corresponding constraint graph.
Title: Relocating Units in Robot Swarms with Uniform Control Signals is PSPACE-Complete
Authors:David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, Tim Wylie
Conference: The 32nd Canadian Conference on Computational Geometry (CCCG 2020)
Abstract: This paper investigates a restricted version of robot motion planning, in which particles on a board uniformly respond to global signals that cause them to move one unit distance in a particular direction on a 2D grid board with geometric obstacles. We show that the problem of deciding if a particular particle can be relocated to a specified location on the board is PSPACE-complete when only allowing 1×1 particles. This shows a separation between this problem, called the relocation problem, and the occupancy problem in which we ask whether a particular location can be occupied by any particle on the board, which is known to be in P with only 1×1 particles. We then consider both the occupancy and relocation problems for the case of extremely simple rectangular geometry, but slightly more complicated pieces consisting of 1×2 and 2×1 domino particles, and show that in both cases the problems are PSPACE-complete.
Title: Building Patterned Shapes in Robot Swarms with Uniform Control Signals
Authors:David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, Tim Wylie
Conference: The 32nd Canadian Conference on Computational Geometry (CCCG 2020)
Abstract: This paper investigates a restricted version of robot motion planning, in which particles on a board uniformly respond to global signals that cause them to move one unit distance in a particular direction. We look at the problem of assembling patterns within this model. We first derive upper and lower bounds on the worst-case number of steps needed to reconfigure a general purpose board into a target pattern. We then show that the construction of k-colored patterns of size-n requires Ω(n log k) steps in general, and Ω(n log k +√k) steps if the constructed shape must always be placed in a designated output location. We then design algorithms to approach these lower bounds: We show how to construct k-colored 1 × n lines in O(n log k + k) steps with unique output locations. For general colored shapes within a w×h bounding box, we achieve O(wh log k+hk) steps.
Virtual Talk:
Accompanying Videos:
Patterned Line Building:
Section 3.2 introduces a construction for building 1xn k-colored patterns. Here is an example of a pattern being built for the constraints n=5,k=4.
Funneling Gadget:
Section 3.3 makes use of the funneling gadget, here is an example of the gadget in use.
General Pattern Builder:
Section 3.3 introduces a construction for building wxh k-colored patterns. Here is an example of a pattern being built for the constraints w=4,h=4,k=4.
Abstract: Motivated by advances is nanoscale applications and simplistic robot agents, we look at problems based on using a global signal to move all agents when given a limited number of directional signals and immovable geometry. We study a model where unit square particles move within a 2D grid based on uniform external forces. Movement is based on a sequence of uniform commands which cause all particles to move 1 step in a specific direction. The 2D grid board additionally contains “blocked” spaces which prevent particles from entry. Within this model, we investigate the complexity of deciding 1) whether a target location on the board can be occupied (by any) particle (\emph{occupancy problem}), 2) whether a specific particle can be relocated to another specific position in the board (\emph{relocation problem}), and 3) whether a board configuration can be transformed into another configuration (\emph{reconfiguration problem}). We prove that while occupancy is solvable in polynomial time, the relocation and reconfiguration problems are both NP-Complete even when restricted to only 2 or 3 movement directions. We further define a hierarchy of board geometries and show that this hardness holds for even very restricted classes of board geometry.
