Domain-Randomized Travel Times for Robust Fleet Makespan

When a team of robots splits up a job, the job is finished only when the slowest robot finishes. Planners that minimize this finishing time, called the makespan, are usually built and tested on the assumption that every move takes a fixed, known amount of time. On real floors that assumption fails. Wheels slip on carpet, a heavy payload slows one robot, and a motor responds a few milliseconds late. Such noise is mostly harmless when the goal is total travel time, because delays simply add up. It is harmful for makespan, because the team's cost is a maximum, and any single robot that happens to straggle sets the result. Domain randomization is the practice of training or testing under many randomly perturbed copies of a simulator so that behavior survives an imperfect simulator. It has been used almost entirely to make single-robot controllers robust. We propose using it for a different job: generating realistic, jointly sampled travel-time scenarios, and feeding them to a combinatorial makespan planner that then optimizes the tail of the real finishing time rather than a deterministic proxy for it.

The key observation is that the structure of the randomization matters as much as its width. Some sources of variation are shared by the whole fleet, such as the floor material in a room. Others belong to one robot, such as its battery state or payload. Shared variation moves every robot together and inflates the maximum only mildly. Independent variation inflates it steadily as the fleet grows. A simulator randomized per episode, per robot and per region reproduces this correlation for free, while the usual fixes do not: padding every edge cost by a constant, or adding independent noise per edge. Our claim is that planning against scenario samples that keep this correlation produces assignments with lower realized high-percentile makespan. It also avoids the over-conservatism that independent-noise robustness causes. The gain should be concentrated in heterogeneous settings, where some robots or routes are noisier than others.

Core Claim

Let a joint plan $\pi$ assign ordered target sequences and paths to $N$ robots. Let $\theta$ be one draw of the randomized physical parameters, covering per-region friction, per-robot mass, motor gain and latency. Let $C_i(\pi,\theta)$ be robot $i$'s completion time when the plan runs under $\theta$. We plan for

$$\min_{\pi}\ \mathrm{CVaR}_{\alpha}\Big[\max_{i} C_i(\pi,\theta)\Big],\qquad \theta\sim p_{\text{cal}},$$

where $\mathrm{CVaR}_\alpha$ is the mean of the worst $(1-\alpha)$ fraction of outcomes, and $p_{\text{cal}}$ is a randomization distribution calibrated with a handful of real runs instead of set by hand as wide uniform intervals. The reason this differs from deterministic planning is the gap $\mathbb{E}[\max_i C_i]\ge\max_i\mathbb{E}[C_i]$. For roughly Gaussian, independent robot delays with spread $\sigma$, extreme-value theory gives an excess that grows about as

$$\mathbb{E}\big[\max_i C_i\big]-\max_i\mathbb{E}[C_i]\ \approx\ \sigma\sqrt{2\ln N}.$$

The excess shrinks toward zero as delays become perfectly correlated. A planner that knows which delays are shared and which are private can therefore do two things. It can move work away from robots and routes with high private variance, and it can decline to pad for variance that everyone suffers together. A deterministic planner cannot represent that tradeoff. Uniform padding represents only one uniform version of it.

Relation to Prior Work

The planner we extend is DMS*, which solves multi-agent combinatorial path finding for makespan. It defers expensive target-sequencing heuristics until nodes are expanded, and it reuses sequences for non-bottleneck robots whose delays fit inside their slack. DMS* was run on Husarion ROSbot 2 hardware, but it assumes unit edge costs and deterministic transitions. We keep its search and replace its scalar arrival times with vectors of arrival times over $K$ sampled scenarios. Its deterministic slack test becomes a probabilistic one: a sequence is reused if slack is non-negative in at least a $1-\delta$ fraction of scenarios. Other makespan-oriented planners supply our competitors rather than our method. Priority-Aware Multi-Robot Coverage Path Planning balances min-max workload in two phases on grid maps, assuming constant identical robot speeds. Mosaic uses an integer program to penalize workload imbalance among LLM-proposed actions, evaluated only in simulation with synthetic pose noise. Both treat execution time as known. Our proposal changes what "cost" means for them, not how they search.

The domain randomization side supplies the scenario generator. Sim-to-Real: Learning Agile Locomotion For Quadruped Robots randomizes dynamics and injects actuator latency in PyBullet. It also constrains our design: randomization alone was not enough there, and matching real speed required identifying motor dynamics and latency. This is why we calibrate $p_{\text{cal}}$ rather than widen it. Reinforced Grounded Action Transformation and its multi-agent variant JL-GAT correct the simulator using real transition data. JL-GAT optimizes average travel time in traffic grids and validates by a sim-to-sim protocol, CityFlow as "sim" and SUMO under rain and snow as "real". We borrow that protocol, but we measure makespan tails, which JL-GAT never examines. COOL-DRMC builds ambiguity sets over the motion of obstacles for local collision avoidance. We apply the same distributional thinking to the robots' own travel times at the task-allocation level, which COOL-DRMC does not address. NCF2 motivates the problem from the learning side: it shows plain navigation policies leave arrival delays badly unbalanced. However, it assumes deterministic transitions, so it says nothing about how physical noise redistributes who straggles.

Research Program

The first component is a travel-time scenario model. We run a fixed low-level waypoint-tracking controller for a differential-drive robot in a physics simulator. The randomized parameters are organized into three groups by who shares them: per-region surface friction shared by every robot in the region, per-robot mass, motor gain and command latency, and small per-traversal noise. For each graph edge type we record traversal times and fit a duration model conditioned on edge features and $\theta$. The model is cheap enough that the planner can evaluate $K$ scenarios, with $K$ from 32 to 256, per candidate plan. Calibration fits the group-level parameter distributions to a small set of timed real traversals, on the order of tens of edge runs per robot and floor type. Scenarios are then drawn from the fitted distribution.

The second component is the scenario-based DMS* extension described above. Search nodes carry per-scenario arrival vectors. The node cost is the sample CVaR of the per-scenario maximum. Deferred sequencing is kept, and margin-based reuse becomes probabilistic. Because each scenario's maximum is evaluated exactly, correlation is handled without any covariance modeling.

The third component is an analysis of when the method should and should not help. We predict parity with simple padding when variance is homogeneous across robots and routes. We predict gains that grow with fleet size and with heterogeneity in private variance. We predict that an independent-noise model will over-pad, most visibly when shared variance dominates. These predictions are stated before running the experiments, and they are what make the results falsifiable.

Baselines

The naive reference point is deterministic DMS with nominal unit or mean edge durations. It is executed open-loop and also with a simple greedy reassignment when a robot falls behind. DMS* is the strongest existing makespan planner in the file for this problem class. It reports roughly tripled planning success over MS under a 60-second limit and makespans up to 50% shorter than iterative greedy baselines. No reported result was found on Lacuna for realized makespan, or for its tail, under physical or randomized travel-time noise. We therefore run it ourselves, on the same maps, with the same 60-second planning budget and the same executor.

The strongest simple competitor is quantile-padded DMS. Each edge cost is replaced by a per-robot, per-floor-type $\alpha$-quantile of the same calibrated simulated durations. It uses identical data and identical calibration. The only difference is that it collapses the scenarios into padded scalars, discarding their joint structure. We also include mean-duration DMS, which uses the calibrated simulator only for expected times.

The key-ingredient ablation keeps our full planner but resamples every edge duration independently from the same marginals. This destroys correlation while keeping variance unchanged. A second ablation replaces $p_{\text{cal}}$ with wide uniform randomization intervals, to test the over-conservatism concern. For the coverage setting, we re-cost Priority-Aware MCPP phase-2 partitioning with the scenario objective and compare it against the original. That paper's reported reference is a 62.5% reduction in priority-weighted latency versus MSTC* at a 9.7% makespan increase, on idealized grids.

Beating the baselines means lower realized 90th-percentile and CVaR makespan than quantile padding in the heterogeneous settings, at comparable mean makespan and within the same planning budget. It also means lower tail makespan than the independent-noise ablation in shared-variance settings. Parity with padding in homogeneous settings is the predicted outcome and does not count against the method.

Why not just…?

Why not just pad every edge with a safety margin and keep the deterministic planner? This is the real threat, and we treat it as one. When all robots and routes have similar variance, padding by a quantile shifts every plan's cost by roughly the same amount, so it picks nearly the same assignment we would. The difference appears only when variance is uneven, for example one robot carrying a payload or one room carpeted. There, a padded scalar cannot express that a plan concentrating work on the noisy robot has a fatter maximum. It also cannot express that shared floor noise does not compound across robots. Our homogeneous-versus-heterogeneous map sweep is designed to show exactly where padding ties and where it loses. If it ties everywhere, the claim is wrong.

Why not just plan deterministically and replan greedily when someone falls behind? Replanning is compatible with our method, so both arms get the same reassignment trigger, and we count replanning events and realized makespan. Evidence from the file suggests greedy repair is costly. Iterative greedy approaches produced makespans up to 50% longer than combinatorial search in DMS*. Mosaic found embodied agents losing 16–51% of execution time to failed actions and recovery loops. A plan that already anticipates who will straggle should trigger fewer repairs, and that is measured directly.

Why not just train an end-to-end multi-robot policy with domain randomization and a time penalty? Such policies do not solve the combinatorial target-assignment problem that dominates makespan here. Even on navigation alone, NCF2 shows that plain learned navigation leaves arrival delays badly unbalanced, with delay variance of 133.9 for Nav-Only versus 74.6 with its fairness filter in CORNER-12-25, under deterministic dynamics. We therefore do not expect a learned policy to compete on assignment. We do include NCF2's continuous environments to check whether scenario-based allocation plus a standard local navigator matches it on makespan once dynamics noise is added.

Why not just randomize more widely until the plan is insensitive? Wide randomization makes every edge look slow and noisy, which pushes the planner toward uniformly cautious, longer plans. This mirrors the over-conservatism known for randomized controllers. Sim-to-Real: Learning Agile Locomotion needed identified motor and latency models, not just broader ranges. The wide-uniform ablation tests this directly on mean and tail makespan.

Proposed Experiments

Sim-to-sim transfer follows the JL-GAT protocol. Plans and scenario models come from one simulator configuration. Execution happens in a held-out "real" simulator with different, fixed but unknown parameters: surface friction per room, per-robot payload and motor degradation, and added command latency. The calibration step sees only a small budget of timed traversals from the "real" side. Maps are the nine MCPP grid maps (office, house, estate, outdoor) and the DMS* target-set instances, with 3 to 20 robots. Each map is run in two regimes, one with homogeneous and one with heterogeneous private variance, and in each regime the balance of shared versus private variance is swept. Metrics are mean, 90th-percentile and CVaR makespan over at least 200 executions per instance, the gap between planned and realized makespan, deadline success rate, planning time under the 60-second cutoff, and number of replans. The continuous NCF2 environments (UNIFORM and CORNER, 25 and 50 obstacles) serve as a secondary check with non-holonomic motion.

Hardware transfer uses a small Husarion ROSbot 2 fleet, matching the DMS* deployment, on a floor mixing tile and carpet, with payloads attached to a subset of robots. Calibration uses tens of timed traversals per robot and floor type, and evaluation repeats each instance enough times to estimate a 90th percentile.

Three checks are decisive. First, the planned-versus-realized makespan gap of deterministic DMS* should grow with fleet size roughly as the $\sqrt{\ln N}$ extreme-value form predicts. Our scenario model should predict the realized distribution closely, and the independent-noise ablation should overestimate it when shared variance dominates. If neither pattern appears, the correlation argument fails. Second, the full method should beat quantile padding on tail makespan in heterogeneous regimes and tie in homogeneous ones. Winning by a wide margin in homogeneous regimes would point to a bug rather than a result. Third, the calibrated distribution should beat wide uniform randomization on mean makespan without losing on the tail, which would show that the benefit comes from correct structure rather than extra caution.