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 measuresexpand
\(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).
ASYNC, no agreement on coordinates
standard settingverifiedWithout any common orientation, an arbitrary pattern can be formed exactly from the configurations in which a leader can be elected.
Assumed (added on the last edge are outlined)
Not assumed
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): oblivious
- OBLOT: a robot's computation depends only on the current snapshot; nothing persists across cycles.
- Agreement on coordinates: disoriented
- Each robot \(r\) observes in its own coordinate system, obtained from the global one by an unknown similarity (translation, rotation, uniform scaling, and possibly reflection); systems may differ between robots and, in some models, between cycles. Papers that call robots disoriented do not always mean this: Défago and Souissi use the word while assuming chirality Défago & Souissi 2008. Some papers also let the adversary change a robot's rotation, reflection and unit at every Look (variable disorientation) Flocchini et al. 2023 Masuzawa et al. 2026.
- 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
- for some initial configurations: symmetric configurations cannot be broken by oblivious deterministic robots
- holds in every scheduler
Results, in order of publication
Introduces arbitrary pattern formation for asynchronous oblivious robots and shows that with no common agreement an arbitrary pattern cannot be formed in general.
Characterisation: arbitrary pattern formation is solvable exactly when leader election is, in ASYNC without chirality. The paper also states that earlier proofs (Fujinaga et al. 2015, Bramas & Tixeuil 2016, the arXiv version of Dieudonné et al. 2010) are not correct.
Open questions
Bound the number of epochs needed by an arbitrary pattern formation algorithm in ASYNC; no time analysis is recorded.
Notes
Patterns are formed up to translation, rotation, scaling and reflection, starting from distinct positions. The four-robot case needed a separate geometric invariant Bramas & Tixeuil 2018. The point (gathering) and the regular polygon (uniform circle) are the only patterns formable from every initial configuration Flocchini et al. 2017.
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
Lower bounds from stronger settings hold here
Branches from here
ASYNC with common chirality
ASYNC with one common axis
ASYNC with a common compass
Randomized, ASYNC, no agreement
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.