Efficient Parallel Self-Assembly Under Uniform Control Inputs
Efficient Parallel Self-Assembly Under Uniform Control Inputs
复制标题
DOI：
10.1109/lra.2018.2853758
复制
发表时间：
2018-10-01
影响因子：
5.2
通讯作者：
Fekete, Sandor P.
中科院分区：
文献类型：
--
作者：
Schmidt, Arne;Manzoor, Sheryl;Fekete, Sandor P.
我们证明，通过连续组合子组件，我们可以实现从大量微小粒子到大类形状的微尺度对象的亚线性组装；这在可编程物质和自组装的背景下是一个重大进步，用于建立高产量的微型工厂。基本模型使粒子在均匀外力的影响下运动，直到它们击中障碍物；当粒子与兼容的粒子强迫在一起时，粒子会粘合在一起。以前的工作考虑了对象的顺序合成，导致构建时间与粒子数量N成线性，这对于大N是低效的。我们的进展意味着对于可构建形状的临界加速；对于凸多项式，甚至恒定的构建时间也是可能的。我们还表明，我们的施工工艺可以用于流水线，从而实现摊销恒定的生产时间。
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.