匿名・完全無向ロボット群による相反するパターン形成
Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots
2次元平面上で、互いに識別できない2群のロボットが、集合と円形成という相反するタスクを同時に解くための分散アルゴリズムを提案した。
著者: Animesh Maiti, Prakhar Shukla, Subhash Bhagat
分類: cs.DC, cs.CG, cs.MA, cs.RO
原文アブストラクト
Two groups of autonomous, anonymous, and oblivious mobile robots are deployed in the two-dimensional Euclidean plane, each assigned a distinct task. We study a setting where the two groups must simultaneously solve two conflicting pattern formation problems: the \textit{gathering problem}, where robots gather at a point not known to them a priori, and the \textit{circle formation problem}, where robots occupy distinct positions on the boundary of a circle. Although each robot knows its own task, it cannot identify other members of its group. A prior solution~\cite{Conflict-1} addressed this problem for asynchronous robots having {\it direction-only axis agreement} and {\it global weak multiplicity detection} capability available to all robots in both groups. In contrast, in this work, we consider fully {\it disoriented robots} without any axis agreement or common \textit{chirality}. We study the feasibility of a solution to this problem for {\it disoriented robots}. We propose a distributed algorithm that solves the problem for semi-synchronous disoriented robots with non-rigid movements. Our proposed algorithm assumes global weak multiplicity detection only for the gathering group, while for the circle formation group, it requires local weak multiplicity detection.