Mobile robots in the plane

Suzuki and Yamashita's robots are points: each one observes "the positions of all the robots" Suzuki & Yamashita 1999, several robots may share a point, and nobody blocks anybody's view. Czyzowicz, Gąsieniec and Pelc Czyzowicz et al. 2009 introduced fat robots, closed unit discs that cannot overlap and hide what lies behind them: a robot sees another if some segment between their boundary circles meets no third robot, and a robot that touches another stops and ends its cycle. Gathering then asks for "a configuration for which the union of all discs representing them is connected", in which moreover every robot sees all others, so that all know the task is done Czyzowicz et al. 2009. Their motivation is realism: "In reality, even very small robots occupy some space", so robots may block each other's view and motion Czyzowicz et al. 2009; later accounts say the same Agathangelou et al. 2013. Czyzowicz et al. 2009 solved three and four oblivious, disoriented robots in ASYNC (non-rigid moves, robots know \(n\)) by case analysis and left \(n \ge 5\) open ("We were unable to do it"); Agathangelou, Georgiou and Mavronicolas Agathangelou et al. 2013 answered it for any \(n\) in ASYNC, assuming chirality and knowledge of \(n\). Fatness is not weaker in every respect: the common radius gives all robots "a common measure of unit" Czyzowicz et al. 2009, a unit of length "for free" Agathangelou et al. 2013 Bandettini et al. 2011. The catalogue puts fat robots at level 0 because they lose multiplicity points and gain obstruction and collisions; point robots are the setting of almost all other work Bandettini et al. 2011.

Suzuki and Yamashita Suzuki & Yamashita 1999 introduced the semi-synchronous model: robots act "at infinitely many unpredictable time instants", and in each round of a discrete time an arbitrary non-empty set of robots observes and moves instantaneously, every robot being active infinitely often; Prencipe calls it Atom Prencipe 2007 and FSYNC, where every robot acts in every round, is its special case Das et al. 2016. The asynchronous model (later named CORDA) is due to Flocchini, Prencipe, Santoro and Widmayer Flocchini et al. 1999, as Flocchini et al. 2023 and Prencipe 2007 also state: they assume "asynchronicity within one step", so that "the actual move of a robot may be based on a situation that lies arbitrarily far in the past", and a robot "may be seen an arbitrary number of times by other robots" while moving; they call this "the most radical deviation" from Suzuki and Yamashita's atomic steps Flocchini et al. 1999. In Prencipe's words, "computations can be made based on obsolete observations" Prencipe 2007. Prencipe motivates delays inside a cycle as a way "to model also different motorial speeds of the robots" Prencipe 2007. The schedulers are interesting because they form a hierarchy: rendezvous of two oblivious robots is solvable in FSYNC and not in SSYNC Suzuki & Yamashita 1999 (Theorem 3.1 and footnote 5), while a problem separating SSYNC from ASYNC for oblivious robots was sought "for more than two decades" and is known only under limited visibility Flocchini et al. 2023 Kirkpatrick et al. 2024. Intermediate schedulers (RSYNC, LC-, CM- and Move-atomic ASYNC) were introduced to locate exactly where the power is lost Flocchini et al. 2023 Buchin et al. 2022. Sequential schedulers, which activate one robot per round, break symmetry by themselves; Flocchini, Navarra, Pattanayak, Piselli and Santoro note that their relationship with FSYNC "has so far been ignored" and show that the two are orthogonal Flocchini et al. 2026.

Suzuki and Yamashita model a robot as "a mobile processor with infinite memory" and call an algorithm oblivious when the new position depends only on the current observation, noting that "oblivious algorithms are self-stabilizing by definition" Suzuki & Yamashita 1999. Obliviousness then became the default, partly because "any algorithm proved correct in this model is also self-stabilizing" Clement et al. 2010 Défago et al. 2006; oblivious, silent robots communicate only by moving, "reminiscent of bees in a bee dance" Flocchini et al. 1999 Prencipe 2007. Unbounded memory was compared early: two non-oblivious robots can rendezvous in SSYNC and oblivious ones cannot Suzuki & Yamashita 1999 (Theorems 3.1 and 3.3) Izumi et al. 2012. Lights were "initially suggested by Peleg" Das et al. 2016 Di Luna et al. 2014: his survey proposes giving robots "a small amount (say, O(1) bits) of stable memory" and "marking (at least some of) the robots with colors, flags or visible indicator lights" Peleg 2005 (see also Efrima & Peleg 2007); Das, Flocchini, Prencipe, Santoro and Yamashita Das et al. 2016 turned them into the LUMI model, a constant-size register that is persistent and visible to all, so that a robot can remember and communicate a constant number of bits per cycle. Their main results are that LUMI under ASYNC is equivalent to LUMI under SSYNC and strictly stronger than OBLOT under SSYNC Das et al. 2016. To separate the two roles of a light, Flocchini, Santoro, Viglietta and Yamashita Flocchini et al. 2016 defined FSTA (a robot sees only its own light: constant memory, no communication) and FCOM (it sees only the others' lights: constant communication, no memory), and showed that FSTA robots with rigid moves rendezvous in SSYNC and FCOM robots even in ASYNC. The question "is it better to remember or to communicate" then became a programme comparing the four models under every scheduler Flocchini et al. 2019 Flocchini et al. 2023 Das et al. 2024.

Suzuki and Yamashita's robots "initially do not have a common x-y coordinate system", although they share handedness: in every local frame "the positive y-direction is 90 degrees counterclockwise from the positive x-direction" Suzuki & Yamashita 1999; together with anonymity, this disorientation is what keeps symmetric configurations symmetric. Flocchini, Prencipe, Santoro and Widmayer Flocchini et al. 1999 Flocchini et al. 2008 dropped that common handedness and made agreement a parameter, studying "the role of common knowledge" in pattern formation by asynchronous robots: with the directions and orientations of both axes any pattern can be formed; with one axis direction (with or without its orientation) the problem is solvable when \(n\) is odd and in general not when \(n\) is even; with no axis it is unsolvable in general (ISAAC version, proofs omitted) Flocchini et al. 1999. Efrima and Peleg Efrima & Peleg 2009, "elaborating on" that work, list full compass, half compass, direction-only, axes-only and no compass, and note that without a common orientation robots "do not share the notion of 'clockwise'". Common handedness, chirality, became the usual intermediate assumption: Dieudonné, Petit and Villain list sense of direction and chirality among the global properties that decide what a swarm can do, and show that leader election and arbitrary pattern formation are equivalent in ASYNC for \(n \ge 4\) with chirality and \(n \ge 5\) without Dieudonné et al. 2010; removing chirality from pattern formation and gathering is a research line of its own Bramas & Tixeuil 2015 Cicerone et al. 2019. Partial agreement has also been quantified: Izumi et al. give each robot an "unreliable compass" and find the largest deviation that still lets two oblivious robots gather Izumi et al. 2012, and agreement on one axis is used for gathering under limited visibility Poudel & Sharma 2021 Castenow et al. 2022.

In CORDA a move may stop before its destination: Prencipe's Assumption A1 gives each robot a constant \(\delta_r > 0\) such that it either reaches its destination or travels at least \(\delta_r\) towards it, so that "it cannot know how far it will go in the current cycle" Prencipe 2007. The physical motivation is "limits to the robot's motorial capabilities" Prencipe 2007; the lower bound \(\delta\) is needed because without it no algorithm could be guaranteed to terminate Bandettini et al. 2011. Non-rigid moves let the adversary act in space as the scheduler acts in time, and rigid moves (every move reaches its destination) are the stronger assumption that many results state explicitly. Flocchini, Santoro, Viglietta and Yamashita Flocchini et al. 2016 first proved their rendezvous algorithms for rigid moves and then showed that "rigidity of the movements can be traded with knowledge of \(\delta\)". Heriban, Défago and Tixeuil Heriban et al. 2018 work explicitly in "the non-rigid ASYNC model", and later landscape papers removed rigidity (and chirality) from the earlier synchronous comparisons of OBLOT, FSTA, FCOM and LUMI, as reported by Das et al. 2024.

With point robots several robots can share a point, and the snapshot decides whether this is visible. In Prencipe's statement of CORDA robots "can not distinguish whether there is more than one fellow on a given position" Prencipe 2007. Prencipe observed that every known gathering algorithm used some "extra" assumption, mainly that robots "detect whether a given point on the plane is occupied by one or more robots", and proved gathering impossible without such help Prencipe 2007. Cieliebak, Flocchini, Prencipe and Santoro Cieliebak et al. 2012 then showed that with multiplicity detection any \(n > 2\) oblivious, disoriented, asynchronous robots gather (abstract read); the idea is to create one multiplicity point and keep it unique Bandettini et al. 2011. Later work distinguishes a weak detector (one robot or more) from a strong one (the exact number) Bouzid et al. 2013 Pattanayak et al. 2019; the earliest source of this split was not traced. The level matters: Terai, Wada and Katayama note that strong detection alone lets robots without lights gather, so a model with lights must keep colours from revealing multiplicities Terai et al. 2023; under sequential schedulers weak detection is necessary and sufficient for gathering Flocchini et al. 2026.

Ando, Oasa, Suzuki and Yamashita Ando et al. 1999 introduced robots that see only within a fixed radius \(V\); Kirkpatrick et al. call it "the pioneering work on Point Convergence under limited visibility", Kirkpatrick et al. 2024. Each robot moves towards the centre of the smallest enclosing circle of the robots it sees, but only so far that every robot it sees stays within distance \(V\); the proof assumes points, no obstruction, and phases of negligible duration (so the scheduler is SSYNC although the paper calls the robots asynchronous), with each move reaching its computed destination, at most a small constant away Ando et al. 1999. Flocchini, Prencipe, Santoro and Widmayer Flocchini et al. 2005 gathered oblivious robots with limited visibility in ASYNC, with non-rigid moves and without multiplicity detection, when they share "orientation", i.e. agree on the directions and orientations of both axes but not on unit or origin; they conclude that "orientation is at least as powerful as instantaneous movements". Limited visibility makes the model local: the initial visibility graph must be connected Flocchini et al. 2005 (Lemma 4.7), and known algorithms keep every initially visible pair visible Ando et al. 1999 Bandettini et al. 2011 Kirkpatrick et al. 2024. It also became a tool for separation: Katreniak introduced bounded asynchrony for this problem Katreniak 2011, and convergence with limited visibility is the known problem that separates SSYNC from ASYNC for oblivious robots Kirkpatrick et al. 2024 Flocchini et al. 2023. Das et al. argue that full visibility "is not practically feasible" and compare OBLOT, FSTA, FCOM and LUMI under both visibilities Das et al. 2024.

In Suzuki and Yamashita's model and in CORDA robots are transparent: "three or more collinear agents are assumed to be mutually visible" Di Luna et al. 2014. Di Luna, Flocchini, Gan Chaudhuri, Santoro and Viglietta Di Luna et al. 2014 Di Luna et al. 2017 started "the study of computing when visibility is obstructable" for point robots, since "given three collinear agents, the one in the middle blocks the visibility between the other two". Before them obstruction had been studied for fat robots Czyzowicz et al. 2009 Agathangelou et al. 2013 and for robots on a line, according to Di Luna et al. 2014. The basic problem they posed, Complete (Mutual) Visibility, asks the robots to reach a configuration in which all see each other; they solved it in ASYNC without collisions with a constant number of colours Di Luna et al. 2014. Opaque robots with lights then became a line of work on time and colours Vaidyanathan et al. 2015 Sharma et al. 2021 and on pattern formation Bose et al. 2021, and Feletti, Mambretti, Mereghetti and Palano compare the computational power of transparent and opaque robots directly Feletti et al. 2025.

Agmon and Peleg Agmon & Peleg 2006 (SODA 2004) brought crash and Byzantine robots into the Look–Compute–Move model, requiring the algorithm "to successfully gather the nonfaulty robots, independently of the behavior of the faulty ones". They observed that most existing algorithms fail with a single crash, gathered \(n \ge 3\) robots with one crash in SSYNC (Theorem 3.8), proved that three robots cannot gather, or even converge, in SSYNC if one may be Byzantine (Theorem 4.4; hence also in ASYNC, which their abstract states), and gathered \(n \ge 3f+1\) robots with \(f\) Byzantine faults in FSYNC (Theorem 5.10) Agmon & Peleg 2006. Their robots share handedness, see multiplicities (a Look returns a multiset) and make non-rigid moves of at least a fixed distance Agmon & Peleg 2006. The motivation is deployment in adverse environments, where a swarm must "ensure coordination in spite of faulty robots" Clement et al. 2010, and oblivious algorithms are already self-stabilizing, so transient faults come for free and permanent ones are the question Défago et al. 2006. Défago, Gradinariu, Messika and Raipin-Parvédy Défago et al. 2006 extended the feasibility study to bounded schedulers and to probabilistic gathering under crash and Byzantine faults. A crashed robot "simply stops moving" and, since correct robots may also stay still, cannot be identified Efrima & Peleg 2009; crash-tolerant gathering of many faults was obtained with strong multiplicity detection Bouzid et al. 2013 and with weak multiplicity detection Pattanayak et al. 2019.

The classical model is deterministic: in CORDA the Compute phase runs "a deterministic algorithm" Prencipe 2007, so a configuration that looks the same to two anonymous, disoriented robots makes them act alike forever. Randomization was introduced to escape such impossibilities: Dieudonné and Petit Dieudonné & Petit 2009 proved that scattering cannot be solved deterministically in SSYNC and gave a randomized algorithm, and Défago, Gradinariu, Messika and Raipin-Parvédy Défago et al. 2006 studied probabilistic gathering with and without faults (abstract read). Clément et al. note that work around the impossibilities had focused on additional assumptions, "less attention being shown to the use of randomization", and analyse probabilistic gathering and scattering with Markov chains Clement et al. 2010. Yamauchi and Yamashita Yamauchi & Yamashita 2014 formed any pattern in ASYNC without a common coordinate system by randomization, as reported by Bramas & Tixeuil 2016; Bramas and Tixeuil then treated randomness as a resource, using one random bit per cycle for pattern formation Bramas & Tixeuil 2016 and proving that \(n \log n\) random bits are necessary to scatter \(n\) robots Bramas & Tixeuil 2017. What the adversary may learn about the coin flips (adaptive or not) is part of the model and is fixed per paper Efrima & Peleg 2009.

Suzuki and Yamashita's robots are anonymous: "they all execute the same algorithm and they cannot be distinguished by their appearances" Suzuki & Yamashita 1999. With disorientation and determinism, anonymity makes symmetry the central obstacle, and the characterisations of solvable instances are stated in terms of the symmetry of the configuration Suzuki & Yamashita 1999 Dieudonné et al. 2010. Das, Flocchini, Santoro and Yamashita Das et al. 2015 compared anonymous and identified (eponymous) robots on forming sequences of patterns and found that anonymous robots form only sequences of equal symmetricity while identified robots form nearly all, as summarised by Bouzid & Lamani 2011. To measure the gap, Bouzid and Lamani Bouzid & Lamani 2011 imported the homonymous model of Delporte-Gallet et al. Delporte-Gallet et al. 2013, in which \(n\) robots share \(\ell\) labels, into the Suzuki–Yamashita model. Asahiro and Yamashita Asahiro & Yamashita 2025 recast labels as algorithms: robots running one of \(\ell\) algorithms behave like robots with \(\ell\) shared labels, so the minimum algorithm size of a task measures how much identification it needs.