Exploration by luminous robots

The three schedulers come from robots in the plane (see the plane model); on graphs the asynchronous one was used from the first ring exploration paper Flocchini et al. 2013, and Datta, Lamani, Larmore and Petit compared all three for myopic robots Datta et al. 2013. For myopic robots on graphs the scheduler decides solvability: oblivious robots that see one hop can explore a ring with five robots under FSYNC but not at all under SSYNC or ASYNC Datta et al. 2013, and with two-colour lights the robots needed for perpetual (terminating) exploration of a ring are two (three) under FSYNC against three (four) under SSYNC and ASYNC Ooshita & Tixeuil 2022. Ooshita and Tixeuil ask whether SSYNC and ASYNC still differ for myopic luminous robots, since with full visibility lights make them equivalent Ooshita & Tixeuil 2022 Das et al. 2016. Most grid and torus results are for FSYNC only; asynchronous perpetual grid exploration is the subject of Bramas et al. 2026.

Peleg suggested giving robots "colors, flags or visible indicator lights" and \(O(1)\) bits of stable memory Peleg 2005; Das, Flocchini, Prencipe, Santoro and Yamashita made this the LUMI model, a persistent register visible to all Das et al. 2016, and Flocchini, Santoro, Viglietta and Yamashita split the light into its two roles: FSTA, a light only its owner sees (memory), and FCOM, a light only the others see (communication) Flocchini et al. 2016. On graphs, Ooshita and Tixeuil gave myopic robots a light (the first study of lights for myopic robots, by their account), noting that it "can be used as a constant-space memory" and that robots communicate "by changing their color and moving" Ooshita & Tixeuil 2022. Every exploration result found for graphs uses full lights; the number of colours \(c\) is a measure, and an algorithm with \(c=1\) is an oblivious one. The scale orders the models by what they assume: OBLOT assumes no light; FSTA and FCOM each assume one role of the light and do not imply each other; LUMI assumes both.

Myopia, a fixed visibility range \(\varphi\), replaces the global snapshot of the oblivious-robot literature, which "somewhat contradicts the principle of very weak mobile entities" Ooshita & Tixeuil 2022. Datta, Lamani, Larmore and Petit studied ring exploration by oblivious robots with \(\varphi = 1, 2, 3\) Datta et al. 2013; Ooshita and Tixeuil chose "the weakest assumption for myopia", \(\varphi = 1\) Ooshita & Tixeuil 2022, and later work compares \(\varphi = 1\) with \(\varphi \ge 2\) Ooshita et al. 2025 Nagahama et al. 2022. With a finite range no algorithm explores from every initial configuration (robots that see nobody cannot coordinate), so algorithms start from designated or locally defined configurations Datta et al. 2013 Bramas et al. 2023. Unlimited visibility is the setting of the parent problem.

Chirality was mostly assumed in the plane; an early use on graphs is by Bramas, Devismes and Lafourcade, for infinite grid exploration Bramas et al. 2021 and for perpetual exploration of finite grids Bramas et al. 2023, noting that only "a few works dedicated to discrete environments" assume it and that it changes the number of robots needed Bramas et al. 2023. Nagahama, Ooshita and Inoue give terminating grid algorithms with and without it Nagahama et al. 2022; without it, perpetual grid exploration needs three robots Rauch et al. 2021 (as reported in Darwich et al. 2023). Ring results assume an unoriented ring.

Both goals come from the oblivious-robot literature: terminating exploration of rings Flocchini et al. 2013 and grids Devismes et al. 2012, and perpetual (often exclusive) exploration, which models patrolling Bramas et al. 2023. Ooshita and Tixeuil studied both for myopic luminous robots Ooshita & Tixeuil 2022. The two goals are incomparable: a terminating algorithm stops, and a perpetual one need never detect that it is done, so the scale puts them side by side above "both". In this literature the impossibility proofs for perpetual exploration show that some node is never visited, which then also rules out terminating exploration Nagahama et al. 2022, and perpetual exploration never needed more robots than terminating exploration.

Rings were the first graphs explored by oblivious robots Flocchini et al. 2013 and by myopic ones Datta et al. 2013 Ooshita & Tixeuil 2022. Finite grids followed for myopic luminous robots in perpetual Bramas et al. 2023 and terminating Nagahama et al. 2022 form, and tori, whose missing border removes the landmark that grid algorithms use to turn, in Darwich et al. 2023. Infinite grids and 3D grids are studied in papers listed under further reading. This axis replaces the model's topology axis because the torus is not one of the model's values.