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.
