Home›Mobile robots in the plane›Formation problems›Pattern formation›k-grouping›Gathering

Gathering

Robots must meet at a single point that is not fixed in advance, and stay there.

Problem statement and measuresexpand

\(n\) robots start at distinct points and must all reach the same point in finite time and remain there. For \(n = 2\) the problem is called rendezvous. Time is counted in rounds (FSYNC, SSYNC) or in epochs (ASYNC: intervals in which every robot completes at least one full Look–Compute–Move cycle); colours count light 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

—

Faults + unlimited visibility, + transparent

—

Scheduler + no faults

—

Lights (persistent memory) + SSYNC

—

Agreement on coordinates + internal light (FSTA)

—

Rendezvous, internal light (FSTA), SSYNC, non-rigid disoriented, non-rigid, + \(n = 2\)

1 open · 1 results

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

tight \(3\) vs \(3\) memory

Rendezvous, internal light (FSTA), SSYNC, rigid disoriented, + rigid, + \(n = 2\)

0 open · 2 results

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

tight \(3\) vs \(3\) memory

Gathering, internal light (FSTA), SSYNC, non-rigid + chirality, + \(n \ge 3\)

1 open · 2 results

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

unknown \(2\) vs \(3\) memory

Agreement on coordinates + external light (FCOM)

—

Rendezvous, external light (FCOM), SSYNC disoriented, non-rigid, + \(n = 2\)

0 open · 1 results

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

tight \(3\) vs \(3\) memory

Gathering, external light (FCOM), SSYNC, rigid + chirality, + rigid, + \(n \ge 3\)

1 open · 1 results

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

tight \(3\) vs \(3\) memory

No multiplicity detection, SSYNC oblivious, disoriented, anonymous, + \(n \ge 3\)

0 open · 0 results

impossible — vs \(\text{impossible}\) indistinguishable multiplicities

impossible — vs —

Two robots, SSYNC oblivious, disoriented, anonymous, + \(n = 2\)

0 open · 0 results

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

impossible — vs —

Homonymous robots, SSYNC oblivious, disoriented, + homonymous

1 open · 1 results

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

tight \(0\) vs —

Gathering, full lights, SSYNC, no multiplicity detection + lights (LUMI), + chirality, + \(n \ge 3\)

1 open · 1 results

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

tight \(2\) vs \(2\) indistinguishable multiplicities

Agreement on coordinates ASYNC, + lights (LUMI)

—

Rendezvous, full lights (LUMI), ASYNC, non-rigid disoriented, + \(n = 2\)

0 open · 3 results

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

tight \(2\) vs \(2\) symmetry breaking

Gathering, full lights, ASYNC, no multiplicity detection + chirality, + \(n \ge 3\)

2 open · 2 results

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

tight \(3\) vs \(2\) indistinguishable multiplicities

Movement ASYNC, + external light (FCOM)

—

Rendezvous, external light (FCOM), ASYNC, non-rigid non-rigid, + \(n = 2\)

1 open · 1 results

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

tight \(3\) vs \(3\) memory

Rendezvous, external light (FCOM), ASYNC, rigid + rigid, + \(n = 2\)

1 open · 2 results

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

tight \(6\) vs \(3\) memory

ASYNC with weak multiplicity detection ASYNC, oblivious, + weak multiplicity, + \(n \ge 3\)

1 open · 1 results

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

tight \(0\) vs —

Rendezvous, internal light (FSTA), ASYNC ASYNC, + internal light (FSTA), + \(n = 2\)

1 open · 0 results

unknown — vs —

unknown — vs \(3\) memory

Gathering, external light, sequential scheduler + sequential, + external light (FCOM), + \(n \ge 3\)

0 open · 1 results

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

tight \(2\) vs \(2\) memory

Lights (persistent memory) + crash faults, + SSYNC

—

Crash faults, SSYNC oblivious, disoriented, non-rigid, + weak multiplicity, + \(n \ge 3\)

1 open · 4 results

unknown \(\text{finite}\) vs \(\text{impossible}\) indistinguishable multiplicities

tight \(0\) vs —

Rendezvous, full lights, a crash, SSYNC + lights (LUMI), + compass, + rigid, + \(n = 2\)

0 open · 0 results

impossible — vs \(\text{impossible}\) indistinguishable crashes

impossible — vs —

Byzantine faults, SSYNC Byzantine, + SSYNC, + \(n \ge 3\)

0 open · 0 results

impossible — vs \(\text{impossible}\) indistinguishable Byzantine agents

impossible — vs —

Byzantine faults, FSYNC Byzantine, + FSYNC, + \(n \ge 3\)

0 open · 1 results

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

tight \(0\) vs —

Scheduler limited visibility, + transparent, + no faults

—

Limited visibility with a compass, ASYNC ASYNC, + compass

0 open · 1 results

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

tight \(0\) vs —

Limited visibility, one common axis, ASYNC ASYNC, + one axis

0 open · 1 results

tight \(O(\Delta_0)\) vs \(\Omega(\Delta_0)\) distance

tight \(0\) vs —

Limited visibility, FSYNC, disoriented + FSYNC

1 open · 2 results

tight \(O(\Delta_0^2)\) vs \(\Omega(\Delta_0^2)\) locality

tight \(0\) vs —

Opacity fat, + unlimited visibility

—

Agreement on coordinates opaque, + no faults

—

Fat robots, few robots, no common orientation disoriented, + \(n \ge 3\)

1 open · 1 results

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

tight \(0\) vs —

Fat robots, chirality, any number + chirality, + \(n \ge 3\)

1 open · 1 results

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

tight \(0\) vs —

Transparent fat robots, no chirality + transparent, + no faults, + \(n \ge 3\)

1 open · 2 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.