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, a torus or a triangular grid) 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).
Triangular grids, FSYNC, perpetual, no chirality, \(\varphi = 1\)
draftOn a triangular grid two robots with three colours and \(\varphi = 1\) explore perpetually under FSYNC, if each robot keeps its own chirality; on a square grid two robots cannot.
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: triangular grid
- The subgraph of the infinite triangular grid (every node of degree six, every face an equilateral triangle of unit side) induced by the nodes on or inside a rectangle, one pair of whose sides is parallel to a family of grid lines; the lines parallel to those sides are its columns. It is anonymous and its dimensions are unknown. Corner nodes have degree two or three and other border nodes degree three, four or five, so the border is seen from within range as on a square grid, but with more cases.
- 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: FSYNC
- FSYNC: in every round every robot executes one atomic Look–Compute–Move cycle.
- 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: no chirality
- Robots share no orientation: on a ring a robot cannot tell its two directions apart; on a grid or torus its snapshot is known only up to rotation and reflection, and the adversary may choose a different transformation in every cycle (self-inconsistent robots, as in Darwich et al. 2023 and Bramas et al. 2026a).
- 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
- one robot, any number of colours and any finite \(\varphi\) (Theorem 3.1)
- a robot far from the border sees nothing, and the adversary sets its local orientation so that it moves between two nodes
- proof sketch only
- two oblivious robots with \(\varphi = 2\), hence also with \(\varphi = 1\) (Theorem 3.2)
- self-inconsistent robots: the adversary sets each robot's local orientation in every round
- proof sketch only
Results, in order of publication
Introductory and current best (algorithm \(A^{VRL}_{123}\), Section 4): the robot coloured \(F\) follows the other, and the pair sweeps the columns one by one, turning at the border. Correctness is argued informally.
Open questions
Is there a proof of perpetual triangular-grid exploration by two robots with \(\varphi = 1\) for self-inconsistent robots, or with two colours?
Notes
Das, Goswami, Mondal and Sau contrast this with the square grid, where two robots with \(\varphi = 1\) and no chirality cannot explore perpetually Rauch et al. 2021 Das et al. 2025c. The paper is a five-page short paper: the impossibilities and the algorithm are given with proof sketches, so the setting stays a draft.
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.