On the runtime of universal coating for programmable matter
On the runtime of universal coating for programmable matter
复制标题
DOI：
10.1007/s11047-017-9658-6
复制
发表时间：
2018-03-01
影响因子：
2.1
通讯作者：
Strothmann, Thim
中科院分区：
文献类型：
--
作者：
Daymude, Joshua J.;Derakhshandeh, Zahra;Strothmann, Thim
想象一下，带有智能颗粒（也是智能油漆）的涂料建筑物和桥梁，可监视结构完整性和感知，并了解交通和风负载，从而导致技术可以更快，更便宜，并同时提高安全性。在本文中，我们研究了在自组织可编程物质的背景下，均匀涂层的任意形状涂层对象的问题，即可编程物质，由可编程的物质由简单的计算元素组成，称为粒子，可以建立和释放债券，并可以主动地自我移动 - 组织的方式。粒子是匿名的，具有恒定大小的内存，并且仅利用局部相互作用来覆盖对象。我们通过关注其运行时分析来继续对通用涂料算法进行研究，这表明我们的算法终止于具有较高概率的线性弹性数。我们还提出了具有高概率的匹配线性下限。我们使用该下限来显示依赖全球信息的完全局部涂层算法和涂料算法之间的竞争差距，这意味着我们的算法在竞争意义上也是最佳的。仿真结果表明，在实践中，我们算法的竞争比可能比线性更好。
Imagine coating buildings and bridges with smart particles (also coined smart paint) that monitor structural integrity and sense and report on traffic and wind loads, leading to technology that could do such inspection jobs faster and cheaper and increase safety at the same time. In this paper, we study the problem of uniformly coating objects of arbitrary shape in the context of self-organizing programmable matter, i.e., programmable matter which consists of simple computational elements called particles that can establish and release bonds and can actively move in a self-organized way. Particles are anonymous, have constant-size memory, and utilize only local interactions in order to coat an object. We continue the study of our universal coating algorithm by focusing on its runtime analysis, showing that our algorithm terminates within a linear number of rounds with high probability. We also present a matching linear lower bound that holds with high probability. We use this lower bound to show a linear lower bound on the competitive gap between fully local coating algorithms and coating algorithms that rely on global information, which implies that our algorithm is also optimal in a competitive sense. Simulation results show that the competitive ratio of our algorithm may be better than linear in practice.