Brief Announcement: A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems
Brief Announcement: A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems
复制标题
简短公告：一种用于异质自组织粒子系统分离的局部随机算法
DOI：
10.1145/3212734.3212792
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Richa, Andrea W
中科院分区：
文献类型：
--
作者：
Cannon, Sarah;Daymude, Joshua J;Gokmen, Cem;Randall, Dana;Richa, Andrea W
我们研究随机的，分布式的算法，可以完成分离和集成行为的自组织粒子系统，抽象的可编程物质。这些粒子系统由称为粒子的单个计算单元组成，这些计算单元具有有限的内存，严格的本地通信能力和适度的计算能力，并共同解决系统范围内的运动和协调问题。在这项工作中，我们扩展了粒子系统的通常概念，通过考虑不同颜色的粒子来处理异质系统。我们提出了一个完全分布式的，异步的，随机的算法分离，粒子系统自组织成隔离的颜色类，只使用本地信息，每个粒子的偏好是附近的其他相同的颜色。相反，通过简单地改变粒子的偏好，颜色类变得很好地集成。我们严格分析我们的分布式，随机算法的收敛性，并证明在一定条件下分离发生。我们还提出了模拟证明我们的算法实现分离和整合。
We investigate stochastic, distributed algorithms that can accomplish separation and integration behaviors in self-organizing particle systems, an abstraction of programmable matter. These particle systems are composed of individual computational units known as particles that have limited memory, strictly local communication abilities, and modest computational power, and which collectively solve system-wide problems of movement and coordination. In this work, we extend the usual notion of a particle system to treat heterogeneous systems by considering particles of different colors. We present a fully distributed, asynchronous, stochastic algorithm for separation, where the particle system self-organizes into segregated color classes using only local information about each particle's preference for being near others of the same color. Conversely, by simply changing the particles' preferences, the color classes become well-integrated. We rigorously analyze the convergence of our distributed, stochastic algorithm and prove that under certain conditions separation occurs. We also present simulations demonstrating our algorithm achieves both separation and integration.