Mobility Matters
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 measurescollapse
Start: neighbours within V share an edgeEach robot moves part way to the centre of what it seesFinal: every robot sees all, none collide
Near-gathering: robots with limited visibility, starting at distinct points whose visibility graph is connected, must come close enough that every robot sees all others, without two robots ever occupying the same point Pagli et al. 2015. Shown in FSYNC rounds: the Go-To-the-Center rule of Castenow et al. 2022: each robot moves part of the way towards the centre of the smallest circle enclosing the robots it sees, staying within \(V/2\) of the midpoint with each neighbour, so edges of the visibility graph are never lost.

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

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Imagine short-sighted people in fog who must come close enough that everybody can see everybody, without bumping into each other. In the problem the people are \(n\) robots, points at distinct places in the plane, and each sees only the robots within distance \(V\) (its visibility radius). Join two robots by an edge when they are within distance \(V\), and call them neighbours; the robots and these edges form the visibility graph, and at the start it is connected (every robot can be reached from every other along edges). Each robot reads positions in its own local coordinate system (its private axes and unit of length) and repeats a Look–Compute–Move cycle: it takes a snapshot of where the robots it sees are (Look), decides on a destination point (Compute) and moves towards it (Move). Robots are identical, silent and oblivious (no memory between cycles); in the basic version their local coordinate systems agree on the direction of one axis, and the scheduler, controlled by an adversary (an imagined opponent) that decides when each robot acts and how long each phase takes, is ASYNC (each phase may take any finite time). The robots must reach a configuration (the positions of all robots) in which every robot sees all others, and two robots may never be at the same point (a collision).

1AlgorithmGo to the centre of what you see, in small steps, keeping your neighbours SSYNC, limited visibility, disoriented → Castenow et al. 2022
  1. Compute the smallest enclosing circle of the robots you can see, and aim for its centre (the Go-To-the-Center rule).
  2. For every robot you see (every neighbour), stay inside the disc of radius \(V/2\) around the midpoint between you and it. Your neighbour obeys the same rule, so the two of you stay within distance \(V\), your edge is kept, and the visibility graph stays connected.
  3. To avoid collisions, move only a short distance and only part of the way to your target. Here robots see a little farther than \(V\): edges still join robots within distance \(V\) (the connectivity range), but each robot sees every robot within distance \(V + \tau\) (its viewing range), for a constant \(0 < \tau \le 2V/3\) Castenow et al. 2022. So a robot can also compute where its nearby neighbours are heading and keep clear of them.
  4. Stop when everyone you see is very close: since the visibility graph is connected, then everyone is close.
Why it works and what it costs. Collisions are the new difficulty compared with gathering. Even for two robots, the simple rule "move half-way to the centre of gravity" can collide in ASYNC: robot \(r\) at \((0,0)\) heads for \((781, 0)\); the scheduler pauses it at \((52, 0)\) while robot \(s\), starting at \((3124, 0)\) and always seeing \(r\) at \((52, 0)\), makes five cycles and arrives at \((781, 0)\); then \(r\) finishes its move onto \(s\) Pagli et al. 2015. Castenow, Harbig, Jung, Kling, Knollmann and Meyer auf der Heide show that any gathering rule of a broad class, including Go-To-the-Center, can be made collision-free and solves near-gathering for disoriented robots in \(O(\Delta_0^2)\) epochs (an epoch is an interval of time in which every robot completes at least one full cycle) in SSYNC, where \(\Delta_0\) is the initial diameter (largest distance between two robots) and \(V\) is the unit (Theorem 18 of Castenow et al. 2022). The steps above simplify their construction.

Why it matters. It lets short-sighted robots reach a state where they all see each other, after which any algorithm for robots with unlimited visibility can take over.

2Lower boundA big regular polygon shrinks slowly SSYNC, limited visibility, disoriented → Castenow et al. 2022

Place \(n\) robots on a regular \(n\)-gon with sides of length 1, the visibility radius, so each robot sees only its two neighbours. The adversary chooses local coordinate systems so that all robots see the same thing and the polygon stays regular forever. Each robot sees itself and two neighbours nearly on a straight line: the triangle they form has height at most about \(\pi/n\). If a robot always moves inside the triangle of what it sees, it moves towards the centre by at most about \(\pi/n\) per round (a step of time in which each robot that the scheduler activates performs one full cycle). The polygon's radius is about \(n/(2\pi)\), so shrinking it to two thirds of its size takes about \(n^2\) rounds.

Why it holds. The diameter of this start is \(\Delta_0 \approx n/\pi\), so \(\Omega(\Delta_0^2)\) rounds are needed by every protocol whose robots always move inside the region spanned by what they see (Theorem 4 of Castenow et al. 2022); Go-To-the-Center and its collision-free version are of this kind, so their \(O(\Delta_0^2)\) bound is tight for them. Whether moving outside that region can be faster is open.

Why it matters. It shows that local rules pay quadratically in the size of the swarm, and points to where a faster algorithm would have to do something different.

3ImpossibilityRobots that see nobody stay apart ASYNC, limited visibility, one common axis → Pagli et al. 2015

Why must the start be connected? Take two robots farther apart than \(V\). Each sees only itself, in every cycle. A deterministic oblivious robot with the same snapshot always computes the same move in its own coordinates. The adversary gives both robots the same orientation and unit and wakes them together: they make exactly the same move in the plane, so their distance never changes. They never see each other.

Why it holds. So near-gathering cannot be solved from a disconnected start, which Pagli, Prencipe and Viglietta note is "easily seen" Pagli et al. 2015; the same holds for gathering Flocchini et al. 2005. From a connected start, Pagli et al. solve near-gathering in ASYNC, without collisions and with termination, for robots that agree on one axis Pagli et al. 2015.

Why it matters. It is the reason every limited-visibility algorithm assumes a connected start and works hard to keep it connected.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Colours
ASYNC, limited visibility, one common axis standard
Robots get close together without ever colliding, from a connected start, if they agree on one axis.
unknown \(\text{finite}\) vs —
tight \(0\) vs —
SSYNC, limited visibility, disoriented
Disoriented robots near-gather in \(O(\Delta_0^2)\) epochs in SSYNC.
tight \(O(\Delta_0^2)\) vs \(\Omega(\Delta_0^2)\) locality
tight \(0\) vs —

Open questions 2

ASYNC, limited visibility, one common axis

  1. Pagli, Prencipe and Viglietta conjecture that near-gathering is impossible without agreement on one axis.

SSYNC, limited visibility, disoriented

  1. Near-gathering in \(O(\Delta_0)\) epochs?

What the community started looking at

Near-gathering was introduced to get robots close without collisions, a safe first phase for other tasks Pagli et al. 2015; later work asked how fast disoriented robots can do it Castenow et al. 2022.

Relaxation of Gathering

Gathering requires a common point; near-gathering only requires being close, but forbids collisions. It is used as a first phase before forming patterns.

Related problems

Convergence: Near-gathering is also a relaxation of gathering: robots must get close (within visibility of each other) without ever colliding Pagli et al. 2015, while convergence lets them approach a point only in the limit.

Perspectives

  • Meeting at one place Rendezvous and gathering on graphs, gathering and convergence in the plane, and evacuation through an unknown exit all ask entities to end at one point. The papers give the same reasons for meeting, but each model makes a different part of it hard: symmetry and exploration on graphs, capability in the plane, information in continuous search.

All settings

The assumption tree (2 settings, 2 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Colours); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Body › Visibility › Opacity › Faults › Scheduler › Lights (persistent memory) › Agreement on coordinates › Movement › Multiplicity detection › Randomness › Identifiers.

tight near-optimal polynomial gap unknown impossible no variant

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