论文标题
在自组织粒子系统中对齐的局部随机算法
Local Stochastic Algorithms for Alignment in Self-Organizing Particle Systems
论文作者
论文摘要
我们在二维晶格上介绍了在自组织粒子系统（SOP）中\ emph {对齐}的局部分布式，随机算法，如果没有占主导地位，则粒子在晶格上占据独特的位点，颗粒可以使空间移动到相邻的地点。这样的模型是可编程物质的抽象，由单个计算粒子组成，内存有限，本地通信能力和适度的计算能力。我们考虑定向粒子系统，其中为粒子指向$ q $方向之一的矢量，每个粒子都可以计算其方向和任何相邻粒子的方向之间的角度，尽管在不了解有关固定基础坐标系统的全局方向的情况下。颗粒随机移动，每个粒子都能在移动过程中修改其方向或沿晶格边缘进行局部空间移动。我们考虑两个设置：（a）粒子配置必须始终保持不变，并且（b）空间移动不受限制并且配置可以断开连接。 Taking inspiration from the Potts and clock models from statistical physics, we prove that for any $q \geq 2,$ these self-organizing particle systems can be made to collectively align along a single dominant direction (analogous to a solid or ordered state) or remain non-aligned, in which case the fraction of particles oriented along any direction is nearly equal (analogous to a gaseous or disordered state).此外，我们表明，通过对输入参数进行适当的设置，我们可以实现\ emph {compression}和\ emph {explention}，控制粒子的紧密收集，以及\ emph {Alignment}或\ emph}或\ emph {nonignerment}，产生单个主导率的前端或非单一的占主导地位。
We present local distributed, stochastic algorithms for \emph{alignment} in self-organizing particle systems (SOPS) on two-dimensional lattices, where particles occupy unique sites on the lattice, and particles can make spatial moves to neighboring sites if they are unoccupied. Such models are abstractions of programmable matter, composed of individual computational particles with limited memory, strictly local communication abilities, and modest computational capabilities. We consider oriented particle systems, where particles are assigned a vector pointing in one of $q$ directions, and each particle can compute the angle between its direction and the direction of any neighboring particle, although without knowledge of global orientation with respect to a fixed underlying coordinate system. Particles move stochastically, with each particle able to either modify its direction or make a local spatial move along a lattice edge during a move. We consider two settings: (a) where particle configurations must remain simply connected at all times and (b) where spatial moves are unconstrained and configurations can disconnect. Taking inspiration from the Potts and clock models from statistical physics, we prove that for any $q \geq 2,$ these self-organizing particle systems can be made to collectively align along a single dominant direction (analogous to a solid or ordered state) or remain non-aligned, in which case the fraction of particles oriented along any direction is nearly equal (analogous to a gaseous or disordered state). Moreover, we show that with appropriate settings of the input parameters, we can achieve \emph{compression} and \emph{expansion}, controlling how tightly gathered the particles are, as well as \emph{alignment} or \emph{nonalignment}, producing a single dominant orientation or not.
