论文标题
尽管视图不足，但聚会
Gathering Despite Defected View
论文作者
论文摘要
一个由许多移动计算实体组成的自动移动机器人系统（称为机器人）吸引了研究人员的广泛关注，并阐明机器人的能力与问题的可解决性之间的关系是近几十年来的一个新兴问题。通常，只要没有任何机器人的数量，每个机器人都可以观察所有其他机器人。在本文中，我们提供了关于机器人观察的新观点。机器人不一定会观察所有其他机器人，而不管距离距离如何。我们称此新的计算模型瑕疵视图模型。在该模型下，在本文中，我们考虑了需要所有机器人在同一时刻收集的收集问题，并提出了两种算法，以解决对抗性（$ n $，$ n-2 $）中的收集问题 - $ n \ geq 5 $（最多是$ n-2 $机器人在$ n-2 $ ablesect）和距离的距离（距离$ n-2 $ ables）和距离（4-2 $ nibe obs obs obs obs obs obs obs obs obs obs obs obs obs obs obs obs obs obs obs tase there）（4）大多数2个最接近的机器人）分别是机器人的数量。此外，我们提出了一个不可能的结果，表明在对抗性或基于距离（3,1）的模型中没有（确定性的）收集算法。此外，我们在放松的（$ n $，$ n-2 $）中的聚会表现出了不可能的结果。
An autonomous mobile robot system consisting of many mobile computational entities (called robots) attracts much attention of researchers, and to clarify the relation between the capabilities of robots and solvability of the problems is an emerging issue for a recent couple of decades. Generally, each robot can observe all other robots as long as there are no restrictions for visibility range or obstructions, regardless of the number of robots. In this paper, we provide a new perspective on the observation by robots; a robot cannot necessarily observe all other robots regardless of distances to them. We call this new computational model defected view model. Under this model, in this paper, we consider the gathering problem that requires all the robots to gather at the same point and propose two algorithms to solve the gathering problem in the adversarial ($N$,$N-2$)-defected model for $N \geq 5$ (where each robot observes at most $N-2$ robots chosen adversarially) and the distance-based (4,2)-defected model (where each robot observes at most 2 closest robots to itself) respectively, where $N$ is the number of robots. Moreover, we present an impossibility result showing that there is no (deterministic) gathering algorithm in the adversarial or distance-based (3,1)-defected model. Moreover, we show an impossibility result for the gathering in a relaxed ($N$, $N-2$)-defected model.
