WorksComputer Science
Autonomous Mobile Robots on a Computing Field
Abstract
We introduce CABOT, a computational model for autonomous mobile robots in which the discrete plane the robots operate on is not a passive stage but an active computing medium. In the classical Look-Compute-Move (LCM) model every increase in computational capability is obtained by strengthening the robots themselves, with lights, memory or wider visibility, at a cost paid once per robot. CABOT strengthens the environment instead: each cell of the grid holds a state from a finite set Q, the states evolve synchronously under a uniform local rule that also senses whether a robot stands on the cell, that is, the floor is a cellular automaton, and the Look operation returns the states of the visible cells in addition to the positions of the visible robots. The robots are as weak as we can make them: oblivious, silent, lightless, myopic with visibility range 1, without multiplicity detection and unable to write to the floor. The number of field states |Q|, rather than any robot capability, becomes the measure of the resources required. On an inert floor (|Q| = 1) such robots can neither form a line, nor gather from scattered positions, nor explore a grid. We show that a handful of states changes this. Line Formation from connected configurations is solvable with four states, and field-silently, so that the floor also reaches a fixed point, with five. Gathering from arbitrary, possibly disconnected, configurations is solvable with three states and Line Formation from arbitrary configurations with six; we prove that neither can be solved field-silently with any number of states. A single robot explores every finite grid forever with four states and every torus with two, which is optimal. Further rule sets, validated by simulation only, equalize the spacing of robots on a row, fill a pattern painted on the floor and guide robots through a maze, and indicate the range of the model.
Introduction
Background
A swarm of autonomous mobile robots is commonly studied through the Look-Compute-Move () model [1, 2]. Robots are points in the plane, anonymous and indistinguishable, all executing the same algorithm (i.e., homogeneous); each repeatedly takes a snapshot of its surroundings (Look), computes a destination (Compute), and moves there (Move). The enduring appeal of the model lies in how little it assumes. Robots have no identifiers, no memory that persists across cycles, and no explicit means of communication. Every positive result is therefore a statement about how much coordination can be extracted from almost nothing.
The price of this minimalism is a long list of impossibility results [1, 3]. Symmetric configurations cannot be broken by identical deterministic robots; oblivious robots cannot accumulate the history a task requires; and myopic robots, which see only a bounded neighborhood, cannot obtain the global view that many formations implicitly need.
The standard response has been to give the robots more. Luminous robots () carry an externally visible light of constant size [4]; the sub-models and separate its use as internal memory from its use as communication [5]; other work enlarges the visibility radius or restricts the scheduler. Together these form a well-understood hierarchy of models. What they all share is that capability is added per robot: a swarm of robots requires copies of the additional hardware, and the robots themselves must become more complex, more expensive, and less disposable.
Our Approach: Let the Floor Compute
We take an orthogonal route. Rather than asking what must be added to the robots, we ask what must be added to the environment so that nothing has to be added to the robots.
Real robots never move in a vacuum. Automated warehouse floors already carry fiducial markers and RFID grids that vehicles read as they travel; social insects coordinate not by direct communication but by depositing and sensing traces in their surroundings, a mechanism known as stigmergy [13]. In both cases the environment is part of the algorithm. The LCM model, however, treats the plane as an inert set of coordinates.
We therefore promote the environment to a first-class computational entity and call the resulting model CABot (robots on a cellular automaton field). The grid on which the robots operate is itself a cellular automaton: every cell carries a state from a finite set , and all cells update synchronously under a single uniform transition rule whose input is the state of the cell, the states of its four neighbors, and the presence or absence of a robot on the cell itself. A robot’s Look operation returns, in addition to the robot positions within its visibility range, the states of the cells within that range. Informally: the floor is computing.
Three properties distinguish this from strengthening the robots. Memory is attached to places, not to robots: a light travels with its carrier and vanishes when the robot leaves, whereas a field state stays where it was produced, survives that departure, and can be read by a different robot arriving later. Information propagates without being carried: in the plain LCM model information travels only as fast as the robots move or as far as they see, while in CABOT it spreads one cell per step on its own, which is what lets robots of visibility range 1 act on circumstances they cannot see. The field is minimal infrastructure: it is anonymous and uniform, its rule is purely local, and it needs no identifiers, no broadcast and no connectivity beyond nearest neighbors, so the question we ask is not what an arbitrarily powerful environment can do but how little environmental support suffices. Accordingly the robots are fixed at the weakest setting throughout the paper, and the single resource we measure is the number of field states.
Field-Silence
Once the environment computes, the usual notion of termination is too weak: an algorithm may halt the robots in the desired configuration while the cells beneath them keep changing forever, so the field still consumes energy and an observer of the field cannot tell that the computation is over. We therefore call an algorithm terminating if every execution reaches a configuration in which no robot moves again, and field-silent if it reaches one in which no cell changes state again either, by analogy with silent self-stabilization [25]. The distinction is not vacuous: our four-state Line Formation algorithm is terminating but not field-silent, since two cells at the ends of the formed line oscillate forever, and removing that obstruction costs one additional state. For robots that start far apart the distinction is even sharper: we show that no algorithm whatsoever can make them meet field-silently.
Our Contribution
We formalize CABOT and study three fundamental problems in it, Line Formation, Gathering and Exploration, with robots that are as weak as the setting permits: oblivious, silent, lightless, myopic with visibility range 1, without multiplicity detection, agreeing on directions and operating fully synchronously (FSYNC). Table 1 summarizes the results.
The model. We define CABOT as an extension of LCM in which measures the resources supplied by the environment, and we introduce field-silence as a refinement of termination that is specific to models with an active environment (§ 3). With the model is the plain one, in which Line Formation from connected configurations, Gathering and Line Formation from arbitrary configurations, and Exploration are all unsolvable (Proposition 1).
Line Formation from connected configurations. Four states suffice on the infinite grid; the algorithm terminates but is not field-silent (§ 4). Five states suffice for a field-silent solution, and we identify the mechanism, a landing mark produced by decay rather than by a persistent predicate, that makes the four-state algorithm non-silent (§ 5).
Gathering from arbitrary configurations. Robots that start on arbitrary distinct cells, with no connectivity whatsoever, gather with three states (§ 6). We also prove that no algorithm, with any number of states, solves Gathering or Line Formation from arbitrary configurations field-silently (Proposition 4).
| Problem | Initial configuration | Arena | Guarantee | Reference | |
| Line Formation | connected | 4 | terminating | Theorem 1 | |
| Line Formation | connected | 5 | field-silent | Theorem 2, Prop. 3 | |
| Gathering | arbitrary | 3 | terminating | Theorem 3 | |
| Line Formation | arbitrary | 6 | terminating | Theorem 4 | |
| Gathering, Line Formation | arbitrary | any | never field-silent | Prop. 4 | |
| Exploration | one robot | torus, bounded grid | 4 | perpetual | Theorem 5 |
| Exploration | one robot | torus | 2 | perpetual, optimal | Theorem 6 |
| all of the above | 1 | impossible | Prop. 1 |
Table 1. Summary of results. All robots are oblivious, silent, lightless and myopic with visibility range 1, and operate under FSYNC.
Line Formation from arbitrary configurations. Six states suffice (Section 7). The algorithm combines the region painting of the gathering algorithm with a landing zone, a cell that knows a robot is directly above it, which makes the approach collision-free although the converging robots cannot see each other.
Exploration. A single robot visits every cell of every finite torus and of every bounded grid infinitely often with four states, the floor acting as a rotor-router; on tori two states suffice, which is optimal (Section 8).
Further examples. Three more rule sets, validated by simulation only, illustrate other uses of the floor: as a ruler that spaces robots equally on a row, and as an excitable medium that calls robots to target cells painted on the floor and routes them through a maze (Section 9).
The state counts are small enough to be striking: four states amount to a cell being blank, occupied, or carrying a trace at one of two levels of freshness. The computational capability that would otherwise demand a light or a memory on every robot is recovered from a handful of states underfoot.
Organization
Section 2 surveys related work. Section 3 defines CABOT, the problems, and what an inert floor cannot do. Sections 4 and 5 present Line Formation from connected configurations with four and with five states. Sections 6 and 7 treat Gathering and Line Formation from arbitrary configurations. Section 8 treats Exploration, Section 9 the further examples, and Section 10 concludes with open problems.
Related Work
The LCM hierarchy. The model is due to Suzuki and Yamashita [1], who established the role of symmetry in its impossibility results; see [2] for a survey. Because so much is impossible for oblivious, silent, disoriented robots, later work adds capability to the robots: a persistent visible light (LUMI [4] and its sub-models FSTA, FCOM [5]), axis agreement, multiplicity detection, or a stricter scheduler. This is a hierarchy along one axis, how much each robot is given. We add a second.
Myopic robots on grids. Gathering under limited visibility was studied in [6]; on discrete spaces the radius is a sharp parameter, since with radius 1 a robot sees only its four neighbors and connectivity must be assumed. Gathering on grids has been studied with global visibility [7] and with local visibility for connected swarms [8], and arbitrary pattern formation on an infinite grid by oblivious robots in [9]. With visibility 1 and no lights, a robot that loses sight of all others can never move again; robots that start out of sight of each other, as in Sections 6 and 7, are beyond the reach of the plain model altogether.
Communicating through the environment. Whiteboard models [10] let an agent read and write bounded information at a node, and pebble models [11] let it drop markers; in both the environment is passive, nothing happening at a node unless an agent stands on it. Ant-inspired covering algorithms let robots leave evaporating traces [12]. Stigmergy is active in our sense, pheromones diffusing and evaporating while the ants are elsewhere [13]; it is a widespread swarm-robotics heuristic but has, to our knowledge, no solvability theory.
Rotor-routers. In the rotor-router model [14], also known as the Propp machine or edge ant walk [15], every node holds a pointer that cycles through its ports, and an agent leaves along the pointer, which then advances. The walk is deterministic, covers every finite graph and locks into an Eulerian circuit [15, 16, 17]. In the literature the pointer is part of the system by definition; in CABOT it is one particular field, and § 8 shows that the floor can run it for an oblivious robot that cannot write.
Cellular automata and embedded agents. A single agent reading and writing the cells it visits is classical, Langton’s ant being the canonical example [19], but such systems are studied as dynamical systems rather than as distributed algorithms. Excitable media, of which the Greenberg–Hastings automaton [20] is the standard discrete model, propagate waves that § 9 uses as a signalling layer. Programmable matter, such as Amoebot [21], SILBOT [22], or Pairbot [23], places computing entities on a lattice, but there the particles are the medium; in our model the field and the robots are heterogeneous substrates and the empty cells do most of the work.
Silence. Dolev et al. [25] call a stabilizing algorithm silent when its communication registers eventually stop changing. In the robot literature the analogue concerns the robots only, the environment having nothing to change; once it computes the two separate, and § 4 and § 6 show the separation is real.
In short, memory resides in the environment rather than the robots, that environment is active rather than passive, and the measured resource is rather than a per-robot capability.
The CABot Model
We describe the two components of the system, the field and the robots, then the cycle that couples them, and finally the problems.
The Field
The default arena is the infinite two-dimensional grid , whose elements we call cells. We write for the four cardinal directions and, for a cell , we let , , and . The neighborhood of is the von Neumann neighborhood .
A cellular automaton field (CA field) is a triple where is a finite set of states, is the quiescent state, and
is the transition function. A cell in state whose four neighbors are in states and which does or does not carry a robot, indicated by , moves to state . All cells apply simultaneously.
Three features matter. The field is anonymous and uniform: one governs every cell, cells have no identifiers or coordinates and see only their four neighbors, so this is the weakest active infrastructure we could place under the robots, not a powerful oracle. A cell detects a robot only on itself: the last argument of refers to , never to , so a cell learns of a robot on a neighbor one round later, through the state that neighbor takes in response; this delay is why several algorithms below must distinguish a robot that has just arrived from one standing still. Finally we require , so that an untouched region stays quiescent and at every time only finitely many cells are non-quiescent.
Finite arenas. Exploration (§ 8) is studied on finite arenas: the torus , in which is computed modulo , and the bounded grid , in which a cell on the border lacks some neighbors. On a bounded grid a missing neighbor is read as quiescent and unoccupied, by and by the robots alike, and a robot that attempts to move to a missing cell stays where it is.
The Robots
A set of robots occupies cells. They are anonymous, identical and deterministic, oblivious, silent and lightless, and myopic with visibility range 1. They agree on the four directions and on nothing else: no common origin, no knowledge of . Several robots may stand on the same cell; a cell only senses whether it is occupied, and a robot only senses whether a neighboring cell is occupied, so there is no multiplicity detection.
Crucially, robots have no write operation: every change in the field is produced by , which merely observes occupancy. A robot here is exactly an OBLOT robot whose Look returns more, which distinguishes CABOT from whiteboard and pebble models, where writing is an action of the agent.
The view of a robot standing on cell when the field assignment is and the set of occupied cells is is
an element of . An algorithm is a function , meaning stay. We abbreviate , and for , and use the same abbreviations for the arguments of . A solution to a problem is a pair , and its cost is .
The Cycle
Robots operate in the fully synchronous scheduler (FSYNC): all robots are activated in every round and execute their cycle in lockstep. A round consists of four phases. In round , with occupied cells and assignment : (Look) every robot on obtains ; (Compute) it evaluates ; (Move) every robot with moves to , rigidly and by at most one cell, yielding ; and (Update) every cell applies using the old states and its new occupancy, .
Phase Update reads and writes , so the field update is synchronous in the usual cellular-automaton sense. Phases Look and Update are the only points of contact between the two layers: the robots read the field, and the field reads the robots’ positions.
A configuration is together with the number of robots on each occupied cell, and the execution determined by is unique since both are deterministic and the scheduler is FSYNC. Robots that share a cell have the same view and therefore move together from then on. An algorithm is collision-free if always, that is, if no two robots ever share a cell.
Initial Configurations
Initially and the robots occupy distinct cells. We call such an initial configuration arbitrary, and connected if in addition is connected under the neighborhood relation. Connectivity is the standard assumption for myopic robots: one of visibility range 1 that sees no one has nothing to act on. In CABOT it can be dropped, because the field carries information between robots that cannot see each other.
Where connectivity is assumed, it is assumed of only: our algorithms do not preserve it, and in most executions the swarm disconnects and later re-forms. A myopic algorithm in the plain LCM model must maintain connectivity, a robot losing sight of the swarm being lost to it; in CABOT the trace in the cells keeps a separated robot coupled to the rest, so the visibility graph may break without harm.
Termination and Field-Silence
An execution is terminating if for all for some , and field-silent if for all , so that the whole system is a fixed point. An algorithm has one of these properties if all its executions do. Field-silence implies termination; the converse fails, as Section 6 and 6 show.
The Problems
A set of cells is a line if it consists of consecutive cells of a single row or of a single column, that is, if or for some .
Definition 1 (Line Formation). An algorithm solves Line Formation from connected (respectively arbitrary) configurations if it is collision-free and, for every and every connected (respectively arbitrary) initial configuration of robots, the execution is terminating and the set of occupied cells it terminates in is a line. It solves the problem field-silently if in addition every execution is field-silent.
Definition 2 (Gathering). An algorithm solves Gathering from arbitrary configurations if, for every and every arbitrary initial configuration of robots, the execution is terminating and terminates with all robots on a single cell.
Definition 3 (Exploration). Let be a torus or a bounded grid. An algorithm solves Exploration of if a single robot, started on any cell of , visits every cell of infinitely often. The cover time is the number of rounds after which every cell has been visited at least once.
Line Formation forbids multiplicity and Gathering demands it; Exploration is a non-terminating task, for which the relevant measure besides is the cover time.
What an Inert Floor Cannot Do
With the field carries no information and CABOT is the plain model of oblivious myopic robots on a grid. A view is then the set of directions in which a neighbor is occupied, and an algorithm is one of the finitely many maps .
Proposition 1. Let .
(i) No algorithm solves Line Formation from connected configurations.
(ii) No algorithm solves Gathering, or Line Formation, from arbitrary configurations.
(iii) No algorithm solves Exploration of a torus with , or of a bounded grid with at least two cells.
Proof. For (i) and (ii), termination with forces , so a robot with no neighbor never moves.
(ii) Two robots on non-adjacent cells both have the view forever and never move, so they neither meet nor become adjacent.
(i) Only the eleven views with at most two occupied neighbors occur when , and . The obstacle is easy to see for the natural algorithms: if a robot with a single neighbor stays, which keeps the two-robot lines in place, then in an L-shaped configuration of three robots only the corner robot may move, and each of its moves collides with an arm or leaves all three robots without a neighbor. Other algorithms rotate a pair before stopping it, and the complete case analysis is finite but tedious, so we carried it out by exhaustive enumeration: of the assignments to the four single-neighbor views, exactly nine make both connected configurations of two robots terminate in a line without a collision, and for each of them none of the assignments to the six two-neighbor views forms a line from all six connected configurations of three robots. Hence every map fails on a connected configuration of at most three robots.
(iii) A single robot has the same view in every round and therefore takes the same action in every round. If it visits one cell. Otherwise, on a torus it stays in one row or column and visits at most cells; on a bounded grid it walks to the border and stays there forever.
Remark 1. Proposition 1 deliberately says nothing about Gathering from connected configurations. There an inert floor appears to suffice: the field-free rule “move east if the eastern or the northern neighbor is occupied; otherwise move south if the southern neighbor is occupied; otherwise stay” gathers every connected configuration of at most 11 robots (all 185,416 of them, checked exhaustively, each within rounds) and every random connected configuration of up to 800 robots that we tried. This is why we study Gathering from arbitrary configurations, where the field is indispensable by Proposition 1(ii).
Line Formation with Four States
In this section and the next the initial configuration is connected. Let with quiescent state . Fix a connected of robots and write
Call row the floor. Robots fall towards it and slide east along it, accumulating into one row; marks a robot and are a trace of decreasing freshness left in the cells beside it (Figure 1).

Figure 1. An execution of the four-state algorithm, . Discs are robots; shading is the field state (white , light , dark ; a cell under a robot is ). The top robot slides east at and falls at . From the robots never move again, yet the two cells at the ends of the line keep swapping and : terminating, not field-silent (Prop. 2).
The Rules
Define the decay map , , . The field transition is given by the first applicable clause:
| Rule | Condition on cell | Next state |
| F1 | carries a robot | |
| F2 | ||
| F3 | otherwise |
Table 1 (PDF p. 6).
The robot algorithm is likewise the first applicable clause:
| Rule | Condition | Action |
| R1 | move E | |
| R2 | move S | |
| R3 | otherwise | stay |
Table 2.
F2 is tested before F3, so a cell beside a robot is refreshed only from or and from it decays; the trace beside a stationary robot therefore alternates, which Lemma 2 turns into the timing device R1 and R2 rely on.
Basic Invariants
Lemma 1 (Marks are occupancy). For every and every cell , if and only if .
Proof. F1 assigns exactly to occupied cells, and F2, F3 never produce .
Lemma 2 (Trace oscillation). Let be unoccupied throughout rounds and suppose some cell of is occupied throughout these rounds. Then for every we have and ; that is, alternates between and with period 2 and never returns to .
Proof. By Lemma 1 the occupied neighbor is at at every round , and at every such round. Hence at every update from round on, F2 turns into , and F3 turns into . So for , and the two values alternate.
Lemma 3 (The floor is frozen). For every : (i) no robot occupies a cell of a row below ; (ii) every cell of row is in state ; and (iii) no robot in row ever moves.
Proof. Simultaneous induction on . Both (i) and (ii) hold at since . Assume them at . For (iii), a robot at cannot apply R2 because , and cannot apply R1 because row is unoccupied, so fails. Since R2 is the only rule that decreases a robot’s row, and it is unavailable in row , no robot enters row , giving (i) at . Then no cell of row is occupied at round ; the horizontal neighbors of such a cell lie in the same row and are in state , so F2 does not apply and F3 keeps at ; this gives (ii) at .
Lemma 4 (Collision-freedom). for every ; no two robots ever occupy the same cell.
Proof. A robot enters a cell only from by R1 or from by R2, and both rules require to be unoccupied at the Look of that round, so no robot enters a cell that is occupied at the beginning of the round. Two robots applying R1 in the same round have distinct sources and hence distinct targets, and likewise for R2. The only remaining possibility is that one robot applies R1 from while another applies R2 from . But R1 requires and R2 requires , and .
Collision-freedom is enforced neither by priorities nor by symmetry breaking, but by the two movement rules reading different states of the same cell: are at once a landing signal and a mutual exclusion mechanism. The same idea, in different guises, makes all our multiplicity-free algorithms safe.
Correctness
Lemma 5 (Landing is adjacent). If a robot moves into a cell of row in round , then at least one of is occupied at round .
Proof. By Lemma 3(iii) the move is an R2 move from , so . A cell reaches only by F3 from , and either by F2, which needs a horizontal neighbor at , or by F3 from , which by Lemma 1 needs to have been occupied. The latter is impossible, since by Lemma 3(iii) a robot that stood on would still be there. Hence F2 applied to two updates earlier, so a horizontal neighbor of was occupied then, and by Lemma 3(iii) it still is at round .
Lemma 6 (The west end is pinned). No robot ever occupies a cell with , and the bottom-most robot of column never applies R1.
Proof. R1 and R2 move east and south only, so is non-decreasing for every robot and no robot leaves the half-plane ; in particular no robot ever enters column . Let be the robot of column with the smallest row. R1 requires , and lies in column below , hence is unoccupied.
Theorem 1. The four-state algorithm solves Line Formation from connected configurations. Moreover every execution terminates in
Proof sketch. By Lemmas 3 and 6 the floor is absorbing and nothing passes west of . Progress: if the robots are idle then by Lemmas 1 and 2 the field becomes periodic with period at most 2 within three rounds, so if no robot moves in the two following rounds none ever will; conversely a static configuration with a robot above the floor enables R1 or R2 at the highest such robot. Shape: by Lemma 5 a robot joins the floor only next to an occupied floor cell, so the occupied part of the floor is a union of intervals growing only at their ends; connectivity of forces a robot into every column between two occupied floor cells, supplying exactly the robots needed to merge them. By Lemma 6 the bottom-most robot of column only falls, so it rests at ; with from Lemma 4 the claim follows.
Corollary 1. Every execution terminates within rounds.
Proof. Each is non-decreasing and each non-increasing, so the total number of moves is . By Theorem 1 and , and is at most the height of , hence at most . So there are at most moves, and by the progress argument above a constant number of rounds passes between consecutive ones.
The Algorithm Is Not Field-Silent
Proposition 2. The four-state algorithm is terminating but not field-silent. In the terminal configuration exactly two cells, namely and , change state forever, alternating between and with period 2; every other cell is fixed.
Proof. Termination is Theorem 1. In every occupied cell is permanently by Lemma 1. An unoccupied cell is refreshed by F2 only if one of is occupied, that is, only if lies in row and is horizontally adjacent to the line; the only such cells are and , and by Lemma 2 both alternate between and forever. Every other unoccupied cell has no horizontal neighbor in state , so F3 applies at every round and it reaches within three rounds and stays there.
The obstruction is structural. The landing signal that R2 waits for is produced by decay: a cell must fall from to for a robot above it to move in. As long as a robot stands beside that cell, F2 keeps pushing it back up to , and the two rules chase each other forever. The next section shows that separating the two roles the trace plays, a persistent “you may land here” predicate and a transient timing signal, removes the oscillation at the cost of a single extra state.
Field-Silent Line Formation with Five States
By Proposition 2 the pair is asked to do two incompatible jobs: to be a persistent predicate marking a legal landing site for as long as it is one, and a transient signal, since R2 waits for the decay while R1 reads and that phase otherwise is what keeps the rules from colliding. A persistent predicate beside a stationary robot cannot decay; a transient one must. We separate the jobs: the landing predicate becomes unconditional, and the timing moves onto the robots’ own cells. One extra state pays for both.
The Rules
Let and . A cell in carries a robot, if it arrived last round and otherwise; say the cell is a legal landing site, while the reason holds and for one round after. The field transition is:
| Rule | Condition on cell | Next state |
| G1 | carries a robot and | |
| G2 | carries a robot | |
| G3 | or | |
| G4 | ||
| G5 | ||
| G6 | otherwise |
Table 5 (PDF p. 9).
| Rule | Condition | Action |
| S1 | move E | |
| S2 | move S | |
| S3 | otherwise | stay |
Table 6 (PDF p. 9).
Three changes matter. The landing predicate is unconditional: G3 fires whatever the cell’s state, whereas F2 refreshed only from , , so a cell beside a motionless robot sits at and stays there, which alone removes the oscillation. The wake is kept, and fades: G4 turns a cell a robot has just left into and G5, G6 let it fade, which is needed because a robot whose support descends would otherwise be stranded with no landing site below and, by S1, no support to slide on; being self-extinguishing, the wake is harmless for silence. The robot mark is split: S2 requires , so a robot waits one round after arriving, which replaces the phase difference as the collision-avoidance mechanism, and exists so that a landing site does not vanish during that wait.
Correctness
Lemma 3 (the floor is frozen) and Lemma 6 (the west end is pinned) carry over verbatim: their proofs use only that is produced in a row with no robots and that robots move east and south. The remaining invariants take the following form.
Lemma 7. For every and every cell : if and only if . Moreover for every , and for , if and only if . Finally, if then the same robot occupies at both rounds.
Proof. Only G1 and G2 produce states of , and they apply exactly to occupied cells, which gives the first claim. G1 additionally requires , which fails for because and is equivalent to for ; this gives the second. For the last claim, a robot enters only by S1 or S2, and both require to be unoccupied at the Look of that round, so no robot can enter in a round in which another robot leaves it.
So reads to the robot on as “I did not move last round”: the only history in the system, and it sits in the floor.
Lemma 8 (The landing predicate is stable). Let be unoccupied at rounds and let one of be occupied at all these rounds. Then for every .
Proof. By Lemma 7 the neighbor is in at every round , so G3 applies to at every update from then on, whatever is.
Lemma 9 (Collision-freedom). for every .
Proof. As in Lemma 4, the only dangerous case is a robot applying S1 from and a robot applying S2 from in the same round . Nobody moves in round 0, since S1 needs and S2 needs ; and in round 1 every robot cell is by Lemma 7, so S2 fails. Let and note .
If , then by Lemma 7, so G3 applied to at the update ending round and ; hence S1 fails at .
If , then , so by Lemma 7; hence S2 fails at .
The two cases are exhaustive, so at most one of the two robots moves. Two robots applying the same rule have distinct sources and hence distinct targets, and neither rule enters an occupied cell.
The model’s one-round delay is exactly what would let both robots move; splitting the robot mark converts it into a one-round wait on the faller.
Theorem 2. The five-state algorithm solves Line Formation from connected configurations, and every execution terminates in the configuration of Theorem 1, within rounds.
Proof sketch. The argument of Theorem 1 applies with Lemmas 8 and 9 in place of Lemmas 2 and 4. Lemma 5 survives once replace : a floor cell becomes a landing site only through G3, hence only next to an occupied floor cell, since by Lemma 3(iii) no floor cell is ever vacated and G4 cannot apply there. Progress is easier here, as no robot waits for a phase and a landing site stays available once it exists.
Field-Silence
Proposition 3. The five-state algorithm is field-silent. Three rounds after the robots reach the field is constant, with on the cells of the line, on the two cells and , and everywhere else.
Proof. Let be a round from which for all . For we have for , so by Lemma 7. The unoccupied cells with an occupied horizontal neighbor are exactly and , because the horizontal neighbors of a cell outside row also lie outside row and are therefore unoccupied; by Lemma 8 these two cells are at from round on. Every other cell is unoccupied and has no occupied horizontal neighbor after , so neither G3 nor, after one round, G4 applies to it, and G5, G6 drive it to within three rounds, where G6 keeps it. No clause changes any of these values again, so the configuration is a fixed point.
The two end cells are the whole difference: under the four-state rules they alternate forever, here they rest at . One state buys the fixed point. We do not claim that five states are necessary; whether some four-state field is field-silent is open.
Gathering from Arbitrary Configurations with Three States
We now drop connectivity. The robots start on arbitrary distinct cells and may be so far apart that no robot ever sees another unless the algorithm brings them together; by Proposition 1(ii) this is hopeless on an inert floor. Three states suffice: , where is blank, (“west”) means that some robot stands strictly east of the cell, and (“axis”) marks a robot’s cell and the cells above it in its column.
The Rules
The field transition and the robot algorithm are, as before, given by the first applicable clause:
| Rule | Condition on cell | Next state |
| H1 | carries a robot | |
| H2 | or or | |
| H3 | ||
| H4 | otherwise | (unchanged) |
Table 1 (PDF p. 10).
| Rule | Condition | Action |
| T1 | move E | |
| T2 | move S | |
| T3 | move N | |
| T4 | otherwise | stay |
Table 2 (PDF p. 10).
The idea is to make every robot walk to the easternmost occupied column and then down that column (Figure 2). By H1 and H3 an axis grows upward from every robot. By H2 a cell that has an axis or west cell to its east becomes a west cell, and the west state also spreads north and south; hence floods the whole half-plane west of the easternmost robots, while nothing east of them is ever painted, because no rule lets information travel east. H2 precedes H3, so west of the easternmost column the axes are overwritten and only the axis of that column survives. A robot walks east as long as the cell to its east is painted (T1). It thereby reaches the column just west of the easternmost one; if the cell to its east is an axis cell it enters the column and descends the axis (T2) onto the lowest robot there. If instead it arrives below that robot, the cell to its east is blank and will remain so; such a robot recognizes its situation from the west cell above it and climbs (T3) until the cell to its east is the meeting cell.

Figure 2. Gathering seven scattered robots with three states. Blue cells are w, magenta cells are a (a robot’s cell is always a), white cells are blank; “×” counts the robots on a cell. The axis grows upward from every robot (H3) and the west region floods everything west of the easternmost robots (H2), overwriting the axes there. Robots walk east through painted cells (T1); the robot that starts just west of the easternmost column but below its lowest robot climbs (T3) until it can enter. All robots meet on the lowest robot of the easternmost column, here .
Correctness
Fix an arbitrary initial configuration and let
We show that all robots meet on , the cell of the lowest robot of the easternmost column.
Lemma 10 (Nothing happens in the east). At every round: (i) no robot is in a column ; (ii) every cell of a column is blank; (iii) no cell of column is in state w.
Proof. Induction on ; all three hold at . Assume them at . A robot in column has by (ii), so T1 does not apply, and T2, T3 are vertical; this gives (i) at . A cell with is unoccupied at , its east, north and south neighbors are blank by (ii), so none of H1–H3 applies and H4 keeps it blank. A cell of column can become w only by H2; its east neighbor is blank by (ii) and its north and south neighbors lie in column and are not w by (iii).
:::
Lemma 11 (The meeting cell). At every round: (i) every cell with is blank and unoccupied; (ii) a robot on does not move, so is always occupied; and (iii) for all and .
Proof. (i) and (ii) by induction on . A robot on has by Lemma 10, by (i), and by Lemma 10(iii), so T4 applies. A cell with can be entered only from the west by T1, from the north by T2, or from the south by T3; the first two need the cell to be non-blank and the third needs an occupied cell below it, contradicting (i) at round . It stays blank because its east neighbor is blank, its vertical neighbors are not w (Lemma 10) and its south neighbor is blank by (i). (iii) By (ii) and H1, for . Inductively, at every update after round the cell is occupied, and H1 applies, or its south neighbor is a, H2 does not apply by Lemma 10, and H3 applies.
:::
Lemma 12 (The easternmost column). A robot in column never leaves it, moves only south, and reaches in finitely many rounds.
Proof. T1 is excluded by Lemma 10(ii) and T3 by Lemma 10(iii), since the cell above the robot lies in column . By Lemma 11(i) the robot is in a row , and by Lemma 11(iii) the cell below it is a from round on if , so T2 applies in every later round until the robot is on , where it stays.
Lemma 13 (Paint). (i) A non-blank cell never becomes blank. (ii) Every cell with and is non-blank from some round on, and whenever it is unoccupied after that round it is in state w.
Proof. (i) H1–H3 produce a or w and H4 preserves the state. (ii) By induction on . The east neighbor of is , which is from a round on by Lemma 11(iii), or a cell that is non-blank from some round on by the induction hypothesis and (i). From then on, at every update, H1 applies if the cell is occupied and H2 applies otherwise.
Theorem 3. The three-state algorithm solves Gathering from arbitrary configurations. Every execution terminates with all robots on , the cell of the lowest robot of the easternmost occupied column of the initial configuration.
Proof sketch. If the robots stop, they have gathered. Suppose that from some round on no robot moves and that some robot is not on . By Lemma 12 every robot of column is on , so the robots off are in columns ; let , on , be one with the largest row. Since T1 never applies to , the cell is blank forever, hence by Lemma 13(ii) and Lemma 11(iii). The cells with are unoccupied by the choice of . By Lemma 13(ii) the cell is eventually w, and then H2, which precedes H3, turns , , , into w one after the other, whatever their previous states. So eventually and at , and T3 applies unless T2 does; in either case moves, a contradiction.
The robots stop. No robot moves west or leaves the columns , so there are at most moves east. Between them a robot moves vertically only by T2, towards a robot below it in its own column, on which it then stands, or by T3, upward through west cells while the cell to its east is blank. A cell that a robot leaves upward becomes w (H2 reads the west cell that the robot is entering), so a climbing robot is not pulled back by T2; a robot that descends merges with the robot below it, and merged robots never separate; and a climb ends at the latest in row , where the cell to the east is painted by Lemma 13. Hence every robot makes finitely many moves. We omit the routine but lengthy bookkeeping of the transient states.
We complemented the proof sketch by machine verification (§ 9.3): the algorithm gathers on from every one of the 4,445 placements of at most three robots in a box and of four robots in a box, and from every random configuration of up to 100 robots that we tried; the number of rounds grows linearly with the diameter of the initial configuration.
Field-Silence Is Impossible from Arbitrary Configurations
The three-state algorithm is terminating but not field-silent: after the robots have met, the west region keeps spreading west and the axis north, forever. This is not a defect of the algorithm.
Proposition 4. No algorithm, with any number of field states, solves Gathering from arbitrary configurations field-silently. The same holds for Line Formation from arbitrary configurations.
Proof. Let be field-silent and consider the execution of a single robot started on the origin. It reaches a fixed point at some round . Since only finitely many cells are non-quiescent at any round, the set of cells that are occupied or non-quiescent at some round of is finite and lies within distance of the origin, for some .
Now start two robots on and with . By induction on , the configuration at round is the superposition of and of its translate by : a cell within distance of one of the two origins has all its neighbors at distance at least from the other origin, so and receive exactly the arguments they receive in the corresponding single-robot execution, and every other cell is quiescent with quiescent neighbors and stays quiescent because . Hence both robots stop within distance of their own origins, at distance at least four from each other: they have neither met nor formed a line.
The proof uses only that information travels at most one cell per round and that a field-silent execution of one robot disturbs a bounded region. For robots that must find each other across unbounded distances, an unbounded amount of field activity is the price, whatever the number of states.
Line Formation from Arbitrary Configurations with Six States
Gathering lets the robots pile up on one cell. Line Formation from arbitrary configurations asks for more: the robots must come together from afar without ever colliding and end on consecutive cells of a row. The difficulty is local. Robots converge on a common cell from the west and from the north, the two robots are diagonal neighbors, and neither sees the other. We resolve it with a landing zone: a cell that knows a robot stands directly above it, and that the two robots read differently.
The Rules
Let . A cell is in state r exactly when it carries a robot. The other non-blank states describe where robots are relative to the cell: w (“west region”) says that some robot stands strictly east of the cell, in its row or below; a (“axis”) that a robot stands below the cell in its column; e (“east region”) that some robot stands strictly west of the cell, in its row or below. Finally l (“landing zone”) marks a cell of type a or e whose north neighbor carries a robot.
| Rule | Condition on cell | Next state |
| K1 | carries a robot | r |
| K2 | w | |
| K3 | l | |
| K4 | w | |
| K5 | a | |
| K6 | e | |
| K7 | e | |
| K8 | otherwise | (unchanged) |
Table 3.
| Rule | Condition | Action |
| U1 | move S | |
| U2 | move E | |
| U3 | move E | |
| U4 | otherwise | stay |
Table 4.
K4–K6 paint the three regions around every robot, with the west region taking precedence over the axis and the axis over the east region; the regions are those of a four-state gathering algorithm in which robots move south onto e or a and east onto w or a, and thereby all meet in the lowest row at the easternmost column. K2 and K3 concern a cell directly below a robot: if its paint is the west region it stays w, since no robot descends into the west region; otherwise it becomes a landing zone. K7 removes the mark once the robot above has left and no neighbor repaints the cell.
The robot rules use the landing zone as a mutual exclusion device. A robot descends only into a landing zone (U1), and it never moves east into one (U2, U3). Because the mark appears one round after the robot above has arrived, a robot approaching from the west gets in first, and the robot above then finds the cell occupied. U3 is the rule that turns a pile into a line, as in § 4: the top robot of a vertical stack slides east off the stack, and U1 lets it drop beside it (Figure 3).

Figure 3. Line Formation from an arbitrary configuration with six states, . Blue cells are w, magenta a, pink e, green l; a robot’s cell is r (grey). Robots walk east through the west region and the axes (U2), descend through landing zones (U1), and the top robot of a stack slides east and drops (U3, U1). The line forms in the lowest initial row.
Correctness
Let be the lowest row of , as in § 4.
Lemma 14 (The ground). At every round, every cell of a row below is blank and unoccupied.
Proof. Induction on . Robots move east and south only, and a robot of row moves south only by U1, which needs the cell below it to be l; so no robot enters the rows below as long as they are blank. A blank unoccupied cell of row stays blank: its east, west and south neighbors are blank, so K4–K6 and the first two disjuncts of K3 fail, K2 fails, and is neither e, a nor l. In lower rows the north neighbor is blank as well.
Lemma 15 (Collision-freedom). for every .
Proof. Robots move east (U2, U3) and south (U1) only, and every rule requires the target cell to be unoccupied at the look of that round. Two robots that enter the same cell in the same round therefore come from and . The robot on applies U1, which requires ; the robot on applies U2, which requires , or U3, which requires . Both read in the same round, a contradiction.
Lemma 16 (Finitely many moves). Every robot moves finitely often.
Proof sketch. By Lemma 14 every move south decreases a row that is bounded below by , so there are finitely many moves south; consider the execution after the last one. Rows are now fixed, and within a row the robots keep their order, since no robot enters an occupied cell. We argue by induction on the row, from upward, that every robot of the row moves east finitely often. A robot moves east by U3 only when it stands on another robot, which belongs to the row below and has stopped by the induction hypothesis (in row this never happens). It moves east by U2 only into a cell in state w or a; such a cell is an axis cell above a robot, or lies west of a robot cell or of an axis cell of its row, so some robot stands in a column east of the moving robot, in its row or below. For the easternmost robot of the row, that robot belongs to a lower row. In both cases the easternmost robot of the row cannot pass the column next to the easternmost robot of the lower rows, and the other robots of the row stay west of it.
Theorem 4. The six-state algorithm solves Line Formation from arbitrary configurations. Every execution terminates in a line that lies in row .
Proof sketch. Collision-freedom is Lemma 15 and termination is Lemma 16. Consider the robots after their last move. The field keeps changing only by propagation, and in every bounded region it stabilizes to the following pattern, by induction from east to west and from bottom to top: an unoccupied cell is w if some robot stands strictly east of it in its row or below; otherwise a if a robot stands below it in its column; otherwise e if some robot stands strictly west of it in its row or below; and a cell of the last two kinds is l instead if a robot stands directly above it. No rule can be enabled in this pattern, since the robots have stopped.
Suppose some robot is above row , and let , on , be the easternmost robot of the highest occupied row. The cells above and east of in its row are unoccupied, and the cell is not a landing zone, as nothing is above it. If a robot stood below , U3 would be enabled. So is unoccupied, and since U1 is not enabled it is not a landing zone, although stands above it. As some robot stands in row , the pattern leaves only one possibility: is w, that is, a robot stands strictly east of column in a row below . Then is a or w and U2 is enabled, a contradiction. Hence all robots are in row . If two of them were separated by an unoccupied cell, the western one would see w to its east and U2 would be enabled. So the occupied cells are consecutive.
In all our experiments the terminal line moreover contains the easternmost initial column: it extends from that column to the west by as many robots as arrive along row and to the east by the robots that slide off the stack. We verified the algorithm on all 5,237 placements of at most three robots in a box, four robots in a box and five robots in a box, and on random configurations of up to 30 robots (§ 9.3). The landing zone is essential: the same rules without it collide in about 30% of random executions. By Proposition 4 the algorithm cannot be field-silent, and indeed its regions spread forever.
Exploration
Our third problem is not a formation problem and has no terminal configuration. A single robot must visit every cell of a finite arena again and again. On an inert floor it cannot (Proposition 1(iii)): an oblivious robot that always sees the same thing always does the same thing. The floor supplies exactly what is missing, a memory of how the robot left each cell the last time.
Four States: The Floor as a Rotor-Router
Let , the state of a cell being read as a pointer, with , and let turn be the cyclic shift .
| Rule | Condition on cell | Next state |
| X1 | carries a robot | |
| X2 | otherwise |
Table 1 (PDF p. 14).
| Rule | Condition | Action |
| Y | move () |
Table 2 (PDF p. 14).
The robot moves in the direction its own cell points to, and a cell advances its pointer in every round in which a robot stands on it at the update. The field never looks at a neighbor and the robot never looks at one either. On a bounded grid a move towards a missing cell leaves the robot in place; no special rule is needed for the border.
Lemma 17. Call a round in which the robot stands on cell at its Look a -round. In consecutive -rounds the robot attempts consecutive directions of the cyclic order N, E, S, W.
Proof. Let be consecutive -rounds. If the robot stays on in round , because its move was blocked, then and was occupied at the update of round . Otherwise the robot leaves in round , is unoccupied at every update until the robot re-enters it in the Move phase of round , and is occupied at the update of round . In both cases X1 applies to exactly once between the two Look phases.
Theorem 5. The four-state rotor field solves Exploration of every torus and of every bounded grid . On with the cover time is from every start cell; on it is .
Proof. Perpetual exploration. The arena is finite, so some cell has infinitely many -rounds. By Lemma 17 every direction is attempted in one of any four consecutive -rounds, so the robot enters every existing neighbor of infinitely often. As the arena is connected, every cell is visited infinitely often.
Cover time on a torus. By symmetry let the robot start on . In round 0 it reads N and moves to . A cell that is entered for the first time turns from N to E on arrival, so the robot leaves it eastward: it runs east along row 1 and re-enters after rounds. This cell now turns to S and sends the robot to , whose pointer is still N and turns to E; the robot runs east along row 0, re-enters , is sent south to , and so on. The rows are thus swept in the order ; each sweep takes rounds and is followed by one round that changes the row, except that the last sweep has seen its whole row after rounds. With the initial round this gives rounds.
Cover time on a bounded grid. By Lemma 17, if the rounds in which the robot is blocked are deleted, the walk is the rotor-router walk on the grid graph with the port order induced by N, E, S, W, and at most two blocked rounds occur between consecutive steps. A rotor-router walk covers a graph with edges and diameter within steps [15]; here and .
After the cover time the walk does not become irregular: a rotor walk on a finite Eulerian graph locks into an Eulerian circuit [14, 16, 17], in which every cell is left once in each direction. Counting the blocked attempts on a bounded grid, one period lasts exactly rounds on both arenas, which is what we observe in simulation for all sizes we tried (§ 9.3). In the long run every cell is therefore revisited within rounds. Figure 4 shows the order of first visits.

Figure 4. Round of the first visit of each cell for a robot started on of a arena. On the torus both rotor fields sweep the arena row by row in rounds; on the bounded grid the four-state field needs 144 rounds.
Two States on a Torus, and Optimality
On a torus two of the four directions are enough. Let ; a cell flips its state in every round in which a robot stands on it at the update, and the robot moves north if its cell is and east if it is .
Theorem 6. The two-state rotor field solves Exploration of every torus , with cover time for . No field with a single state solves Exploration of a torus with , so two states are optimal.
Proof. Lemma 17 holds with the cyclic order N, E, and no move is ever blocked. Some cell has infinitely many -rounds, so its northern and its eastern neighbor are entered infinitely often; since every cell of a torus can be reached from every other by moving north and east only, every cell is visited infinitely often. For the cover time, the robot moves from to , runs east along row 1, re-enters , which flips back to and sends it north to , and so on; the rows are swept in the order , with the same count as in Theorem 5. The lower bound is Proposition 1(iii).
The two-state field does not explore bounded grids: the robot ends in the north-east corner, where both of its moves are blocked. Whether two or three states suffice there is open; four do, by Theorem 5.
Remark 2. Lemma 17 and the first part of the proof of Theorem 5 hold for any number of robots, so robots also explore the arena perpetually, and in our simulations faster. Robots that enter the same cell move together from then on, however, so the parallelism of multi-agent rotor walks is not guaranteed.
Remark 3. On the infinite grid neither rotor field explores: a robot leaves every cell it enters for the first time eastward, so after its first step it marches east forever. This matches the fact that rotor walks on may escape to infinity [18]. Whether a finite-state field lets an oblivious robot visit every cell of is open.
Further Examples
The algorithms above use the floor as a trace, as a map of regions and as a memory of departures. This section sketches three more rule sets that use it in other ways. We do not prove them correct; they were validated by simulation only (§ 9.3) and are meant as evidence of the range of the model and as a source of problems.
The Floor as a Ruler: Equal Spacing
Robots stand on distinct cells of a row and must end exactly cells apart, measured from the westmost robot, which does not move. Use states . A robot’s cell is , and the cells east of a robot count their distance to it: the cell east of becomes , the cell east of becomes , the cell east of or becomes (“far”), and a cell with nothing to its west stays blank. A robot only reads the cells beside it:
| Condition | Action | Meaning |
| move E | closer than to the robot on the west | |
| move W | farther than | |
| otherwise | stay | : exactly ; : westmost |
Table 1 (PDF p. 16).
A robot steps east only into a cell that already shows , that is, a cell that has registered it, and west only into a cell that shows ; since a cell cannot show both, two robots never enter the same cell from opposite sides, which is the device of Lemma 4 once more. In our simulations all 1,200 random rows with and up to 12 robots ended with the robots exactly apart (Figure 5); rows are independent, so every row of a two-dimensional configuration becomes a ruler of its own. Uniform spreading on a line is a classical problem for robots that see their neighbors [24]; here the robots see nothing beyond the adjacent cells and the floor measures the distance for them.

Figure 5. Equal spacing with gap (five states). Green cells count the distance to the robot on the west ( light, dark), orange cells are far from it. The dense group spreads east and the straggler comes west.
The Floor as an Excitable Medium: Filling a Painted Pattern
In the problems so far the floor starts blank. A floor can also carry the input. Suppose some cells are painted as targets before the robots start, as a pattern would be painted on a warehouse floor, and the robots, scattered arbitrarily, must end with exactly one robot on each target. We allow the initial field to be non-uniform for this purpose and use eight states: the target states T (empty target) and D (target with a robot on it), an inert state for walls, and five states , , , , that make the rest of the floor an excitable medium in the sense of Greenberg and Hastings [20]: a resting cell (, never excited, or , resting again) that has an excited neighbor () or an empty target next to it becomes excited, and an excited cell passes through and back to rest. Every empty target thus emits waves of period four, waves from different targets annihilate where they meet, and a target stops emitting as soon as a robot stands on it, so no stale information is left behind.
A robot steps to a neighbor whose phase is one ahead of the phase of its own cell, that is, to a neighbor that the wave reached one round earlier and that is therefore closer to the nearest empty target, or onto an adjacent empty target; a robot on a target stays. The phase is at the same time the traffic rule. A robot on an excited cell may only move north, on only east, on only south, and on a resting cell only west. Two robots that enter the same cell must both see it one phase ahead of their own cells, hence have the same phase, hence move in the same direction, which is impossible for distinct robots; the phase of the wave acts as a clock that multiplexes the four directions. With at least as many robots as targets every target ends with exactly one robot and the floor comes to rest (Figure 6); surplus robots simply stop.

Figure 6. Filling a pattern painted on the floor. Red cells are empty targets, green cells filled ones, the dark column is a wall; blue shades are the phases of the waves emitted by the empty targets ( darkest). Robots follow the waves, pass around the wall, and the floor comes to rest when every target is taken.
In simulation, 360 random patterns of up to 20 targets were filled without a collision, with as many robots as targets, with a surplus, and with too few robots (in which case all robots end on targets). With walls the same rules guide robots through a maze, along shortest paths to the nearest target that is still empty, because the waves run through the corridors. One limitation is geometric rather than algorithmic: a target in a corridor of width one blocks the passage once it is occupied.
| Algorithm | Instances | |
| Line Formation, connected (Sec. 4, 5) | 4, 5 | 540 random connected configurations each, |
| Gathering, arbitrary (Sec. 6) | 3 | all 4,445 small placements, ; 890 random, |
| Line Formation, arbitrary (Sec. 7) | 6 | all 5,237 small placements, ; 400 random, |
| Exploration (Sec. 8) | 4 | tori and bounded grids from to |
| Exploration (Sec. 8) | 2 | tori from to |
| Equal spacing, | 300 random rows for each | |
| Pattern filling and maze | 8 | 360 random patterns without walls; one maze with four targets |
Table 2 (PDF p. 17). Instances checked by simulation (FSYNC).
Simulator and Validation
All rule sets of this paper were implemented in a simulator of the model, in which a rule set is a short list of guarded clauses for and for , exactly as in the tables above. Table 2 lists the instances on which each algorithm was run; every run ended in the configuration claimed, without a collision where collisions are forbidden. These runs complement the proof sketches of Theorems 3 and 4; for the rule sets of this section they are the only evidence.
Conclusion
We proposed CABOT, a model in which the plane underlying an LCM system is an anonymous, uniform cellular automaton and Look returns cell states along with robot positions. No capability is added to the robots: they stay oblivious, silent, lightless and myopic with visibility range 1, and cannot even write to the field. A handful of field states then solves problems that are out of reach on an inert plane: Line Formation from connected configurations with four states and field-silently with five, Gathering and Line Formation from arbitrary configurations with three and six states, and perpetual Exploration of finite grids with four states and of tori with two. The floor plays a different part each time: a decaying trace, a map of regions, a mutual exclusion device, a rotor-router, a ruler, an excitable medium.
Several directions are open.
Lower bounds. Only one of our state counts is known to be optimal, the two states for exploring a torus. Is Gathering from arbitrary configurations possible with two states? Is Line Formation from connected configurations possible with three, or field-silently with four? How many states does a bounded grid need for Exploration? Even separating two consecutive values would say something about what a field can store.
Field-silence. Proposition 4 rules out silence whenever robots must find each other across unbounded distances. A characterization of the problems that admit field-silent solutions, and of the price of silence in states, would be the analogue for CABOT of the memory lower bounds for silent stabilization [25].
Weaker schedulers. Our algorithms are FSYNC. The natural next model keeps the field synchronous and lets the robots be SSYNC or ASYNC. In simulation the two algorithms for arbitrary configurations and the pattern-filling rules also succeed when a random subset of the robots is activated in each round, whereas under an asynchronous scheduler, in which a robot may act on an outdated snapshot, collisions occur. How much of the timing survives, and at what cost in states, decides how close the model is to the warehouse floors that motivated it.
Proofs and the infinite grid. The examples of Section 9 call for proofs, and Exploration of by an oblivious robot on a finite-state floor is open.
Acknowledgement
This work was supported by JSPS KAKENHI Grant Numbers JP23K24825, JP25K03078, JP25K03079, JP26K02865, JP26K23809, and MEXT Supporting Pioneering Research through AI for 1,000 Discovery challenges Program (SPReAD) Japan Grant Number JPMXP1726306000.
References
- [1]I. Suzuki and M. Yamashita, “Distributed anonymous mobile robots: formation of geometric patterns,” SIAM J. Comput., vol. 28, no. 4, pp. 1347–1363, 1999.DOI
- [2]P. Flocchini, G. Principe, and N. Santoro, Eds., Distributed Computing by Mobile Entities. Springer, 2019.
- [3]M. Cieliebak et al., “Distributed computing by mobile robots: gathering,” SIAM J. Comput., vol. 41, no. 4, pp. 829–879, 2012.DOI
- [4]S. Das et al., “Autonomous mobile robots with lights,” Theor. Comput. Sci., vol. 609, pp. 171–184, 2016.DOI
- [5]P. Flocchini, N. Santoro, G. Viglietta, and M. Yamashita, “Rendezvous with constant memory,” Theor. Comput. Sci., vol. 621, pp. 57–72, 2016.DOI
- [6]P. Flocchini et al., “Gathering of asynchronous robots with limited visibility,” Theor. Comput. Sci., vol. 337, pp. 147–168, 2005.
- [7]G. D’Angelo, G. Di Stefano, R. Klasing, and A. Navarra, “Gathering of robots on anonymous grids and trees without multiplicity detection,” Theor. Comput. Sci., vol. 610, pp. 158–168, 2016.
- [8]M. Fischer, D. Jung, and F. Meyer auf der Heide, “Gathering anonymous, oblivious robots on a grid,” in ALGOSENSORS, LNCS vol. 10718, pp. 168–181, 2017.
- [9]K. Bose et al., “Arbitrary pattern formation on infinite grid by asynchronous oblivious robots,” Theor. Comput. Sci., vol. 815, pp. 213–227, 2020.
- [10]L. Barrière, P. Flocchini, P. Fraigniaud, and N. Santoro, “Capture of an intruder by mobile agents,” in SPAA, pp. 200–209, 2002.
- [11]M. A. Bender et al., “The power of a pebble: exploring and mapping directed graphs,” in STOC, pp. 269–278, 1998.
- [12]I. A. Wagner, M. Lindenbaum, and A. M. Bruckstein, “Distributed covering by ant-robots using evaporating traces,” IEEE Trans. Robot. Autom., vol. 15, no. 5, pp. 918–933, 1999.DOI
- [13]G. Theraulaz and E. Bonabeau, “A brief history of stigmergy,” Artificial Life, vol. 5, no. 2, pp. 97–116, 1999.pubmed.ncbi.nlm.nih.gov/10633572
- [14]V. B. Priezzhev, D. Dhar, A. Dhar, and S. Krishnamurthy, “Eulerian walkers as a model of self-organized criticality,” Phys. Rev. Lett., vol. 77, no. 25, pp. 5079–5082, 1996.
- [15]V. Yanovski, I. A. Wagner, and A. M. Bruckstein, “A distributed ant algorithm for efficiently patrolling a network,” Algorithmica, vol. 37, no. 3, pp. 165–186, 2003.
- [16]E. Bampas et al., “Euler tour lock-in problem in the rotor-router model,” in DISC, LNCS vol. 5805, pp. 423–435, 2009.
- [17]A. E. Holroyd et al., “Chip-firing and rotor-routing on directed graphs,” in In and Out of Equilibrium 2, Progress in Probability, vol. 60, pp. 331–364, 2008.DOI
- [18]L. Florescu, S. Ganguly, L. Levine, and Y. Peres, “Escape rates for rotor walks in ℤᵈ,” SIAM J. Discrete Math., vol. 28, no. 1, pp. 323–334, 2014.
- [19]C. G. Langton, “Studying artificial life with cellular automata,” Physica D, vol. 22, pp. 120–149, 1986.
- [20]J. M. Greenberg and S. P. Hastings, “Spatial patterns for discrete models of diffusion in excitable media,” SIAM J. Appl. Math., vol. 34, no. 3, pp. 515–523, 1978.
- [21]Z. Derakhshandeh et al., “Brief announcement: amoebot – a new model for programmable matter,” in SPAA, pp. 220–222, 2014.
- [22]G. D’Angelo et al., “Leader election and compaction for asynchronous silent programmable matter,” in AAMAS, pp. 276–284, 2020.
- [23]Y. Kim et al., “Pairbot: Enhancing computational capabilities by pairing of autonomous mobile robots,” in IPDPSW, pp. 578–587, 2025.
- [24]R. Cohen and D. Peleg, “Local spreading algorithms for autonomous robot systems,” Theor. Comput. Sci., vol. 399, no. 1–2, pp. 71–82, 2008.
- [25]S. Dolev, M. G. Gouda, and M. Schneider, “Memory requirements for silent stabilization,” Acta Inf., vol. 36, pp. 447–462, 1999.