Brief Announcement: Universal Dancing by Luminous Robots Under Sequential Schedulers

Feletti, Caterina; Flocchini, Paola; Pattanayak, Debasish; Prencipe, Giuseppe; Santoro, Nicola

doi:10.4230/LIPIcs.DISC.2025.56

Brief Announcement: Universal Dancing by Luminous Robots Under Sequential Schedulers

Caterina Feletti

Department of Computer Science, Università degli Studi di Milano, Italy Paola Flocchini

School of Electrical Engineering and Computer Science, University of Ottawa, Canada Debasish Pattanayak

Department of Computer Science and Engineering, Indian Institute of Technology Indore, India Giuseppe Prencipe

Department of Computer Science, Università di Pisa, Italy Nicola Santoro

School of Computer Science, Carleton University, Ottawa, Canada

Abstract

The Dancing problem requires a swarm of $n$ autonomous mobile robots to form a sequence of patterns, aka perform a choreography. Existing work has proven that some crucial restrictions on choreographies and initial configurations (e.g., on repetitions of patterns, periodicity, symmetries, contractions/expansions) must hold so that the Dancing problem can be solved under certain robot models. Here, we prove that these necessary constraints can be dropped by considering the $\mathcal{LUMI}$ model (i.e., where robots are endowed with a light whose color can be chosen from a constant-size palette) under the quite unexplored sequential scheduler. We formalize the class of Universal Dancing problems which require a swarm of $n$ robots starting from any initial configuration to perform a (periodic or finite) sequence of arbitrary patterns, only provided that each pattern consists of $n$ vertices (including multiplicities). However, we prove that, to be solvable under $\mathcal{LUMI}$ , the length of the feasible choreographies is bounded by the compositions of $n$ into the number of colors available to the robots. We provide an algorithm solving the Universal Dancing problem by exploiting the peculiar capability of sequential robots to implement a distributed counter mechanism. Even assuming non-rigid movements, our algorithm ensures spatial homogeneity of the performed choreography.

Keywords and phrases:

Luminous Robots, Sequence of Patterns, Pattern Formation, Sequential Scheduler

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Distributed algorithms

Related Version:

Full Version: https://doi.org/10.48550/arXiv.2508.15484 [10]

Acknowledgements:

This research was done while Caterina Feletti was visiting Profs. Flocchini and Santoro.

Funding:

This work was partly supported by NSERC through the Discovery Grant program.

DOI:

10.4230/LIPIcs.DISC.2025.56

Event:

39th International Symposium on Distributed Computing (DISC 2025)

Editor:

Dariusz R. Kowalski

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The Look-Compute-Move (LCM) model is a theoretical model used to study distributed systems of mobile robots, aka swarms [12]. Generally, a swarm is modeled as a set of punctiform mobile robots $\mathcal{R}=\{r_{1},\dots,r_{n}\}$ acting on the Euclidean plane $\mathbb{R}^{2}$ ; they are assumed to be anonymous and indistinguishable (i.e., no internal nor external ids), autonomous (no central control), and homogeneous (they execute the same deterministic algorithm). Any robot, idle by default, is repeatedly activated by a scheduler. As soon as activated, the robot performs an LCM cycle: it takes the snapshot of the system (Look), it executes the given algorithm calculating a position (Compute), and it moves straight towards the computed position (Move). By repeating the LCM cycle infinitely, the swarm performs a given task (aka solves a problem). Different LCM (sub) models, usually referred to as $X^{S}$ , have been considered to study the solvability of a problem: $X=\mathcal{OBLOT}$ represents the most limited model where robots are both oblivious and silent, while $X=\mathcal{LUMI}$ represents the model where robots are embedded with a $O(1)$ -size light whose color is used both as an internal state and a communication means. Instead, $S$ refers to the synchronization scheduler setting: FSYNCH, SSYNCH, and ASYNCH are the most considered ones, while the sequential setting (SEQ), which activates only one robot at each round assuming the fairness condition, has remained nearly unexplored until a few years ago [3, 7, 8, 11, 15].

Interest in SEQ has been driven by recent research on the well-known Pattern Formation problem [1, 2, 9, 13, 14, 17, 18, 19]. Pattern Formation for a given pattern $\Pi$ (i.e., a multiset of positions in $\mathbb{R}^{2}$ ) requires the robots to rearrange themselves into a configuration similar to $\Pi$ , and terminate. Indeed, the features of the model, particularly its $X$ and $S$ , characterize the class of patterns that a swarm can form [20]. A question arose: under which model assumptions can a swarm solve the Universal Pattern Formation (UPF) problem, namely form any pattern starting from any initial configuration? An answer is given in [11] which shows that, except for point formation, UPF is solvable under $\mathcal{OBLOT}^{\texttt{SEQ}}$ without any additional assumption: consequently, UPF, with point formation, is solvable under $\mathcal{LUMI}^{\texttt{SEQ}}$ .

Recognizing the power of SEQ, the same interest has turned towards the quite unexplored Dancing problem, which asks a swarm to form a periodic or finite sequence of patterns, aka a choreography [4, 5, 6]. In [6] it was shown that under $\mathcal{OBLOT}^{\texttt{SSYNCH}}$ robots can perform choreographies with several constraints (on patterns and choreography periodicity), assuming chirality agreement among robots; in [5], it has shown that, under $\mathcal{LUMI}$ and with a global chirality, the feasible choreographies are subject to fewer constraints, even assuming ASYNCH and non-rigid movements. Now, the question is similar: under which model assumptions can a swarm solve the Universal Dancing (UD) problem, namely perform a sequence of arbitrary patterns starting from any initial configuration?

This paper answers this question. We provide an algorithm that solves UD under $\mathcal{LUMI}^{\texttt{SEQ}}$ and considering robots that are completely disoriented (i.e., no agreement on origin, unit distance, axes, chirality) and suffering from variable disorientation (i.e., their local coordinate system may change from one LCM cycle to the next one). Robots have strong multiplicity detection, i.e., they can detect the number of all the robots – and their colors – lying in the same point (aka forming a multiplicity). We assume non-rigid movements; thus, any robot may be stopped unpredictably after having traveled at least a non-null constant distance $\delta$ , unknown to robots. Despite non-rigidity, our solution guarantees an interesting spatial property which provides homogeneity to the whole choreography performance: the smallest circles enclosing the patterns of the choreography (except for patterns with only two or three points) formed by the swarm are concentric. We prove that, to be solvable under $\mathcal{LUMI}$ , the length/period of the feasible choreographies of UD is bounded by the compositions of $n$ into the number of colors available to the robots. Our contribution is summarized here:

Theorem 1.

The Universal Dancing problem can be solved under $\mathcal{LUMI}^{\texttt{SEQ}}$ by a swarm of $n$ disoriented robots with $k\geq 4$ colors, assuming that the choreographies have length/period $q\leq\binom{n+k-7}{k-4}$ , even assuming non-rigid movements.

2 Preliminaries

Patterns and choreographies.

A pattern $\Pi$ is a multiset of positions in $\mathbb{R}^{2}$ , called vertices. We denote with $shape(\Pi)$ the set containing the unique positions in $\Pi$ . We distinguish between four classes of patterns, namely Point, TwoPoints, ThreePoints, and NPoints, according to $|shape(\cdot)|$ , which is respectively 1, 2, 3, and more than 3. We denote with $\mathscr{P}({\Pi})$ the set of patterns similar¹¹1We consider non-degenerate similarities. to $\Pi$ . A swarm forms $\Pi$ if it stops in a configuration whose multiset of positions is in $\mathscr{P}({\Pi})$ .

A choreography is a sequence of patterns $\mathcal{S}=(\Pi_{0},\dots,\Pi_{q-1})^{x}$ where $\Pi_{i+1}\notin\mathscr{P}(\Pi_{i})$ and with $x\in\{1,\infty\}$ . If $\mathcal{S}$ is periodic (i.e., if $x=\infty$ ), then we assume that $\Pi_{0}\notin\mathscr{P}(\Pi_{q-1})$ and that the sequence $\Pi_{0},\dots,\Pi_{q-1}$ cannot be written as $(\Pi_{0},\dots,\Pi_{h-1})^{\frac{q}{h}}$ for any $h<q$ . We say that $q$ is the length (period, resp.) of $\mathcal{S}$ if $x=1$ ( $x=\infty$ , resp.). A swarm $\mathcal{R}$ performs $\mathcal{S}$ if, for any $j=1,\dots,x$ , there exists a series of increasing finite times $\{t_{i+(j-1)q}\}_{i=0,\dots,q-1,j=1,\dots,x}$ such that $\mathcal{R}$ forms $\Pi_{i}$ at time $t_{i+(j-1)q}$ . If $x=1$ , then $\mathcal{R}$ must remain still after time $t_{q-1}$ .

The Dancing problems.

Dancing refers to the generic problem of performing choreographies. Multiple constraints can be applied to the set of choreographies in order to make them performable (aka feasible). Different constraints define specific Dancing problems, each one formalized as the triple $\mathfrak{D}=\langle\Sigma(n),\mathcal{I}(n),\phi\rangle$ , where:

$\blacksquare$

$\Sigma(n)$ is a set of patterns with $n$ vertices;
$\blacksquare$

$\mathcal{I}(n)$ is a set of initial configurations for a swarm of $n$ robots;
$\blacksquare$

$\phi$ is a predicate on choreographies (e.g., limiting their length, pattern repetitions, etc.).

We say that $\mathcal{S}=(\Pi_{0},\dots,\Pi_{q-1})^{x}$ is a feasible choreography for $\mathfrak{D}$ if $\Pi_{i}\in\Sigma(n)$ for any $i\in[0,q-1]$ and $\mathcal{S}$ satisfies $\phi$ . For $\mathfrak{D}$ to be well-defined, each pattern in $\Sigma(n)$ must appear in at least one feasible choreography. An algorithm $\mathbb{A}$ solves $\mathfrak{D}$ if, for any swarm $\mathcal{R}$ starting from a configuration in $\mathcal{I}(n)$ , it makes $\mathcal{R}$ perform any feasible choreography for $\mathfrak{D}$ . A Dancing problem $\langle\Sigma(n),\mathcal{I}(n),\phi\rangle$ is said to be Universal if $\Sigma(n)=(\mathbb{R}^{2})^{n}$ (i.e., any pattern with $n$ vertices), $\mathcal{I}(n)=(\mathbb{R}^{2}\times\{\mathsf{off}\})^{n}$ (i.e., set of all possible initial configurations where robots are $\mathsf{off}$ -colored), and $\phi$ can only bound the length/period of the choreographies. In this paper, we solve the Universal Dancing under a specific bound $\phi$ . We prove that if $\phi$ is a tautology $\top$ , then the problem is unsolved under our model.

Theorem 2.

The $\langle(\mathbb{R}^{2})^{n},(\mathbb{R}^{2}\times\{\mathsf{off}\})^{n},\top\rangle$ problem cannot be solved under $\mathcal{LUMI}^{\texttt{SEQ}}$ even if robots have rigid movements and share a global coordinate system.

Proof.

(sketch) A contradiction is achieved considering $\mathcal{S}=(\mathtt{P}_{1},\Pi_{1},\dots,\mathtt{P}_{z},\Pi_{z},\mathtt{P}_{z% +1},\Pi_{z+1})$ , where $z=\binom{n+k-1}{k-1}$ is the number of color-compositions in a $n$ -size swarm using $k$ colors, and where $\mathtt{P}_{i}\in\texttt{Point}$ for any $i\in[1,z+1]$ and $\Pi_{i}\neq\Pi_{j}$ for any $i\neq j\in[1,z+1]$ . Then, there will be two times during the performance of $\mathcal{S}$ in which the swarm has the same configuration (same colors, forming $\mathtt{P}_{a}$ and $\mathtt{P}_{b}$ , with $a<b$ ). This may lead the swarm to perform in a loop the sub-sequence $(\Pi_{a},\dots,\Pi_{b-1}\mathtt{P}_{b})^{\infty}$ , thus never completing the choreography. $\hfill\blacktriangleleft$

3 Algorithm Outline

We here outline the algorithm that proves Theorem 1. Our algorithm uses a totally-ordered palette $\mathcal{L}=\{\ell_{1},\dots,\ell_{k-3},\mathsf{L_{1}},\mathsf{L_{2}},\mathsf{% L_{3}}\}$ of $k\geq 4$ colors which allows a $n$ -size swarm $\mathcal{R}$ to perform any feasible choreography $\mathcal{S}=(\Pi_{0},\dots,\Pi_{q-1})^{x}$ with $x\in\{1,\infty\}$ that satisfies $q\leq\binom{n+k-7}{k-4}$ . By convention, $\ell_{1}=\mathsf{off}$ , which is the default color to which all robots are initialized.

Techniques

Our algorithm adopts peculiar techniques which combine both the power of $\mathcal{LUMI}^{\texttt{SEQ}}$ and some concepts taken and adapted from other fields.

$\blacksquare$

Universal orientation. The SEQ setting allows us to elect three leaders, starting from any configuration. These leaders, colored with the colors $\mathsf{L_{1}}$ , $\mathsf{L_{2}}$ , and $\mathsf{L_{3}}$ , will be destined to form the chiral angle, a special triangle $\triangle\nu_{1}\nu_{2}\nu_{3}$ which globally defines a coordinate system for the swarm, and the position of the actual pattern, i.e., the pattern on whose vertices the robots must arrange. The construction of the chiral angle occurs before the formation of each pattern $\Pi_{i}$ of the choreography and strictly depends on it; moreover, it is built to maintain spatial homogeneity to the choreography performance (e.g., $\nu_{1}$ is always the same point for any $\Pi_{i}$ ). Notably, if $\Pi_{i}\notin\texttt{NPoints}$ , then the vertices of the chiral angle²²2Degenerate if $\Pi_{i}\in\texttt{Point}\cup\texttt{TwoPoints}$ . exactly define the points where the robots have to arrange themselves. Instead, if $\Pi_{i}\in\texttt{NPoints}$ , $\nu_{1}$ sets the origin $(0,0)$ , $\nu_{2}$ sets the coordinate $(0,1)$ thus the $x$ -axis and the unit distance, and $\nu_{3}$ sets the clockwise direction³³3When the vertices in $\Pi_{i}$ are not aligned.. The actual pattern $\Pi\in\mathscr{P}(\Pi_{i})$ is univocally defined by the chiral angle: $\nu_{2}$ and $\nu_{3}$ are two specific vertices of $\Pi$ , and $SEC(\Pi)$ will be centered in $\nu_{1}$ , so that $\nu_{2}$ lies on its boundary. See Figure 1.
$\blacksquare$

Robot-vertex matching. The formation of each pattern is based on a technique that makes the robots match their target vertices, exploiting properties of Dyck words on the Boolean alphabet.
$\blacksquare$

Distributed counter. We exploit the power of $\mathcal{LUMI}^{\texttt{SEQ}}$ by implementing a distributed counter to keep track of the pattern to form along the choreography. Specifically, the $n-3$ non-leader robots, using the colors $\ell_{1},\dots,\ell_{k-3}$ , can encode an integer in the range $[0,z-1]$ where $z=\binom{n+k-7}{k-4}$ is the number of weak-compositions of $n-3$ robots with $k-3$ colors. For this purpose, we exploit the Gray Code for compositions in [16]: that method allows us to order all the composition vectors $X_{0},\dots,X_{z-1}$ , so that each $X_{i}=(x_{1},\dots,x_{k-3})$ indicates the number of robots $x_{j}$ of color $\ell_{j}$ , for any $j\in[1,k-3]$ . The vector $X_{i}$ thus encodes the counter value $i$ . The Gray code ensures that $X_{0}$ corresponds to the vector where all the $n-3$ robots are $\mathsf{off}$ , and that $X_{i}$ and $X_{i+1}$ differ at exactly two indices, say $a, b$ , so that $X_{i+1}[a]=X_{i}[a]+1$ and $X_{i+1}[b]=X_{i}[b]-1$ : thus, to increment the counter, an $\ell_{b}$ -colored robot must turn into $\ell_{a}$ .

(a)

\Pi_{i}\in\texttt{Point}

.

(b)

\Pi_{i}\in\texttt{TwoPoints}

.

(c)

\Pi_{i}\in\texttt{NPoints}

.

Figure 1: Chiral angles in different scenarios.

Phases

The core of our algorithm is composed of three phases, i.e., Phase 1, Phase 2, Phase 3, which are repeated cyclically until the choreography ends. For each $\Pi_{i}\in\mathcal{S}$ , Phase 1 aims at setting the chiral angle; Phase 2 aims at making robots form $\Pi_{i}$ ; Phase 3 aims at updating the counter value. Before entering the loop, robots execute an initial phase Phase 0.

Phase 0 - Election of leaders.

This phase is executed only once, starting from the initial configuration, and terminates when the three leaders have properly elected themselves by setting the dedicated colors $\mathsf{L_{1}}$ , $\mathsf{L_{2}}$ , and $\mathsf{L_{3}}$ . No robot moves. The counter value now is 0.

Phase 1 - Chiral angle setup.

Let $i$ be the counter’s value, and let $\Pi_{i}$ be the corresponding pattern in the choreography. In this phase, the three leaders $\mathsf{L_{1}}$ , $\mathsf{L_{2}}$ , $\mathsf{L_{3}}$ compute the chiral angle $\triangle\nu_{1}\nu_{2}\nu_{3}$ for $\Pi_{i}$ , and sequentially reach the relative vertices. No other robot moves.

Phase 2 - Pattern Formation.

This phase starts when the leaders have formed the chiral angle for $\Pi_{i}$ and ends as soon as each vertex of $\Pi\in\mathscr{P}(\Pi_{i})$ , unequivocally defined by the chiral angle, is covered by a robot. We describe Phase 2 for the case $\Pi\in\texttt{NPoints}$ .

Let $\Omega$ be the circle centered in $\mathsf{L_{1}}$ and such that $\mathsf{L_{2}}$ lies on its boundary. By construction, all the robots are enclosed in $\Omega$ , and they will form $\Pi$ so that $SEC(\Pi)=\Omega$ . Note that $\mathsf{L_{2}}$ and $\mathsf{L_{3}}$ already lie on two vertices of $\Pi$ , thus they will not move. Let $D$ be the diameter of $\Omega$ starting from $\mathsf{L_{2}}$ . Given a vertex $v$ of $\Pi$ , we indicate with $v_{\perp}$ its projection on $D$ .

(a) Non-leader robots and their projections on

D

.

(b) Projections of the target vertices,

\Pi_{\perp}

.

Figure 2: Phase 2, case

\Pi\in\texttt{NPoints}

.

Robots arrange on $\Pi$ in four sub-phases:

1.

Migration towards $D$ . Each non-leader robot reaches $D$ moving along a perpendicular trajectory (see Figure 2(a)).
2.

Arrangement on $D$ . Once all $m=n-3$ non-leader robots have reached $D$ , they compute $\Pi_{\perp}=\{\mskip-5.0mu\{v_{\perp}\mid v\in\Pi\}\mskip-5.0mu\}$ , i.e., the multiset of all the projections of $\Pi$ (see Figure 2(b)), and remove from it the projections of the three vertices intended for the leaders. Let $r$ be an activated robot on $D$ . Thus, $r$ computes the boolean string $w\in\{0,1\}^{\leq 2m}$ that represents the ordered arrangement of unmatched robots (1s) and uncovered projections (0s) along $D$ . Note that multiplicities of robots (vertices, resp.) on $D$ are treated by unrolling and representing them through factors of adjacent 1s (0s, resp.). Then, $w$ can be factorized uniquely into Dyck words (or their reverses), which univocally defines the robot-projection matching (see Figure 3). Thus, each non-leader robot moves along $D$ to reach the matching target projection. The properties of Dyck words ensure that each of the $m$ non-leader robots will reach a vertex projection on $D$ in finite time, even considering non-rigid movements.
3.

Back to the vertices. In this sub-phase, all the non-leader robots travel perpendicularly to $D$ and reach the corresponding vertices of $\Pi$ . Let $r$ be a non-leader robot on $D$ : it unambiguously chooses the closest uncovered vertex of $\Pi$ whose projection corresponds to its current position on $D$ , and for which there does not yet exist a robot moving towards it. Note that multiple vertices (belonging to both the semi-circles cut by $D$ ) can have the same projection; in this case, $r$ unambiguously elects the target vertex by considering the clockwise orientation of the plane. After the vertex choice, $r$ starts traveling perpendicularly to $D$ towards the computed vertex. Robot $r$ may be stopped before reaching its vertex. Let $h$ be the segment perpendicular to $D$ which starts from $D$ , contains $r$ , and ends at $\Omega$ . Let $v_{1},\dots,v_{s}$ be the list of vertices along $h$ so that $d(v_{i},D)\geq d(v_{i+1},D)$ . Then $r$ moves to $v_{j}$ where $j\in[1,s]$ is the greatest index such that $v_{j}$ is not covered and $r$ lies on the segment $[v_{j},v_{j_{\perp}})$ .
4.

$\mathsf{L_{1}}$ towards its vertex. Lastly, $\mathsf{L_{1}}$ moves to reach the last missing vertex of the pattern $\Pi$ , which has been properly selected by the swarm.

Figure 3: Robot-projection matching through Dyck words, where

w=100001011110

.

Phase 3 - Counter Update.

This phase starts as soon as each vertex of $\Pi$ is covered by a robot. Let the current counter vector be $X_{i}=(x_{1},\dots,x_{k-3})$ . We distinguish three actions:

$\blacksquare$

Termination. If $i=q-1$ and $x=1$ , then the swarm has terminated the choreography, and then it does not update the counter: this causes the swarm to freeze in $\Pi_{q-1}$ .
$\blacksquare$

Increment. If $i<q-1$ , then the swarm must increment the counter from $i$ to $i+1$ . Let $X_{i+1}$ be the next vector. From the Gray code construction, there are exactly two differences between $X_{i}$ and $X_{i+1}$ corresponding to one decrement value and one increment value. Let $a$ and $b$ be the two indices that change between $X_{i}$ and $X_{i+1}$ . Thus, as soon as a robot with color $\ell_{a}$ gets activated, it changes its color to $\ell_{b}$ .
$\blacksquare$

Resetting. If $i=q-1$ and $x=\infty$ , then the swarm must reset the counter to the initial value $X_{0}$ , i.e., where all the non-leader robots are $\mathsf{off}$ -colored. For an unambiguous resetting, we make the leader $\mathsf{L_{3}}$ set its color to $\mathsf{L_{2}}$ : the presence of two $\mathsf{L_{2}}$ robots signals non-leader robots that they have to reset the counter. Once all non-leader robots have turned into $\mathsf{off}$ , then one of the two $\mathsf{L_{2}}$ robots turns into $\mathsf{L_{3}}$ : if it is possible to establish which was the original $\mathsf{L_{3}}$ , the leaders maintain their former roles.

References

[1] Serafino Cicerone, Gabriele Di Stefano, and Alfredo Navarra. Asynchronous arbitrary pattern formation: The effects of a rigorous approach. Distributed Computing, 32(2):91–132, 2019. doi:10.1007/S00446-018-0325-7.
[2] Serafino Cicerone, Gabriele Di Stefano, and Alfredo Navarra. Solving the pattern formation by mobile robots with chirality. IEEE Access, 9:88177–88204, 2021. doi:10.1109/ACCESS.2021.3089081.
[3] Stefano Clemente and Caterina Feletti. Fault detection and identification by autonomous mobile robots. In Proc. of 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND), pages 10:1–10:20, 2025. doi:10.4230/LIPIcs.SAND.2025.10.
[4] Shantanu Das, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Synchronized dancing of oblivious chameleons. In Proc. of 7th International Conference on Fun with Algorithms (FUN), volume 8496, pages 113–124. Springer, 2014. doi:10.1007/978-3-319-07890-8_10.
[5] Shantanu Das, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Forming sequences of patterns with luminous robots. IEEE Access, 8:90577–90597, 2020. doi:10.1109/ACCESS.2020.2994052.
[6] Shantanu Das, Paola Flocchini, Nicola Santoro, and Masafumi Yamashita. Forming sequences of geometric patterns with oblivious mobile robots. Distributed Computing, 28(2):131–145, 2015. doi:10.1007/s00446-014-0220-9.
[7] Xavier Défago, Maria Gradinariu, Stéphane Messika, and Philippe Raipin Parvédy. Fault-tolerant and self-stabilizing mobile robots gathering. In Proc. of 20th International Symposium on Distributed Computing (DISC), volume 4167, pages 46–60. Springer, 2006. doi:10.1007/11864219_4.
[8] Xavier Défago, Maria Potop-Butucaru, and Sébastien Tixeuil. Fault-Tolerant Mobile Robots. Chapter 10 of [12], pages 234–251, 2019. doi:10.1007/978-3-030-11072-7_10.
[9] Yoann Dieudonné, Franck Petit, and Vincent Villain. Leader election problem versus pattern formation problem. In Proc. of 24th International Symposium on Distributed Computing (DISC), pages 267–281, 2010. doi:10.1007/978-3-642-15763-9_26.
[10] Caterina Feletti, Paola Flocchini, Debasish Pattanayak, Giuseppe Prencipe, and Nicola Santoro. Universal dancing by luminous robots under sequential schedulers, 2025. arXiv:2508.15484.
[11] Paola Flocchini, Alfredo Navarra, Debasish Pattanayak, Francesco Piselli, and Nicola Santoro. Oblivious robots under sequential schedulers: Universal pattern formation. In Proc. 32nd International Colloquium of Structural Information and Communication Complexity (SIROCCO), volume 15671, pages 297–314. Springer, 2025. doi:10.1007/978-3-031-91736-3_18.
[12] Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro, editors. Distributed Computing by Mobile Entities: Current Research in Moving and Computing, volume 11340. Springer, 2019. doi:10.1007/978-3-030-11072-7.
[13] Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. Hard tasks for weak robots: The role of common knowledge in pattern formation by autonomous mobile robots. In Proc. of 10th International Symposium on Algorithms and Computation (ISAAC), pages 93–102, 1999. doi:10.1007/3-540-46632-0_10.
[14] Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theoretical Computer Science, 407(1):412–447, 2008. doi:10.1016/j.tcs.2008.07.026.
[15] Fabian Frei and Koichi Wada. Brief announcement: Distinct gathering under round robin. In Proc. of 38th International Symposium on Distributed Computing (DISC), volume 319, pages 48:1–48:8, 2024. doi:10.4230/LIPIcs.DISC.2024.48.
[16] Paul Klingsberg. A Gray code for compositions. Journal of Algorithms, 3(1):41–44, 1982. doi:10.1016/0196-6774(82)90006-2.
[17] Giuseppe Prencipe. Pattern formation. In Chapter 3 of [12], volume 11340, pages 37–62. Springer, 2019. doi:10.1007/978-3-030-11072-7_3.
[18] Ichiro Suzuki and Masafumi Yamashita. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal on Computing, 28(4):1347–1363, 1999. doi:10.1137/S009753979628292X.
[19] Ramachandran Vaidyanathan, Gokarna Sharma, and Jerry Trahan. On fast pattern formation by autonomous robots. Information and Computation, 285:104699, 2022. doi:10.1016/j.ic.2021.104699.
[20] Masafumi Yamashita and Ichiro Suzuki. Characterizing geometric patterns formable by oblivious anonymous mobile robots. Theoretical Computer Science, 411(26-28):2433–2453, 2010. doi:10.1016/j.tcs.2010.01.037.

[bib.bib1] [1] Serafino Cicerone, Gabriele Di Stefano, and Alfredo Navarra. Asynchronous arbitrary pattern formation: The effects of a rigorous approach. Distributed Computing, 32(2):91–132, 2019. doi:10.1007/S00446-018-0325-7.

[bib.bib2] [2] Serafino Cicerone, Gabriele Di Stefano, and Alfredo Navarra. Solving the pattern formation by mobile robots with chirality. IEEE Access, 9:88177–88204, 2021. doi:10.1109/ACCESS.2021.3089081.

[bib.bib3] [3] Stefano Clemente and Caterina Feletti. Fault detection and identification by autonomous mobile robots. In Proc. of 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND), pages 10:1–10:20, 2025. doi:10.4230/LIPIcs.SAND.2025.10.

[bib.bib4] [4] Shantanu Das, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Synchronized dancing of oblivious chameleons. In Proc. of 7th International Conference on Fun with Algorithms (FUN), volume 8496, pages 113–124. Springer, 2014. doi:10.1007/978-3-319-07890-8_10.

[bib.bib5] [5] Shantanu Das, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Forming sequences of patterns with luminous robots. IEEE Access, 8:90577–90597, 2020. doi:10.1109/ACCESS.2020.2994052.

[bib.bib6] [6] Shantanu Das, Paola Flocchini, Nicola Santoro, and Masafumi Yamashita. Forming sequences of geometric patterns with oblivious mobile robots. Distributed Computing, 28(2):131–145, 2015. doi:10.1007/s00446-014-0220-9.

[bib.bib7] [7] Xavier Défago, Maria Gradinariu, Stéphane Messika, and Philippe Raipin Parvédy. Fault-tolerant and self-stabilizing mobile robots gathering. In Proc. of 20th International Symposium on Distributed Computing (DISC), volume 4167, pages 46–60. Springer, 2006. doi:10.1007/11864219_4.

[bib.bib8] [8] Xavier Défago, Maria Potop-Butucaru, and Sébastien Tixeuil. Fault-Tolerant Mobile Robots. Chapter 10 of [12], pages 234–251, 2019. doi:10.1007/978-3-030-11072-7_10.

[bib.bib9] [9] Yoann Dieudonné, Franck Petit, and Vincent Villain. Leader election problem versus pattern formation problem. In Proc. of 24th International Symposium on Distributed Computing (DISC), pages 267–281, 2010. doi:10.1007/978-3-642-15763-9_26.

[bib.bib10] [10] Caterina Feletti, Paola Flocchini, Debasish Pattanayak, Giuseppe Prencipe, and Nicola Santoro. Universal dancing by luminous robots under sequential schedulers, 2025. arXiv:2508.15484.

[bib.bib11] [11] Paola Flocchini, Alfredo Navarra, Debasish Pattanayak, Francesco Piselli, and Nicola Santoro. Oblivious robots under sequential schedulers: Universal pattern formation. In Proc. 32nd International Colloquium of Structural Information and Communication Complexity (SIROCCO), volume 15671, pages 297–314. Springer, 2025. doi:10.1007/978-3-031-91736-3_18.

[bib.bib12] [12] Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro, editors. Distributed Computing by Mobile Entities: Current Research in Moving and Computing, volume 11340. Springer, 2019. doi:10.1007/978-3-030-11072-7.

[bib.bib13] [13] Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. Hard tasks for weak robots: The role of common knowledge in pattern formation by autonomous mobile robots. In Proc. of 10th International Symposium on Algorithms and Computation (ISAAC), pages 93–102, 1999. doi:10.1007/3-540-46632-0_10.

[bib.bib14] [14] Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theoretical Computer Science, 407(1):412–447, 2008. doi:10.1016/j.tcs.2008.07.026.

[bib.bib15] [15] Fabian Frei and Koichi Wada. Brief announcement: Distinct gathering under round robin. In Proc. of 38th International Symposium on Distributed Computing (DISC), volume 319, pages 48:1–48:8, 2024. doi:10.4230/LIPIcs.DISC.2024.48.

[bib.bib16] [16] Paul Klingsberg. A Gray code for compositions. Journal of Algorithms, 3(1):41–44, 1982. doi:10.1016/0196-6774(82)90006-2.

[bib.bib17] [17] Giuseppe Prencipe. Pattern formation. In Chapter 3 of [12], volume 11340, pages 37–62. Springer, 2019. doi:10.1007/978-3-030-11072-7_3.

[bib.bib18] [18] Ichiro Suzuki and Masafumi Yamashita. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal on Computing, 28(4):1347–1363, 1999. doi:10.1137/S009753979628292X.

[bib.bib19] [19] Ramachandran Vaidyanathan, Gokarna Sharma, and Jerry Trahan. On fast pattern formation by autonomous robots. Information and Computation, 285:104699, 2022. doi:10.1016/j.ic.2021.104699.

[bib.bib20] [20] Masafumi Yamashita and Ichiro Suzuki. Characterizing geometric patterns formable by oblivious anonymous mobile robots. Theoretical Computer Science, 411(26-28):2433–2453, 2010. doi:10.1016/j.tcs.2010.01.037.