Arbitrary pattern formation by asynchronous, anonymous, oblivious robots
Arbitrary pattern formation by asynchronous, anonymous, oblivious robots
复制标题
异步、匿名、不经意的机器人形成任意模式
DOI：
10.1016/j.tcs.2008.07.026
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
P. Widmayer
中科院分区：
文献类型：
--
作者：
P. Flocchini;G. Prencipe;N. Santoro;P. Widmayer
从工程学的角度来看，在过去的十年里，协调一组自主的移动机器人以合作执行任务的问题得到了广泛的研究。相比之下，在本文中，我们的目标是了解一组自主移动机器人可以或不能实现的基本算法限制。因此，我们研究了一组弱机器人的硬任务。任务是让飞机上的机器人形成任何预先给定的任意图案。这项任务的根本意义在于，如果机器人可以形成任何模式，它们就可以在随后的协调行动中就各自的角色达成一致。机器人在几个方面都很薄弱。他们是匿名的；他们不能明确地相互交流，而只是观察他人的立场；他们不记得过去；他们以一种非常强的异步性的形式运作。我们表明，这样的机器人系统能够执行的任务在很大程度上取决于它们对环境的共同认同，即它们的环境传感器的读数。如果机器人对它们的环境没有共同的共识，它们就不能形成任意的模式。如果每个机器人都有一个指示北方的指南针(机器人世界是一个平面，指南针是平行的)，那么任何奇数个机器人都可以形成任意图案，但偶数个机器人不能(在最坏的情况下)。如果每个机器人都有两个独立的指南针，比如北针和东针，那么任何一组机器人都可以形成任何图案。
From an engineering point of view, the problem of coordinating a set of autonomous, mobile robots for the purpose of cooperatively performing a task has been studied extensively over the past decade. In contrast, in this paper we aim to understand the fundamental algorithmic limitations on what a set of autonomous mobile robots can or cannot achieve. We therefore study a hard task for a set of weak robots. The task is for the robots in the plane to form any arbitrary pattern that is given in advance. This task is fundamental in the sense that if the robots can form any pattern, they can agree on their respective roles in a subsequent, coordinated action. The robots are weak in several aspects. They are anonymous; they cannot explicitly communicate with each other, but only observe the positions of the others; they cannot remember the past; they operate in a very strong form of asynchronicity. We show that the tasks that such a system of robots can perform depend strongly on their common agreement about their environment, i.e. the readings of their environment sensors. If the robots have no common agreement about their environment, they cannot form an arbitrary pattern. If each robot has a compass needle that indicates North (the robot world is a flat surface, and compass needles are parallel), then any odd number of robots can form an arbitrary pattern, but an even number cannot (in the worst case). If each robot has two independent compass needles, say North and East, then any set of robots can form any pattern.