Particle computation: complexity, algorithms, and logic
Particle computation: complexity, algorithms, and logic
复制标题
DOI：
10.1007/s11047-017-9666-6
复制
发表时间：
2019-03-01
影响因子：
2.1
通讯作者：
Morris-Wright, Rose
中科院分区：
文献类型：
--
作者：
Becker, Aaron T.;Demaine, Erik D.;Morris-Wright, Rose
我们研究的算法控制的一大群移动的粒子（如机器人，传感器，或建筑材料），在一个二维工作空间中使用的全球输入信号（如重力或磁场）。在激活场时，每个粒子在同一方向上最大限度地移动，直到前进被静止的障碍物或另一个静止的粒子阻挡。在一个开放的工作空间中，这个系统模型的使用是有限的，因为它只有两个可控的自由度-所有的粒子接收相同的输入和均匀移动。我们表明，在环境中添加迷宫般的障碍物可以使系统更加复杂，但也更有用。我们为广泛的问题提供了广泛的结果。这些可以细分为外部算法问题，其中粒子配置作为在其他地方执行的计算的输入，以及内部逻辑问题，其中粒子配置本身用于执行计算。对于外部算法，我们给出了否定和肯定的结果。如果给定一组固定的障碍物，我们证明了决定一个给定的单位尺寸粒子的初始配置是否可以转化为所需的目标配置是NP-难的。此外，我们发现，找到一个最小长度的控制序列是PSPACE完全的。我们还致力于反问题，提供建设性的算法来设计有效地实现不同配置之间的任意排列的设计。对于内部逻辑，我们研究如何实现任意计算。我们演示了如何编码双轨逻辑，以构建一个通用的逻辑门，同时评估与，非，或或操作。使用许多这样的门和适当的互连，我们可以评估任何逻辑表达式。然而，我们建立，模拟各种复杂的相互作用存在于任意数字电路遇到了一个根本的困难：扇出门不能生成。我们在2 x 1粒子的帮助下解决了这个丢失的组件，它可以创建扇出门，产生输入的多个副本。使用这些门，我们提供了复制任意数字电路的规则。
We investigate algorithmic control of a large swarm of mobile particles (such as robots, sensors, or building material) that move in a 2D workspace using a global input signal (such as gravity or a magnetic field). Upon activation of the field, each particle moves maximally in the same direction until forward progress is blocked by a stationary obstacle or another stationary particle. In an open workspace, this system model is of limited use because it has only two controllable degrees of freedom-all particles receive the same inputs and move uniformly. We show that adding a maze of obstacles to the environment can make the system drastically more complex but also more useful. We provide a wide range of results for a wide range of questions. These can be subdivided into external algorithmic problems, in which particle configurations serve as input for computations that are performed elsewhere, and internal logic problems, in which the particle configurations themselves are used for carrying out computations. For external algorithms, we give both negative and positive results. If we are given a set of stationary obstacles, we prove that it is NP-hard to decide whether a given initial configuration of unit-sized particles can be transformed into a desired target configuration. Moreover, we show that finding a control sequence of minimum length is PSPACE-complete. We also work on the inverse problem, providing constructive algorithms to design workspaces that efficiently implement arbitrary permutations between different configurations. For internal logic, we investigate how arbitrary computations can be implemented. We demonstrate how to encode dual-rail logic to build a universal logic gate that concurrently evaluates and, nand, nor, and or operations. Using many of these gates and appropriate interconnects, we can evaluate any logical expression. However, we establish that simulating the full range of complex interactions present in arbitrary digital circuits encounters a fundamental difficulty: a fan-out gate cannot be generated. We resolve this missing component with the help of 2 x 1 particles, which can create fan-out gates that produce multiple copies of the inputs. Using these gates we provide rules for replicating arbitrary digital circuits.