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).
Limited visibility, SSYNC, rigid moves
verifiedWith limited visibility, semi-synchronous oblivious robots whose moves reach their computed destination converge within each connected component of the visibility graph.
Assumed (added on the last edge are outlined)
Not assumed
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: SSYNC
- SSYNC: time is divided into rounds; in each round a non-empty subset of robots, chosen by a fair adversary, executes one atomic Look–Compute–Move cycle. Called Atom by Prencipe Prencipe 2007.
- 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: rigid
- Every Move phase ends at the computed 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
Results, in order of publication
Introductory and current best (Theorem 1).
Open questions
None recorded for this variant.
Notes
Checked against the full text of Ando et al. 1999. The formal model (assumptions A1–A6) has point robots that do not obstruct each other, phases of "negligibly small" duration, so that a robot observes others only when they are stationary (an SSYNC scheduler, although the paper calls the robots asynchronous), every robot active infinitely often, and exact sensing and motion. There is no common coordinate system. A robot moves towards the centre of the smallest enclosing circle of the robots it sees, but no farther than keeps every visible robot within distance \(V\) (Lemma 2: mutually visible robots stay mutually visible). Whether the same algorithm works with non-rigid moves is not addressed in the paper.
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
Lower bounds from stronger settings hold here
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.