Autonomous Mobile Robots on a Computing Field

AUTONOMOUS M OBILE ROBOTS ON A C OMPUTING F IELD

arXiv:2611.16652v1 [cs.DC] 12 Nov 2026

Yonghwan Kim Nagoya Institute of Technology Nagoya, Japan kim@nitech.ac.jp

Gil-Tak Kong Busan National University Busan, Republic of Korea ggt3080@gmail.com

Un-Sook Choi Tongmyong University Busan, Republic of Korea choies@tu.ac.kr

A BSTRACT We introduce CAB OT, 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. CAB OT 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. Keywords autonomous mobile robots · Look-Compute-Move model · cellular automaton · active environment · line formation · gathering · exploration · silence

1

Introduction

1.1

Background

A swarm of autonomous mobile robots is commonly studied through the Look-Compute-Move (LCM) 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 (LUMI) carry an externally visible light of constant size [4]; the sub-models FST A and FCOM 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 wellunderstood hierarchy of models. What they all share is that capability is added per robot: a swarm of n robots requires

Autonomous Mobile Robots on a Computing Field

n copies of the additional hardware, and the robots themselves must become more complex, more expensive, and less disposable. 1.2

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 CAB OT (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 Q, 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 CAB OT 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 |Q| of field states. 1.3

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. 1.4

Our Contribution

We formalize CAB OT 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 CAB OT as an extension of LCM in which |Q| 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 (Section 3). With |Q| = 1 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 (Section 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 (Section 5). • Gathering from arbitrary configurations. Robots that start on arbitrary distinct cells, with no connectivity whatsoever, gather with three states (Section 6). We also prove that no algorithm, with any number of states, solves Gathering or Line Formation from arbitrary configurations field-silently (Proposition 4). 2

Autonomous Mobile Robots on a Computing Field

Table 1: Summary of results. All robots are oblivious, silent, lightless and myopic with visibility range 1, and operate under FSYNC. Problem Line Formation Line Formation Gathering Line Formation Gathering, Line Formation Exploration Exploration

Initial configuration connected connected arbitrary arbitrary arbitrary one robot one robot

Arena

|Q|

Guarantee

Reference

2

4 5 3 6 any 4 2

terminating field-silent terminating terminating never field-silent perpetual perpetual, optimal

Theorem 1 Theorem 2, Prop. 3 Theorem 3 Theorem 4 Prop. 4 Theorem 5 Theorem 6

1

impossible

Prop. 1

Z Z2 Z2 Z2 Z2 torus, bounded grid torus

all of the above

• 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. 1.5

Organization

Section 2 surveys related work. Section 3 defines CAB OT, 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.

2

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 FST A, 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–17]. In the literature the pointer is part 3

Autonomous Mobile Robots on a Computing Field

of the system by definition; in CAB OT it is one particular field, and Section 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 Section 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 Sections 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 |Q| rather than a per-robot capability.

3

The CAB OT Model

We describe the two components of the system, the field and the robots, then the cycle that couples them, and finally the problems. 3.1

The Field

The default arena is the infinite two-dimensional grid Z2 , whose elements we call cells. We write D = {N, S, E, W} for the four cardinal directions and, for a cell c = (x, y), we let c + N = (x, y + 1), c + S = (x, y − 1), c + E = (x + 1, y) and c + W = (x − 1, y). The neighborhood of c is the von Neumann neighborhood N (c) = {c + d | d ∈ D}. A cellular automaton field (CA field) is a triple F = (Q, q0 , δ) where Q is a finite set of states, q0 ∈ Q is the quiescent state, and δ : Q × Q4 × {0, 1} −→ Q is the transition function. A cell in state q whose four neighbors are in states qN , qS , qE , qW and which does or does not carry a robot, indicated by b ∈ {0, 1}, moves to state δ(q, qN , qS , qE , qW , b). 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 c, never to N (c), 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 δ(q0 , q0 , q0 , q0 , q0 , 0) = q0 , so that an untouched region stays quiescent and at every time only finitely many cells are non-quiescent. Finite arenas. Exploration (Section 8) is studied on finite arenas: the torus Tw,h = Zw × Zh , in which c + d is computed modulo (w, h), and the bounded grid Bw,h = {0, . . . , w − 1} × {0, . . . , h − 1}, 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. 3.2

The Robots

A set of n ≥ 1 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 n. 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 CAB OT from whiteboard and pebble models, where writing is an action of the agent. The view of a robot standing on cell c when the field assignment is λ : Z2 → Q and the set of occupied cells is P is  

V (c) = λ(c); λ(c + d) d∈D ; [ c + d ∈ P ] d∈D , 4

Autonomous Mobile Robots on a Computing Field

an element of Q5 × {0, 1}4 . An algorithm is a function φ : Q5 × {0, 1}4 → D ∪ {⊥}, ⊥ meaning stay. We abbreviate λc = λ(c), λd = λ(c + d) and ρd = [ c + d ∈ P ] for d ∈ D, and use the same abbreviations for the arguments of δ. A solution to a problem is a pair (φ, F), and its cost is |Q|. 3.3

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 t, with occupied cells Pt and assignment λt : (Look) every robot on c ∈ Pt obtains Vt (c); (Compute) it evaluates φ(Vt (c)); (Move) every robot with φ(Vt (c)) = d ̸= ⊥ moves to c + d, rigidly and by at most one cell, yielding Pt+1 ; and (Update) every cell applies δ using the old states and its new occupancy, λt+1 (c) = δ(λt (c), (λt (c + d))d∈D , [ c ∈ Pt+1 ]). Phase Update reads λt and writes λt+1 , 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 Ct = (Pt , λt ) together with the number of robots on each occupied cell, and the execution C0 , C1 , . . . determined by φ, δ, C0 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 |Pt | = n always, that is, if no two robots ever share a cell. 3.4

Initial Configurations

Initially λ0 ≡ q0 and the robots occupy n distinct cells. We call such an initial configuration arbitrary, and connected if in addition P0 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 CAB OT it can be dropped, because the field carries information between robots that cannot see each other. Where connectivity is assumed, it is assumed of P0 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 CAB OT the trace in the cells keeps a separated robot coupled to the rest, so the visibility graph may break without harm. 3.5

Termination and Field-Silence

An execution C0 , C1 , . . . is terminating if Pt = Pt0 for all t ≥ t0 for some t0 , and field-silent if Ct = Ct0 for all t ≥ t0 , 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 Sections 4 and 6 show. 3.6

The Problems

A set P of cells is a line if it consists of n consecutive cells of a single row or of a single column, that is, if P = {(x0 + i, y0 ) | 0 ≤ i < n} or P = {(x0 , y0 + i) | 0 ≤ i < n} for some (x0 , y0 ). Definition 1 (Line Formation). An algorithm (φ, F) solves Line Formation from connected (respectively arbitrary) configurations if it is collision-free and, for every n ≥ 1 and every connected (respectively arbitrary) initial configuration of n 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 n ≥ 1 and every arbitrary initial configuration of n robots, the execution is terminating and terminates with all robots on a single cell. Definition 3 (Exploration). Let G be a torus or a bounded grid. An algorithm solves Exploration of G if a single robot, started on any cell of G, visits every cell of G 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 |Q| is the cover time. 5

Autonomous Mobile Robots on a Computing Field

3.7

What an Inert Floor Cannot Do

With |Q| = 1 the field carries no information and CAB OT is the plain model of oblivious myopic robots on a grid. A view is then the set S ⊆ D of directions in which a neighbor is occupied, and an algorithm is one of the finitely many maps φ : 2D → D ∪ {⊥}. Proposition 1. Let |Q| = 1. (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 Tw,h with w, h ≥ 2, or of a bounded grid with at least two cells. Proof. For (i) and (ii), termination with n = 1 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 n ≤ 3, 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 54 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 56 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 a in every round. If a = ⊥ it visits one cell. Otherwise, on a torus it stays in one row or column and visits at most max(w, h) < wh 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 2(n − 1) 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).

4

Line Formation with Four States

In this section and the next the initial configuration is connected. Let Q = {q0 , q1 , q2 , q3 } with quiescent state q0 . Fix a connected P0 of n robots and write ymin = min{y | (x, y) ∈ P0 }, xL = min{x | (x, y) ∈ P0 }. Call row ymin the floor. Robots fall towards it and slide east along it, accumulating into one row; q3 marks a robot and q2 , q1 are a trace of decreasing freshness left in the cells beside it (Fig. 1). 4.1

The Rules

Define the decay map dec(q3 ) = q2 , dec(q2 ) = q1 , dec(q1 ) = dec(q0 ) = q0 . The field transition δ is given by the first applicable clause: Rule F1 F2 F3

Condition on cell c c carries a robot (λc ∈ {q0 , q1 }) ∧ (λE = q3 ∨ λW = q3 ) otherwise

Next state q3 q2 dec(λc )

The robot algorithm is likewise the first applicable clause: Rule R1 R2 R3

Condition ¬ρN ∧ ρS ∧ ¬ρE ∧ λE = q2 ∧ λN = q0 ¬ρS ∧ λS = q1 otherwise

6

Action move E move S stay

Autonomous Mobile Robots on a Computing Field

t=0 initial

t=6 fall (R2)

t=3

t=2

slide (R1)

t=8

t=5

t=9

Figure 1: An execution of the four-state algorithm, n = 3. Discs are robots; shading is the field state (white q0 , light q1 , dark q2 ; a cell under a robot is q3 ). The top robot slides east at t=3, 5 and falls at t=6. From t=8 the robots never move again, yet the two cells at the ends of the line keep swapping q2 and q1 : terminating, not field-silent (Prop. 2). F2 is tested before F3, so a cell beside a robot is refreshed only from q0 or q1 and from q2 it decays; the trace beside a stationary robot therefore alternates, which Lemma 2 turns into the timing device R1 and R2 rely on. 4.2

Basic Invariants

Lemma 1 (Marks are occupancy). For every t ≥ 1 and every cell c, λt (c) = q3 if and only if c ∈ Pt . Proof. F1 assigns q3 exactly to occupied cells, and F2, F3 never produce q3 . Lemma 2 (Trace oscillation). Let c be unoccupied throughout rounds t, t+1, . . . and suppose some cell of {c+E, c+W} is occupied throughout these rounds. Then for every t′ ≥ t + 2 we have λt′ (c) ∈ {q1 , q2 } and λt′ +1 (c) ̸= λt′ (c); that is, λ(c) alternates between q2 and q1 with period 2 and never returns to q0 . Proof. By Lemma 1 the occupied neighbor is at q3 at every round t′ ≥ max(t, 1), and λt′ (c) ̸= q3 at every such round. Hence at every update from round max(t, 1) on, F2 turns λ(c) ∈ {q0 , q1 } into q2 , and F3 turns λ(c) = q2 into q1 . So λt′ (c) ∈ {q1 , q2 } for t′ ≥ max(t, 1) + 1, and the two values alternate. Lemma 3 (The floor is frozen). For every t: (i) no robot occupies a cell of a row below ymin ; (ii) every cell of row ymin − 1 is in state q0 ; and (iii) no robot in row ymin ever moves. Proof. Simultaneous induction on t. Both (i) and (ii) hold at t = 0 since λ0 ≡ q0 . Assume them at t. For (iii), a robot at (x, ymin ) cannot apply R2 because λt (x, ymin − 1) = q0 ̸= q1 , and cannot apply R1 because row ymin − 1 is unoccupied, so ρS fails. Since R2 is the only rule that decreases a robot’s row, and it is unavailable in row ymin , no robot enters row ymin − 1, giving (i) at t + 1. Then no cell of row ymin − 1 is occupied at round t + 1; the horizontal neighbors of such a cell lie in the same row and are in state q0 ̸= q3 , so F2 does not apply and F3 keeps q0 at q0 ; this gives (ii) at t + 1. Lemma 4 (Collision-freedom). |Pt | = n for every t; no two robots ever occupy the same cell. Proof. A robot enters a cell c only from c + W by R1 or from c + N by R2, and both rules require c 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 c + W while another applies R2 from c + N. But R1 requires λ(c) = q2 and R2 requires λ(c) = q1 , and q1 ̸= q2 . Collision-freedom is enforced neither by priorities nor by symmetry breaking, but by the two movement rules reading different states of the same cell: q2 , q1 are at once a landing signal and a mutual exclusion mechanism. The same idea, in different guises, makes all our multiplicity-free algorithms safe. 4.3

Correctness

Lemma 5 (Landing is adjacent). If a robot moves into a cell c of row ymin in round t, then at least one of c + E, c + W is occupied at round t. 7

Autonomous Mobile Robots on a Computing Field

Proof. By Lemma 3(iii) the move is an R2 move from c + N, so λt (c) = q1 . A cell reaches q1 only by F3 from q2 , and q2 either by F2, which needs a horizontal neighbor at q3 , or by F3 from q3 , which by Lemma 1 needs c to have been occupied. The latter is impossible, since by Lemma 3(iii) a robot that stood on c would still be there. Hence F2 applied to c two updates earlier, so a horizontal neighbor of c was occupied then, and by Lemma 3(iii) it still is at round t. Lemma 6 (The west end is pinned). No robot ever occupies a cell with x < xL , and the bottom-most robot of column xL never applies R1. Proof. R1 and R2 move east and south only, so x is non-decreasing for every robot and no robot leaves the half-plane x ≥ xL ; in particular no robot ever enters column xL . Let r be the robot of column xL with the smallest row. R1 requires ρS , and c + S lies in column xL below r, hence is unoccupied. Theorem 1. The four-state algorithm solves Line Formation from connected configurations. Moreover every execution terminates in  P∞ = (xL + i, ymin ) 0 ≤ i < n . Proof sketch. By Lemmas 3 and 6 the floor is absorbing and nothing passes west of xL . 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 P0 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 xL only falls, so it rests at (xL , ymin ); with |P∞ | = n from Lemma 4 the claim follows. Corollary 1. Every execution terminates within O(n2 ) rounds. P Proof. Each x is non-decreasing and each y non-increasing, so the total number of moves is r [(xf − xi ) + (yi − yf )]. By Theorem 1 xf ≤ xL + n − 1 and xi ≥ xL , and yi − yf is at most the height of P0 , hence at most n − 1. So there are at most 2n(n − 1) moves, and by the progress argument above a constant number of rounds passes between consecutive ones. 4.4

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 (xL − 1, ymin ) and (xL + n, ymin ), change state forever, alternating between q2 and q1 with period 2; every other cell is fixed. Proof. Termination is Theorem 1. In P∞ every occupied cell is permanently q3 by Lemma 1. An unoccupied cell c is refreshed by F2 only if one of c + E, c + W is occupied, that is, only if c lies in row ymin and is horizontally adjacent to the line; the only such cells are (xL − 1, ymin ) and (xL + n, ymin ), and by Lemma 2 both alternate between q2 and q1 forever. Every other unoccupied cell has no horizontal neighbor in state q3 , so F3 applies at every round and it reaches q0 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 q2 to q1 for a robot above it to move in. As long as a robot stands beside that cell, F2 keeps pushing it back up to q2 , 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.

5

Field-Silent Line Formation with Five States

By Proposition 2 the pair q2 , q1 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 q2 → q1 while R1 reads q2 and that phase difference 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. 8

Autonomous Mobile Robots on a Computing Field

5.1

The Rules

Let Q = {q0 , ℓ1 , ℓ2 , m− , m+ } and M = {m− , m+ }. A cell in M carries a robot, m− if it arrived last round and m+ otherwise; ℓ2 , ℓ1 say the cell is a legal landing site, ℓ2 while the reason holds and ℓ1 for one round after. The field transition is: Rule G1 G2 G3 G4 G5 G6 Rule S1 S2 S3

Condition on cell c c carries a robot and λc ∈ M c carries a robot λE ∈ M or λW ∈ M λc ∈ M λc = ℓ2 otherwise

Next state m+ m− ℓ2 ℓ2 ℓ1 q0

Condition ¬ρN ∧ ρS ∧ ¬ρE ∧ λE = ℓ2 ∧ λN = q0 ¬ρS ∧ λS ∈ {ℓ1 , ℓ2 } ∧ λc = m+ otherwise

Action move E move S stay

Three changes matter. The landing predicate is unconditional: G3 fires whatever the cell’s state, whereas F2 refreshed only from q0 , q1 , so a cell beside a motionless robot sits at ℓ2 and stays there, which alone removes the oscillation. The wake is kept, and fades: G4 turns a cell a robot has just left into ℓ2 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 λ(c) = m+ , so a robot waits one round after arriving, which replaces the q2 /q1 phase difference as the collision-avoidance mechanism, and ℓ1 exists so that a landing site does not vanish during that wait. 5.2

Correctness

Lemma 3 (the floor is frozen) and Lemma 6 (the west end is pinned) carry over verbatim: their proofs use only that q0 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 t ≥ 1 and every cell c: λt (c) ∈ M if and only if c ∈ Pt . Moreover λ1 (c) = m− for every c ∈ P1 , and for t ≥ 2, λt (c) = m+ if and only if c ∈ Pt ∩ Pt−1 . Finally, if c ∈ Pt ∩ Pt−1 then the same robot occupies c at both rounds. Proof. Only G1 and G2 produce states of M , and they apply exactly to occupied cells, which gives the first claim. G1 additionally requires λt−1 (c) ∈ M , which fails for t = 1 because λ0 ≡ q0 and is equivalent to c ∈ Pt−1 for t ≥ 2; this gives the second. For the last claim, a robot enters c only by S1 or S2, and both require c to be unoccupied at the Look of that round, so no robot can enter c in a round in which another robot leaves it. So λ(c) = m+ reads to the robot on c 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 c be unoccupied at rounds t, t + 1, . . . and let one of c + E, c + W be occupied at all these rounds. Then λt′ (c) = ℓ2 for every t′ ≥ t + 2. Proof. By Lemma 7 the neighbor is in M at every round ≥ max(t, 1), so G3 applies to c at every update from then on, whatever λ(c) is. Lemma 9 (Collision-freedom). |Pt | = n for every t. Proof. As in Lemma 4, the only dangerous case is a robot applying S1 from b = c + W and a robot applying S2 from a = c + N in the same round t. Nobody moves in round 0, since S1 needs ℓ2 and S2 needs m+ ; and in round 1 every robot cell is m− by Lemma 7, so S2 fails. Let t ≥ 2 and note a = (b + N) + E. If a ∈ Pt−1 , then λt−1 (a) ∈ M by Lemma 7, so G3 applied to b + N at the update ending round t − 1 and λt (b + N) = ℓ2 ̸= q0 ; hence S1 fails at b. If a ∈ / Pt−1 , then a ∈ Pt \ Pt−1 , so λt (a) = m− ̸= m+ by Lemma 7; hence S2 fails at a. 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. 9

Autonomous Mobile Robots on a Computing Field

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 P∞ = {(xL + i, ymin ) | 0 ≤ i < n} of Theorem 1, within O(n2 ) 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 ℓ1 , ℓ2 replace q1 , q2 : 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. 5.3

Field-Silence

Proposition 3. The five-state algorithm is field-silent. Three rounds after the robots reach P∞ the field is constant, with λ(c) = m+ on the n cells of the line, λ(c) = ℓ2 on the two cells (xL − 1, ymin ) and (xL + n, ymin ), and λ(c) = q0 everywhere else. Proof. Let t0 ≥ 1 be a round from which Pt = P∞ for all t ≥ t0 . For c ∈ P∞ we have c ∈ Pt ∩ Pt−1 for t > t0 , so λt (c) = m+ by Lemma 7. The unoccupied cells with an occupied horizontal neighbor are exactly (xL − 1, ymin ) and (xL + n, ymin ), because the horizontal neighbors of a cell outside row ymin also lie outside row ymin and are therefore unoccupied; by Lemma 8 these two cells are at ℓ2 from round t0 + 2 on. Every other cell is unoccupied and has no occupied horizontal neighbor after t0 , so neither G3 nor, after one round, G4 applies to it, and G5, G6 drive it to q0 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 ℓ2 . 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.

6

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: Q = {q0 , w, a}, where q0 is blank, w (“west”) means that some robot stands strictly east of the cell, and a (“axis”) marks a robot’s cell and the cells above it in its column. 6.1

The Rules

The field transition and the robot algorithm are, as before, given by the first applicable clause: Rule H1 H2 H3 H4

Condition on cell c c carries a robot λE ∈ {a, w} or λN = w or λS = w λS = a otherwise

Next state a w a λc (unchanged)

Rule T1 T2 T3 T4

Condition λE ∈ {w, a} λS = a λE = q0 ∧ λN = w otherwise

Action move E move S move N stay

The idea is to make every robot walk to the easternmost occupied column and then down that column (Fig. 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 w 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. 10

Autonomous Mobile Robots on a Computing Field

×3

t=0

t=5

×7

t = 11

t = 17 (gathered)

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; “×k” 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 (11, 4). 6.2

Correctness

Fix an arbitrary initial configuration P0 and let X = max{x | (x, y) ∈ P0 },

y ∗ = min{y | (X, y) ∈ P0 },

g = (X, y ∗ ).

We show that all robots meet on g, 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 x > X; (ii) every cell of a column x > X is blank; (iii) no cell of column X is in state w. Proof. Induction on t; all three hold at t = 0. Assume them at t. A robot in column X has λE = q0 by (ii), so T1 does not apply, and T2, T3 are vertical; this gives (i) at t + 1. A cell c with x > X is unoccupied at t + 1, 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 X can become w only by H2; its east neighbor is blank by (ii) and its north and south neighbors lie in column X and are not w by (iii). Lemma 11 (The meeting cell). At every round: (i) every cell (X, y) with y < y ∗ is blank and unoccupied; (ii) a robot on g does not move, so g is always occupied; and (iii) λt (X, y ∗ + k) = a for all k ≥ 0 and t ≥ k + 1. Proof. (i) and (ii) by induction on t. A robot on g has λE = q0 by Lemma 10, λS = q0 by (i), and λN ̸= w by Lemma 10(iii), so T4 applies. A cell (X, y) with y < y ∗ 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 t. 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, λt (g) = a for t ≥ 1. Inductively, at every update after round k the cell (X, y ∗ + k) 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 X never leaves it, moves only south, and reaches g 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 X. By Lemma 11(i) the robot is in a row y ≥ y ∗ , and by Lemma 11(iii) the cell below it is a from round y − y ∗ on if y > y ∗ , so T2 applies in every later round until the robot is on g, where it stays. Lemma 13 (Paint). (i) A non-blank cell never becomes blank. (ii) Every cell (x, y) with x < X and y ≥ y ∗ 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 X − x. The east neighbor of (x, y) is (X, y), which is a from round y − y ∗ + 1 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 g = (X, y ∗ ), the cell of the lowest robot of the easternmost occupied column of the initial configuration. 11

Autonomous Mobile Robots on a Computing Field

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 g. By Lemma 12 every robot of column X is on g, so the robots off g are in columns x < X; let r, on (x, y), be one with the largest row. Since T1 never applies to r, the cell (x + 1, y) is blank forever, hence y < y ∗ by Lemma 13(ii) and Lemma 11(iii). The cells (x, y ′ ) with y < y ′ ≤ y ∗ are unoccupied by the choice of r. By Lemma 13(ii) the cell (x, y ∗ ) is eventually w, and then H2, which precedes H3, turns (x, y ∗ − 1), (x, y ∗ − 2), . . . , (x, y + 1) into w one after the other, whatever their previous states. So eventually λE = q0 and λN = w at r, and T3 applies unless T2 does; in either case r moves, a contradiction. P The robots stop. No robot moves west or leaves the columns x ≤ X, so there are at most r (X − xr ) 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 y ∗ , 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 (Section 9.3): the algorithm gathers on g from every one of the 4,445 placements of at most three robots in a 5 × 5 box and of four robots in a 4 × 4 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. 6.3

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 fieldsilently. The same holds for Line Formation from arbitrary configurations. Proof. Let (φ, F) be field-silent and consider the execution E1 of a single robot started on the origin. It reaches a fixed point at some round t0 . 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 E1 is finite and lies within distance ϱ of the origin, for some ϱ. Now start two robots on (0, 0) and (L, 0) with L ≥ 2ϱ + 4. By induction on t, the configuration at round t is the superposition of E1 and of its translate by (L, 0): a cell within distance ϱ + 1 of one of the two origins has all its neighbors at distance at least ϱ + 2 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 δ(q0 , . . . , q0 , 0) = q0 . 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.

7

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. 7.1

The Rules

Let Q = {q0 , e, w, a, r, l}. 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. 12

Autonomous Mobile Robots on a Computing Field

t=0

t=8

t = 18

t = 40 (line)

Figure 3: Line Formation from an arbitrary configuration with six states, n = 6. 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. Rule K1 K2 K3 K4 K5 K6 K7 K8

Condition on cell c c carries a robot λN = r ∧ λE ∈ {r, a, w}
λN = r ∧ λS ∈ {r, a} ∨ λW ∈ {r, a, e, l} ∨ λc ∈ {e, a, l} λE ∈ {r, a, w} λS ∈ {r, a} λW ∈ {r, a, e, l} λc = l otherwise Rule U1 U2 U3 U4

Condition ¬ρS ∧ λS = l ¬ρE ∧ λE ∈ {w, a} ρS ∧ ¬ρN ∧ ¬ρE ∧ λE ̸= l otherwise

Next state r w l w a e e λc (unchanged)

Action move S move E move E stay

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 Section 4: the top robot of a vertical stack slides east off the stack, and U1 lets it drop beside it (Fig. 3). 7.2

Correctness

Let ymin be the lowest row of P0 , as in Section 4. Lemma 14 (The ground). At every round, every cell of a row below ymin is blank and unoccupied. Proof. Induction on t. Robots move east and south only, and a robot of row ymin moves south only by U1, which needs the cell below it to be l; so no robot enters the rows below ymin as long as they are blank. A blank unoccupied cell of row ymin − 1 stays blank: its east, west and south neighbors are blank, so K4–K6 and the first two disjuncts of K3 fail, K2 fails, and λc is neither e, a nor l. In lower rows the north neighbor is blank as well. Lemma 15 (Collision-freedom). |Pt | = n for every t. 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 c in the same round therefore come from c + W and c + N. The robot on c + N applies U1, which requires λ(c) = l; the robot on c + W applies U2, which requires λ(c) ∈ {w, a}, or U3, which requires λ(c) ̸= l. Both read λ(c) 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 ymin , 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 ymin upward, that every robot of 13

Autonomous Mobile Robots on a Computing Field

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 ymin 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 ymin . 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 ymin , and let r, on (x, k), be the easternmost robot of the highest occupied row. The cells above r and east of r in its row are unoccupied, and the cell (x + 1, k) is not a landing zone, as nothing is above it. If a robot stood below r, U3 would be enabled. So (x, k − 1) is unoccupied, and since U1 is not enabled it is not a landing zone, although r stands above it. As some robot stands in row ymin ≤ k − 1, the pattern leaves only one possibility: (x, k − 1) is w, that is, a robot stands strictly east of column x in a row below k. Then (x + 1, k) is a or w and U2 is enabled, a contradiction. Hence all robots are in row ymin . 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 ymin 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 5 × 5 box, four robots in a 4 × 4 box and five robots in a 3 × 4 box, and on random configurations of up to 30 robots (Section 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.

8

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. 8.1

Four States: The Floor as a Rotor-Router

Let Q = {N, E, S, W}, the state of a cell being read as a pointer, with q0 = N, and let turn be the cyclic shift N 7→ E 7→ S 7→ W 7→ N. Rule X1 X2

Condition on cell c c carries a robot otherwise

Next state turn(λc ) λc

Rule Y

Condition λc = d

Action move d (d ∈ D)

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 v at its Look a v-round. In consecutive v-rounds the robot attempts consecutive directions of the cyclic order N, E, S, W. Proof. Let t < t′ be consecutive v-rounds. If the robot stays on v in round t, because its move was blocked, then t′ = t + 1 and v was occupied at the update of round t. Otherwise the robot leaves v in round t, v is unoccupied at every update until the robot re-enters it in the Move phase of round t′ − 1, and v is occupied at the update of round t′ − 1. In both cases X1 applies to v exactly once between the two Look phases. 14

Autonomous Mobile Robots on a Computing Field

27

22

23

24

25

26

13

8

9

10

11

12

144

60

61

62

63

64

6

1

2

3

4

5

6

1

2

3

4

5

58

1

2

3

4

5

13

0

9

10

11

12

27

0

23

24

25

26

55

0

35

25

15

7

20

15

16

17

18

19

20

15

16

17

18

19

52

42

32

22

12

9

torus, four states

torus, two states

bounded grid, four states

Figure 4: Round of the first visit of each cell for a robot started on (1, 1) of a 6 × 4 arena. On the torus both rotor fields sweep the arena row by row in wh + h − 1 = 27 rounds; on the bounded grid the four-state field needs 144 rounds. Theorem 5. The four-state rotor field solves Exploration of every torus Tw,h and of every bounded grid Bw,h . On Tw,h with w, h ≥ 2 the cover time is wh + h − 1 from every start cell; on Bw,h it is O(wh(w + h)). Proof. Perpetual exploration. The arena is finite, so some cell v has infinitely many v-rounds. By Lemma 17 every direction is attempted in one of any four consecutive v-rounds, so the robot enters every existing neighbor of v 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 (0, 0). In round 0 it reads N and moves to (0, 1). 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 (0, 1) after w rounds. This cell now turns to S and sends the robot to (0, 0), whose pointer is still N and turns to E; the robot runs east along row 0, re-enters (0, 0), is sent south to (0, h − 1), and so on. The rows are thus swept in the order 1, 0, h − 1, h − 2, . . . , 2; each sweep takes w rounds and is followed by one round that changes the row, except that the last sweep has seen its whole row after w − 1 rounds. With the initial round this gives 1 + (h − 1)(w + 1) + (w − 1) = wh + h − 1 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 m edges and diameter D within 2mD steps [15]; here m < 2wh and D < w + h. 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 4wh rounds on both arenas, which is what we observe in simulation for all sizes we tried (Section 9.3). In the long run every cell is therefore revisited within 4wh rounds. Fig. 4 shows the order of first visits. 8.2

Two States on a Torus, and Optimality

On a torus two of the four directions are enough. Let Q = {q0 , q1 }; 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 q0 and east if it is q1 . Theorem 6. The two-state rotor field solves Exploration of every torus Tw,h , with cover time wh + h − 1 for w, h ≥ 2. No field with a single state solves Exploration of a torus with w, h ≥ 2, so two states are optimal. Proof. Lemma 17 holds with the cyclic order N, E, and no move is ever blocked. Some cell v has infinitely many v-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 (0, 0) to (0, 1), runs east along row 1, re-enters (0, 1), which flips back to q0 and sends it north to (0, 2), and so on; the rows are swept in the order 1, 2, . . . , h − 1, 0, 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 k 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 Z2 may escape to infinity [18]. Whether a finite-state field lets an oblivious robot visit every cell of Z2 is open. 15

Autonomous Mobile Robots on a Computing Field

t=0 t=6 t = 11 t = 24

Figure 5: Equal spacing with gap k = 3 (five states). Green cells count the distance to the robot on the west (c1 light, c2 dark), orange cells are far from it. The dense group spreads east and the straggler comes west.

9

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 (Section 9.3) and are meant as evidence of the range of the model and as a source of problems. 9.1

The Floor as a Ruler: Equal Spacing

Robots stand on distinct cells of a row and must end exactly k cells apart, measured from the westmost robot, which does not move. Use k + 2 states {q0 , r, c1 , . . . , ck−1 , f}. A robot’s cell is r, and the cells east of a robot count their distance to it: the cell east of r becomes c1 , the cell east of cj becomes cj+1 , the cell east of ck−1 or f becomes f (“far”), and a cell with nothing to its west stays blank. A robot only reads the cells beside it: Condition λW ∈ {r, c1 , . . . , ck−2 } ∧ λE = c1 λW = f otherwise

Action move E move W stay

Meaning closer than k to the robot on the west farther than k λW = ck−1 : exactly k; λW = q0 : westmost

A robot steps east only into a cell that already shows c1 , that is, a cell that has registered it, and west only into a cell that shows f; 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 k = 2, . . . , 5 and up to 12 robots ended with the robots exactly k apart (Fig. 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. 9.2

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 q0 , r, w1 , w2 , w3 that make the rest of the floor an excitable medium in the sense of Greenberg and Hastings [20]: a resting cell (q0 , never excited, or r, resting again) that has an excited neighbor (w1 ) or an empty target next to it becomes excited, and an excited cell passes through w2 and w3 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 w2 only east, on w3 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 (Fig. 6); surplus robots simply stop. 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. 16

Autonomous Mobile Robots on a Computing Field

t=0

t=9

t = 25

t = 64 (filled, at rest)

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 (w1 darkest). Robots follow the waves, pass around the wall, and the floor comes to rest when every target is taken. Table 2: Instances checked by simulation (FSYNC).

9.3

Algorithm

|Q|

Instances

Line Formation, connected (Sec. 4, 5) Gathering, arbitrary (Sec. 6) Line Formation, arbitrary (Sec. 7) Exploration (Sec. 8) Exploration (Sec. 8) Equal spacing, k = 2, . . . , 5 Pattern filling and maze

4, 5 3 6 4 2 k+2 8

540 random connected configurations each, n ≤ 9 all 4,445 small placements, n ≤ 4; 890 random, n ≤ 100 all 5,237 small placements, n ≤ 5; 400 random, n ≤ 30 tori and bounded grids from 1 × 1 to 31 × 17 tori from 1 × 1 to 31 × 17 300 random rows for each k 360 random patterns without walls; one maze with four targets

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.

10

Conclusion

We proposed CAB OT, 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 CAB OT 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 Z2 by an oblivious robot on a finite-state floor is open. 17

Autonomous Mobile Robots on a Computing Field

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. [2] P. Flocchini, G. Prencipe, 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. [4] S. Das et al., “Autonomous mobile robots with lights,” Theor. Comput. Sci., vol. 609, pp. 171–184, 2016. [5] P. Flocchini, N. Santoro, G. Viglietta, and M. Yamashita, “Rendezvous with constant memory,” Theor. Comput. Sci., vol. 621, pp. 57–72, 2016. [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. [13] G. Theraulaz and E. Bonabeau, “A brief history of stigmergy,” Artificial Life, vol. 5, no. 2, pp. 97–116, 1999. [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. [18] L. Florescu, S. Ganguly, L. Levine, and Y. Peres, “Escape rates for rotor walks in Zd ,” 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. 18

Autonomous Mobile Robots on a Computing Field

[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.

19

Related documents

• Comparative Analysis Of Line Follower Robot Implementation: A Comparative Literature Study Of Arduino Microcontroller-Based Systems And Analog Systems Without Microcontrollers#1003128
• Software integration in mobile robotics, a science to scale up machine intelligence#1100180
• Técnicas inteligentes para la optimización de trayectorias en robots industriales y móviles#285943
• Plan de negocio para la creación de una empresa de limpieza de superficies verticales mediante el uso y desarrollo de robots autónomos sostenibles#230184
• La sanità del futuro: intelligenza artificiale, robotica e nuove frontiere del diritto#1375193