We study the computational power that oblivious robots operating in the plane have under sequential schedulers. We show that this power is much stronger than the obvious capacity these schedulers offer of breaking symmetry, and thus to create a leader. More precisely, we consider the class of pattern formation problems, and focus on the most general problem in this class, Universal Pattern Formation (UPF), which requires the robots to form any pattern given in input, starting from any initial configurations (where robots may occupy the same point). We first show that UPF is unsolvable under \(\mathcal {FSYNC}\) , even if the robots are endowed with additional strong capabilities (multiplicity detection, rigid movement, agreement on coordinate systems, presence of a unique leader). On the other hand, we prove that, except for point formation (Gathering), UPF is solvable under any sequential scheduler without any additional assumptions. We then turn our attention to the Gathering problem, and prove that weak multiplicity detection is necessary and sufficient for solvability under sequential schedulers. The obtained results show that the computational power of the robots under \(\mathcal {FSYNC}\) (where Gathering is solvable without any multiplicity detection) and that under sequential schedulers are orthogonal.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Oblivious Robots Under Sequential Schedulers: Universal Pattern Formation

  • Paola Flocchini,
  • Alfredo Navarra,
  • Debasish Pattanayak,
  • Francesco Piselli,
  • Nicola Santoro

摘要

We study the computational power that oblivious robots operating in the plane have under sequential schedulers. We show that this power is much stronger than the obvious capacity these schedulers offer of breaking symmetry, and thus to create a leader. More precisely, we consider the class of pattern formation problems, and focus on the most general problem in this class, Universal Pattern Formation (UPF), which requires the robots to form any pattern given in input, starting from any initial configurations (where robots may occupy the same point). We first show that UPF is unsolvable under \(\mathcal {FSYNC}\) , even if the robots are endowed with additional strong capabilities (multiplicity detection, rigid movement, agreement on coordinate systems, presence of a unique leader). On the other hand, we prove that, except for point formation (Gathering), UPF is solvable under any sequential scheduler without any additional assumptions. We then turn our attention to the Gathering problem, and prove that weak multiplicity detection is necessary and sufficient for solvability under sequential schedulers. The obtained results show that the computational power of the robots under \(\mathcal {FSYNC}\) (where Gathering is solvable without any multiplicity detection) and that under sequential schedulers are orthogonal.