Forming sequences of geometric patterns with oblivious mobile robots
Forming sequences of geometric patterns with oblivious mobile robots
复制标题
使用不经意的移动机器人形成几何图案序列
DOI：
10.1007/s00446-014-0220-9
复制
发表时间：
2015
影响因子：
1.3
通讯作者：
Masafumi Yamashita
中科院分区：
文献类型：
--
作者：
Shantanu Das;Paola Flocchini;Nicola Santoro;Masafumi Yamashita
我们研究了由在平面上运动的简单自主机器人组成的分布式系统的计算能力。这些机器人具有视觉感知，允许它们看到对方，但它们之间没有任何明确的交流手段。此外，机器人是健忘的，这意味着它们总是根据当前对环境的感知来行动，并且对过去没有记忆。这种简单的机器人系统已经被广泛研究，目的是实现协调任务，例如将机器人排成一条线或一个圈。事实上，事实已经表明，遗忘并不是形成一个单一几何图案的限制因素，无论它是多么随意。本文旨在通过研究一系列几何图案而不是单一图案的形成来理解机器人的遗忘所带来的计算限制。如果可以形成这样的一系列模式，这将在一个原本没有内存的系统中创建某种形式的内存。我们证明了，在特定条件下，不经意机器人系统确实可以从任意构形开始形成一系列给定的几何图案。更准确地说，我们刻画了遗忘机器人系统在各种附加限制下形成的一系列模式，如匿名性、异步性和缺乏共同定向。这些结果有力地表明，对于直觉上似乎需要记忆的任务，也可以获得不经意的解决方案。
We study the computational power of distributed systems consisting of simple autonomous robots moving on the plane. The robots are endowed with visual perception, allowing them to see each other, but they do not have any means of explicit communication with each other. Further the robots are oblivious, meaning that they always act based on their current perception of the environment, and they have no memory of the past. Such system of simple robots have been studied extensively with the objective of achieving coordinated tasks e.g. arranging the robots in a line or a circle. In fact it has been shown that obliviousness is not a limiting factor to form asinglegeometric pattern, however arbitrary. This paper aims to understand the computational limits imposed by the obliviousness of the robots by studying the formation of aseriesof geometric patterns instead of a single pattern. If such a series of patterns could be formed this would create some form of memory in an otherwise memory-less system. We show that, under particular conditions, oblivious robot systems can indeed form a given series of geometric patterns starting from any arbitrary configuration. More precisely, we characterize the series of patterns that can be formed by oblivious robot systems under various additional restrictions such as anonymity, asynchrony and lack of common orientation. These results provide strong indications that oblivious solutions may be obtained also for tasks that intuitively seem to require memory.