Mobility Matters
Home›Mobile robots in the plane›Formation problems›Pattern formation›Pattern sequences

Pattern sequences

Robots must form a given sequence of patterns, one after the other, forever.

Problem statement and measuresexpand

Robots are given a sequence of patterns \(P_1, P_2, \dots, P_m\) (sets of points in the plane) and must form them in order, repeatedly, with all robots taking part in each.

Measures: Time, rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known; Colours, colours of the light per robot (0 for oblivious robots).

no assumptions›+ point, + unlimited visibility, + transparent, + no faults›ASYNC, + lights (LUMI), + chirality

Luminous robots, ASYNC, non-rigid, chirality

verified
Time: unknownColours: polynomial gap

With lights and common chirality, the formable pattern sequences are characterised under ASYNC and non-rigid moves; the number of colours grows with the sequence and is not known to be optimal.

Assumed (added on the last edge are outlined)

+Bodypoint robots+Visibilityunlimited+Opacitytransparent: every robot sees every robot within range+Faultsno faults+Lights (persistent memory)full light (LUMI): every robot sees all lights, including its own+Agreement on coordinatescommon chirality (same clockwise orientation)

Not assumed

Schedulerasynchronous (ASYNC)Movementnon-rigid: the adversary may stop a move after some minimum distance \(\delta\)Multiplicity detectionnone: a point with several robots looks like one robotRandomnessdeterministicIdentifiersanonymous: all robots are identical
Formal definitions of this setting
Body: point
Each robot is a point of the plane: several robots may share a point (multiplicity), and a robot hides only what lies exactly behind it on a line of sight.
Visibility: unlimited visibility
A robot sees all robots (subject to opacity).
Opacity: transparent
Robots do not obstruct each other's view.
Faults: no faults
All robots follow the algorithm forever.
Scheduler: ASYNC
ASYNC: each robot's Look, Compute and Move phases take finite but unbounded, adversarially chosen time; a robot may look while others move, and compute on an outdated snapshot. Time is counted in epochs: an epoch is an interval of time in which every robot completes at least one full Look–Compute–Move cycle; it need not be the shortest such interval. The execution is divided into consecutive epochs, and a bound of \(X\) epochs holds for every such division. In FSYNC and SSYNC time is counted in rounds. Called Corda by Prencipe Prencipe 2007. Intermediate variants restrict interleavings: LC-atomic (no Look by another robot between a robot's Look and its Compute), Move-atomic (no Look during another robot's Move) and CM-atomic Flocchini et al. 2023.
Lights (persistent memory): lights (LUMI)
LUMI: each robot has a light with \(c\) colours, set at the end of Compute, visible to all robots including itself; it is both memory and communication. Also called luminous robots, or a full light.
Agreement on coordinates: chirality
All local coordinate systems have the same handedness (clockwise orientation): no reflection. Also called handedness. Prencipe uses chirality for agreement on North and East, i.e. a compass Prencipe 2007.
Movement: non-rigid
In a Move phase the adversary may stop a robot before its destination, but only after it has travelled at least \(\delta>0\) (a constant unknown to the robots) or reached the destination.
Multiplicity detection: no multiplicity detection
A snapshot is a set of points: a point occupied by several robots looks like a single robot.
Randomness: deterministic
The destination computed in a cycle is a function of the snapshot (and the light, if any).
Identifiers: anonymous
Robots are indistinguishable and run the same algorithm.

What is known

Time · rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known
unknown
Only solvability.
lower bound
\(\text{impossible}\) Das et al. 2020
bottlenecksymmetry breaking
holds when
  • Theorem 2: sequences that violate the paper's symmetry conditions
introductory—
current best
\(\text{finite}\)
weak chromatic multiplicity detection
Colours · colours of the light per robot (0 for oblivious robots)
polynomial gap
\(\alpha(S)+\mu(S)+O(1)\) against the Theorem 18 bound; closing it is called an important open question.
lower bound
\(\max\{\alpha(S)/\min_i\alpha(S_i),\ \mu(S)^{1/\alpha(S)}\}\) Das et al. 2020
bottleneckmemory
holds when
  • Theorem 18
  • holds even in FSYNC with rigid moves
introductory—
current best
\(\alpha(S)+\mu(S)+O(1)\)
weak chromatic multiplicity detection

Results, in order of publication

Das et al. 2020 current best
Time \(\text{finite}\)Colours \(\alpha(S)+\mu(S)+O(1)\)
weak chromatic multiplicity detection

Introductory and current best: a universal protocol for every formable sequence (Theorem 17). The number of colours is "bounded but not by a constant".

Open questions

  1. Close the gap between the colours used and the lower bound of Theorem 18 Das et al. 2020.

  2. Pattern sequences with lights without chirality, with faults, or self-stabilising Das et al. 2020.

Notes

\(\alpha(S)\) and \(\mu(S)\) are parameters of the sequence \(S=\langle S_1,\dots\rangle\) defined in Das et al. 2020 (equation 1 and Theorem 18). Checked against the full text (HAL copy of the IEEE Access version).

Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.