Title: Fast Reconfiguration of Robot Swarms with Uniform Control Signals
Authors: David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, and Tim Wylie.
Published: Natural Computing, 2021
Verification and Computation in Restricted Tile Automata
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.
Hierarchical Shape Construction and Complexity for Slidable Polyominos under Uniform External Forces
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.
Accompanying videos related to the paper
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.
Relocating Units in Robot Swarms with Uniform Control Signals is PSPACE-Complete
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:
Building Patterned Shapes in Robot Swarms with Uniform Control Signals
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:
Hardness of Reconfiguring Robot Swarms with Uniform External Control in Limited Directions
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
This is the full version on arxiv of the initial short abstract Relocation with Uniform External Control in Limited Directions
Link: https://arxiv.org/abs/2003.13097
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.
Relocation with Uniform External Control in Limited Directions
Title: Relocation with Uniform External Control in Limited Directions (Short Abstract)
Authors: Jose Balanza-Martinez, David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, and Tim Wylie.
Conference: The 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3’19), 2019.
Abstract: 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 \times 1$ particles even when only allowed to move in 2 or 3 directions.
Discrete Planar Map Matching
Title: Discrete Planar Map Matching
Authors: Bin Fu, Robert Schweller, Tim Wylie
Conference: The 31st Canadian Conference on Computational Geometry (CCCG’19)
Abstract:
Route reconstruction is an important application for Geographic Information Systems (GIS) that rely heavily upon GPS data and other location data from IoT devices. Many of these techniques rely on geometric methods involving the Frechet distance to compare curve similarity. The goal of reconstruction, or map matching, is to find the most similar path within a given graph to a given input curve, which is often only approximate location data. This process can be approximated by sampling the curves and using the discrete Frechet distance. Due to power and coverage constraints, the GPS data itself may be sparse causing improper constraints along the edges during the reconstruction if only the continuous Frechet distance is used. Here, we look at two variations of discrete map matching: one constraining the walk length and the other limiting the number of vertices visited in the graph. We give an efficient algorithm to solve one and prove the other is NP-complete and the minimization version is APX-hard while also giving a parameterized algorithm to solve the problem.
Covert Computation in Self-Assembled Circuits
Title: Covert Computation in Self-Assembled Circuits
Authors: Angel Cantu, Austin Luchsinger, Robert Schweller, and Tim Wylie
Conference: The 46th International Colloquium on Automata, Languages, and Programming (ICALP ’19)
Abstract:
Traditionally, computation within self-assembly models is hard to conceal because the self-assembly process generates a crystalline assembly whose computational history is inherently part of the structure itself. With no way to remove information from the computation, this computational model offers a unique problem: how can computational input and computation be hidden while still computing and reporting the final output? Designing such systems is inherently motivated by privacy concerns in biomedical computing and applications in cryptography.
In this paper we propose the problem of performing “covert computation” within tile self-assembly that seeks to design self-assembly systems that “conceal” both the input and computational history of performed computations. We achieve these results within the growth-only restricted abstract tile assembly model (aTAM) with positive and negative interactions. We show that general-case covert computation is possible by implementing a set of basic covert logic gates capable of simulating any circuit (functionally complete). To further motivate the study of covert computation, we apply our new framework to resolve an outstanding complexity question; we use our covert circuitry to show that the unique assembly verification problem within the growth-only aTAM with negative interactions is coNP-complete.
Nearly Constant Tile Complexity for any Shape in Two-Handed Tile Assembly
Title: Nearly Constant Tile Complexity for any Shape in Two-Handed Tile Assembly
Authors: Robert Schweller, Andrew Winslow, and Tim Wylie
Journal: Algorithmica, 2019
Abstract:
Tile self-assembly is a well-studied theoretical model of geometric computation based on nanoscale DNA-based molecular systems. Here, we study the two-handed tile self-assembly model or 2HAM at general temperatures, in contrast with prior study limited to small constant temperatures, leading to surprising results. We obtain constructions at larger (i.e., hotter) temperatures that disprove prior conjectures and break well-known bounds for low-temperature systems via new methods of temperature-encoded information.
In particular, for all $n \in \mathbb{N}$, we assemble $n \times n$ squares using $O(2^{\log^*{n}})$ tile types, thus breaking the well-known information theoretic lower bound of Rothemund and Winfree. Using this construction, we then show how to use the temperature to encode general shapes and construct them at scale with $O(2^{\log^*{K}})$ tiles, where $K$ denotes the Kolmogorov complexity of the target shape. Following, we refute a long-held conjecture by showing how to use temperature to construct $n \times O(1)$ rectangles using only $O(\log{n}/\log\log{n})$ tile types. We also give two small systems to generate nanorulers of varying length based solely on varying the system temperature.
These results constitute the first real demonstration of the power of high temperature systems for tile assembly in the 2HAM. This leads to several directions for future explorations which we discuss in the conclusion.