Shape formation by programmable particles
Shape formation by programmable particles
复制标题
DOI：
10.1007/s00446-019-00350-6
复制
发表时间：
2020-02-01
影响因子：
1.3
通讯作者：
Yamauchi, Yukiko
中科院分区：
文献类型：
--
作者：
Di Luna, Giuseppe A.;Flocchini, Paola;Yamauchi, Yukiko
形状形成（或图案形成）是计算移动的实体系统的基本分布式问题。深入研究的自主移动的机器人系统，它最近被调查的领域，可编程物质，其中实体被假定为小，并具有严重有限的能力。也就是说，它已经在几何Amoebot模型中进行了研究，其中称为粒子的匿名实体在平面的六边形镶嵌上操作，并且具有有限的计算能力（他们有恒定的记忆），严格的本地互动和沟通能力（仅在网格的相邻节点中具有粒子）和有限的运动能力（从网格节点到空的相邻节点）;它们的激活由对抗调度器控制。最近的研究表明，从一个结构良好的配置开始，粒子形成一个（不一定是完整的）三角形，粒子可以形成一个大类的形状。这个结果是在几个假设下建立的：在顺时针方向上的一致性（即，手性），顺序激活时间表，和随机化（即，粒子可以掷硬币来选出领导者）。在本文中，我们得到了几个结果，除其他事项外，提供了一个表征的形状可以形成确定性从任何简单连接的初始配置n粒子。特征是建设性的：我们提供了一个通用的形状形成算法，对于每个可行的形状对（S-0，S-F），允许粒子从初始形状S-0开始形成最终形状SF（在输入中给出），粒子未知。最终的配置将是S-F的适当放大副本，具体取决于n。如果允许随机化，那么任何输入形状都可以通过我们的算法从任何初始（单连通）形状形成，前提是有足够的粒子。我们的算法没有手征，证明手征是计算无关的形状形成。此外，它在强大的对抗性调度器下工作，不一定是顺序的。我们还考虑了形状形成的复杂性，无论是在轮数和粒子执行通用形状形成算法的移动总数。我们证明了我们的解决方案具有O（n（2））轮和移动的复杂度：这个移动的数量也是渐近最坏情况下的最优。
Shape formation (or pattern formation) is a basic distributed problem for systems of computational mobile entities. Intensively studied for systems of autonomous mobile robots, it has recently been investigated in the realm of programmable matter, where entities are assumed to be small and with severely limited capabilities. Namely, it has been studied in the geometric Amoebot model, where the anonymous entities, called particles, operate on a hexagonal tessellation of the plane and have limited computational power (they have constant memory), strictly local interaction and communication capabilities (only with particles in neighboring nodes of the grid), and limited motorial capabilities (from a grid node to an empty neighboring node); their activation is controlled by an adversarial scheduler. Recent investigations have shown how, starting from a wellstructured configuration in which the particles form a (not necessarily complete) triangle, the particles can form a large class of shapes. This result has been established under several assumptions: agreement on the clockwise direction (i.e., chirality), a sequential activation schedule, and randomization (i.e., particles can flip coins to elect a leader). In this paper we obtain several results that, among other things, provide a characterization of which shapes can be formed deterministically starting from any simply connected initial configuration of n particles. The characterization is constructive: we provide a universal shape formation algorithm that, for each feasible pair of shapes (S-0, S-F), allows the particles to form the final shape SF (given in input) starting from the initial shape S-0, unknown to the particles. The final configuration will be an appropriate scaled-up copy of S-F depending on n. If randomization is allowed, then any input shape can be formed from any initial (simply connected) shape by our algorithm, provided that there are enough particles. Our algorithm works without chirality, proving that chirality is computationally irrelevant for shape formation. Furthermore, it works under a strong adversarial scheduler, not necessarily sequential. We also consider the complexity of shape formation both in terms of the number of rounds and the total number of moves performed by the particles executing a universal shape formation algorithm. We prove that our solution has a complexity of O(n(2)) rounds and moves: this number of moves is also asymptotically worst-case optimal.