论文标题
在无限规则镶嵌图上的任意图案形成
Arbitrary Pattern Formation on Infinite Regular Tessellation Graphs
论文作者
论文摘要
给定一组机器人，每个机器人都位于无限常规镶嵌图的不同顶点，我们旨在探索任意模式形成（APF）问题。在给定一个网格顶点的多组f中，| r | = | f |，APF要求提供一种分布式算法，该算法移动机器人，以达到类似于F的配置。相似性意味着必须将机器人作为F处置为F，而不管翻译，旋转，反射。到目前为止，在经典的外观摩托车模型的背景下，仅考虑了标准的平方网格，以使欧几里得平面离散。但是，自然也可以考虑三角形和六边形网格的其他常规镶嵌图。当初始配置不对称时，我们为APF提供了分辨率算法，并且所考虑的拓扑是任何常规的镶嵌图。
Given a set R of robots, each one located at different vertices of an infinite regular tessellation graph, we aim to explore the Arbitrary Pattern Formation (APF) problem. Given a multiset F of grid vertices such that |R|=|F|, APF asks for a distributed algorithm that moves robots so as to reach a configuration similar to F. Similarity means that robots must be disposed as F regardless of translations, rotations, reflections. So far, as possible graph discretizing the Euclidean plane only the standard square grid has been considered in the context of the classical Look-Compute-Move model. However, it is natural to consider also the other regular tessellation graphs, that are triangular and hexagonal grids. We provide a resolution algorithm for APF when the initial configuration is asymmetric and the considered topology is any regular tessellation graph.
