Algorithmic Self-Assembly Research Group
Congratulations to two research students that have received Engaged Scholarships from the UTRGV Office of Engaged Scholarship and Learning! They offer research funding for undergraduates wanting to do research. The students then participate in a symposium of the scholars.
The two projects and students awarded funding are:
Thomas Thirlwall – Robot Sorting with Uniform External Forces
Kaiwei Sung – 3 Dimensional Single Step Tilt
A new paper has been published in the Journal of Information Processing. This is a full extended version of the short abstract from JCDCG3 last year.
Title: Hardness of Reconfiguring Robot Swarms with Uniform External Control in Limited Directions
Authors: David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, and Tim Wylie
There is also an Arxiv version: https://arxiv.org/abs/2003.13097
The journal version of last years ICALP paper on Covert Computation has been accepted to Algorithmica. URL: http://link.springer.com/article/10.1007/s00453-020-00764-w
A version is also available on Arxiv: https://arxiv.org/abs/1908.06068
One of our papers has been accepted to the International Symposium on Algorithms and Computation (ISAAC) for this year.
Title: Signal Passing Self-Assembly Simulates Tile Automata
Authors: Angel A. Cantu, Austin Luchsinger, Robert Schweller, and Tim Wylie
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
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.
Hierarchy Constructor: Strict Level 2 Polyomino Construction:
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.
Virtual Talk:
Accompanying Videos:
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:
Funneling Gadget:
General Pattern Builder: