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

Universal pattern formation

Robots must be able to form any pattern from any initial configuration, not only the ones symmetry allows.

Problem statement and measurescollapse
222222Start: 6 robots on 4 points; pattern has 5Now 5 points: fill the pattern, one robot a roundFinal: the pattern, with its multiplicity
Universal pattern formation: from every configuration of \(n\) robots, possibly with several robots on one point (a multiplicity), the robots must be able to form every given pattern of \(n\) points, including patterns with multiplicities Flocchini et al. 2026. Shown, simplified, the plan of Flocchini et al. 2026 under the sequential scheduler (one ringed robot is activated per round): a robot leaves a multiplicity until the robots occupy as many points as the pattern (hollow), then the points of the pattern are filled one by one; the last robot creates the pattern's multiplicity.

From every initial configuration of \(n\) robots (several robots may start on the same point, forming a multiplicity Flocchini et al. 2026), the robots must form every given pattern of \(n\) points (a multiset of points given to every robot; multiplicities allowed). With lights, universal dancing asks for any sequence of patterns.

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

Imagine a troupe that must be able to form every shape the director might ask for, from wherever its members happen to stand, even if some of them are standing on top of each other. There are \(n\) robots, points in the plane; their positions form the configuration, and a point that holds two or more robots is a multiplicity. 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). They are identical, silent and oblivious (no memory between cycles), and each uses its own local coordinate system, so they agree on no direction. The scheduler, an adversary, decides the activation of robots, that is, when each performs a cycle; here it is sequential: time runs in rounds, in each round it activates exactly one robot, and every robot is activated again and again. Universal pattern formation asks for one algorithm that, from every initial configuration, forms every given pattern of \(n\) points (a list of points that every robot is given, to be matched up to position, rotation and size; it may contain multiplicities) and then stops.

1AlgorithmOne robot at a time: create enough occupied points, agree on a map, fill it in Sequential schedulers → Flocchini et al. 2026
  1. Initialization. If the robots occupy fewer distinct points than the pattern has, robots leave multiplicities one at a time until there are enough occupied points.
  2. Scale the pattern so that its smallest enclosing circle (the smallest circle containing all its points) matches the smallest enclosing circle of the configuration.
  3. Leader configuration. Move robots so that all of them agree on how the pattern is laid over the robots' positions (a common map from robots to pattern points).
  4. Partial formation. Fill the empty points of the pattern one by one in an agreed order, moving along detours that never pass over another robot.
  5. Finalization. When only one robot is off the pattern, the last robots move to their places.
Why it works and what it costs. Under a sequential scheduler only one robot moves at a time, so the moving robot is automatically different from all others; in particular, a multiplicity can be split, since only one of its robots moves. Flocchini, Navarra, Pattanayak, Piselli and Santoro show that this gives oblivious robots universal pattern formation with no extra assumption, except for the single point (gathering), which needs weak multiplicity detection (a robot sees whether a point holds more than one robot), necessary and sufficient Flocchini et al. 2026. The steps above are their high-level plan; the actual algorithm handles many special cases, and patterns with fewer than 5 points separately. Time is not analysed.

Why it matters. It shows that sequential activation is more than a way to elect a leader: it gives power that even a leader with full synchrony does not have.

2ImpossibilityFully synchronous robots cannot split a multiplicity Sequential schedulers → Flocchini et al. 2026

Take three robots: two on one point, the third alone elsewhere. Under FSYNC every robot is activated in every round. The two robots on the multiplicity get the same snapshot; even if they have identical local coordinate systems, move rigidly, can count robots on each point, and the third robot is a recognisable leader, the two compute the same destination and move together. They stay on one point forever, so no pattern with three distinct points is ever formed.

Why it holds. This is Theorem 1 of Flocchini et al. 2026: universal pattern formation is unsolvable under FSYNC for \(n \ge 3\), even with all these extra capabilities, and hence also under SSYNC and ASYNC, where the scheduler may choose to activate every robot. Gathering alone, in contrast, is solvable under FSYNC with no extra capability.

Why it matters. It shows that the fully synchronous and the sequential schedulers are incomparable: each solves something the other cannot.

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
Sequential schedulers standard
Under any sequential scheduler, oblivious robots can form every pattern from every starting configuration, except a single point, which needs weak multiplicity detection.
unknown \(\text{finite}\) vs \(\text{impossible}\) symmetry
tight \(0\) vs —

What the community started looking at

Universal pattern formation asked whether a scheduler alone can break the symmetry that blocks pattern formation: under sequential schedulers it can, except for a single point Flocchini et al. 2026; with lights, robots can then perform any sequence of patterns Feletti et al. 2026.

Strengthening of Pattern formation

Pattern formation asks which patterns are formable from a given start; universal pattern formation asks for all patterns from all starts, which symmetry forbids under SSYNC and FSYNC but sequential schedulers allow Flocchini et al. 2026.

Perspectives

  • Symmetry is the adversary Identical agents running the same deterministic program can be kept in lockstep forever. Across graphs, the plane and programmable matter, the papers break this symmetry with identifiers, with randomness, with asymmetric starts, or with the scheduler, and leader election keeps reappearing as the common core.
  • 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 (1 settings, 1 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.