## 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

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.

## Verification in Staged Tile Self-Assembly

Verification in Staged Tile Self-Assembly.
Robert Schweller, Andrew Winslow, and Tim Wylie.
In Proc. of the 16th Inter. Conf. on Unconventional Computation and Natural Computation (UCNC’17), 2017.

## Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces

Title:
Authors:Cameron Chalk, Erik D. Demaine, Martin L. Demaine, Eric Martinez, Robert Schweller, Luis Vega, and Tim Wylie.
Abstract:

citation:
In Proc. of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA’17), 2017.

## 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:

## Optimal Staged Self-Assembly of General Shapes

Title: Optimal Staged Self-Assembly of General Shapes
Authors: Cameron Chalk, Eric Martinez, Robert Schweller, Luis Vega, Andrew Winslow, Tim Wylie
Abstract:
We analyze the number of tile types t, bins b, and stages necessary to assemble $$n \times n$$ squares and scaled shapes in the staged tile assembly model. For $$n \times n$$ squares, we prove $$\mathcal {O}\left( \frac{\log {n} – tb – t\log t}{b^2} + \frac{\log \log b}{\log t}\right)$$ stages suffice and $$\varOmega \left( \frac{\log {n} – tb – t\log t}{b^2}\right)$$ are necessary for almost all n. For shapes S with Kolmogorov complexity K(S), we prove $$\mathcal {O}\left( \frac{K(S) – tb – t\log t}{b^2} + \frac{\log \log b}{\log t}\right)$$ stages suffice and $$\varOmega \left( \frac{K(S) – tb – t\log t}{b^2}\right)$$ are necessary to assemble a scaled version of S, for almost all S. We obtain similarly tight bounds when the more powerful flexible glues are permitted.
Published: Arxiv, European Symposium on Algorithms (ESA’16), Algorithmica

Journal Citation: Algorithmica, 80(4), 1383-1409, 2018.

Bibtex:
@article{CMSVWW:2018:Algorithmica,
author=”Chalk, Cameron and Martinez, Eric and Schweller, Robert and Vega, Luis and Winslow, Andrew and Wylie, Tim”,
title=”Optimal Staged Self-Assembly of General Shapes”,
journal=”Algorithmica”,
year=”2018″,
month=”Apr”,
day=”01″,
volume=”80″,
number=”4″,
pages=”1383–1409″,
issn=”1432-0541″,
doi=”10.1007/s00453-017-0318-0″,
url=”https://doi.org/10.1007/s00453-017-0318-0″
}

Conference Citation: Proceedings of the 24th European Symposium of Algorithms (ESA’16), 57, 26:1–26:17, 2016.