Home›Mobile robots in the plane›Formation problems›Pattern formation›Uniform circle formation

Uniform circle formation

Robots must form a regular \(n\)-gon: a circle with equal spacing.

Problem statement and measuresexpand

\(n\) robots start at distinct points and must reach the vertices of a regular \(n\)-gon (in any position and size) and stay there. Time is in epochs (ASYNC: intervals in which every robot completes at least one full Look–Compute–Move cycle) or rounds; colours count light colours in the luminous model.

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

—

Opacity + point, + unlimited visibility

—

ASYNC, oblivious, disoriented + transparent, + no faults

1 open · 2 results

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

tight \(0\) vs —

SSYNC, oblivious + SSYNC

0 open · 1 results

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

tight \(0\) vs —

Scheduler opaque, + no faults

—

Opaque robots with lights, ASYNC ASYNC, + lights (LUMI), + rigid

2 open · 4 results

tight \(O(1)\) vs \(\Omega(1)\) trivial

Opaque robots with lights, FSYNC + FSYNC, + lights (LUMI), + rigid

0 open · 2 results

tight \(3\) vs —

tight \(O(1)\) vs —

Transparent fat robots, SSYNC fat, + unlimited visibility, + transparent, + no faults, + SSYNC, + one axis, + rigid

0 open · 1 results

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

tight \(0\) vs —

Opaque fat robots, ASYNC, limited visibility, compass fat, limited visibility, opaque, + no faults, + compass, + rigid

0 open · 1 results

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

tight \(0\) vs —

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