Exploration by luminous robots
Myopic Look–Compute–Move robots with a light of a few colours must visit every node of a ring, grid or torus, and stop or keep visiting; how many robots and colours are needed?
Problem statement and measuresexpand
\(k\) anonymous robots, each with a light that shows one of \(c\) colours, are placed on an anonymous graph \(G=(V,E)\) (a ring, a finite grid or a torus) in an initial configuration designated by the algorithm (positions and colours). Each robot repeats Look–Compute–Move cycles. Look: it sees every node within distance \(\varphi\), with the multiset of colours of the robots on each (so it sees towers, nodes with several robots), and its own colour. Compute: a deterministic function of this snapshot, the same for all robots, gives a new colour and a destination, its own node or a neighbour; the robot sees no identifiers, no ports, and (without chirality) no orientation. Move: it moves there. A fair adversarial scheduler (FSYNC, SSYNC or ASYNC) activates the robots. Terminating exploration: every node is visited by some robot and eventually no robot is enabled. Perpetual exploration: every node is visited infinitely often. With finite \(\varphi\) no algorithm works from every initial configuration, so each result names its initial configurations; some papers also require exclusive executions (no two robots on one node or one edge) or opaque robots, recorded under each result. Measures: the number of robots \(k\) and the number of colours \(c\).
Measures: Robots, number of robots \(k\) needed; Colours, number of colours \(c\) of each light; \(c = 1\) means no usable light (oblivious robots).
Grids, ASYNC, perpetual, chirality, \(\varphi = 1\) (exclusive)
verifiedWith \(\varphi = 1\) no number of exclusive asynchronous robots explores a grid perpetually, whatever the number of colours.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: static graph
- \(G_t=G\) for all \(t\): the edge set never changes.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- Network: grid
- An \(a \times b\) grid (\(n = ab\) nodes; nodes \((i,j)\), edges between nodes at Manhattan distance one); anonymous, with \(a\) and \(b\) unknown. A robot sees the border of the grid when it is within range, since nodes beyond the border are missing from its snapshot.
- Exploration goal: perpetual
- Every node is visited by at least one robot infinitely often; robots never stop.
- Lights (memory and messages): luminous
- LUMI (luminous robots): each robot has a light with \(c\) colours, set at the end of Compute, persistent across cycles, and visible to the robot itself and to every robot within distance \(\varphi\) Das et al. 2016. It is both memory and message. A Look returns, for every node within distance \(\varphi\), the multiset of colours of the robots on it.
- Scheduler: ASYNC
- ASYNC: each robot's Look, Compute and Move phases take finite but unbounded, adversarially chosen time; a robot may Look while others are between phases, so it may move on an outdated snapshot. A robot is always seen on a node (an edge traversal is instantaneous), and its new colour is visible from the end of its Compute phase. The scheduler is fair: every robot is activated infinitely often. Called CORDA in Datta et al. 2013.
- Visibility range: \(\varphi=1\)
- In a Look phase a robot at node \(v\) sees every node at distance at most \(\varphi = 1\) from \(v\) (in the graph metric), with the robots on it, their colours, and how many robots each node holds. It sees no node identifiers and, without chirality, no orientation.
- Chirality: chirality
- All robots agree on the clockwise direction: a snapshot is known up to rotation only (no reflection), so a robot on an axis of symmetry of its view can still tell its two sides apart. Robots still share no North.
- Faults: no faults
- All agents follow the algorithm forever.
- Identifiers: anonymous
- All agents run the same deterministic algorithm on the same input; no agent has a label. Formally the label function is constant: \(\mathrm{id}(a)=\mathrm{id}(b)\) for all agents \(a,b\).
What is known
- any number of robots and colours, even with common chirality (Theorem 2)
- robots may never share a node (the model of the paper)
- the adversary prevents any group of robots from crossing a fence of width two (test of the fence)
Results, in order of publication
No result recorded yet.
Open questions
Is perpetual grid exploration with \(\varphi = 1\) solvable under ASYNC when robots may share nodes (form towers)? Terminating exploration is, with three robots and three colours Nagahama et al. 2022.
Notes
The impossibility assumes, as the model of Bramas et al. 2026 does, that two robots never occupy one node. Terminating exploration in the same scheduler and range is solvable when towers are allowed Nagahama et al. 2022, so co-location is what the impossibility needs.
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.