Efficient Parallel Self- Assembly Under Uniform Control Inputs



Journal Title

Journal ISSN

Volume Title


IEEE Robotics and Automation Letters


We prove that by successively combining subassemblies, we can achieve sublinear construction times for “staged” assembly of microscale objects from a large number of tiny particles, for vast classes of shapes; this is a significant advance in the context of programmable matter and self-assembly for building high-yield microfactories. The underlying model has particles moving under the influence of uniform external forces until they hit an obstacle; particles bond when forced together with a compatible particle. Previous work considered sequential composition of objects, resulting in construction time that is linear in the number N of particles, which is inefficient for large N. Our progress implies critical speedup for constructible shapes; for convex polyominoes, even a constant construction time is possible. We also show that our construction process can be used for pipelining, resulting in an amortized constant production time.



Shape, Self-assembly, Production, Robots, Tiles, Containers


Copyright 2018 IEEE Robotics and Automation Letters. This is a pre-print version of a published paper that is available at: https://ieeexplore.ieee.org/abstract/document/8408555 Recommended citation: Schmidt, Arne, Sheryl Manzoor, Li Huang, Aaron T. Becker, and Sándor P. Fekete. "Efficient parallel self-assembly under uniform control inputs." IEEE Robotics and Automation Letters 3, no. 4 (2018): 3521-3528. DOI: 10.1109/LRA.2018.2853758 This item has been deposited in accordance with publisher copyright and licensing terms with the author's permission.