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 measurescollapse
Start: ringed robots move towards the centre of gravitySSYNC rounds; moves may stop earlyAfter 9 rounds: the convex hull keeps shrinking
Convergence: robots at arbitrary points must, for every \(\varepsilon > 0\), eventually stay within distance \(\varepsilon\) of each other; they approach a common limit point but need never meet Suzuki & Yamashita 1999. Shown: the centre-of-gravity rule of Cohen & Peleg 2005 in SSYNC rounds; ringed robots are activated and move towards the centre of gravity (star) of all robots, some stopping early.

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

A first look

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

Think of a flock that must squeeze ever closer together, without ever needing to land on one spot. There are \(n\) robots, points in the plane; their positions form the configuration. Each robot repeats a Look–Compute–Move cycle: it takes a snapshot of where the other robots are (Look), decides on a destination point (Compute) and moves towards it (Move). They are identical, silent, oblivious (no memory between cycles), and each has its own local coordinate system; the scheduler, an adversary, decides the activation of robots, that is, when each performs a cycle. In the basic version the scheduler is ASYNC (each phase may take any finite time, so a robot may act on an outdated snapshot) and every robot sees all others. The robots must converge: for every distance \(\varepsilon > 0\), there must come a time after which all robots stay within \(\varepsilon\) of each other. Unlike gathering, they never have to meet exactly.

1AlgorithmGo to the centre of gravity ASYNC, unlimited visibility → Cohen & Peleg 2005
  1. Look at the positions of all robots.
  2. Compute their centre of gravity: the average of all positions (add up the \(x\)-coordinates and divide by \(n\), and the same for \(y\)).
  3. Move towards it.
Why it works and what it costs. The centre of gravity does not depend on the local coordinate system, so robots with different local coordinate systems aim at the same point. In FSYNC (every robot is activated in every round) with rigid moves (moves that reach their destination), all robots compute the same point and meet in one round. In ASYNC the snapshots are outdated, but each destination is an average of positions that were already inside the convex hull of the robots (the smallest convex region containing them), so the convex hull of the robots and their destinations never grows; Cohen and Peleg prove that it actually shrinks to a point Cohen & Peleg 2005. A later analysis in ASYNC, counting a round as a stretch of time in which every robot completes a Look–Compute–Move cycle, shows that with rigid moves \(O(n)\) rounds halve the diameter, improving \(O(n^2)\), and that this is tight for the centre of gravity Cord-Landwehr et al. 2011.

Why it matters. It is the simplest convergence rule, and the never-growing convex hull is reused as a building block, for example to split robots into groups Efrima & Peleg 2009.

2AlgorithmShort sight: go to the centre of what you see, but keep your neighbours Limited visibility, SSYNC, rigid moves → Ando et al. 1999

Now each robot sees only the robots within distance \(V\) (its visibility radius).

  1. Compute the smallest enclosing circle of the robots you see, and head for its centre.
  2. Do not go farther than a fixed maximum step.
  3. For every robot you see, stay inside the disc of radius \(V/2\) around the midpoint between you and it.
Why it works and what it costs. If two robots that see each other both obey rule 3, both end in the same disc of radius \(V/2\), so they are still within \(V\) and still see each other (Lemma 2 of Ando et al. 1999). Groups therefore never split, the convex hull of each group never grows, and Ando, Oasa, Suzuki and Yamashita prove that each connected group converges to a point in SSYNC with rigid moves (Theorem 1). The argument uses that a whole cycle happens at once; in ASYNC a robot may move on outdated information and break a visibility link. The catalogue records limited-visibility convergence as solved for every bounded amount of asynchrony and open for full ASYNC Kirkpatrick et al. 2024.

Why it matters. Its "stay within \(V/2\) of the midpoint" trick for keeping neighbours is reused by many limited-visibility algorithms, including Go-To-the-Center gathering Castenow et al. 2022.

Simulator watch an algorithm run

A simulator of Look–Compute–Move robots in the plane that runs in the browser. Each case below starts one of its algorithms from a fixed starting configuration and seed; the run is the simulator's, not a proof. Source.

Go to the centre of gravity. Each robot moves to the average position of the robots it sees, the rule of Cohen & Peleg 2005. Here 30 robots see everyone and run under the simulator's asynchronous scheduler. Open in the simulator ↗

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
Limited visibility, asynchronous
With limited visibility, convergence is solved for every bounded asynchrony (k-ASYNC) but open for full ASYNC.
unknown \(\text{finite}\) vs —
tight \(0\) vs —
Limited visibility, SSYNC, rigid moves
With limited visibility, semi-synchronous oblivious robots whose moves reach their computed destination converge within each connected component of the visibility graph.
unknown \(\text{finite}\) vs —
tight \(0\) vs —
ASYNC, unlimited visibility standard
Moving to the centre of gravity makes oblivious robots converge in ASYNC, for any \(n\).
unknown \(\text{finite}\) vs —
tight \(0\) vs —

Open questions 2

Limited visibility, asynchronous

  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 the community started looking at

Convergence was introduced alongside gathering as its relaxation Suzuki & Yamashita 1999. The first questions were which simple rules converge under each scheduler (centre of gravity in ASYNC Cohen & Peleg 2005, limited visibility in SSYNC Ando et al. 1999); then the rate of convergence Cord-Landwehr et al. 2011, and how much asynchrony is compatible with limited visibility Kirkpatrick et al. 2024.

Related problems

Gathering: Every gathering algorithm solves convergence, but not conversely: two oblivious robots in SSYNC cannot gather, while "two oblivious robots can converge to a point with a naive algorithm" Izumi et al. 2012. In ASYNC the centre-of-gravity algorithm converges for any \(n\) Cohen & Peleg 2005, whereas gathering needs extra assumptions such as multiplicity detection.

Near-gathering: 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

  • Why compute by moving The atlas collects four models that grew out of four different wishes: software that travels through a network, swarms of robots that are as weak as possible, searchers that must find something at an unknown place, and matter that reshapes itself. They share an adversary, locality and symmetry; they differ in what they count.
  • 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.
  • The most consequential open problems Ten open questions ranked by how far a solution would propagate through the atlas, with the chain of problems each one feeds.

Further reading

Papers on this problem that are not yet placed in a setting.

  • Asahiro & Yamashita 2023 Compatibility of Convergence Algorithms for Autonomous Mobile Robots (Extended Abstract). Compatibility: robots may run different target functions; a set of them is compatible for a task if every mix solves it. Every set of functions that always shrink the convex hull is compatible for convergence and for convergence with one crash, but no such set is compatible for gathering; fault-tolerant convergence with \(f \ge 2\) crashes lies in between. Read (arXiv v7).
  • Pattanayak et al. 2017 Convergence of Even Simpler Robots without Position Information. Convergence by 'monoculus' robots that cannot measure distances, in two weaker sensing models. Abstract read.
  • De Carufel & Flocchini 2017 Fault-Induced Dynamics of Oblivious Robots on a Line. What the convergence algorithm of Ando et al. does on a line when some robots have crashed undetectably. Abstract read.

All settings

The assumption tree (3 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.