Physically Grounded Worst-Case Delays for Multi-Robot Plan Execution

Warehouse robot fleets run on plans computed by multi-agent pathfinding (MAPF), the problem of finding collision-free routes for many robots sharing a map. The plans assume every robot moves one grid cell per time step. Real robots slip, sag on low batteries, and brake over finite distances, so the plan is executed through a precedence structure that tells each robot whom it must wait for. Current execution methods are tested almost entirely against random delays, such as pausing 10% of agents at random. The failures that matter are rare and correlated: one slippery floor patch slows every robot that crosses a bottleneck, or one weak motor sits on the critical chain of a dense room map. Random testing will almost never hit these cases, which is the long-tail problem that safety research has documented for driving.

We propose to find such failures directly. We would write the execution of a multi-robot plan as a differentiable program. Physical parameters (floor friction by region, motor gain and battery sag per robot) set how long each move takes through a differentiable dynamics model. Precedence waiting is expressed as a smoothed "wait for the latest predecessor" operation. We then run gradient ascent on a small, physically plausible perturbation budget to find the parameter settings that most inflate completion time, induce stalls, or cause near-collisions under inertia. The two-sentence version is this. The timing of a multi-robot plan is a composition of max and plus operations over physically determined durations, so it can be differentiated end to end. That lets us search for rare, correlated physical faults that break adaptive execution schemes far more efficiently than random or black-box sampling.

Core Claim

The claim is conditional, and the condition is part of the idea. For a rigid precedence graph with independent per-move delays, the worst case needs no gradients. Completion time increases by the largest sum of delays along any precedence path, so an adversary with a total-delay budget just loads it onto the critical path. That can be computed exactly with a longest-path pass. We therefore treat that setting as a sanity baseline, not as the target.

Gradients earn their place under two conditions. The first is that delays are coupled through shared physical causes: one friction parameter changes the durations of dozens of moves across many robots, so the budget lives in a low-dimensional physical space rather than on individual edges. The second is that the executor adapts, reordering robots at intersections, which makes the worst case depend on the executor's own decisions rather than on a fixed longest path. Our claim is that in this regime gradient search through a smoothed execution model finds failures substantially worse than random sampling at equal budget, and matches or beats derivative-free search with far fewer simulator queries as the number of coupled parameters grows. We also claim that failures found in the smoothed model transfer to the exact, non-smoothed executor.

Where This Sits

The execution side supplies the object we differentiate. Ma et al. compile discrete plans into a Temporal Plan Graph and add kinematic limits through MAPF-POST, a post-processing step that turns the plan into a Simple Temporal Network so that slack absorbs small delays (Overview: A Hierarchical Framework for Plan Generation and Execution in Multirobot Systems). Two later lines make the precedence adaptive. Bidirectional Temporal Plan Graphs let robots swap passing order at switchable edges when no deadlock would result (Bidirectional Temporal Plan Graph). The Location Dependency Graph reorders blocked agents online (Multi-Agent Path Execution with Uncertainty). All three are evaluated only under random pauses, and they are the systems we would stress-test.

Liu et al. also prove that deciding feasibility under stochastic delays is NP-complete. This constrains our proposal. No gradient method can certify worst-case robustness, so we present our search as a falsification tool and measure its gap to exact worst cases on instances small enough to solve exactly.

The long-tail side motivates the approach. AdvSim perturbs background vehicles under a bicycle model and uses Bayesian optimization. The authors note that search becomes exponentially harder as adversaries are added (AdvSim). SAFE-SIM steers a trajectory diffusion model toward collisions while keeping behavior realistic (SAFE-SIM). Both perturb one to a few uncoordinated actors. Neither targets the combinatorial, chain-reaction failures that are characteristic of dense MAPF.

The differentiable-physics side supplies method. JAX MD shows that long rollouts can be differentiated for parameter calibration (JAX MD). DiSECt shows that smoothing contact discontinuities gives usable gradients at the cost of bias (DiSECt). The traffic work closest to ours derives analytical Jacobians for car-following and uses them to speed up policy learning (Traffic-Aware Autonomous Driving with Differentiable Traffic Simulation). That setting is one-dimensional and cooperative. We apply differentiation adversarially, to two-dimensional precedence-coupled fleets.

Research Program

Each move $e$ in the plan has a duration $d_e(\theta)$, produced by simulating a differential-drive robot with inertia and braking over that grid edge. Here $\theta$ collects the physical parameters (regional friction, per-robot motor gain, battery sag rate). The start time of move $v$ in the precedence graph obeys

$$t_v = \operatorname{smax}_\tau\big(\{\, t_u + d_u(\theta) : u \in \mathrm{pred}(v) \,\}\big),$$

where $\mathrm{pred}(v)$ is the set of moves that must finish before $v$ starts. The operator $\operatorname{smax}_\tau$ is a log-sum-exp soft maximum with temperature $\tau$, and it recovers the exact max as $\tau \to 0$. The adversary maximizes a failure objective $J(\theta)$ subject to $\theta$ lying within a plausibility set $\Theta_B$. $J$ is either makespan inflation or a smoothed count of moments where two robots' braking envelopes overlap. $\Theta_B$ is defined by per-parameter ranges that could occur on real hardware and a total deviation budget $B$.

Adaptive executors add discrete choices. For the bidirectional graph we relax each switchable edge's passing order into a soft mixture weighted by the executor's own local rule. For the location dependency graph we use a straight-through estimator: the forward pass runs the exact reordering, and the backward pass uses the soft relaxation. Every candidate $\theta$ is then scored in the exact, non-smoothed executor with hard max and hard switches, so relaxation bias can only lower the reported attack strength, not inflate it.

The second part asks whether found failures are useful. We would feed the discovered worst-case parameters back as targeted extra slack in MAPF-POST, or as extra switchable edges, and then measure robustness on held-out random and adversarial perturbations.

Baselines

The naive reference is the protocol the execution papers already use: random pauses and random physical parameter draws from the same plausibility set $\Theta_B$, sampled until the query budget matches ours. For each method we report the worst failure found. The attack counts as meaningful only if it beats random search by a clear margin at an equal number of exact-executor rollouts.

The strongest competitor for the search itself is derivative-free optimization over the same physical parameterization. We would run CMA-ES and Bayesian optimization in the AdvSim style. AdvSim reports finding failures in 75 queries per scene for one to two actors (AdvSim). Both methods get the same $\Theta_B$, the same exact-executor scoring, and the same total wall-clock and rollout budget, with hyperparameters tuned on held-out maps using a matched tuning budget. Beating them means reaching a higher worst-case makespan inflation, or a higher incidence of stalls and near-collisions, at equal rollouts, and showing that the advantage widens as the parameter dimension grows from a handful of regions to per-robot parameters for 50 or more agents.

The strongest executor under attack is the optimized Bidirectional Temporal Plan Graph. On MovingAI maps under random delays it reports median execution-time improvements of 8% to 20% over standard graphs and never produced a collision or deadlock (Bidirectional Temporal Plan Graph). A decisive result would be structured physical perturbations inside $\Theta_B$ that erase that advantage or produce near-collisions once inertia is modeled. For the online reordering executor, Liu et al. report about 0.25 seconds per timestep to coordinate 50 agents (Multi-Agent Path Execution with Uncertainty). We would keep that executor's per-step budget fixed while attacking it.

For the rigid graph we compute the exact worst case: a longest-path computation for independent delays, and a mixed-integer program over physical parameters on small instances. This measures how far gradient search falls from the optimum. No reported result was found on Lacuna for adversarial or worst-case delay attacks on any MAPF executor.

Two ablations isolate the key ingredients. The first applies gradient search to per-move delays directly, with no physics coupling. This tests whether shared physical causes are what make the problem both harder and more realistic. The second compares the soft relaxation with hard max plus subgradients, which tests whether smoothing is needed at all.

Why not just…?

Why not just sample random delays at higher rates? Random sampling is how the execution literature tests today, and the safety-generation survey argues that unguided sampling needs infeasible numbers of trials to reach corner cases (A Survey on Safety-Critical Driving Scenario Generation). Our equal-budget comparison measures this directly. If random search matches us on these maps, then the MAPF long tail is not narrow, and that is itself a publishable negative finding.

Why not just use CMA-ES or Bayesian optimization, which need no differentiable model? This is the real threat. With a few regional friction parameters, derivative-free search may well match gradients. Our prediction is that it degrades as coupled per-robot parameters grow, echoing the exponential wall AdvSim reports. The dimension sweep in the baseline comparison settles this. If the two curves never separate, we would recommend black-box search and restrict our contribution to the physically coupled threat model.

Why not just compute the worst case combinatorially? For rigid graphs with independent delays this is exactly right, and we adopt it as a baseline rather than compete with it. It stops working once one physical parameter moves many durations at once and the executor makes its own reordering decisions. At that point the worst case is no longer a single longest path, and the NP-completeness result suggests exact methods will not scale (Multi-Agent Path Execution with Uncertainty). The small-instance MILP comparison quantifies both the regime where exactness is affordable and our optimality gap.

Why not just train a model-free reinforcement-learning adversary? The traffic work found that gradient-enhanced policy optimization converges faster than plain PPO in congested settings (Traffic-Aware Autonomous Driving with Differentiable Traffic Simulation). The same data-efficiency argument applies here. We would include a PPO adversary over $\Theta_B$ with matched rollouts as a secondary baseline.

Proposed Experiments

Plans come from anytime large neighborhood search (Anytime Multi-Agent Path Finding via Large Neighborhood Search) on MovingAI maps (Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks). The maps are the warehouse, room, random, maze, and city layouts used by the bidirectional-graph and reordering papers, with 20 to 200 agents. The robot model is a JAX differential-drive simulator with acceleration limits and braking distances. Its parameter ranges would be calibrated so that the random-delay regime reproduces the pause statistics used in prior work.

Metrics are worst-case makespan and sum-of-costs inflation per unit budget $B$, rollouts needed to reach a target inflation, and the incidence of stalls longer than a fixed threshold. We also count near-collisions, defined as overlapping braking envelopes in continuous replay. A plausibility audit reports how many attacking parameter settings lie on the boundary of $\Theta_B$ versus in its interior.

Three checks are decisive. The first is transfer: attacks optimized in the smoothed model must remain damaging in the exact executor, and we report this gap for each temperature $\tau$. The second is scaling: the advantage over CMA-ES and Bayesian optimization must grow with parameter dimension. The third is usefulness: slack or switchable edges placed using discovered attacks must improve robustness on held-out adversarial perturbations without hurting nominal random-delay performance. That last test would show the long tail is being learned rather than overfit.

A feasible final step replays the worst discovered friction layouts on a small physical fleet in the style of the Ozobot and iRobot testbeds (ESO-MAPF). Tape strips or low-friction mats would realize the regional friction changes.