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›+ SSYNC, + chirality, + rigid

Oblivious, SSYNC, chirality

standard settingverified
Time: unknownColours: tight

A cyclic sequence of patterns is formable exactly when all patterns have the same symmetricity, a multiple of the start's.

Assumed (added on the last edge are outlined)

+Bodypoint robots+Visibilityunlimited+Opacitytransparent: every robot sees every robot within range+Faultsno faults+Schedulersemi-synchronous (SSYNC)+Agreement on coordinatescommon chirality (same clockwise orientation)+Movementrigid: every move reaches its destination

Not assumed

Lights (persistent memory)oblivious, no light (OBLOT)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: SSYNC
SSYNC: time is divided into rounds; in each round a non-empty subset of robots, chosen by a fair adversary, executes one atomic Look–Compute–Move cycle. Called Atom by Prencipe Prencipe 2007.
Lights (persistent memory): oblivious
OBLOT: a robot's computation depends only on the current snapshot; nothing persists across cycles.
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: rigid
Every Move phase ends at the computed 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
—
lower boundnone known
introductory—
current best
\(\text{finite}\)
Colours · colours of the light per robot (0 for oblivious robots)
tight
No colours.
lower boundnone known
introductory—
current best
\(0\)

Results, in order of publication

Das et al. 2015 current best
Time \(\text{finite}\)Colours \(0\)

Introductory and current best; with distinct identifiers, any sequence of patterns of size at most \(n\).

Open questions

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

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