pith. sign in

arxiv: 1907.06741 · v1 · pith:VC3E3Q7Unew · submitted 2019-07-15 · 💻 cs.CG

Full Tilt: Universal Constructors for General Shapes with Uniform External Forces

Jose Balanza-Martinez , David Caballero , Angel A. Cantu , Luis Angel Garcia , Timothy Gomez , Austin Luchsinger , Rene Reyes , Robert Schweller
show 1 more author
Tim Wylie
This is my paper

Pith reviewed 2026-05-24 21:15 UTC · model grok-4.3

classification 💻 cs.CG
keywords tilt assemblyuniversal constructorspolyomino reconfigurationPSPACE-completeshape assemblyuniform external forcescomputational geometrymotion planning
0
0 comments X

The pith

There exist strongly universal configurations with O(hw) 1x1 particles that assemble any h by w patterned rectangle under uniform external forces.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to design one fixed board of obstacles together with an initial placement of O(hw) slidable 1x1 particles so that sequences of uniform tilts can produce any desired h by w patterned rectangle without leftover particles. The same style of construction yields a weakly universal setup for every connected shape inside an h by w bounding box and a strongly universal setup for every shape in the previously studied drop class that uses only quadratically less space than earlier constructions. The work also proves that three natural motion-planning questions—whether a board location can ever be occupied, whether one particle can be moved to a target spot, and whether one configuration can reach another—become PSPACE-complete once 2 by 2 squares or dominoes are allowed.

Core claim

There exists a strongly universal configuration (no excess particles) with O(hw) 1×1 slidable particles that can be reconfigured to build any h×w patterned rectangle. A weakly universal configuration exists for any connected h×w-bounded shape, and a strongly universal configuration exists for the entire drop class while occupying quadratically less space than prior results. Occupancy, relocation, and reconfiguration problems are PSPACE-complete when a single 2×2 polyomino is added to the 1×1 tiles, and relocation and occupancy remain PSPACE-complete inside a rectangular board when dominoes are present.

What carries the argument

Strongly universal configuration consisting of a fixed obstacle board and an initial set of O(hw) 1×1 slidable particles whose tilt sequences can be chosen to realize any target pattern.

If this is right

  • Every h by w patterned rectangle is reachable from the same initial configuration by a suitable sequence of uniform tilts.
  • Every connected shape inside an h by w box is reachable from a single weakly universal initial configuration.
  • Every shape in the drop class is reachable from a single strongly universal configuration that occupies only quadratically less space than earlier constructions.
  • Occupancy, relocation, and reconfiguration remain PSPACE-complete even when the board is restricted to a rectangle once dominoes are allowed.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same universal-board technique might be adapted to produce families of 3-D shapes under gravity-like forces.
  • The PSPACE-completeness results indicate that computing the required tilt sequence is unlikely to be tractable for large instances even when a universal board is supplied.
  • Practical fabrication systems could use one physical tilt table and one set of reusable particles to realize many different target patterns simply by changing the control sequence.

Load-bearing premise

Fixed obstacle boards and initial particle placements can be chosen so that the allowed tilt sequences enforce exactly the assembly order needed for every possible target pattern without extra particles.

What would settle it

An explicit h by w pattern together with a concrete board and initial placement for which no sequence of four cardinal tilts produces the target without using extra particles or redesigning the board.

Figures

Figures reproduced from arXiv: 1907.06741 by Angel A. Cantu, Austin Luchsinger, David Caballero, Jose Balanza-Martinez, Luis Angel Garcia, Rene Reyes, Robert Schweller, Timothy Gomez, Tim Wylie.

Figure 1
Figure 1. Figure 1: Tilt Example Universal Configuration. A configuration C 0 is universal to a set of configurations C = {C1, C2, . . . , Ck} if and only if C 0 →∗ Ci ∀ Ci ∈ C. 4 [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An overview of the universal pattern and shape constructor. (a) The universal binary-patterned [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The rectangle construction process at different points. Patterns are built row by row and then added [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Basic sequences used in the constructor. The cyclic sequence to advance the fuel is [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The shape construction process at different intervals. (a) The first row of the shape being built, [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Drop Shapes examples. (a) This polyomino is buildable with the drop shape method, whereas (b) [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: (a) The universal drop-shape builder. (b) An overview of the parts of the drop shape builder. [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Tile selection gadget. Each tile is pulled out with the sequence [PITH_FULL_IMAGE:figures/full_fig_p012_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The column selection gadget for drop shapes. Assuming the shape to build is at a fixed location, [PITH_FULL_IMAGE:figures/full_fig_p013_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: (a) A flowchart where each state represents a set of configurations and the symbols represent [PITH_FULL_IMAGE:figures/full_fig_p014_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: (a) The two states of the crossing 2-toggle gadget. Robot traversal through either tunnel toggles [PITH_FULL_IMAGE:figures/full_fig_p016_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: (a) Relocation sections where 1) represents entrance/exits locations, 2) represents areas where [PITH_FULL_IMAGE:figures/full_fig_p017_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Relocation Properties. (a) A gadget with states 1 (dark) and 2 (light). (b) The robot-traversal [PITH_FULL_IMAGE:figures/full_fig_p017_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Example of a traversing sequence and state change when a gadget is in the state from Figure 11a. [PITH_FULL_IMAGE:figures/full_fig_p019_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Intersections of tunnels. The geometric block in the center stops the robot and allows it to choose [PITH_FULL_IMAGE:figures/full_fig_p019_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: (a) Sections 1 are the entrance chambers, sections 2 are the pre-reconfiguration tunnels, section 3 is the reconfiguration tunnel, section 4 is the relocation gadget. The solid lines depict the pathways the state tile and robot polyomino are free to move through, and the dotted lines depict the pathways which are only accessible through cooperation between the state tile and robot polyomino. Reconfigurati… view at source ↗
Figure 17
Figure 17. Figure 17: When the robot has reached its goal location, all the state tiles will be in one of the two state paths [PITH_FULL_IMAGE:figures/full_fig_p023_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: An example of a empty space moving through a configuration. The board geometry is just a [PITH_FULL_IMAGE:figures/full_fig_p024_18.png] view at source ↗
Figure 19
Figure 19. Figure 19: Two states of the CTL domino gadget. Dark blue tiles represent tiles that can move to transfer [PITH_FULL_IMAGE:figures/full_fig_p025_19.png] view at source ↗
Figure 20
Figure 20. Figure 20: (a) The Straight Wire Gadget used to allow the agent to traverse straight wires. (b) The Corner [PITH_FULL_IMAGE:figures/full_fig_p025_20.png] view at source ↗
read the original abstract

We investigate the problem of assembling general shapes and patterns in a model in which particles move based on uniform external forces until they encounter an obstacle. While previous work within this model of assembly has focused on designing a specific board configuration for the assembly of a specific given shape, we propose the problem of designing universal configurations that are capable of constructing a large class of shapes and patterns. In particular, for given integers $h,w$, we show that there exists a strongly universal configuration (no excess particles) with $\mathcal{O}(hw)$ $1 \times 1$ slidable particles that can be reconfigured to build any $h \times w$ patterned rectangle. We then expand this result to show that there exists a weakly universal configuration that can build any $h \times w$-bounded size connected shape. Following these results, we go on to show the existence of a strongly universal configuration which can assemble any shape within a previously studied ``drop'' class, while using quadratically less space than previous results. Finally, we include a study of the complexity of motion planning in this model. We consider the problems of deciding if a board location can be occupied by any particle (occupancy problem), deciding if a specific particle may be relocated to another position (relocation problem), and deciding if a given configuration of particles may be transformed into a second given configuration (reconfiguration problem). We show all of these problems to be PSPACE-complete with the allowance of a single $2\times 2$ polyomino in addition to $1\times 1$ tiles. We further show that relocation and occupancy remain PSPACE-complete even when the board geometry is a simple rectangle if domino polyominoes are included.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript establishes existence results for universal configurations in the tilt-assembly model (particles move under uniform external forces until blocked). For integers h and w, it constructs a strongly universal board with O(hw) 1×1 slidable particles and no excess particles that can be reconfigured via tilt sequences to any h×w patterned rectangle. It extends the result to a weakly universal configuration for any connected h×w-bounded shape and to an improved (quadratically smaller) strongly universal construction for the previously studied drop class. Separate from the constructions, it proves PSPACE-completeness of the occupancy, relocation, and reconfiguration problems when a single 2×2 polyomino is allowed, and shows that relocation and occupancy remain PSPACE-complete for rectangular boards when dominoes are permitted.

Significance. If the constructions are correct, the work supplies the first parameter-free, strongly universal tilt configurations that achieve linear particle count and eliminate excess particles, a clear advance over shape-specific board designs. The quadratic space improvement for the drop class and the PSPACE-completeness results (independent of any fitted parameters) further strengthen the contribution. Explicit constructions and reductions constitute verifiable strengths of the manuscript.

minor comments (3)
  1. [Abstract] Abstract: the phrases 'strongly universal configuration (no excess particles)' and 'weakly universal configuration' are introduced without a one-sentence definition; adding brief parenthetical glosses would improve accessibility for readers outside the sub-area.
  2. [Section 3] Section 3 (or wherever the main construction appears): the O(hw) particle bound is stated, but the accompanying board-size bound is not made explicit in the high-level statement; a single sentence relating board area to hw would clarify that the construction remains linear overall.
  3. [PSPACE-completeness section] The PSPACE-completeness section: the reduction for the reconfiguration problem with one 2×2 polyomino is sketched, but the precise gadget that encodes the PSPACE-hard problem (e.g., Nondeterministic Constraint Logic) is not named; adding the name of the source problem would help readers trace the reduction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their thorough reading, positive assessment of the significance of the constructions and complexity results, and recommendation of minor revision. The report does not enumerate any specific major comments requiring point-by-point rebuttal.

Circularity Check

0 steps flagged

No significant circularity in existence proofs or complexity results

full rationale

The paper's central claims consist of explicit existence constructions for strongly and weakly universal configurations in the tilt-assembly model, plus separate PSPACE-completeness proofs for motion-planning problems. These are standard constructive proofs and reductions that start from the model's definitions (uniform forces, 1x1 tiles, fixed obstacles) and do not reduce any claimed result to a fitted parameter, self-citation chain, or renamed input. No equations or steps equate a prediction to its own construction by definition. The derivation chain is self-contained against the stated model assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper operates inside the standard tilt-assembly model; no new free parameters, invented entities, or ad-hoc axioms beyond the established movement rule are introduced.

axioms (1)
  • domain assumption Particles move in the direction of a uniform external force until they collide with an obstacle or another particle.
    This defines the core dynamics of the assembly model used throughout the constructions and hardness proofs.

pith-pipeline@v0.9.0 · 5871 in / 1216 out tokens · 24997 ms · 2026-05-24T21:15:33.538225+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    Atomix, Thalion Software, 1990

    work page 1990

  2. [2]

    Mega maze, Phillips Media, 1995

    work page 1995

  3. [3]

    Jose Balanza-Martinez, Austin Luchsinger, David Caballero, Rene Reyes, Angel Cantu, Robert Schweller, Luis Garcia, and Tim Wylie, Full tilt: Universal constructors for general shapes with uniform external forces, Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’19, 2019

    work page 2019

  4. [4]

    Becker, Parallel self-assembly of polyominoes under uniform control inputs , https://www

    Aaron T. Becker, Parallel self-assembly of polyominoes under uniform control inputs , https://www. youtube.com/watch?v=G93H1Tecj-w, 2018

    work page 2018

  5. [5]

    Becker, Erik D

    Aaron T. Becker, Erik D. Demaine, S´ andor P. Fekete, Golnaz Habibi, and James McLurkin, Recon- figuring massive particle swarms with limited, global control , Algorithms for Sensor Systems (Berlin, Heidelberg), Springer Berlin Heidelberg, 2014, pp. 51–66

    work page 2014

  6. [6]

    Becker, Erik D

    Aaron T. Becker, Erik D. Demaine, S´ andor P. Fekete, Jarrett Lonsford, and Rose Morris-Wright,Particle computation: complexity, algorithms, and logic , Natural Computing (2017)

    work page 2017

  7. [7]

    Becker, Erik D

    Aaron T. Becker, Erik D. Demaine, S´ andor P. Fekete, and James McLurkin, Particle computation: Designing worlds to control robot swarms with only global signals , (2014), 6751–6756

    work page 2014

  8. [8]

    Becker, S´ andor P

    Aaron T. Becker, S´ andor P. Fekete, Phillip Keldenich, Dominik Krupke, Christian Rieck, Christian Scheffer, and Arne Schmidt, Tilt Assembly: Algorithms for Micro-Factories that Build Objects with Uniform External Forces , 28th International Symposium on Algorithms and Computation (ISAAC 2017), Leibniz International Proceedings in Informatics (LIPIcs), vol...

    work page 2017

  9. [9]

    Becker, Yan Ou, Paul Kim, Min J

    Aaron T. Becker, Yan Ou, Paul Kim, Min J. Kim, and Agung Julius, Feedback control of many magne- tized: Tetrahymena pyriformis cells by exploiting phase inhomogeneity , 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems, Nov 2013, pp. 3317–3323

    work page 2013

  10. [10]

    Brio, Labyrinth game. 26

    work page

  11. [11]

    Erik D. Demaine, Isaac Grosof, Jayson Lynch, and Mikhail Rudoy, Computational complexity of motion planning of a robot through simple gadgets , 9th International Conference on Fun with Algorithms, FUN 2018, June 13-15, 2018, La Maddalena, Italy, 2018, pp. 18:1–18:21

    work page 2018

  12. [12]

    12, 78–88

    Dave Doty, Theory of algorithmic self-assembly , Communications of the ACM 55 (2012), no. 12, 78–88

    work page 2012

  13. [13]

    Allen, and Andrew D

    Cheulhee Jung, Peter B. Allen, and Andrew D. Ellington, A simple, cleated dna walker that hangs on to surfaces, ACS Nano 11 (2017), no. 8, 8047–8054, PMID: 28719175

    work page 2017

  14. [14]

    Fekete, and Aaron T

    Phillip Keldenich, Sheryl Manzoor, Li Huang, Dominik Krupke, Arne Schmidt, Sandor P. Fekete, and Aaron T. Becker, On designing 2D discrete workspaces to sort or classify 2D polyominoes , 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)

    work page 2018

  15. [15]

    Khalil, Hazem Abass, Mostafa Shoukry, Anke Klingner, Rasha M

    Islam S.M. Khalil, Hazem Abass, Mostafa Shoukry, Anke Klingner, Rasha M. El-Nashar, Mohamed Serry, and Sarthak Misra, Robust and optimal control of magnetic microparticles inside fluidic channels with time-varying flow rates , International Journal of Advanced Robotic Systems 13 (2016), no. 3, 123

    work page 2016

  16. [16]

    9, 1169–1182

    Sylvain Martel, Ouajdi Felfoul, Jean-Baptiste Mathieu, Arnaud Chanu, Samer Tamaz, Mahmood Mo- hammadi, Martin Mankiewicz, and Nasr Tabatabaei, MRI-based medical nanorobotic platform for the control of magnetic nanoparticles and flagellated bacteria for target interventions in human capillaries , The International journal of robotics research 28 (2009), no....

    work page 2009

  17. [17]

    Patitz, An introduction to tile-based self-assembly and a survey of recent results , Natural Computing 13 (2014), no

    Matthew J. Patitz, An introduction to tile-based self-assembly and a survey of recent results , Natural Computing 13 (2014), no. 2, 195–224

    work page 2014

  18. [18]

    Becker, and Sndor Fekete, Efficient parallel self- assembly under uniform control inputs , IEEE Robotics and Automation Letters (2018), 1–1

    Arne Schmidt, Sheryl Manzoor, Li Huang, Aaron T. Becker, and Sndor Fekete, Efficient parallel self- assembly under uniform control inputs , IEEE Robotics and Automation Letters (2018), 1–1

    work page 2018

  19. [19]

    Kim, Shuming Nie, and Dong M

    Rajni Sinha, Gloria J. Kim, Shuming Nie, and Dong M. Shin, Nanotechnology in cancer therapeutics: bioconjugated nanoparticles for drug delivery, Molecular Cancer Therapeutics 5 (2006), no. 8, 1909–1917

    work page 2006

  20. [20]

    ThinkFun, Tilt: Gravity fed logic maze

    work page

  21. [21]

    Damien Woods, Intrinsic universality and the computational power of self-assembly , Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 373 (2015), no. 2046

    work page 2015

  22. [22]

    David Zhang and Georg Seelig, Dynamic dna nanotechnology using strand-displacement reactions , 3 (2011), 103–13

    work page 2011

  23. [23]

    Chao Zhou, Xiaoyang Duan, and Na Liu, A plasmonic nanorod that walks on dna origami , Nature Communications 6 (2015), 8102–8102, 26303016[pmid]. 27

    work page 2015