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. In fact, we prove that under any sequential scheduler, robots are capable of solving problems that are unsolvable even with a leader under the fully synchronous scheduler <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathcal {FSYNC}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">FSYNC</mi> </math></EquationSource> </InlineEquation>. More precisely, we consider the class of pattern formation problems, and focus on the most general problem in this class, <Emphasis FontCategory="NonProportional">Universal Pattern Formation</Emphasis> (<Emphasis FontCategory="NonProportional">UPF</Emphasis>), which requires the robots to form every pattern given in input, starting from any initial configuration (where some robots may occupy the same point, hence forming a multiplicity).We first show that <Emphasis FontCategory="NonProportional">UPF</Emphasis> is unsolvable under <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mathcal {FSYNC}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">FSYNC</mi> </math></EquationSource> </InlineEquation>, 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 (<Emphasis FontCategory="NonProportional">Gathering</Emphasis>), <Emphasis FontCategory="NonProportional">UPF</Emphasis> is solvable under any sequential scheduler without any additional assumptions. We then turn our attention to the <Emphasis FontCategory="NonProportional">Gathering</Emphasis> problem, and prove that weak multiplicity detection (the ability to detect a multiplicity but not the exact number of robots forming it) is necessary and sufficient for solvability under sequential schedulers. The results obtained show that the computational power of the robots under <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathcal {FSYNC}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">FSYNC</mi> </math></EquationSource> </InlineEquation> (where <Emphasis FontCategory="NonProportional">Gathering</Emphasis> is solvable without any multiplicity detection) and that under sequential schedulers are orthogonal.

Universal pattern formation by oblivious robots under sequential schedulers

期刊论文
发表日期：

2026年3月25日

查看全文

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. In fact, we prove that under any sequential scheduler, robots are capable of solving problems that are unsolvable even with a leader under the fully synchronous scheduler $\mathcal {FSYNC}$ $FSYNC$ . 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 every pattern given in input, starting from any initial configuration (where some robots may occupy the same point, hence forming a multiplicity).

We first show that UPF is unsolvable under $\mathcal {FSYNC}$ $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 (the ability to detect a multiplicity but not the exact number of robots forming it) is necessary and sufficient for solvability under sequential schedulers. The results obtained show that the computational power of the robots under $\mathcal {FSYNC}$ $FSYNC$ (where Gathering is solvable without any multiplicity detection) and that under sequential schedulers are orthogonal.