Meeting at one place

The reasons given are practical and much the same in every model. Robots exploring a terrain meet "to exchange samples of the ground previously collected by the robots, or exchange information obtained when exploring different parts of the terrain", and software agents meet periodically "to exchange collected data and plan further actions" Pelc 2019. Bouchard, Dieudonné and Pelc add mobile robots "moving along corridors of a contaminated mine that is not accessible to humans", and give as reasons to gather samples or "to coordinate some future task, such as network maintenance or finding a map of the network" Bouchard et al. 2023. In the plane, gathering is called "one of the most fundamental tasks one can ask mobile robots to perform, e.g. to collect acquired data or to update the robots' algorithm" Bramas et al. 2023.

The second reason is that meeting is a building block. Gathering "turns out to be an essential prerequisite to achieve more complex cooperative works", so that results on gathering are results on everything built on it Bouchard et al. 2022; Devismes, Dieudonné and Labourel use almost the same words Devismes et al. 2026. Clement et al. place gathering among agreement problems: like scattering, it is "similar to the consensus problem in conventional distributed systems", with simple definitions but solvability that "greatly depends on the synchrony of the systems as well as the nature of the faults" Clement et al. 2010.

Pelc separates rendezvous settings by whether agents can see something other than the environment, other agents or marks Pelc 2019. On graphs they usually cannot, and two conventions fix the difficulty. Nodes are anonymous because "if nodes had distinct labels, then agents might explore the graph and meet in the smallest node, hence gathering would reduce to the well-studied task of exploration"; ports are numbered because without them "the adversary could prevent an agent from taking some edge" Bouchard et al. 2023. Identical agents may never meet: two of them starting together on a ring with consistent ports run forever in parallel Ta-Shma & Zwick 2014. So the labels of the agents are the symmetry breaker, and the cost is polynomial in \(n\) and the label length Dessmark et al. 2006 Ta-Shma & Zwick 2014. In trees the cost is \(\Theta(n+\log\lambda)\), where \(\lambda\) is the smaller label Dessmark et al. 2006. Ta-Shma and Zwick also posed treasure hunt, rendezvous in which one agent never moves, as a tool for this question Ta-Shma & Zwick 2014.

Without labels the question becomes which initial configurations can meet. Dieudonné and Pelc characterise the configurations of identical agents that can gather, and show that detecting that gathering is complete needs a bound on \(n\) Dieudonné & Pelc 2016. For two identical asynchronous agents, meeting is feasible exactly when their views differ or their starting nodes are joined by a path whose port sequence is a palindrome Guilbault & Pelc 2011, as summarised in Pelc 2019. A middle ground is homonymous agents, motivated by cost and privacy: unique labels "can be costly", and agents "may deliberately blur their identity by revealing it only partially" Devismes et al. 2026. With asynchronous agents the adversary controls speeds and agents may meet inside an edge; polynomial cost was reached only in Dieudonné et al. 2015, after the ring case De Marco et al. 2006.

Robots in the plane see each other, so finding the others is not the issue; agreeing on a point is. Prencipe states the research question as "under which conditions this task can be accomplished by the robots?", and shows that without extra assumptions such as multiplicity detection gathering is in general impossible Prencipe 2007. Suzuki and Yamashita had shown that two oblivious robots cannot meet in SSYNC Suzuki & Yamashita 1999, and Flocchini et al. explain why two robots matter: rendezvous "separates FSynch from SSynch for oblivious robots", whereas \(n \ge 3\) robots gather even in ASYNC with multiplicity detection Flocchini et al. 2016 Cieliebak et al. 2012. Izumi et al. note that, for semi-synchronous robots, two-robot gathering is the single pattern that memory makes formable Izumi et al. 2012.

That made rendezvous the test case for every new capability. Unreliable compasses solve it below a threshold deviation Izumi et al. 2012. A light with two colours solves it in ASYNC Das et al. 2016 Heriban et al. 2018, and three colours suffice when a robot sees only its own light (FSTA, in SSYNC) or only the other's (FCOM, even in ASYNC) Flocchini et al. 2016, and three colours are also necessary Otaka et al. 2026. The measure throughout is feasibility and the number of colours, not time.

Relaxing the goal removes most of the difficulty. Izumi et al. remark in passing that "Two oblivious robots can converge to a point with a naive algorithm that consists of always moving toward the midpoint of their positions" Izumi et al. 2012. Convergence of \(n\) robots was given by Suzuki and Yamashita Suzuki & Yamashita 1999, with limited visibility by Ando et al. the same year Ando et al. 1999, and the centre of gravity converges in ASYNC Cohen & Peleg 2005.

With convergence and with limited visibility, time becomes measurable again, and the bounds are about locality. Under limited visibility in FSYNC, a class of local protocols needs and achieves \(\Theta(\Delta_0^2)\) rounds, where \(\Delta_0\) is the initial diameter in units of the visibility range Castenow et al. 2022; near-gathering, in which robots must come close without colliding Pagli et al. 2015, takes \(O(\Delta_0^2)\) epochs for disoriented robots in SSYNC, again tight within that class Castenow et al. 2022. With one common axis, asynchronous gathering takes \(\Theta(\Delta_0)\) epochs Poudel & Sharma 2021.

Evacuation fixes the meeting point in advance but hides it. Bampas et al. set the three measures side by side: in search the cost is the arrival of the first searcher at a target placed by an adversary; in rendezvous it is the arrival of the last robot, and "the meeting point is arbitrary, i.e., the robots may choose the most convenient one"; in their linear search problem "a pair of robots has to meet at an unknown fixed target point of the environment" and the cost is the arrival of the second Bampas et al. 2019. Evacuation is this third problem.

Czyzowicz et al., posing evacuation from a disk, describe the tension: robots should spread to find the exit fast but not so far that the walk to it becomes long Czyzowicz et al. 2014. Communication decides how much the meeting costs. Two wireless robots evacuate in exactly \(1+2\pi/3+\sqrt3 \approx 4.826\) Czyzowicz et al. 2014; with face-to-face communication the best algorithm takes about \(5.6234\) Disser & Schmitt 2019 against a lower bound of about \(5.255\) Czyzowicz et al. 2020. On the line, face-to-face robots that must all reach the target cannot beat the single-robot ratio 9 Bampas et al. 2019 Chrobak et al. 2015.

Read across the models, meeting is hard for three different reasons. On graphs agents cannot see each other, so meeting needs exploration and symmetry breaking, and the open questions are about cost: labelled rendezvous is polynomial, but the exponent is far from the lower bound (see the rendezvous page). In the plane robots see each other but cannot remember or agree, so the open questions are about which capabilities suffice and how many colours they need. In continuous search robots know the domain and each other's plans but not the target, so the open questions are gaps between constants.

Faults sharpen each version differently: \(f\) Byzantine agents on graphs require \(f+1\) good agents, or \(f+2\) when the number \(n\) of nodes is unknown Bouchard et al. 2016; one Byzantine robot among three already prevents gathering in the plane in SSYNC Agmon & Peleg 2006; and a faulty robot in a disk raises the evacuation time Czyzowicz et al. 2017. The perspective When agents fail follows that thread.