Exploration by luminous robots

\(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).