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 measurescollapse
Start: lights show step 1 (square)P1: square formedP2: line formedP3: square formed again, other colourP4: kite formedLights change to step 1: the cycle repeats
Pattern sequences: robots must form the patterns \(P_1, P_2, \dots, P_m\) one after another, all robots taking part in each, and repeat the sequence forever Das et al. 2015. Shown in FSYNC rounds: the sequence square, line, square, kite, which oblivious robots cannot form because the two squares look alike; with lights, the colour records the step, so the second square differs from the first by its colour.

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).

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Picture a marching band that must form a sequence of shapes, for instance a square, then a line, then a triangle, then the square again, over and over. There are \(n\) robots, points in the plane; their positions form the configuration. Each robot repeats a Look–Compute–Move cycle: it takes a snapshot of where the other robots are (Look), decides on a destination point (Compute) and moves towards it (Move). In the basic version they are oblivious (no memory between cycles), agree on what clockwise means (chirality) but on nothing else, every move is a rigid move (it always reaches the computed destination), and the scheduler, an adversary, is SSYNC: time runs in rounds, and in each round it decides the activation of some of the robots, each of which performs one cycle. Given patterns \(P_1, P_2, \dots, P_m\) (\(m\) is the number of patterns; a pattern is a set of points, formed when the configuration has its shape), the robots must form \(P_1\), then \(P_2\), and so on up to \(P_m\), then \(P_1\) again, forever, with every robot taking part in each pattern.

1ImpossibilityOblivious robots cannot repeat a pattern Oblivious, SSYNC, chirality → Das et al. 2015

Take \(n = 4\) and the sequence square, line, square, kite. When the robots stand in the square they must decide where to go next: to the line (if this is the first square) or to the kite (if it is the second). But oblivious robots use only the current snapshot, and the two squares look exactly alike to robots that see only shapes, not sizes or directions. With the same snapshot a robot computes the same destination, so it cannot follow both continuations. A second obstacle is symmetry: robots can form a pattern only if it has at least the symmetry of the configuration they start from. In a cycle \(P_1 \to P_2 \to \dots \to P_m \to P_1\) each pattern must have at least the symmetry of the one before, and going round the cycle this forces all of them to have the same symmetry.

Why it holds. Das, Flocchini, Santoro and Yamashita characterised the sequences formable by oblivious robots under these assumptions Das et al. 2015: as summarised in Das et al. 2020, all patterns must have the same number of points and no pattern may appear twice, and the catalogue records that the patterns must have equal symmetricity (the largest \(q\) such that the points split into regular \(q\)-gons centred at the centre of their smallest enclosing circle, a point at that centre counting as a \(1\)-gon Das et al. 2020), a multiple of that of the initial configuration. With distinct identifiers, any sequence of patterns of size at most \(n\) can be formed.

Why it matters. It isolates what memory buys: forming one pattern needs none, but following a script needs a way to know where you are in it.

2AlgorithmKeep your place in the sequence with a coloured light Luminous robots, ASYNC, non-rigid, chirality → Das et al. 2020

Give each robot a light: a lamp that shows one of \(c\) colours, set by its robot, visible to all robots and kept between cycles.

  1. Use the colours shown by the robots to record which step of the sequence is being formed.
  2. Form the current pattern with a single-pattern algorithm.
  3. When the pattern is complete, the robots change their colours to record the next step, and start forming the next pattern.
  4. A repeated pattern is no longer a problem: the positions are the same, but the colours differ.
Why it works and what it costs. Lights act as a small shared memory, so repetitions, and even patterns with fewer points than robots, become possible. Das, Flocchini, Prencipe and Santoro give one protocol that forms every formable sequence, in ASYNC and with non-rigid moves Das et al. 2020. The number of colours is bounded but not by a constant: it must grow with the number of repetitions and contractions in the sequence, by a lower bound that holds even for fully synchronous robots with rigid moves (Theorem 18 of Das et al. 2020). The steps above are the basic idea, not the paper's protocol, which must also cope with robots acting on outdated snapshots and with symmetric initial configurations.

Why it matters. It measures, in colours, exactly how much memory a choreography needs.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Colours
Oblivious, SSYNC, chirality standard
A cyclic sequence of patterns is formable exactly when all patterns have the same symmetricity, a multiple of the start's.
unknown \(\text{finite}\) vs —
tight \(0\) vs —
Luminous robots, ASYNC, non-rigid, chirality
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.
unknown \(\text{finite}\) vs \(\text{impossible}\) symmetry breaking
polynomial gap \(\alpha(S)+\mu(S)+O(1)\) vs \(\max\{\alpha(S)/\min_i\alpha(S_i),\ \mu(S)^{1/\alpha(S)}\}\) memory
Luminous robots, sequential scheduler (universal dancing)
Under a sequential scheduler, disoriented luminous robots form every sequence of patterns up to a length fixed by the number of colours.
unknown \(\text{finite}\) vs —
near-optimal \(c \ge 4\) vs \(\text{with } c \text{ colours, length} \le \tbinom{n+c-1}{c-1}\) memory

Open questions 3

Oblivious, SSYNC, chirality

  1. Form a sequence of patterns in ASYNC with oblivious robots Das et al. 2015.

Luminous robots, ASYNC, non-rigid, chirality

  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.

What the community started looking at

Forming a sequence of patterns asked how much memory the configuration itself can hold for oblivious robots: the answer is a symmetricity condition Das et al. 2015; lights remove the restriction and work asynchronously Das et al. 2020.

Generalisation of Pattern formation

Forming one pattern is the case \(m = 1\); a sequence needs the robots to remember (or encode in the configuration) which pattern comes next.

Perspectives

  • Weak robots in the plane Why the theory of robots in the plane starts from oblivious, anonymous, disoriented points; how formation problems became its testbed and the scheduler its adversary; and how a light with a few colours turned into memory, communication and a measure.

All settings

The assumption tree (3 settings, 2 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Colours); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Body › Visibility › Opacity › Faults › Scheduler › Lights (persistent memory) › Agreement on coordinates › Movement › Multiplicity detection › Randomness › Identifiers.

tight near-optimal polynomial gap unknown impossible no variant

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