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. 2019. 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. 2023. 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. 2008, 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. 2015.

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. 2016, while \(n \ge 3\) robots with multiplicity detection gather even in ASYNC Flocchini et al. 2016 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. 2019. 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. 2019. 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. 2016. 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. 2019. 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. 2016 and 2 do not Otaka et al. 2026; with internal lights (FSTA), 3 colours suffice in rigid SSYNC Flocchini et al. 2016 Masuzawa 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.

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. 2023 to \(O(\log n)\) Feletti et al. 2023, a time-colour trade-off was reported Pattanayak & Sharma 2024 (abstract only), and \(O(1)\) epochs with \(O(1)\) colours is achievable, which is optimal in both Feletti et al. 2024. Mutual visibility also takes \(O(1)\) epochs with a constant number of colours in ASYNC Sharma et al. 2021. 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. 2026.

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 Masuzawa 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. 2024. Das et al. left open whether ASYNC with lights is stronger than, or incomparable with, FSYNC without lights Das et al. 2016.