The topology of a robotic swarm affects the convergence speed of consensus and the mobility of the robots. In this paper, we prove the existence of a complete set of local topology manipulation operations that allow the transformation of a swarm topology. The set is complete in the sense that any other possible set of manipulation operations can be performed by a sequence of operations from our set. The operations are local as they depend only on the first and second hop neighbors' information to transform any initial spanning tree of the network's graph to any other connected tree with the same number of nodes. The flexibility provided by our method is similar to global methods that require full knowledge of the swarm network. We prove the existence of a sequence of transformations for any tree-to-tree transformation, and derive sequences of operations to form a line or star from any initial spanning tree. Our work provides a theoretical and practical framework for topological control of a swarm, establishing global properties using only local information.
翻译:机器人群的地形学影响着共识的趋同速度和机器人的流动性。 在本文中, 我们证明存在一套完整的本地地形操纵操作, 能够转换成群状的地形。 这套系统是完整的, 也就是说, 任何其他可能的操纵操作方法都可以由我们一组的操作序列来进行。 这些操作是局部的, 因为它们仅依赖于第一和第二跳邻居的信息, 才能将网络图上任何最初的横贯树转换成任何其他连接的树, 并拥有相同数目的节点。 我们的方法所提供的灵活性类似于全球方法, 需要充分了解群状网络。 我们证明, 任何树到树的变形都有一系列的变形, 并从任何最初的横贯树上形成一线或一颗恒星。 我们的工作提供了一个理论和实践框架, 用于对群的地形控制, 仅使用本地信息来建立全球特性 。