A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems
A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems
复制标题
自组织粒子系统压缩的马尔可夫链算法
DOI：
10.1145/2933057.2933107
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Richa, Andréa W.
中科院分区：
文献类型：
--
作者：
Cannon, Sarah;Daymude, Joshua J.;Randall, Dana;Richa, Andréa W.
我们将可编程物质视为具有有限（恒定大小）内存的简单计算元素（或粒子）的集合，这些元素（或粒子）可以自组织以解决系统范围的运动、配置和协调问题。在这里，我们专注于压缩问题，其中粒子系统尽可能紧密地聚集在一起，就像在一个球体或其等效物中存在一些潜在的几何形状一样。更具体地说，我们寻求完全分布式，本地和异步算法，导致系统收敛到一个配置与小周长。我们提出了一个马尔可夫链为基础的算法，解决了压缩问题下的几何变形虫模型，粒子系统，开始在一个连接的配置没有孔。该算法将偏置参数λ作为输入，其中λ > 1对应于有利于在粒子系统内诱导更多晶格三角形的粒子。我们证明了对于所有λ > 5，存在一个常数α > 1，使得在平稳状态下，除了指数小的概率外，粒子都是α压缩的，这意味着系统配置的周长至多是α pmin，其中pmin是粒子系统的最小可能周长。我们还证明了同样的算法可以用于λ的小值展开，特别是对于all0< λ 2，有一个常数β < 1，使得在平稳性下，除了指数小的概率外，周长至少是β pmax，其中pmax是最大可能周长。
We consider programmable matter as a collection of simple computational elements (or particles) with limited (constant-size) memory that self-organize to solve system-wide problems of movement, configuration, and coordination. Here, we focus on the compression problem, in which the particle system gathers as tightly together as possible, as in a sphere or its equivalent in the presence of some underlying geometry. More specifically, we seek fully distributed, local, and asynchronous algorithms that lead the system to converge to a configuration with small perimeter. We present a Markov chain based algorithm that solves the compression problem under the geometric amoebot model, for particle systems that begin in a connected configuration with no holes. The algorithm takes as input a bias parameter λ, where λ > 1 corresponds to particles favoring inducing more lattice triangles within the particle system. We show that for all λ > 5, there is a constant α > 1 such that at stationarity with all but exponentially small probability the particles areα-compressed, meaning the perimeter of the system configuration is at most α ⋅pmin, wherepminis the minimum possible perimeter of the particle system. We additionally prove that the same algorithm can be used for expansion for small values of λ in particular, for all0< λ < √2, there is a constant β < 1 such that at stationarity, with all but an exponentially small probability, the perimeter will be at least β ⋅pmax, wherepmaxis the maximum possible perimeter.
登录
查看更多内容
异步、匿名、不经意的机器人形成任意模式
DOI：
10.1016/j.tcs.2008.07.026
发表时间：
2008
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
P. Flocchini;G. Prencipe;N. Santoro;P. Widmayer
通讯作者：
P. Widmayer
自组织可编程物质的领导者选举和形态形成
DOI：
10.1007/978-3-319-21999-8_8
发表时间：
2015
期刊：
ArXiv
影响因子：
--
作者：
Zahra Derakhshandeh;Robert Gmyr;Thim Strothmann;Rida A. Bazzi;Andrea W. Richa;Christian Scheideler
通讯作者：
Christian Scheideler
通过可编程粒子进行线路恢复
DOI：
--
发表时间：
2017
期刊：
International Conference of Distributed Computing and Networking
影响因子：
--
作者：
Giuseppe Antonio Di Luna;P. Flocchini;G. Prencipe;N. Santoro;G. Viglietta
通讯作者：
G. Viglietta
利用对称性：异步遗忘机器人聚集在环上
DOI：
--
发表时间：
2008
期刊：
International Conference on Principles of Distributed Systems
影响因子：
--
作者：
R. Klasing;A. Kosowski;A. Navarra
通讯作者：
A. Navarra
利用对称性：将许多异步遗忘机器人聚集在环上
影响因子：
1.1
作者：
R. Klasing;A. Kosowski;A. Navarra
通讯作者：
A. Navarra