Pattern Formation, Dancing, and Sequential Schedulers

In distributed computing, extensive research has focused on the computational power of systems of autonomous mobile robots. The robots operate in Euclidean spaces (typically the plane) in Look–Compute–Move (LCM) cycles of activities: upon activation, each robot observes the positions of the others - Look, executes a set of deterministic rules common to all robots to compute a destination - Compute, and moves toward it - Move.

One of the main concerns of the research in the field is the study of the minimal capabilities that would allow the robots to solve a given problem (e.g., see [13]). Examples of capabilities are a shared coordinate system (a compass), chirality (a common notion of clockwise), rigidity of movements (the robots reach exactly their destination), multiplicity detection (the ability of distinguishing points occupied by multiple robots).

In the standard $𝒪$BLOT model, robots are anonymous, oblivious, and silent: they have no persistent memory, no means of explicit communication, and no distinguishing features. An extension of the model that has been widely investigated is the $ℒ$UMI model, where each robot is equipped with a visible light displaying a colour (from a small set of colours) that can change at every cycle. This light can be used as a constant-size persistent memory, as well as a limited form of communication [8].

One of the key factors influencing the computational power of the robots is the level of synchronization and the duration of each operation within the LCM cycle. In the synchronous setting, time is divided into discrete rounds; in each round, a non-empty subset of robots is activated and perform their LCM cycle simultaneously. The activation of robots is governed by a fair adversary (called scheduler). Under the special fully synchronous scheduler $ℱ𝒮𝒴𝒩𝒞$ all robots are activated at each cycle; under the most general synchronous scheduler $𝒮𝒮𝒴𝒩𝒞$ (also called semi-synchronous), the adversary can activate any subset of robots.

Among the synchronous schedulers, considerable attention has been recently given to the class of Sequential ones, where exactly one robot is activated at each round [6, 10, 11, 12, 18]. The most general sequential schedulers is $𝒮𝒬$, where the adversary can chose an arbitrary robot to be activated at each cycle. At first glance, such schedulers appear to offer only the advantage of enabling symmetry breaking, and thus leader election; the computational power of robots operating under a sequential scheduler is instead much more interesting.

The impact of the type of schedulers on the computational power of the robots in the $𝒪$BLOT, $ℒ$UMI, and related models, as well as a picture of their computational landscape has been studied in [1, 2, 11, 16, 17].

In the following, we report on recent results on the impact that sequential schedulers have on the class of pattern formation problems.

Pattern formation (or Shape formation) refers to the problem of the robots rearranging themselves from their initial positions so that, at some point in time, the set of their locations in the plane (the configuration) satisfies some geometric predicate given in input (the pattern) and no longer move. Typically, the pattern is specified as a set of points representing a geometric figure that the robots must form irrespective of rotation, reflection, translation or scaling (e.g., [15, 19, 20, 22]). A special pattern is the point; in the point formation problem (also known as Gathering), all robots must meet at a single, unspecified location (e.g., [5, 21]).

Pattern formation has been widely studied under various assumptions. A trivial assumption is that the robots must be at least as many as the points in the target pattern - if they are more, multiple robots will lie on the same points of the pattern. Most of the algorithmic research has however relied on additional assumptions. These include: limiting the types of permissible initial configurations (for example, requiring robots to start from distinct positions); imposing restrictions on the number of robots or the size of the pattern (e.g., the size of the swarm is a prime number, or it is equal to the number of points in the pattern); enforcing specific symmetry relationships between the initial configuration and the target pattern; assuming a shared coordinate system or common chirality among the robots; requiring rigid movements; designating a particular robot as a distinguished leader different from the others, etc. (e.g., [3, 4, 14, 15, 20, 22]).

Universal Pattern Formation (UPF) is the most general problem in this class, and it requires the robots to form any arbitrary pattern given in input, starting from any arbitrary initial configuration, regardless of the number of robots, and of the number of points in the pattern, under just the trivial assumption. Let ${\mathrm{𝚄𝙿𝙵}}^{\ast }$ be the UPF problem when the pattern to be formed is not a single point. It has recently been shown in [12] that ${\mathrm{𝚄𝙿𝙵}}^{\ast }$ is solvable in $𝒪$BLOT under $𝒮𝒬$ without any additional assumption. Furthermore, for point formation, weak multiplicity detection has been identified as a necessary and sufficient condition for solvability in $𝒮𝒬$, and an algorithm has been provided. In other words, it has been established that under any sequential scheduler: $i)$ oblivious robots can solve ${\mathrm{𝚄𝙿𝙵}}^{\ast }$ without any additional assumption; $ii)$ Gathering and, hence, UPF can be solved with the only addition of weak multiplicity detection. Since it is known from the literature that Gathering is solvable under $ℱ𝒮𝒴𝒩𝒞$ but not under $𝒮𝒮𝒴𝒩𝒞$, then it follows that the sets of problems solvable in $𝒮𝒬$ and $ℱ𝒮𝒴𝒩𝒞$ are orthogonal, whereas the computational power of the robots under $𝒮𝒬$ is stronger than under $𝒮𝒮𝒴𝒩𝒞$; see Figure 1.

The Dancing problem has been introduced in [9], and it requires the robots to form a given ordered sequence of patterns (choreography). For an example of a choreography, see Figure 2. Note that transitioning from one pattern to the next requires forming intermediate patters that still allow to determine the next pattern to be formed in the choreography. This is especially challenging for oblivious robots, and remains quite complicated even for robots equipped with lights, as these offer only constant memory.

In $𝒪$BLOT, the possibility to perform a choreography is subject to several constraints: on the patterns (they must all be distinct, have the same number of points, and share the same degree of symmetry); on the number of robots (it must match the number of points in the patterns); on the initial configuration (the robots must start from distinct locations and their positions must have the same symmetricity as the patterns); and on the structure of the choreography (the sequence must be periodic). Under these necessary constraints, an algorithm was presented that allows $𝒪$BLOT robots to carry out a choreography under $𝒮𝒮𝒴𝒩𝒞$, using a distinctive technique based on the relative distances among selected robots to collectively encode the “index” of the next pattern to be formed; this algorithm assumes chirality agreement and rigid movements [9].

The impact of $ℒ$UMI’s limited memory and communication capabilities on the feasibility of Dancing was studied in [7], where it was shown that, assuming chirality, the set of feasible sequences is subject to fewer restrictions, even with non-rigid movements. In particular, given a sufficient number of colors, a swarm can perform a periodic choreography that includes repeated patterns as well as contractions and expansions, starting from any configuration where robots occupy distinct locations and under weaker symmetry requirements on the patterns and the initial configuration. Interestingly, this results hold even under asynchronous schedulers (where no notion of synchronized round exists).

The results of [7, 9] reveal a fundamental insight when moving from Pattern Formation to Dancing. Let $X^S$ indicate a model $X\in \{$$𝒪$BLOT, $ℒ$UMI$\}$ under scheduler $S$, and let $𝒫(X^S)$ be the set of patterns formable under $X^S$. Given a set $P\subseteq 𝒫(X^S)$, a periodic sequence of patterns chosen from $P$ is not necessarily a feasible choreography under $X^S$. In other words, a collection of feasible patterns does not necessarily yield a feasible sequence.

The most general Dancing problem is Universal Dancing, requiring the robots to form any sequence of arbitrary patterns, independently of any property (e.g., symmetry, size, shape, etc.) of the patterns or of the initial configuration, whether the sequence is periodic or not.

The power of sequential schedulers with respect to Dancing in $ℒ$UMI has been recently established in [10], where it has been shown that Universal Dancing is indeed solvable under $𝒮𝒬$, even without rigid movement nor agreement on a common chirality. The universal dancing algorithm of [10] is based, among other techniques, on the possibility of implementing a distributed colored counter, which allows the robots to keep track of the current pattern being formed in the choreography.

In conclusion, when considering pattern formation problems, sequential schedulers do not simply provide robots with means to break the symmetry. By enabling forms of implicit coordination unavailable in other synchronous settings, sequential schedulers allow the creation of new algorithmic tools that can be exploited especially to remove assumptions that are inherent when the robots operate under the other classical schedulers. The research is ongoing to study the impact of sequential schedulers on the solution of other classes of problems.