Weak robots in the plane

Since the work of Suzuki and Yamashita Suzuki & Yamashita 1999, the theory of robots in the plane has asked which minimal assumptions let a team solve a task, rather than how a capable robot should solve it Flocchini et al. 2023. A robot is a point that repeats Look-Compute-Move cycles; it is anonymous, runs the same algorithm as everyone else, has its own coordinate system, and in the standard model OBLOT it is also oblivious and silent Flocchini et al. 2019b. Dieudonné, Petit and Villain state the motive plainly: "The motivation behind such a weak and unrealistic model is the study of the minimal level of ability the robots are required to have in the accomplishment of some basic cooperative tasks in a deterministic way" Dieudonné et al. 2008.

The introductions also give practical reasons. Many simple robots are cheaper and easier to extend than one strong robot Bandettini et al. 2011; silent robots can be deployed where communication is impossible or jammed, under water or in a military setting Di Luna et al. 2014; and robots that do not know \(n\) make the system "scalable and open to robot insertions or removals" Feletti et al. 2023a. Flocchini, Prencipe, Santoro and Viglietta summarise the resulting research programme: the literature has "almost exclusively focused on very simple entities operating in strong adversarial conditions", robots that are anonymous, autonomous, oblivious, disoriented and non-rigid Flocchini et al. 2017.

Almost all computability results in this model concern geometric pattern formation: the robots must reach, and stay in, a configuration similar to a given pattern Flocchini et al. 2017. As Flocchini et al. recount, Suzuki and Yamashita observed that whether a pattern can be formed depends on the symmetricity of the pattern and of the start, so the only patterns that might be formable from every start are a point and a regular polygon Flocchini et al. 2017. These two became the reference problems. A point is gathering: without multiplicity detection and without extra assumptions, oblivious robots cannot gather Prencipe 2007, while with weak multiplicity detection \(n \ge 3\) asynchronous robots gather from any start Cieliebak et al. 2012. The regular polygon is uniform circle formation. Défago and Konagaya conjectured that the last step, spreading robots evenly on a circle, has no deterministic finite-time solution; Dieudonné, Petit and Villain proved the conjecture and still formed the circle in SSYNC by another route, for \(n \notin \{4, 6, 8\}\) Dieudonné et al. 2008. In ASYNC the question stayed open until Flocchini, Prencipe, Santoro and Viglietta solved it from every start of distinct points Flocchini et al. 2017, with the square (\(n = 4\)) handled in Mamino & Viglietta 2016; they conclude that for pattern formation "asynchrony is not a computational handicap" and that chirality and rigidity are "computationally irrelevant" Flocchini et al. 2017.

Arbitrary patterns connect formation to symmetry breaking. Flocchini, Prencipe, Santoro and Widmayer posed arbitrary pattern formation for asynchronous oblivious robots Flocchini et al. 2008a, and showed, as Dieudonné, Petit and Villain quote, that forming arbitrary patterns implies leader election for \(n \ge 3\) Dieudonné et al. 2010. The converse holds with chirality for \(n \ge 4\) Dieudonné et al. 2010 and, after a careful re-examination of earlier proofs, without it Cicerone et al. 2019; which configurations admit a leader is characterised by Dieudonné, Levé, Petit and Villain Dieudonné et al. 2013. Later formation problems change one physical assumption at a time. Mutual visibility drops the assumption, shared by all earlier models, "that visibility is unobstructed" Di Luna et al. 2014: opaque robots must reach a position in which no three are collinear Di Luna et al. 2017. Pattern sequences ask the robots to form patterns one after another Das et al. 2015b.

Because robots do nothing but look and move, the main adversary is time. In FSYNC all robots act in every round; in SSYNC a fair adversary picks which robots act in each round; in ASYNC each phase takes a finite but unpredictable time Das et al. 2016. Asynchrony hurts because robots "can be seen while moving" and compute "on the base of obsolete information" Cicerone et al. 2019; Flocchini, Santoro, Sudo and Wada name as "one of the strongest debilitating effects of unrestricted asynchrony" that "a robot, when looking, cannot detect if another robot is still or moving" Flocchini et al. 2023. The adversary also chooses how far a robot moves, subject to a minimum distance \(\delta\) (non-rigid moves) Flocchini et al. 2017.

Rendezvous is the separating example: two oblivious robots meet trivially in FSYNC but cannot meet in SSYNC Flocchini et al. 2016a, while \(n \ge 3\) robots with multiplicity detection gather even in ASYNC Flocchini et al. 2016a Cieliebak et al. 2012. Between SSYNC and ASYNC lie finer schedulers, which make some of the phases atomic (LC-atomic, CM-atomic, M-atomic ASYNC), and below SSYNC lie restricted ones such as RSYNC and the sequential schedulers Flocchini et al. 2023. Weakening the adversary can be decisive: under any sequential scheduler oblivious robots form every pattern from every start, except a point, which needs weak multiplicity detection Flocchini et al. 2026.

The luminous model, which Das et al. attribute to a suggestion of Peleg, gives each robot a light with a constant number of colours that persists between cycles and is seen by all robots; a robot can therefore both remember and communicate a constant number of bits Das et al. 2016. Das et al. asked what additional power "would allow the robots to overcome the inherent difficulties and weaknesses of the ASYNC setting". Their answer: with 5 colours ASYNC robots simulate any SSYNC algorithm, two robots with 4 colours meet in ASYNC, and with lights the difference between SSYNC and ASYNC disappears Das et al. 2016.

Lights then split into two capabilities. Flocchini, Santoro and Wada ask directly, "is it better to remember or to communicate?" Flocchini et al. 2019b. In FSTA the light is seen only by its owner (finite state, silent); in FCOM only by the others (finite communication, oblivious) Flocchini et al. 2019b. Flocchini, Santoro, Viglietta and Yamashita had already shown that rendezvous does not need both: either kind of constant memory suffices under suitable conditions Flocchini et al. 2016a. Under FSYNC, LUMI and FCOM are equivalent and stronger than FSTA, which is stronger than OBLOT; under SSYNC, FCOM and FSTA are incomparable Flocchini et al. 2019b. Under asynchrony, SSYNC is strictly stronger than ASYNC for OBLOT, FCOM and FSTA, and only LUMI removes the difference Flocchini et al. 2023. These separations mostly assume chirality and rigid moves. For two robots, LUMI, FCOM and FSTA coincide under FSYNC Kitamura et al. 2025, a preprint.

Once lights were known to help, the number of colours became a resource. For two robots with full lights, the count fell from 4 Das et al. 2016 to 3, optimal for algorithms that look only at colours Viglietta 2013, and to 2, which is optimal, in ASYNC with non-rigid moves and arbitrary initial colours Heriban et al. 2018. With external lights (FCOM), 3 colours suffice in SSYNC Flocchini et al. 2016a and 2 do not Otaka et al. 2026; with internal lights (FSTA), 3 colours suffice in rigid SSYNC Flocchini et al. 2016a Wada et al. 2026. For \(n \ge 3\) robots without multiplicity detection, full lights gather with 2 colours in SSYNC Terai et al. 2023 and with 3 in ASYNC Nakai et al. 2021. Opaque robots reach mutual visibility with 2 colours in rigid SSYNC, which is optimal Di Luna et al. 2017, and 2 colours also suffice with non-rigid moves in SSYNC, with rigid moves in ASYNC, and with non-rigid moves in ASYNC when the robots agree on one axis Sharma et al. 2015b.

Colours are then traded against time. For uniform circle formation by opaque luminous robots in ASYNC, the time fell from \(O(n)\) epochs Feletti et al. 2023b to \(O(\log n)\) Feletti et al. 2023a, Pattanayak and Sharma traded colours for time, with \(O(x)\) epochs and \(O(n^{1/2^x})\) colours, hence \(O(1)\) epochs with \(O(\sqrt{n})\) colours or \(O(\log\log n)\) epochs with \(O(1)\) colours, for rigid robots Pattanayak & Sharma 2024, and \(O(1)\) epochs with \(O(1)\) colours is achievable, which is optimal in both Feletti et al. 2026a. Mutual visibility also takes \(O(1)\) epochs with a constant number of colours in ASYNC Sharma et al. 2021a. With lights and a sequential scheduler, robots can form any sequence of patterns up to a length fixed by the number of colours Feletti et al. 2026c.

Whether two robots with internal lights (FSTA) can meet in ASYNC at all is open, and in rigid ASYNC the best count for external lights is 6 colours against a lower bound of 3 Wada et al. 2026 Otaka et al. 2026. Whether 2 colours suffice for gathering \(n \ge 3\) robots in ASYNC is open Nakai et al. 2021. For uniform circle formation, the exact number of colours for \(O(1)\) time, and whether oblivious robots can do it in \(O(1)\) epochs, are open Feletti et al. 2026a. Das et al. left open whether ASYNC with lights is stronger than, or incomparable with, FSYNC without lights Das et al. 2016.

Further reading.

What weak robots can compute. A few oblivious robots with limited visibility can together hold real numbers and simulate a rigid robot with memory Di Luna et al. 2021; oblivious robots that move on a graph in synchronous rounds compute functions of their initial configuration, and several classes of such systems compute every finite function Flocchini et al. 2016c. Asynchronous robots with lights and limited visibility can simulate SSYNC algorithms that obey visibility constraints Flocchini et al. 2020, a preprint. A robot can store information in its own position, even with non-rigid moves if it has \(O(1)\) bits and can move along circles, which suffices to map a polygon Bose et al. 2019; a robot that only sees the distance to the nearest end of a segment can settle at its midpoint under small relaxations Monde et al. 2017. Robots that cannot steer at all but bounce off each other on a ring or a segment can still discover every robot's initial position, except in characterised configurations Czyzowicz et al. 2015b. Robots that form pairs and recognise their partner, a model proposed in a preprint, solve perpetual marching and the gathering of seven pairs under ASYNC Kim et al. 2020, and proof assistants help design correct protocols for new tasks Balabonski et al. 2021. On graphs, D'Emidio, Di Stefano, Frigioni and Navarra rank the schedulers for oblivious robots as FSYNC above SSYNC above ASYNC, and show that FSYNC robots and ASYNC robots with a light of \(O(1)\) colours are incomparable there D'Emidio et al. 2016 D'Emidio et al. 2018, as SSYNC luminous and FSYNC oblivious robots are in the plane Flocchini et al. 2019b. They also note that the simulation of FSYNC by ASYNC robots with three colours and one stored snapshot (Theorem 4.4 of Das et al. 2016) synchronises the Looks but not the Moves, so it does not cover tasks that forbid collisions D'Emidio et al. 2018; a later claim that ASYNC robots with limited visibility, a common compass, four colours and one stored snapshot execute every FSYNC algorithm rests on an informal proof and does not address this point Das et al. 2021c. A certified proof in Coq shows that oblivious ASYNC robots on a graph that move continuously along edges, but whose sensors report positions only at nodes, have exactly the executions of robots that jump from node to node Balabonski et al. 2019. Other tasks test the same models: ASYNC robots with limited visibility and a common compass, spread densely enough over an obstacle-free rectangle, paint all of it Das & Mukhopadhyaya 2018; and a swarm can detect that some robot has crashed with lights under FSYNC or under a scheduler that activates every robot once per epoch, one at a time, and with external lights under FSYNC, while telling which robots crashed is impossible in all twenty models studied unless the adversary that decides crashes is restricted Clemente & Feletti 2026. These papers were read for the backfill of October 2026 and are not yet placed in settings.