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

Near-gathering

Robots must get within a small distance of each other without ever colliding.

Problem statement and measuresexpand

Robots with limited visibility, each seeing only the robots within its visibility radius \(V\), start at distinct points whose visibility graph (two robots joined by an edge when they are within distance \(V\)) is connected. They must reach a configuration in which every robot sees all others, without a collision (two robots at the same point) ever happening.

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

—

Scheduler + point, + transparent, + no faults

—

ASYNC, limited visibility, one common axis ASYNC, + one axis

1 open · 1 results

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

tight \(0\) vs —

SSYNC, limited visibility, disoriented + SSYNC

1 open · 1 results

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

tight \(0\) vs —

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