Universal Dancing by Luminous Robots under Sequential Schedulers
Preprint
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 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 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
All Related Versions
This publication has 19 references indexed in Scilit:
- On fast pattern formation by autonomous robotsInformation and Computation, 2022
- Fault-Tolerant Mobile Robots2019
- Gathering of mobile robots with weak multiplicity detection in presence of crash-faultsJournal of Parallel and Distributed Computing, 2019
- Embedded pattern formation by asynchronous robots without chiralityDistributed Computing, 2018
- Asynchronous Arbitrary Pattern Formation: the effects of a rigorous approachDistributed Computing, 2018
- Distributed computing by mobile robots: uniform circle formationDistributed Computing, 2016
- Forming sequences of geometric patterns with oblivious mobile robotsDistributed Computing, 2014
- Arbitrary pattern formation by asynchronous, anonymous, oblivious robotsTheoretical Computer Science, 2008
- Coordination without communication: the case of the flocking problemDiscrete Applied Mathematics, 2004
- A Gray code for compositionsJournal of Algorithms, 1982