cs.DCNov 12, 2026

Autonomous Mobile Robots on a Computing Field

Authors: Yonghwan Kim, Gil-Tak Kong, Un-Sook Choi

Organizations: Nagoya Institute of Technology, Nagoya, Japan · Busan National University, Busan, Republic of Korea · Tongmyong University, Busan, Republic of Korea

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.

Figures & tables

Explore similar work

Nov 3, 2026

Nested Field-of-View Barriers for Teleoperated Multi-Robot Relay Chains

Teleoperation of mobile robots in communication-denied environments requires maintaining a communication link while allowing the operator to maneuver freely. We propose a shared-autonomy framework in which a teleoperated leader is followed by a chain of autonomous robots that relays a line of sight to a fixed base station, a geometric proxy for the link. Connectivity is enforced geometrically through visibility-based Control Barrier Functions (CBFs), with each agent computing its control input locally through a quadratic program. A strict visibility constraint guarantees connectivity, but a follower with no independent motion objective remains stationary, stalling the leader at the boundary of the safe set. Relaxing it preserves mobility at the cost of the guarantee. Our framework resolves this conflict through nested hard-soft visibility constraints: a full field-of-view (FoV) constraint enforced strictly to guarantee connectivity and a contracted FoV constraint imposed on each follower as a relaxed behavioral objective that drives it inward before the connectivity boundary is reached. We prove feasibility of the local quadratic programs and forward invariance of the connected, collision-free set under the resulting distributed controller. The contraction parameter shapes follower behavior without affecting the guarantee, which follows from the strict constraint alone. The framework is evaluated in confined and cluttered environments on two simulated systems: a kinematic integrator and software-in-the-loop Crazyflie quadrotors. Compared with a baseline tuned to reach the goal in comparable time, the framework keeps the links far closer to the connected set and moves the followers less.
Oct 3, 2026

Budget-Constrained Fault-Tolerant Mutual Visibility for Autonomous Robots under the Mobility Fault Model

We investigate the mutual visibility problem for a swarm of n≥3n\ge3 autonomous mobile robots under the budget-constrained mobility fault model. The robots are opaque, so if three robots are collinear, the middle robot obstructs the visibility between the other two. Each robot is assigned a finite movement budget, reflecting its limited energy, that bounds the total distance it may traverse during the execution. Moreover, an arbitrary number of robots may become permanently immobile due to mobility faults. The objective is to design a distributed algorithm that enables the non-faulty robots to coordinate their movements so that, within a finite time, every non-faulty robot attains unobstructed visibility of all robots in the system, including the faulty ones, while respecting the prescribed movement budget. We consider luminous robots operating under the SSYNC\mathsf{SSYNC} model with non-rigid movements, without any agreement on their local coordinate systems, and equipped only with a {\it common fixed reference point}. We present a deterministic distributed algorithm that solves the problem despite an arbitrary number of mobility faults. The algorithm guarantees mutual visibility for the non-faulty robots, respects the movement budget of every robot, provides collision-free movements for the robots, and uses only 12 light colors.
Oct 28, 2026

Minimum Sufficient Communication for Independent Behaviour Tree Robot Teams

We present an experimental framework for determining sufficient communication in robot teams running fixed, independent Behaviour Trees with private blackboards. Within a declared policy family, we vary message content and admission frequency and measure traffic in recipient-weighted bits per robot decision. A dense sweep identifies candidate policies for comparison with full-state communication. We retest selected candidates and the reference on fresh, paired scenarios, using one-sided simultaneous confidence bounds to assess whether success remains within five percentage points of the full-state reference. The bounds also assess whether tested cheaper policies can be ruled out as insufficient. Depending on the evidence, the framework reports an exact minimum, a positive bracket, a sufficient upper bound, or an unresolved boundary. Experiments with eight content policies across four warehouse conditions identify zero communication as the exact minimum under low contention. In the scaled condition, the no-release policy at gate q=0.992222q=0.992222 is confirmed sufficient, achieving 96.33% success at an estimated rate of 738.55 bits per robot decision, or 0.544% of full-state traffic. The positive minimum remains unresolved. These claims apply only to the declared policy family, sampled gate values and operating conditions.