Mobility Matters
Home›Mobile robots in the plane›Formation problems›Convergence

Convergence

Robots must get arbitrarily close to a common point; they need not ever meet.

Problem statement and measuresexpand

\(n\) robots start at arbitrary points. For every \(\varepsilon > 0\) there must be a time after which all robots stay within distance \(\varepsilon\) of each other (equivalently, of a common limit point). Robots never need to coincide.

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

no assumptions›+ point›limited visibility, + transparent, + no faults

Limited visibility, asynchronous

verified
Time: unknownColours: tight

With limited visibility, convergence is solved for every bounded asynchrony (k-ASYNC) but open for full ASYNC.

Assumed (added on the last edge are outlined)

+Bodypoint robots+Opacitytransparent: every robot sees every robot within range+Faultsno faults

Not assumed

Visibilitylimited: robots see only within a fixed radiusSchedulerasynchronous (ASYNC)Lights (persistent memory)oblivious, no light (OBLOT)Agreement on coordinatesno agreement on local coordinate systemsMovementnon-rigid: the adversary may stop a move after some minimum distance \(\delta\)Multiplicity detectionnone: a point with several robots looks like one robotRandomnessdeterministicIdentifiersanonymous: all robots are identical
Formal definitions of this setting
Body: point
Each robot is a point of the plane: several robots may share a point (multiplicity), and a robot hides only what lies exactly behind it on a line of sight.
Visibility: limited visibility
A robot sees exactly the robots within Euclidean distance \(V\) of its position, for a fixed radius \(V>0\).
Opacity: transparent
Robots do not obstruct each other's view.
Faults: no faults
All robots follow the algorithm forever.
Scheduler: ASYNC
ASYNC: each robot's Look, Compute and Move phases take finite but unbounded, adversarially chosen time; a robot may look while others move, and compute on an outdated snapshot. Time is counted in epochs: an epoch is an interval of time in which every robot completes at least one full Look–Compute–Move cycle; it need not be the shortest such interval. The execution is divided into consecutive epochs, and a bound of \(X\) epochs holds for every such division. In FSYNC and SSYNC time is counted in rounds. Called Corda by Prencipe Prencipe 2007. Intermediate variants restrict interleavings: LC-atomic (no Look by another robot between a robot's Look and its Compute), Move-atomic (no Look during another robot's Move) and CM-atomic Flocchini et al. 2023.
Lights (persistent memory): oblivious
OBLOT: a robot's computation depends only on the current snapshot; nothing persists across cycles.
Agreement on coordinates: disoriented
Each robot \(r\) observes in its own coordinate system, obtained from the global one by an unknown similarity (translation, rotation, uniform scaling, and possibly reflection); systems may differ between robots and, in some models, between cycles. Papers that call robots disoriented do not always mean this: Défago and Souissi use the word while assuming chirality Défago & Souissi 2008. Some papers also let the adversary change a robot's rotation, reflection and unit at every Look (variable disorientation) Flocchini et al. 2023 Masuzawa et al. 2026.
Movement: non-rigid
In a Move phase the adversary may stop a robot before its destination, but only after it has travelled at least \(\delta>0\) (a constant unknown to the robots) or reached the destination.
Multiplicity detection: no multiplicity detection
A snapshot is a set of points: a point occupied by several robots looks like a single robot.
Randomness: deterministic
The destination computed in a cycle is a function of the snapshot (and the light, if any).
Identifiers: anonymous
Robots are indistinguishable and run the same algorithm.

What is known

Time · rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known
unknown
Full ASYNC is open.
lower boundnone known
introductory
\(\text{finite}\)
1-ASYNC
current best
\(\text{finite}\)
k-ASYNC for any fixed bound on the asynchrony
Colours · colours of the light per robot (0 for oblivious robots)
tight
No colours.
lower boundnone known
introductory
\(0\)
1-ASYNC
current best
\(0\)
k-ASYNC for any fixed bound on the asynchrony

Results, in order of publication

Katreniak 2011 introductory
Time \(\text{finite}\)Colours \(0\)
1-ASYNC

Also solves unlimited-visibility ASYNC convergence without multiplicity detection.

Kirkpatrick et al. 2024 current best
Time \(\text{finite}\)Colours \(0\)
k-ASYNC for any fixed bound on the asynchrony

Also shows that cohesive convergence is impossible in ASYNC for hull-diminishing or coherent algorithms when perception has errors.

Open questions

  1. Is point convergence with limited visibility solvable in full ASYNC, without perception or motion errors? Kirkpatrick et al. 2024

  2. Is there a problem that separates k-ASYNC from SSYNC? Kirkpatrick et al. 2024

What carries over from neighbouring settings

Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.

Algorithms from weaker settings work here

No catalogued weaker setting.

Lower bounds from stronger settings hold here

ASYNC, unlimited visibility
Limited visibility, SSYNC, rigid moves

Branches from here

Limited visibility, SSYNC, rigid moves

+SSYNC+rigid
With limited visibility, semi-synchronous oblivious robots whose moves reach their computed destination converge within each connected component of the visibility graph.

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