An official website of the United States government
We investigate motion planning algorithms for the assembly of shapes in the tilt model in which unit-square tiles move in a grid world under the influence of uniform external forces and self-assemble according to certain rules. We provide several heuristics and experimental evaluation of their success rate, solution length, and runtime. Video: https://youtu.be/VU1SZYzeaXw Transcript: This animation shows colored tiles moved by a global signal so they all move in the same direction unless blocked. This simple example is solved using the Greatest Distance heuristic, which finds the shortest path in 21 steps. Each tile has glue on the four sides that only stick to compatible glues. Glue type is denoted by color. The objective is to manipulate the tiles to bond in the shape of the connected polyomino target outlined in red. The Polyomino Assembly Problem is PSPACE-hard, so optimal solutions are difficult to find. This more complicated workspace was solved using the Minimum Move to Polyomino or Target. This approach is not optimal, but is a best-first search that attempts to keep tiles not involved in the present construction step separated from each other. This is done by pruning configurations with undesired subassemblies from the search tree. The solution requires 473 steps.
more »
« less
2048 without merging
Imagine t ≤ mn unit-square tiles in an m×n rectangular box that you can tilt to cause all tiles to slide maximally in one of the four orthogonal directions. Given two tiles of interest, is there a tilt sequence that brings them to adjacent squares? We give a linear-time algorithm for this problem, motivated by 2048 endgames. We also bound the number of reachable configurations, and design instances where all t tiles permute according to a cyclic permutation every four tilts.
more »
« less
- Award ID(s):
- 1800734
- PAR ID:
- 10253546
- Date Published:
- Journal Name:
- Proceedings of the 32nd Canadian Conference on Computational Geometry
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract DNA tiles serve as the fundamental building blocks for DNA self-assembled nanostructures such as DNA arrays, origami, and designer crystals. Introducing additional binding arms to DNA crossover tiles holds the promise of unlocking diverse nano-assemblies and potential applications. Here, we present one-, two-, and three-layer T-shaped crossover tiles, by integrating T junction with antiparallel crossover tiles. These tiles carry over the orthogonal binding directions from T junction and retain the rigidity from antiparallel crossover tiles, enabling the assembly of various 2D tessellations. To demonstrate the versatility of the design rules, we create 2-state reconfigurable nanorings from both single-stranded tiles and single-unit assemblies. Moreover, four sets of 4-state reconfiguration systems are constructed, showing effective transformations between ladders and/or rings with pore sizes spanning ~20 nm to ~168 nm. These DNA tiles enrich the design tools in nucleic acid nanotechnology, offering exciting opportunities for the creation of artificial dynamic DNA nanopores.more » « less
-
We develop a symmetry-based low-energy theory for monolayer \mathrm{WTe}_2 W T e 2 in its 1T ^{\prime} ′ phase, which includes eight bands (four orbitals, two spins). This modelreduces to the conventional four-band spin-degenerate Dirac model nearthe Dirac points of the material. We show that measurements of the spinsusceptibility, and of the magnitude and time dependence of theanomalous Hall conductivity induced by injected or equilibrium spinpolarization can be used to determine the magnitude and form of thespin-orbit coupling Hamiltonian, as well as the dimensionless tilt ofthe Dirac bands.more » « less
-
Hierarchical Shape Construction and Complexity for Slidable Polyominos under Uniform External ForcesAdvances 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 strongly universal for any w×h bounded shape within this hierarchy (it can be reconfigured to construct any w×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(n4logn)-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×1 tiles with no glues. We achieve this result by a reduction from Non-deterministic Constraint Logic for a one-player unbounded game.more » « less
-
null (Ed.)This paper presents a two-layer RF/analog weighting MIMO transceiver that comprises fully-connected (FC) multi-stream beamforming tiles in the RF-domain first layer, followed by a fully connected analog- or digital-domain baseband layer. The architecture mitigates the complexity versus spectral-efficiency tradeoffs of existing hybrid MIMO architectures and enables MIMO stream/user scalability, superior energy-efficiency, and spatial-processing flexibility. Moreover, multi-layer architectures with FC tiles inherently enable the co-existence of MIMO with carrier-aggregation and full-duplex beamforming. A compact, reconfigurable bidirectional circuit architecture is introduced, including a new Cartesian-combining/splitting beamforming receiver/transmitter, dual-band bidirectional beamforming network, dual-band frequency translation chains, and baseband Cartesian beamforming with an improved programmable gain amplifier design. A 28/37 GHz band, two-layer, eight-element, four-stream (with two FC-tiles) hybrid MIMO transceiver prototype is designed in 65-nm CMOS to demonstrate the above features. The prototype achieves accurate beam/null-steering capability, excellent area/power efficiency, and state-of-the-art TX/RX mode performance in two simultaneous bands while demonstrating multi-antenna (up to eight) multi-stream (up to four) over-the-air spatial multiplexing operation using proposed energy-efficient two-layer hybrid beamforming scheme.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
