Planning Around Your Own Solver: Latency as a Stochastic Duration in Nonlinear MPC

A robot running model predictive control (MPC) re-solves an optimization problem many times per second: it plans a short future trajectory, applies the first control, and plans again. The time each solve takes is not a constant. Solver iteration counts vary, threads compete for the processor, the GPU is shared with perception, and offloaded computation waits on the network. Yet controllers that compensate for computation delay almost always assume the delay is exactly one fixed step. When a solve runs long, the robot has already moved past the state the plan was computed for. The new controls are stale, and the safety margins derived for a fixed delay no longer hold.

We propose to treat the solver's own run time the way the stochastic-scheduling literature treats an uncertain task duration: as a random variable with a risk budget. For a nonlinear vehicle controlled by sampling-based MPC, each new plan is optimized starting from a distribution of hand-off states. This distribution comes from rolling the nonlinear dynamics forward over sampled computation delays. The robot also keeps executing a committed segment of the previous plan, long enough that the new plan arrives in time with probability at least $1-\delta_L$. If a solve overruns even that window, a pre-verified fallback takes over. The claim is that this turns a hidden failure, the stale plan, into an explicit chance constraint. It should hold crash and constraint-violation rates near their zero-latency values under heavy-tailed latency, where fixed-delay and worst-case-delay compensation either fail or become too conservative.

Core Claim and How It Differs From Prior Work

Prior work splits along lines that leave this case uncovered. Delay-compensating controllers assume deterministic delay. Smooth Computation without Input Delay solves the problem for the state predicted exactly one step ahead and linearizes the manipulator dynamics around that point. Its authors explicitly leave stochastic disturbances to future work, and its delay model cannot express a solve that takes 1.5 or 3 steps. Asynchronous Computation of Tube-based MPC runs a slow background solver beside a fast primary loop. Its guarantees rest on linear system-level parameterization and convex combinations of stored tubes, so they do not transfer to nonlinear dynamics. Cloud-Assisted Nonlinear MPC for Finite-Duration Tasks projects the state ahead by a round-trip latency bound and solves the cloud problem once. That makes it a worst-case, one-shot treatment of latency. These three papers motivate the gap and supply architectural patterns: anticipation, and a slow solver paired with a fast executor. We keep both patterns but replace their fixed delay with a distribution.

Two lines supply the method. On the nonlinear side, BSS-MPPI runs thousands of parallel rollouts on a GPU and tracks the mean and covariance of the state. It enforces chance constraints with a barrier-style penalty in belief space, meaning over the distribution of possible states rather than a single predicted state. We reuse this machinery directly. Our key move is to inject latency uncertainty as initial-state uncertainty, so the same belief-space propagation that handles tire-slip noise also handles "we do not know when this plan will start." On the scheduling side, Rubato splits a total risk budget across uncertain durations. CS-HSSRG certifies a candidate schedule against fresh samples with Wald's sequential probability ratio test, which keeps drawing samples until it can accept or reject the risk bound without assuming a distribution. We borrow both ideas, applied at a scale they never considered. The "tasks" are individual solver calls, and the risk budget is divided between state-constraint violation and deadline overrun. Neither scheduling paper models continuous dynamics, and neither BSS-MPPI nor the delay-compensation papers model random compute time. That conjunction is what is new here.

Mechanism

Let $t_k$ be the time solve $k$ begins, and let $L_k \sim P_L$ be its random duration. At $t_k$ the controller commits to executing the previous plan for a window $h_k$. It then optimizes a new control sequence that will take over at $t_k + h_k$. The commit window and risk split are chosen so that

$$ \Pr(L_k > h_k) \le \delta_L, \qquad \Pr(\text{state leaves safe set over horizon}) \le \delta_x, \qquad \delta_L + \delta_x \le \delta, $$

where $\delta$ is the user's total per-cycle risk tolerance. A short $h_k$ keeps plans fresh but risks overruns. A long $h_k$ is safe against overruns, but the hand-off state is more uncertain and the plan reacts later. The controller trades these off online, re-allocating $\delta_L$ against $\delta_x$ in the spirit of Rubato's risk allocation.

Inside the solver, each MPPI rollout first samples a hand-off state. It does this by simulating the committed plan under nonlinear dynamics and process noise up to $t_k + h_k$, and it propagates belief statistics exactly as BSS-MPPI does. The optimized plan is therefore robust to where the robot will actually be when the plan starts. If the solve overruns $h_k$, which should happen with probability at most $\delta_L$, the executor switches to a fallback appended to every committed plan, such as a braking or hold maneuver. That fallback was checked in belief space when the plan was made. Because the fallback is always present, an overrun lowers performance but does not hand the robot unverified controls.

The latency distribution $P_L$ is learned online from logged solve times, conditioned on cheap features such as concurrent GPU load, the previous solve's sample count, and network round-trip estimates. The $1-\delta_L$ quantile is re-certified with a sequential probability ratio test as in CS-HSSRG. When the test rejects the current quantile, for example after a load spike, $h_k$ is enlarged before the next cycle.

Research Program

The work has three parts. First, we characterize real latency. We log MPPI and sequential-quadratic-programming solve times under controlled sources of variation: GPU contention from a concurrent perception workload, CPU interrupt load, and emulated network offload with jittered round trips. This tells us whether latency is heavy-tailed and whether it is predictable from features. Second, we build the latency-aware controller on top of a BSS-MPPI implementation for the AutoRally single-track model with Pacejka tires. Third, we analyze the guarantee. We will state a per-cycle bound of the form above and test empirically whether the realized overrun frequency tracks $\delta_L$ when $P_L$ is estimated online rather than known. We do not expect a full recursive-feasibility proof for nonlinear dynamics. That limitation is shared by BSS-MPPI's heuristic barrier constraint, and we will report it as such.

Baselines

The naive reference point is synchronous BSS-MPPI that ignores latency. It optimizes from the state sampled at $t_k$ and applies controls whenever the solve finishes. It shows how much stale plans cost under each latency regime. The literature reference is BSS-MPPI's own result on AutoRally: a 0% crash rate at a sample size of 500 × 40 and a 1% collision ratio, against 13% for Shield-MPPI and a 93% crash rate for vanilla MPPI, all at 39–43 Hz BSS-MPPI. Those numbers are for its standard real-time setup. No reported result was found on Lacuna for any controller under injected stochastic computation latency, so we will regenerate every baseline ourselves in that setting.

The strongest existing method for delay is fixed-step anticipatory computation as in Smooth Computation without Input Delay. We port it to BSS-MPPI by optimizing from the state predicted exactly one control period ahead. A second strong baseline is worst-case anticipation in the style of Cloud-Assisted NMPC. It sets the anticipation window to the maximum observed latency, which tests whether our method merely matches pure conservatism. A third baseline is timestamp-shift dispatch. The plan is computed from the current state, and on arrival the executor indexes into it at the actual elapsed time, skipping stale controls. All baselines share the same rollout budget, horizon, cost weights tuned once on a zero-latency setting, GPU, and latency traces. The latency traces are replayed identically across methods.

Two ablations isolate the key ingredients. The first keeps the quantile-based commit window and fallback but optimizes from the mean hand-off state instead of sampled hand-off states. This tests whether injecting latency into the belief matters. The second keeps sampled hand-off states but fixes $h_k$ offline instead of re-certifying it online. Beating the baselines means two things at matched or better lap time. Under heavy-tailed latency, crash rate and collision ratio should stay within a few points of the zero-latency BSS-MPPI figures, while fixed-step anticipation degrades. And the method should be faster than worst-case anticipation at equal safety.

Why not just…?

Why not just cap the solver at a fixed number of samples or iterations so latency becomes deterministic? This is the real threat. If most latency variance comes from iteration counts, an anytime solver with a hard time budget removes the problem more simply, and MPPI is naturally anytime. Capping does not help when the variance comes from outside the solver: GPU sharing, operating-system interrupts, or network offload. A capped solve under contention either misses the deadline anyway or returns a plan from too few samples. BSS-MPPI's own results show that sample size is what drives its crash rate to zero, so too few samples is not a safe outcome. Our latency-characterization study will split variance into internal and external sources. We will include a time-capped BSS-MPPI baseline. If it matches our method when latency variance is mostly internal, we will report that and narrow the claim to externally caused latency.

Why not just anticipate by the worst-case delay? This is safe if the worst case is known, but heavy tails make the worst case large. The anticipation window then sets how slowly the controller reacts to disturbances. Bampis et al. show that worst-case duration planning in scheduling yields overly conservative schedules, and we expect the same effect here as slower laps and wider margins. The worst-case baseline measures this directly. If its lap times match ours under realistic traces, the quantile machinery is not worth its complexity.

Why not just shift the plan by the measured elapsed time when it arrives? Shifting fixes the time index but not the starting state. The plan was optimized assuming the robot would be at the sampled state, and under nonlinear tire dynamics the true state after a long, noisy delay can sit outside the plan's region of good performance. The first ablation, which uses the mean hand-off state, together with this baseline will show whether the gap comes from distributional starting states or only from timing.

Why not just distill MPC into a neural policy with sub-millisecond inference? Fast inference removes latency but also removes online constraint handling. The 93% vanilla-MPPI crash rate under noise BSS-MPPI shows how dangerous unshielded control is on this platform. We treat a distilled policy as out of scope rather than a baseline we can match fairly.

Proposed Experiments and Decisive Checks

The main testbed is the AutoRally simulation with Pacejka tires and Gaussian process noise. We run it under four latency regimes: none, light jitter, heavy-tailed contention from a co-scheduled GPU workload, and emulated cloud offload with jittered round trips. Metrics are crash rate, collision ratio, lap time, overrun frequency, and fallback activation rate. A secondary testbed is the UR5 manipulator simulation from Smooth Computation without Input Delay. There we replace MPPI with a sequential-quadratic-programming nonlinear MPC, whose iteration counts genuinely vary, to check that the idea is not specific to sampling-based solvers. Metrics there are tracking error and input jumps.

Three checks would settle the claim. First, the realized overrun frequency should stay at or below $\delta_L$ across regimes when $P_L$ is learned online. If it exceeds $\delta_L$ under distribution shift in latency, the online certification has failed. Second, under heavy-tailed latency, our controller should keep collision ratio near the zero-latency level while fixed-step anticipation does not, and it should run faster laps than worst-case anticipation. Third, the hand-off-sampling ablation should lose to the full method specifically in high-speed cornering, where nonlinearity is strongest. If that gap is absent, the contribution reduces to a quantile-chosen commit window, and we would say so.