Gathering

Further reading

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

• Shukla et al. 2026b Gathering Autonomous Mobile Robots Under the Adversarial Defected View Model. Gathering under the adversarial \((n, K)\)-defected view model of Kim, Shibata, Sudo, Nakamura, Katayama and Masuzawa (OPODIS 2022, not in the bibliography): in each Look the adversary shows a robot only \(K\) of the occupied points other than its own (all of them if there are at most \(K\)), and may change its choice at every Look. Oblivious robots without multiplicity detection and with non-rigid moves gather in finite time for \(n = 4\) and \(K = 2\) in FSYNC without any agreement on coordinates (Theorem 4.1), and for any \(n \ge 3\) and \(1 \le K \le n-2\) in ASYNC if they agree on one axis (Theorem 6.1); no time bound. The plane model has no value for such defective views, so the results have no setting here. A preprint; several proofs are sketched, and some lemma references do not match the lemmas. Read.
• Di Luna et al. 2025c Gathering on a circle with limited visibility by anonymous oblivious robots. Robots confined to a circle, with chirality, rigid moves, SSYNC, and visibility limited to angular distance below \(\vartheta\), gather from every rotationally asymmetric configuration when \(\vartheta = \pi\) (Theorem 4.14); for \(\vartheta \le \pi/2\) no algorithm gathers, even from asymmetric configurations with a connected visibility graph (Theorem 3.7), by a new random-perturbation argument. Read (arXiv v3).
• Ghosh et al. 2025 Asynchronous Gathering of Finite Memory Robots on a Circle under Limited Visibility. The same circle with \(\vartheta = \pi\) under ASYNC, for robots with finite persistent memory (FSTA): gathering from every rotationally asymmetric configuration (Theorem 2). Read (arXiv v1).
• Flocchini et al. 2019a Gathering and Election by Mobile Robots in a Continuous Cycle. Robots on a continuous cycle of length \(\ell\) that see only their own position, move at unit speed and act in synchronous rounds: randomized gathering and leader election by Las Vegas algorithms when \(n\) or \(\ell\) is known (Theorems 1 and 9) and Monte Carlo ones with upper bounds (Theorems 8 and 16); no Las Vegas algorithm exists when neither is known exactly (Theorem 19). Read (ISAAC version).
• Heriban & Tixeuil 2021 Unreliable Sensors for Reliable Efficient Robots. Quantitative results by simulation: the largest distance travelled when gathering two or \(n\) oblivious robots under FSYNC, SSYNC and ASYNC, the behaviour of known rendezvous and leader-election algorithms when vision is unreliable, and two algorithms (fuel-efficient convergence, leader election) that tolerate such errors. Read (arXiv v1).
• Courtieu et al. 2016 Certified Universal Gathering in \(\mathbb{R}^2\) for Oblivious Mobile Robots. Universal gathering certified in Coq: oblivious SSYNC robots with rigid moves and strong multiplicity detection, without chirality, gather from every configuration that is not bivalent, including starts with several robots on one point. Read (arXiv v1).
• Castenow et al. 2021 Gathering a Euclidean Closed Chain of Robots in Linear Time. A closed chain of \(n\) disoriented robots with limited visibility, each seeing its chain neighbours, gathers in \(\Theta(n)\) FSYNC rounds with lights, against \(\Theta(n^2)\) for the oblivious algorithms; configurations that are isogonal polygons are gathered without lights. Read (arXiv v2).
• Braun et al. 2020 Local Gathering of Mobile Robots in Three Dimensions. Gathering with limited visibility in three dimensions: a 3D Go-To-The-Center strategy takes \(\Theta(n^2)\) FSYNC rounds, and every contracting strategy in continuous time takes \(O(\Delta n^{3/2})\) for initial diameter \(\Delta\), against \(\Omega(\Delta n)\). Read (arXiv v1).
• Pattanayak et al. 2021a Randomized gathering of asynchronous mobile robots. Randomized gathering of two robots under ASYNC, by what the adversary controls (waiting time, computation delay, speed) and knows: possible against an oblivious adversary with zero computation delay or with waiting time plus delay bounded below, impossible against an adaptive one; extended to many robots with merging. Read (arXiv v1).
• Kim et al. 2022 Gathering of Mobile Robots with Defected Views. Defected views: each robot sees only some of the others. Gathering for \(N \ge 5\) robots when each sees at most \(N-2\) chosen by the adversary, and for four robots that each see their two nearest; impossible when each of three robots sees only one. Read (LIPIcs version).
• Czyzowicz et al. 2020e Gathering in the plane of location-aware robots in the presence of spies. A central authority that knows the positions of all robots, among them Byzantine spies it cannot identify, plans trajectories so that the reliable robots gather fast: optimal competitive ratio with at most one spy, small constants when fewer than a half or a third are spies. Read (arXiv v1).
• Barel et al. 2021 Probabilistic Gathering of Agents with Simple Sensors. Agents with simple sensors pick random headings and move only if nobody is behind them: gathering in finite expected time is proved for continuous motion with a blind zone, and observed empirically for unit jumps. Read (arXiv v2).
• Di Luna et al. 2020a Meeting in a polygon by anonymous oblivious robots. Meeting in an unknown polygon, possibly with holes, whose edges block movement and vision: \(\sigma+1\) searchers suffice and are needed when the polygon has rotational symmetry of order \(\sigma\); two suffice when the barycentre is not in a hole; also for oblivious robots. Abstract read.
• Bramas et al. 2020a Stand Up Indulgent Rendezvous. Two oblivious robots in the plane must meet even if one crashes, the correct one then going to the crashed one's position (stand-up indulgent rendezvous): solvability characterised by scheduler, with algorithms. Abstract read.
• Sharma et al. 2025b Gathering of Asynchronous Robots on Circle with Limited Visibility Using Finite Communication. Gathering on a circle by robots with limited angular visibility that agree on the clockwise direction, asynchronous, using finite communication (lights). Abstract read.
• Aponte et al. 2026 Formal Certification of async Protocols: The Case of Gathering in \(\mathbb{R}^2\) Using Weber Points. A formal model of ASYNC executions for the Pactole library of the Rocq (Coq) prover, and a certified gathering algorithm based on Weber points: oblivious disoriented robots with non-rigid moves and strong multiplicity detection gather from every configuration that is not bivalent, starts where robots share points included. Cieliebak et al. 2012 use Weber points only where they are unique; the authors stress that Weber points do not make gathering trivial. Read in full.
• Li et al. 2021a A continuous strategy for collisionless gathering. Gathering in continuous time (robots adjust their unit-speed motion to what they see at every instant) with visibility radius \(V\) and a connected start: every algorithm whose target points satisfy a simple contraction criterion gathers in \(O(n\Delta_0)\) time (Theorem 1, their \(d\) is \(\Delta_0\)), so \(O(n^2)\); two such algorithms move to the centre of the smallest circle around the relative-neighbourhood neighbours (Theorem 2), and a variant gathers without collisions in \(O(n^2)\) time using lights and chirality (Theorems 3, 4). Read in full.