Silence-Indexed Contracts: Certified Multi-Robot Safety When the Radio Goes Quiet

When robots coordinate over a wireless link, each one keeps a mental picture of where its teammates are. The moment messages stop arriving, that picture starts to go stale, and it goes stale continuously: a teammate that last reported its position 50 milliseconds ago is almost exactly where it said, and one that went silent four seconds ago could be in many places. Existing methods either ignore this decay or treat it crudely. Formal planners assume perfect communication. Learned multi-agent controllers tolerate delay empirically but certify nothing. The cautious fallback, which assumes a silent teammate could be anywhere it could physically reach, makes tight coordination such as two vehicles sharing a narrow passage provably impossible.

We propose that each robot publish, ahead of time, a silence-indexed contract: a guarantee of the form "if my last message placed me in region $q$, then for any silence lasting between $\tau_k$ and $\tau_{k+1}$ seconds, I will be inside region $R(q,k)$ with probability at least $1-\epsilon$." Each robot then plans against its teammates' contracts instead of against their worst possible behavior, and must also honor its own contract while doing so. Each contract is certified from data with interval-valued transition probabilities, so a single robot's planning problem stays small: its own few state dimensions plus one clock that counts time since the last message. A message resets that clock and shrinks the region. The bet is that conditioning on elapsed silence and on a pre-agreed behavior gives certified joint safety that is much less conservative than worst-case padding, at a fraction of the cost of planning over the joint state of all robots.

Background and the gap

The interval Markov decision process (IMDP) is the formal tool we build on. It is a planning model in which each transition probability is known only to lie in an interval, and a planner computes policies that hold against every probability inside those intervals by letting an adversary, "Nature," pick the worst one. Data-Driven Yet Formal Policy Synthesis for Stochastic Nonlinear Dynamical Systems builds such abstractions for nonlinear systems from samples, using Lipschitz bounds on backward reachable sets and Clopper-Pearson confidence intervals. It reports probably-approximately-correct reach-avoid lower bounds, for instance 0.572 on car parking with 10,000 samples against 0.490 for the scenario approach. The method is discrete-time, single-agent, and limited to two or three state dimensions. We reuse it as the per-robot abstraction engine. Probabilities Are Not Enough supplies the scaling idea: weak couplings between subsystems are treated as bounded nondeterministic disturbances, which let a 10-dimensional building model be solved in about 8 minutes where coupled abstractions ran out of memory. Its disturbance bound is a fixed constant and its controller is centralized. In our setting the coupling is the teammate's position, and its bound should grow with silence time. That makes the bound time-varying and informed by communication.

Continuous time enters through the clock. CTMCs with Imprecisely Timed Observations unfolds a continuous-time chain into pairs of state and observation time, abstracts continuous time intervals into a finite IMDP, and refines the time partition until upper and lower bounds meet. We borrow this unfolding for the silence clock. The difference is that our clock is reset by stochastic message arrivals, and the underlying state follows nonlinear physical dynamics rather than a discrete-state jump process. Safe Continuous-time Multi-Agent Reinforcement Learning via Epigraph Form tackles continuous-time multi-agent safety with neural solvers of the Hamilton-Jacobi-Bellman equation. It assumes ideal communication and gives no certificates, so it is a point of contrast rather than a component.

On coordination, Planning Not to Talk is the closest motivation. It minimizes inter-agent dependency so that agents can simulate teammates ("imaginary play") during blackouts, and keeps 97% success under total blackout versus 82% for a baseline in grid worlds. It assumes exact transitions on a grid, so its simulated teammates drift from reality without any bound. CoDe and Sequential World Models share learned intents or planned trajectories and handle delay empirically, without guarantees. Our contracts can be read as a certified version of a shared intent: a promise about future occupancy whose width is honest about how much the sender's own noise and model error can accumulate during silence.

The file also surfaces a tension. Treating cooperative teammates as worst-case Nature is what makes multi-agent interval planning hopelessly conservative. Contracts resolve this in an assume-guarantee style: a teammate is adversarial only within the region it has promised to stay in.

Core Claim

For robots with nonlinear stochastic dynamics coordinating over a lossy, delayed channel, the following holds under a modelled channel. Planning each robot against its teammates' silence-indexed contracts, and constraining it to honor its own, yields a sound lower bound on the probability of joint reach-avoid success. That bound is substantially tighter than both constant-disturbance decoupling and the bound from padding each teammate by maximum speed times silence time. Computation grows roughly linearly in team size, not exponentially. The bound composes by a union argument. If robot $i$ satisfies its own contract except with probability $\epsilon_i$, and reaches its goal while avoiding the contract regions of others with lower-bound probability $p_i$, then

$$ \Pr(\text{all robots succeed}) \;\ge\; 1 - \sum_{i=1}^{n}\big[(1-p_i) + \epsilon_i\big], $$

where $n$ is the number of robots. It follows from a union bound over each robot's failure to reach its goal and its failure to keep its promise.

Research Program

The per-robot abstraction is a product of three parts: a grid over the robot's own continuous state (three dimensions for a unicycle or car), a finite partition of the silence clock into intervals $[\tau_k,\tau_{k+1})$, and the last-reported region of each teammate, coarsened to a small set of contract indices. Transitions in the physical state get Clopper-Pearson intervals from sampled trajectories, as in Data-Driven Yet Formal Policy Synthesis. Clock transitions get intervals from a channel model fitted to logged packet traces. We will use Bernoulli drops, a two-state bursty model, and delay distributions. A received message resets the clock. Its arrival probability within a continuous time slice is bounded by an interval, which the partition refinement of CTMCs with Imprecisely Timed Observations tightens.

A contract $R_i(q,k)$ is computed as a set that robot $i$'s abstraction, under its own policy, stays inside with probability at least $1-\epsilon_i$ for every silence slice $k$. It is computed from the same backward-reachability machinery run forward over the abstraction.

Synthesis alternates. We fix the current contracts and solve each robot's robust value iteration, which treats teammate occupancy as nondeterministic within their contracts and adds the robot's own contract as a constraint. We then recompute the contracts from the new policies and shrink them where slack allows. The iteration stops when the contracts stop changing or the bound stops improving. We will study when this converges, because a contract can only be tightened if the policy that enforces it remains feasible.

A design choice we expect to matter is letting contracts switch modes with silence length. A robot might promise to stay close to its planned path for short silences and to retreat to a pre-agreed holding region for long ones. This is a certified analogue of the spatial separation that Planning Not to Talk found emerging from dependency minimization.

The open technical risk is circularity in the assume-guarantee loop and the coarseness of the teammate-region index. Both will be measured, not assumed away.

Baselines

The naive reference point is a planner that treats the last received teammate state as current. It is the same per-robot IMDP but with no clock and a zero-width teammate region. It shows what happens when staleness is ignored. We expect it to report high certified values that empirical simulation then violates, demonstrating that its "bound" is unsound.

The strongest simple competitor is maximum-speed padding. Each silent teammate is replaced by a ball of radius $v_{\max}\tau$ around its last reported position, and each robot plans against the balls with the identical per-robot IMDP, sample budget, and grid. This baseline isolates our key ingredient: conditioning the teammate's region on its committed policy and data-driven intervals rather than on physics alone. We beat it if, at matched computation, our certified joint lower bound is higher on tight-coordination tasks and our task completion time is shorter, with no loss of soundness.

The strongest existing formal method is constant-disturbance decoupling in the style of Probabilities Are Not Enough, with one silence-independent bound per teammate. On two-robot instances small enough to solve, we also compare against the full joint IMDP from Data-Driven Yet Formal Policy Synthesis. The joint model gives the tightest achievable bound and tells us how much tightness decoupling costs. For a single robot, that paper reports a car-parking lower bound of 0.572 at 10,000 samples. We will reproduce this number before building on it. For multi-robot continuous nonlinear reach-avoid under communication loss, no reported result was found on Lacuna, so all multi-robot numbers will be produced here under one protocol.

Two baselines represent the empirical camp. On the grid-world blackout task we run the minimum-dependency policy of Planning Not to Talk; its reported 97% success under total blackout is the number to match. On the continuous tasks we run a CoDe-style intent-sharing learner trained with message dropout and delay. It gets the same simulator, the same channel models, and a training budget equal to our total sampling and synthesis compute; its hyperparameters are tuned on held-out channel settings. Here we compare empirical success and collision rate. The learner cannot produce a certificate.

Two ablations isolate the remaining design choices. The first removes the clock, using one contract per last-reported region regardless of silence length. The second replaces the refined continuous-time partition with a fixed coarse time step.

Why not just…?

Why not just pad teammates by maximum speed times silence time? This is the real threat. It is sound, trivial to implement, and needs no contracts. For loose tasks such as robots with distant goals it may well match us, and we will report that honestly. Its weakness is that the padding grows linearly without limit, regardless of what the teammate is actually doing, so any task requiring proximity under even moderate silence becomes infeasible. The two-car crossing experiment below is designed to show whether contracts recover feasibility there. If they do not, the contribution reduces to a scheduling heuristic, and we would drop the claim.

Why not just use tube model predictive control with linearization and a latency margin? Linear tubes rely on ellipsoids staying ellipsoids. Under nonlinear car dynamics this fails, and the margins absorbing linearization error become large. Probabilities Are Not Enough also shows how controllers that ignore epistemic uncertainty can collapse, with safety dropping from 100% to 6% at parameter limits. Tube MPC also has no native model of stochastic packet loss beyond worst-case stopping. We will include a linearized tube baseline on the crossing task, with latency margins set to the 99th-percentile delay, and measure both collisions and deadlocks.

Why not just train multi-agent reinforcement learning with dropout? This may achieve high empirical success, and CoDe shows learned intent alignment beats earlier communication learners under delay, at 68.6% versus about 38–43% on a 5-step-delay StarCraft task. It produces no lower bound, however, and we will test it under channel conditions outside its training distribution. Our claim is not higher reward but a certificate that holds under shifts in the channel within the modelled class.

Why not just discretize time coarsely and use a standard discrete-time IMDP? A coarse step either misses message arrivals within the step or must assume the worst over the whole step, inflating contracts. The fixed-step ablation directly measures how much bound tightness the partition refinement buys. If the gain is negligible, the continuous-time component should be dropped in favor of the simpler model.

Proposed Experiments

The testbeds extend benchmarks from the file. The base is the car-parking nonlinear model of Data-Driven Yet Formal Policy Synthesis, duplicated into two- and three-car scenes: crossing a single narrow gate, modelled on the Gate task of Sequential World Models, and swapping parking bays. Robots carry additive process noise and uncertain parameters such as an uncertain mass, as in the drone benchmark of Probabilities Are Not Enough. The grid-world blackout task of Planning Not to Talk serves as a sanity check against a published number. Channel regimes sweep drop probability from 0 to total blackout, include bursty losses, and include Gaussian delays.

The metrics are four. The first is the certified joint lower bound. The second is empirical joint success over at least 10,000 Monte Carlo rollouts per setting, used to check soundness: the empirical rate must never fall below the bound. The third is the conservatism gap between empirical success and the bound. The fourth is completion time and deadlock rate, and synthesis time as a function of team size.

Three checks are decisive. First, soundness must hold in every regime, including mismatched channel parameters inside the modelled interval. Second, on gate crossing at moderate silence, the contracts must certify a nonzero joint bound in settings where maximum-speed padding certifies zero, while staying within a stated fraction of the joint-IMDP bound on two-robot instances. Third, synthesis time must grow close to linearly from two to three robots, whereas the joint abstraction becomes infeasible. Failing the second check would falsify the core claim. Failing only the third would leave a tighter but unscalable method, and we would say so.