Risk-Calibrated Multi-Robot Schedules from Randomized Simulation

Multi-robot planners that satisfy temporal logic, meaning formal rules such as "robot A must reach the dock within 40 seconds, and only after robot B has cleared the aisle," usually assume each robot needs a fixed, known time to drive each route. Real robots do not behave this way. Motors lag, wheels slip, and two robots of the same model can differ noticeably in speed. One late arrival then propagates through every task that depends on it. Researchers who train robot controllers in simulation already handle this kind of variation through domain randomization: they train under many randomized versions of the physics so that the real world looks like one more sample. That randomized simulator holds exactly the information a scheduler is missing, namely how long each robot's controller takes to cross each route under plausible physics. Planners currently do not use it.

We propose to turn domain-randomized rollouts of each robot's learned driving controller into travel-time intervals for each robot and each route. A small number of real traversals per robot then adjusts these intervals, using conformal prediction, a distribution-free method that converts held-out errors into intervals with guaranteed coverage. The adjusted intervals are passed to a chance-constrained temporal scheduler, which assigns and times tasks so that the whole fleet meets its timed-partial-order or temporal-logic specification with a user-chosen probability on hardware. Two claims follow. The realized real-world failure rate should track the requested risk budget. And for the same failure rate, schedules should finish faster than uniformly padded schedules, because the padding goes only where it is needed: to particular robots and particular routes.

Core Claim

The obvious combination would be to "train controllers with domain randomization, then run a multi-robot temporal logic planner on top." That combination is incomplete, because the planner never learns how uncertain execution is. The closest existing work shows each half separately. Signal Temporal Logic Compliant Co-design of Planning and Control pairs reinforcement-learned motion primitives with a sampling planner over space and time on a Go1 quadruped and Turtlebot3s. Its travel-time estimator, however, is a deterministic curve fit trained in one nominal simulator, and it handles only one robot. Chance-Constrained Probabilistic Simple Temporal Problems schedules many vehicles under uncertain durations by dividing a risk budget across activities with a union bound. It assumes the duration distributions are known and stationary, and it never asks where those distributions come from or whether they hold on real hardware. Robust Conformal Prediction for STL Runtime Verification under Distribution Shift shows that conformal calibration can carry temporal-logic guarantees from simulation to a shifted test distribution, but it only monitors a single simulated arm and never makes plans.

Our contribution is the pipeline that connects these three. Each robot gets its own sim-to-real correction factor, and that factor determines the duration bounds a fleet scheduler optimizes over. The guarantee is that every temporal constraint holds with probability at least $1-\Delta$, where $\Delta$ is the risk budget, provided the calibration assumption holds. The scheduling and allocation decisions also change as a result: a robot whose real traversals run slow receives fewer tightly timed tasks.

Research Program

Controllers and simulated durations. We train goal-reaching driving primitives for differential-drive robots (Turtlebot3, Jackal) under dynamics randomization over mass, wheel friction, motor gain, and control latency. The latency ranges follow the 15–19 ms loop delay that Sim-to-Real: Learning Agile Locomotion For Quadruped Robots found was required for transfer. We then use the randomized simulator a second time. For each route $e$ in the workspace's roadmap, we roll out the trained controller under $K$ randomized physics draws, which gives an empirical travel-time distribution with median $m_e$. Inter-robot collisions are handled by adding exclusive-resource constraints on narrow corridors to the schedule. We do not leave them to post-processing, which is a limitation the file notes in the timed-partial-order planner.

Per-robot calibration. Each physical robot $r$ drives $n$ short calibration routes, about 20 to 30 total, pooled across many routes. For each one we record the score $s = d^{\text{real}}_{r,e} / m_e$, the real duration divided by the simulated median. Let $\hat q_r(\delta)$ denote the $\lceil (n+1)(1-\delta)\rceil$-th smallest score for robot $r$, and $\check q_r(\delta)$ the matching lower order statistic. The duration interval handed to the scheduler is then

$$ \big[\, m_e \,\check q_r(\delta_e),\; m_e\, \hat q_r(\delta_e) \,\big], $$

where $\delta_e$ is the share of the global risk budget $\Delta$ assigned to route $e$. Standard split-conformal reasoning gives each interval coverage of at least $1-\delta_e$, as long as deployment traversals are exchangeable with the calibration traversals for that robot. The union bound then gives fleet-level success of at least $1-\Delta$, following the same risk-allocation logic as the chance-constrained scheduler. Two choices make this sample-efficient. Pooling across routes through a ratio score means a few real runs per robot are enough. And because the simulated distribution sets the shape of the uncertainty, the real data only has to correct its scale. Where the exchangeability assumption is doubtful, for example as batteries drain, we substitute the shift-robust variant from the conformal STL paper with a total-variation slack.

Scheduler. We extend the mixed-integer formulation of Optimal Planning for Timed Partial Order Specifications, which handles task allocation with time windows and precedence. In our version, each robot–route assignment carries its calibrated interval, and the timing must remain feasible for every duration inside those intervals, which is the strong-controllability requirement. The risk shares $\delta_e$ are optimized jointly, as in the chance-constrained scheduler. For specifications given in linear temporal logic, we use the decomposition of Temporal Logic Task Allocation in Heterogeneous Multirobot Systems unchanged, swapping only its fixed edge costs for the calibrated intervals.

Baselines

The naive reference point plans with the nominal-simulator mean travel times and no padding. This is the deterministic-estimator approach of the STL co-design paper extended to a fleet, and it measures how much a schedule that ignores uncertainty fails.

The strongest practical competitor is uniform padding tuned on real data. Every nominal duration is multiplied by a single factor, and that factor is tuned on the same real calibration runs our method receives, so that it hits the target success rate. This baseline gets the same real data and the same solver time limit as our method. It is also given a second chance: the post-hoc tolerance computed by the timed-partial-order paper's linear program.

The strongest published method is the chance-constrained scheduler of Chance-Constrained Probabilistic Simple Temporal Problems, with Gaussian durations fitted to nominal-simulator rollouts. That paper reports schedules 5.37%–6.82% faster than earlier risk-minimizing methods, and roughly 90% success under a 10% risk budget on its 1,800-instance Boston car-sharing benchmark, where the assumed distributions are exactly correct. No reported result was found on Lacuna for any temporal-logic multi-robot planner's measured deadline satisfaction on real hardware; the Jackal deployment of the timed-partial-order paper reports viability only.

Three ablations isolate which ingredient matters. The first replaces the randomized rollouts with nominal-simulator rollouts and keeps the conformal calibration, which tests whether domain randomization contributes. The second keeps the randomized rollouts but removes calibration, which tests whether real data contributes. The third uses a single calibration factor for the whole fleet instead of one per robot, which tests whether per-robot heterogeneity matters.

Our method beats a baseline if, at a matched realized failure rate, its makespan is lower with non-overlapping confidence intervals across missions, or if, at matched makespan, its realized failure rate is lower. Against the published scheduler specifically, the bar is that our realized failure rate on hardware stays at or below $\Delta$ while the Gaussian-from-nominal version exceeds it.

Why not just…?

Why not just pad every travel time by a tuned margin? This is the most serious threat. On a fleet of near-identical robots with nearly uniform slippage it may perform as well as our method. Our advantage should appear only when sim-to-real error varies across robots or across routes, for example on tight turns, ramps, or worn units. The experiments therefore vary heterogeneity directly. If the gap in makespan at matched risk disappears in every heterogeneity condition, we will report that per-robot calibration is unnecessary.

Why not just fit duration distributions directly from real runs, as system identification would? With hundreds of runs per robot per route, that would work and would make simulation unnecessary. With a budget of 20 to 30 runs per robot spread over dozens of routes, per-route estimates of the 95th percentile are unreliable. The ablation in which real data alone sets the intervals, under the same run budget and with no simulated shape, tests whether domain randomization adds anything. Towards Closing the Sim-to-Real Gap in Collaborative Multi-Robot Deep Reinforcement Learning also shows that actuation errors differ from robot to robot in ways a single calibrated model cannot capture. That supports per-robot correction, though not necessarily simulation.

Why not just replan online when robots fall behind? Replanning helps when deadlines are soft. It cannot recover time already lost on strict, use-it-or-lose-it windows or on synchronized handoffs. We run a version of the nominal baseline that replans every time an arrival is late, and we compare its constraint violations and its replanning cost against those of our method.

Why not just use pessimistic domain randomization at the controller level? SPiDR: A Simple Approach for Zero-Shot Safety in Sim-to-Real Transfer reduced safety violations sharply; standard domain randomization had 26.1 times more violations on the Go1. Its penalty, however, applies to individual steps and keeps a robot away from uncertain regions. It says nothing about whether a team meets its deadlines, and the paper itself warns that too much pessimism slows robots down, which would make deadlines harder to meet. We treat it as an option that complements our method, using pessimistic controllers underneath, rather than as a replacement.

Proposed Experiments

In simulation, we build a heterogeneous navigation fleet in which a chosen fraction of robots, 0%, 17%, 50%, or 83%, receive variable actuation errors modeled on the variable-output-error condition of the collaborative multi-robot study. Their missions are the aircraft-turnaround and synthetic timed-partial-order benchmarks from Optimal Planning for Timed Partial Order Specifications, and we report solve times against its 182 ± 102 seconds for 160 tasks across 40 robots. The test physics are drawn partly from inside the randomization range and partly from outside it, so we can measure how the guarantee degrades when reality falls outside the prior. On hardware, we use six Turtlebot3s and three Jackals. Two Turtlebots are deliberately degraded with added mass and reduced motor gain. The robots run 100 or more timed-partial-order missions in a lab with shared narrow corridors.

We measure four things: the realized fraction of missions in which every constraint holds, plotted against the requested $1-\Delta$ for $\Delta$ of 0.05, 0.1, and 0.2; makespan at matched realized risk; the number of real calibration runs needed; and whether tight tasks are actually reassigned away from the degraded robots.

Three outcomes decide whether the idea works. Realized failure must stay at or below $\Delta$ on hardware while the Gaussian-from-nominal scheduler exceeds it. Our method must achieve lower makespan than tuned uniform padding when the fleet is heterogeneous. And removing the randomized simulation must hurt at the 20-to-30-run budget. If the first outcome holds and the second does not, the honest conclusion is that calibration matters and fine-grained per-robot structure does not. That would still be a useful result for practitioners.