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

Progress map

tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound

Setting

Time

Colours

No assumptions

—

Visibility + point

—

Opacity + unlimited visibility

—

ASYNC, no agreement on coordinates + transparent, + no faults

1 open · 2 results

unknown \(\text{finite}\) vs \(\text{impossible}\) symmetry

tight \(0\) vs —

ASYNC with common chirality + chirality

0 open · 2 results

unknown \(\text{finite}\) vs —

tight \(0\) vs —

ASYNC with one common axis + one axis

0 open · 1 results

unknown \(\text{finite}\) vs \(\text{impossible}\) symmetry

tight \(0\) vs —

ASYNC with a common compass + compass

0 open · 1 results

unknown \(\text{finite}\) vs —

tight \(0\) vs —

Randomized, ASYNC, no agreement disoriented, + randomized

0 open · 1 results

unknown — vs —

tight — vs —

Lights (persistent memory) opaque, + no faults

—

Agreement on coordinates + lights (LUMI)

—

Opaque robots with lights, ASYNC, one axis, rigid + one axis, + rigid

1 open · 1 results

unknown \(\text{finite}\) vs —

unknown \(6\) vs —

Opaque robots with lights, ASYNC, compass, rigid + compass, + rigid

0 open · 1 results

unknown \(\text{finite}\) vs —

unknown \(3\) vs —

Opaque oblivious robots, ASYNC, compass oblivious, + compass

0 open · 0 results

impossible — vs \(\text{impossible}\) obstruction

impossible — vs —

Limited visibility limited visibility, + transparent, + no faults

1 open · 1 results

unknown \(\text{finite}\) vs —

tight \(0\) vs —

Scheduler fat, + unlimited visibility, + no faults

—

Opaque fat robots with lights, ASYNC, one axis ASYNC, + lights (LUMI), + one axis

0 open · 1 results

unknown \(\text{finite}\) vs —

unknown \(10\) vs —

Fat robots with lights, FSYNC, randomized, no agreement + FSYNC, + lights (LUMI), + rigid, + randomized

0 open · 1 results

unknown \(O(n)+O(\kappa\log n)\) vs —

unknown \(7\) vs —

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