Universal Dancing by Luminous Robots under Sequential Schedulers
Caterina Feletti, Paola Flocchini, Debasish Pattanayak, Giuseppe Prencipe, Nicola Santoro · 2025
Read Universal Dancing by Luminous Robots under Sequential Schedulers by Caterina Feletti, Paola Flocchini, Debasish Pattanayak, Giuseppe Prencipe, Nicola Santoro (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-15484.txt.
Introduction
Caterina Feletti and co-authors prove that luminous robots can perform any dance choreography under a sequential scheduler. Their 2025 paper sets the Dancing problem: a swarm of robots must form a sequence of patterns in order. Past work showed some choreographies and starting layouts are impossible under standard robot models, due to repeats, symmetry, or size changes.
In the LUMI model each robot carries a light with a color from a small palette, and a sequential scheduler activates robots one at a time. Under that setup the old restrictions fall away. Feasible choreography length is bounded by how n robots can split among the available colors. Their algorithm uses a distributed counter trick and works even with non-rigid movement.
Catalog record
| CREATOR | Caterina Feletti, Paola Flocchini, Debasish Pattanayak, Giuseppe Prencipe, Nicola Santoro |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 89 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-15484
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Universal Dancing by Luminous Robots under Sequential Schedulers Caterina Feletti, Paola Flocchini, Debasish Pattanayak, Giuseppe Prencipe, Nicola Santoro Abstract The Dancing problem requires a swarm of n 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 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 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 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: Luminous Robots, Sequence of Patterns, Pattern Formation, Sequential Scheduler. 1 Introduction 1.1 Framework and Background In the 2020 Olympic Opening Ceremony, a swarm of thousands of drones combined to display an artistic performance in the sky of Tokyo. While it is true that such a technological spectacle has required an engineering effort, it is evident that it could not have been achieved without an accurate algorithmic study. In that case, the drones had to combine in a sequence of patterns (e.g., the Olympic rings), thus performing a sort of choreography, “dancing” in perfect synchrony, and avoiding collisions. In the last two decades, scenarios like this have been formally modeled and studied to design algorithmic techniques intended for the emerging field of swarm robotics . Besides entertainment and performance, swarm robotics can be adopted in multiple domains (e.g., agricultural, aerospace) and for different promising purposes (e.g., exploration, data collection, security, and rescue). Typically, a swarm is modeled as a decentralized and distributed system where multiple computational entities (aka robots) have to arrange on the environment to solve a common task collaboratively. The Look-Compute-Move (LCM) is one of the main models used to describe these systems [ 26 ] . Generally, a swarm is modeled as a set of punctiform mobile robots that can act on the Euclidean plane. The robots are idle by default, and are repeatedly activated by a scheduler. As soon as activated, a robot performs a LCM cycle: it takes the snapshot of the system ( Look ), it executes a deterministic algorithm calculating a position ( Compute ), and eventually it moves straight towards the computed position. By repeating the LCM cycle infinitely, the robots perform a given task (aka solve a problem): typically, robots are required to arrange in the environment to satisfy some conditions (e.g., Scattering [ 18 , 32 ] ) or according to some patterns (e.g., Pattern Formation [ 2 , 7 , 9 , 19 , 24 , 25 , 37 , 41 , 39 ] , Gathering [ 1 , 5 , 10 , 33 , 21 , 35 , 36 ] ). To design algorithms as robust as possible—namely, which can be executed in very limited systems— the literature considers robots that are: anonymous (no internal ids), indistinguishable (no external ids), autonomous (no central control), and homogeneous (they execute the same algorithm). Typically, robots are assumed to be partially or totally disoriented: there might not be agreement between their local coordinate systems, on the unit of distance, or on chirality (i.e., clockwise orientation of the plane). Other limitations may concern robots’ movements, which can be rigid or non-rigid according to the impossibility or possibility of being stopped by an adversary, respectively. In the early literature, starting from the pioneering work of [ 38 ] , robots are assumed to be oblivious and silent , i.e., with neither a persistent memory nor communication means. This very restricted LCM sub-model, called \mathcal{OBLOT} , has been widely studied to both explore its power and delimit its limitations regarding computability. Not surprisingly, not all problems can be solved without memory or communication. The more recent sub-model \mathcal{LUMI} has been introduced by Das et al. [ 14 ] to overcome such limitations: here, robots are assumed to be luminous , i.e., endowed with a persistent register, called light , whose value, called color , can be updated at each LCM cycle choosing from a O(1) -size palette of colors. Being visible to all robots in the swarm, the robot’s light serves as an internal persistent memory and an external communication means. Nevertheless, it is not just the presence/absence of lights that changes the computing power of a swarm. It has been proven that the setting under which robots are activated and synchronized can affect their power. In the synchronous settings, time is divided into atomic discrete rounds ; at each round an arbitrary non-empty subset of the robots is activated and they execute their LCM cycle in perfect synchrony. The most general synchronous setting is called semi-synchronous ( SSYNCH ) and it has been widely studied together with its special case fully synchronous ( FSYNCH ), where all the robots are activated simultaneously at every round. In the even more general asynchronous setting ( ASYNCH ), the robots are activated without any assumptions on the duration of a LCM cycle (except that is finite) nor on the synchronization among them. Note that under SSYNCH (and thus ASYNCH ), robots are unaware of the activation scheduling of the swarm, which is assumed to be made by an adversarial scheduler that, however, operates under the fairness condition , stating that each robot is activated infinitely often within finite time. For years, the literature has mainly focused on these three settings; notably, it has studied the computational power and limits of a model X^{S} , where X\in\{\mathcal{OBLOT},\mathcal{LUMI}\} represents the memory/communication setting while S\in\{\texttt{FSYNCH},\texttt{SSYNCH},\texttt{ASYNCH}\} represents the synchronization setting [ 3 , 14 , 20 , 27 ] . On the sidelines, the sequential setting ( SEQ ), which activates only one robot at a round, remained nearly unexplored until a few years ago. Recently, some works have addressed this setting and its sub-settings (e.g., the famous round-robin ), especially to investigate fault-prone swarms [ 11 , 16 , 17 ] , and the well-known Pattern Formation and Gathering problems [ 22 , 29 ] . 1.2 Pattern Formation Pattern Formation refers to the abstract problem of the robots rearranging themselves so that, within finite time, the set of their locations in the plane (the configuration ) forms (irrespective to rotation, reflection, translation or scaling) a given geometric figure (the pattern ), and the robots no longer move. Which patterns are formable depends on many factors, first