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

Pattern formation

Robots start at distinct points and must form a given geometric pattern, up to similarity; which patterns are formable, and from which initial configurations?

Problem statement and measurescollapse
pattern Ppattern Ppattern Ppattern Ppattern Ppattern PLLStart: SEC = unit circle; leader L fixes eastOne robot at a time walks to its target pointFinal: the robots form a copy of P
Pattern formation: \(n\) oblivious robots at distinct points are given the same pattern \(P\) in their local coordinate systems and must reach a configuration similar to \(P\), up to translation, rotation and scaling Suzuki & Yamashita 1999. Shown, with chirality, the plan of Dieudonné et al. 2010 in SSYNC rounds: the smallest enclosing circle (dashed) gives the origin and unit, the ray to the leader \(L\) (the robot nearest the centre) gives east; \(P\) is placed accordingly (hollow points: the target points), and ringed (activated) robots walk to their target points one at a time without changing the circle or the leader; \(L\) moves last.

\(n\) robots start at distinct points of the plane. Each is given the same pattern \(P\), a set (or multiset) of \(n\) points in its own local coordinate system. The robots must reach a configuration similar to \(P\) (equal up to translation, rotation, uniform scaling and, without chirality (a common clockwise direction), reflection) and stay there. The question is for which pairs (initial configuration, pattern) this is possible under the given assumptions, and at what cost in time and colours.

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 drones at a light show that must arrange themselves into a picture, say a star, with no director and no radio. There are \(n\) robots, tiny points at different places in the plane; the positions of all robots at one instant form a 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). The robots are identical, silent and oblivious (they forget everything at the end of each cycle), and each one sees the world in its own local coordinate system, with its own origin, unit of length and directions. An adversary called the scheduler decides the activation of each robot, that is, when it performs a cycle; in the standard version (ASYNC) every phase may take any finite time, so a robot may look while others are still moving. All robots receive the same pattern \(P\), a list of \(n\) points, and must end in a configuration equal to \(P\) up to shifting, turning, resizing and mirroring, and then stop; the question is from which initial configurations this is possible.

1AlgorithmElect a leader, then build a shared coordinate system from the smallest enclosing circle ASYNC with common chirality → Dieudonné et al. 2010
  1. Every robot computes the smallest enclosing circle (SEC): the smallest circle that contains all robots. It is the same circle for everyone, whatever their local coordinate systems.
  2. The centre of the SEC becomes the common origin and its radius the common unit of length.
  3. The robots elect a leader, a robot whose position in the configuration looks different from every other robot's (for example the only robot closest to the centre). The ray from the centre through the leader becomes the common "east"; because all robots agree on what clockwise means (chirality), this also fixes a common "north".
  4. Now all robots use the shared coordinate system, so they all place the pattern \(P\) in the same spot (scaled to the circle) and compute the same assignment of robots to points of \(P\); the point assigned to a robot is its target point.
  5. The robots move to their target points in a careful order that never changes the SEC and never lets another robot take over the leader's special position, so the shared coordinate system survives every move.
Why it works and what it costs. Once everyone agrees on coordinates, the task is just "walk to your target point"; the difficulty is step 5, because an oblivious robot recomputes everything in every cycle, and one careless move (a robot on the circle stepping inwards, say) can change the circle or the leader and with them every robot's target point. Dieudonné, Petit and Villain used this plan to show that, with chirality, pattern formation is solvable exactly when leader election is, for \(n \ge 4\) robots in ASYNC Dieudonné et al. 2010. The catalogue's current best drops chirality: arbitrary pattern formation is solvable exactly when a leader can be elected Cicerone et al. 2019. Running time is not analysed in these papers.

Why it matters. It turned a geometric problem into a symmetry-breaking problem: forming any pattern is as hard as choosing one leader.

2ImpossibilityA symmetric initial configuration that the scheduler keeps symmetric forever ASYNC, no agreement on coordinates → Suzuki & Yamashita 1999

Place \(n = 4\) robots on the corners of a square and ask for a pattern that does not look the same after a quarter turn, for example four points on a line. The adversary gives each robot a local coordinate system with its origin at the robot, the \(x\)-axis pointing to the centre of the square, and the same unit; the four systems are then copies of each other turned by \(90^\circ\). Every robot now gets exactly the same snapshot. The scheduler activates all four together. Identical robots with identical snapshots choose the same move in their own local coordinate systems, which in the real plane is the same move turned by \(90^\circ\). So after these cycles the robots again form a square (or all stand at its centre), and the scheduler repeats this forever. The line is never formed.

Why it holds. The same argument works for any initial configuration that looks the same after some rotation: whatever the algorithm, the robots can only form patterns that keep at least that much symmetry. Suzuki and Yamashita measured this with the symmetricity of a configuration Suzuki & Yamashita 1999. The scheduler only needs to activate every robot at once, so the obstacle holds in the fully synchronous model (FSYNC) and therefore under every less synchronous scheduler. Hence, without any agreement between local coordinate systems, an arbitrary pattern cannot be formed from every initial configuration Flocchini et al. 2008; from a regular \(n\)-gon only a point and the regular \(n\)-gon itself can be formed Flocchini et al. 2017.

Why it matters. It explains why every pattern-formation result is about breaking symmetry, and why leader election keeps appearing.

3AlgorithmWith a common compass nobody is symmetric ASYNC with a common compass → Flocchini et al. 2008

Suppose all robots agree on north and east (a common compass), though not on origin or unit.

  1. Each robot sorts all robots from west to east, and robots on the same north-south line from south to north. Since all robots agree on north and east, they all obtain the same order, even though their origins and units differ.
  2. Each robot sorts the points of the pattern \(P\) in the same way and matches the \(i\)-th robot with the \(i\)-th point of \(P\), its target point, (after placing and scaling \(P\) by a rule everyone computes alike).
  3. The robots move in an order chosen so that the order of step 1, and hence the assignment of target points, does not change while they move.
Why it works and what it costs. A common compass removes the adversary's trick: no rotation or mirror image can map a set of points to itself while keeping north and east fixed, so every configuration has a first robot that all robots recognise. Flocchini, Prencipe, Santoro and Widmayer showed that with a common compass any number of robots form any pattern in ASYNC, and that agreement on one axis suffices for an odd number of robots Flocchini et al. 2008. The steps above are a simplified sketch that was not checked against that paper's full text; the fact that a compass gives all robots the same order is Lemma 2.1 of Efrima & Peleg 2009.

Why it matters. It shows that symmetry, not obliviousness or asynchrony, is the real obstacle to forming patterns.

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
ASYNC, no agreement on coordinates standard
Without any common orientation, an arbitrary pattern can be formed exactly from the configurations in which a leader can be elected.
unknown \(\text{finite}\) vs \(\text{impossible}\) symmetry
tight \(0\) vs —
ASYNC with common chirality
With common chirality, pattern formation and leader election are equivalent for \(n \ge 4\).
unknown \(\text{finite}\) vs —
tight \(0\) vs —
ASYNC with one common axis
With a common North and chirality, any odd number of robots forms any pattern; an even number cannot, in the worst case.
unknown \(\text{finite}\) vs \(\text{impossible}\) symmetry
tight \(0\) vs —
ASYNC with a common compass
If robots agree on both axes, any number of robots forms any pattern.
unknown \(\text{finite}\) vs —
tight \(0\) vs —
Randomized, ASYNC, no agreement
Randomness breaks symmetry: with one random bit per cycle, \(n \ge 5\) robots form any pattern except gathering.
unknown — vs —
tight — vs —
Opaque robots with lights, ASYNC, one axis, rigid
Opaque point robots with lights that agree on one axis form any pattern from the starts the paper characterises, with 6 colours.
unknown \(\text{finite}\) vs —
unknown \(6\) vs —
Opaque robots with lights, ASYNC, compass, rigid
With a common compass, opaque robots with lights form any pattern with 3 colours.
unknown \(\text{finite}\) vs —
unknown \(3\) vs —
Opaque oblivious robots, ASYNC, compass
Without lights, opaque robots cannot form arbitrary patterns in ASYNC, even with a common compass.
impossible — vs \(\text{impossible}\) obstruction
impossible — vs —
Limited visibility
With limited visibility, oblivious robots form a pattern under the usual symmetry condition if they start within diameter 1; the general case is open.
unknown \(\text{finite}\) vs —
tight \(0\) vs —
Opaque fat robots with lights, ASYNC, one axis
Opaque fat robots with lights that agree on one axis form any pattern from every start not symmetric about a robot-free line parallel to that axis, with 10 colours.
unknown \(\text{finite}\) vs —
unknown \(10\) vs —
Fat robots with lights, FSYNC, randomized, no agreement
Randomized fat robots with lights and no common orientation form any pattern in FSYNC in \(O(n)+O(\kappa\log n)\) rounds with probability at least \(1-n^{-\kappa}\), with 7 colours.
unknown \(O(n)+O(\kappa\log n)\) vs —
unknown \(7\) vs —

Open questions 3

ASYNC, no agreement on coordinates

  1. Bound the number of epochs needed by an arbitrary pattern formation algorithm in ASYNC; no time analysis is recorded.

Opaque robots with lights, ASYNC, one axis, rigid

  1. The minimum number of colours, and formation with chirality only or with no agreement Bose et al. 2021.

Limited visibility

  1. Arbitrary pattern formation by oblivious robots with limited visibility from a general (connected) initial configuration Hahn et al. 2024.

What the community started looking at

The founding question was which patterns robots can form at all Suzuki & Yamashita 1999: Suzuki and Yamashita characterised formable patterns by the symmetry of the starting configuration, for SSYNC robots with unbounded memory and common handedness: only a point and a regular \(n\)-gon can be formed from every starting configuration. Flocchini, Prencipe, Santoro and Widmayer then asked the question that shaped the field, how much agreement is needed: none is not enough, one axis is enough for an odd number of robots, two axes for all Flocchini et al. 1999 Flocchini et al. 2008. The aim has been to remove assumptions one at a time (chirality, synchrony, rigidity), ending in the equivalence with leader election without chirality Cicerone et al. 2019.

Derived problems

Circle formation: A circle is a family of patterns; forming some circle is easier than forming a given pattern, and it is the precursor of uniform circle formation Feletti et al. 2024.

Uniform circle formation: Uniform circle formation is "an important special case of the geometric pattern formation problem" Feletti et al. 2024: the target is the regular \(n\)-gon. It is also the special case of circle formation with equal spacing; circle formation is "its precursor" Feletti et al. 2024.

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

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

Mutual visibility: Mutual visibility asks for any pattern in general position, a family of patterns; it is the usual first step of pattern formation for opaque robots.

k-grouping: When the groups sit at points, \(k\)-grouping forms a pattern of \(k\) points; which points, and how many robots each holds, is up to the robots. Gathering is its special case \(k = 1\). Splitting needs symmetry breaking Efrima & Peleg 2009.

Partitioning: A partition into \(k\) groups at points is a pattern of \(k\) points, each of multiplicity \(n/k\).

Related problems

Leader election in the plane: Arbitrary pattern formation is solvable from a configuration exactly when leader election is, in ASYNC without chirality Cicerone et al. 2019; with chirality and \(n \ge 4\) this was shown by Dieudonné et al. 2010.

Shape formation in programmable matter: "Shape formation is a basic distributed problem for systems of computational mobile entities. Intensively studied for systems of autonomous mobile robots, it has recently been investigated in the realm of programmable matter" Di Luna et al. 2020.

Perspectives

  • Why compute by moving The atlas collects four models that grew out of four different wishes: software that travels through a network, swarms of robots that are as weak as possible, searchers that must find something at an unknown place, and matter that reshapes itself. They share an adversary, locality and symmetry; they differ in what they count.
  • 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.
  • From robots to particles Programmable matter re-asks the questions of robots in the plane on a lattice, with particles that touch, remember a little and stay connected; SILBOT takes memory and messages away again, and the stochastic approach replaces algorithms by a biased local rule.
  • The most consequential open problems Ten open questions ranked by how far a solution would propagate through the atlas, with the chain of problems each one feeds.

All settings

The assumption tree (11 settings, 6 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.