Teams of robots, vehicles, or grid devices often coordinate through model predictive control (MPC), in which each agent repeatedly plans a short future trajectory, applies only the first control input, and replans at the next sampling instant. When the planning problem is split across agents, they have to exchange messages over a wireless network until their plans agree. That network is slow and jittery, and the control deadline allows only a handful of solver iterations. Current theory handles one of these problems at a time. Some results prove stability when the solver stops early but assume messages arrive instantly. Other results prove convergence when messages are late but assume the solver runs until it converges.
This proposal starts from a simple observation. Each message an agent sends is a whole planned trajectory, and the parts of that trajectory are not equally important. Optimal-control theory shows that the effect of stage $k$ on the input applied now shrinks geometrically in $k$. It follows that a stale value for the plan ten steps ahead should hurt far less than a stale value for the next step. We propose to make message freshness depend on the stage of the plan. Near-future stages are exchanged with bounded delay, and far-future stages are accepted at any age. We then prove that the number of solver iterations needed for closed-loop stability depends on a discounted average delay rather than on the worst-case delay.
Core Claim
Consider distributed MPC whose prediction horizon is split into per-stage blocks. Staleness in the coupling variables of stage $k$ disturbs the applied input by an amount weighted by $\rho^k$, where $\rho\in(0,1)$ is the sensitivity-decay rate of the control problem. Concretely, we conjecture a bound of the form
$$\|u_0^{\text{stale}} - u_0^{\text{fresh}}\| \le C \sum_{k=0}^{N-1} \rho^k \delta_k ,$$
where $u_0$ is the first control input, $N$ is the horizon length, $\delta_k$ is the mismatch in stage-$k$ coupling variables caused by delayed neighbor messages, and $C$ is a problem constant. Combined with a small-gain argument that couples the plant and the optimizer, this bound would give a minimum iteration count $\ell^*$ that grows with the effective delay
$$\bar\tau_\rho = (1-\rho)\sum_{k=0}^{N-1}\rho^k \tau_k ,$$
where $\tau_k$ is the delay bound tolerated on stage $k$. The worst-case delay $\tau_{\max}$ would no longer appear. The form comes from summing the geometric sensitivity weights against per-stage staleness. The practical result would be a messaging protocol that needs bounded delay only on the first $d$ stages and runs delay-agnostically on the rest, with a certified choice of $d$.
The mechanism comes from Exponential Decay in the Sensitivity Analysis of Nonlinear Dynamic Programming, which shows that the sensitivity of the optimal control at time $k$ to parameters at time $i$ decays as $\rho^{|k-i|}$, independently of horizon length. That result covers exact optimal solutions under uniform controllability and second-order sufficient conditions, and it is largely limited to equality constraints. Extending it to truncated iterates of a consensus algorithm, and to problems with active inequality constraints, is the main theoretical risk. We treat that extension as work to be done, not as something we can assume.
Relation to Prior Work
Three papers provide the scaffolding, and each leaves out one ingredient we need. Stability and Robustness of Distributed Suboptimal Model Predictive Control runs a fixed number $\ell$ of dual-ascent communication rounds at each sampling step, warm-started from the previous step. It proves local input-to-state stability through the small-gain theorem, down to $\ell=1$. Its rounds are synchronous and delay-free, and it relies on a coordinator. We reuse its interconnection model and add per-stage staleness. Asynchronous splitting design for Model Predictive Control splits the horizon into $N+1$ stage blocks and updates near-future blocks more often. That is the right temporal intuition, but its asynchrony is random block selection inside a single processor, with no network and no delay. Cooperative Distributed Model Predictive Control for Embedded Systems: Experiments with Hovercraft Formations deploys asynchronous ADMM on physical hovercraft under 50 ms deadlines and finds that wireless communication is the bottleneck. It gives no stability proof and treats every stage alike. That paper motivates our work, and its uniform asynchrony is the main thing we must beat.
Delay-tolerant optimization supplies the machinery for the far-future stages. Delay-Agnostic Asynchronous Distributed Optimization and Asynchronous Distributed Optimization With Delay-free Parameters prove convergence of asynchronous decentralized gradient descent with stepsizes chosen without knowing the delay bound. The second of these reports heavy-tailed delays: a maximum of 160 iterations, with 95% under 40. Both papers study static learning problems run to convergence, and both converge only to a neighborhood of the optimum. Delay-agnostic Asynchronous Coordinate Update Algorithm shows that speed can follow the empirical delay distribution rather than the worst case, but only in a master-worker setting. DTAC-ADMM tolerates heterogeneous fixed delays but needs about 2,400 iterations to reach $10^{-6}$ error, far beyond real-time budgets.
These results constrain the design. The optimality neighborhood of delay-agnostic methods acts as a persistent disturbance, and inexactness of that kind can break Lyapunov descent (A Generalized Stopping Criterion for Real-Time MPC with Guaranteed Stability). Our response is to confine that neighborhood to stages whose influence is discounted by $\rho^k$.
Distributed model predictive control without terminal cost under inexact distributed optimization keeps a vehicle platoon feasible and stable with 5 iterations by tightening constraints. Its authors name communication delays as an open problem. Our stage-dependent design suggests a specific answer: tighten against delay only on the near-term stages, because tightening every stage against worst-case delay risks leaving no feasible plan at all.
Research Program
On the theory side, we will first extend sensitivity decay from exact optima to the warm-started, $\ell$-step iterates of a distributed dual or ADMM solver. The goal is a bound on how an error injected into stage $k$ at iteration $j$ propagates to the first input after the remaining iterations. We will begin with linear-quadratic problems that have box input constraints, where Riccati-type decay arguments apply. We will then treat polytopic state constraints under a strict-complementarity assumption. Next, we will insert this bound into the small-gain interconnection of Stability and Robustness of Distributed Suboptimal Model Predictive Control, replacing its delay-free optimizer gain with a gain that depends on $\bar\tau_\rho$. Finally, we will derive the tiering depth $d$ and the near-stage tightening margins from this gain. Because small-gain bounds are known to be loose (85 certified iterations against 23 to 30 observed in Closed-loop Analysis of ADMM-based Suboptimal Linear Model Predictive Control), we will judge the theory by whether it predicts trends correctly and orders designs correctly, not only by its constants.
On the algorithm side, we will build a tiered protocol. In each packet, an agent sends its first $d$ stage blocks as a small high-priority message and waits for its neighbors' copies for at most a fixed bounded time. The remaining stages are updated asynchronously with delay-agnostic fixed stepsizes, and the latest value received is used regardless of age. Smaller near-term packets should also shorten their own transmission latency, and we will measure that effect separately from the algorithmic one. The applied input is projected onto the tightened near-term feasible set so that the controller remains feasible at any stopping point.
Baselines
The naive reference is synchronous distributed MPC with a timeout. Each agent performs $\ell$ rounds. When a neighbor's message has not arrived, the agent reuses that neighbor's last received full plan, as a practical controller would. It uses the same solver, warm start, horizon, and stepsizes as our method. This baseline shows how much any delay handling is worth.
The strongest existing competitor is uniform asynchronous ADMM in the style of the hovercraft paper (Cooperative Distributed Model Predictive Control for Embedded Systems), with every stage treated alike. It is the only method in the file that has been deployed under real latency with an iteration cap. That paper reports real-time control at 50 ms sampling but no tracking-error figure; no reported result found on Lacuna for its closed-loop tracking error. The second strongest competitor is the synchronous time-distributed dual ascent of Stability and Robustness of Distributed Suboptimal Model Predictive Control. Without delays it reports local input-to-state stability with a single communication round ($\ell=1$) on the three-agent double-integrator formation. We will run it under the same delay traces, having it wait for all messages up to the deadline. The comparator for feasibility is the 5-iteration constraint-tightened platoon controller of Distributed model predictive control without terminal cost, with tightening scaled to $\tau_{\max}$.
All methods share the same plants, delay traces, horizon, iteration cap $\ell$, and wall-clock deadline. Each gets the same grid search over stepsize and penalty parameters, 30 configurations per method, tuned on held-out traces. Our method beats a baseline if, on heavy-tailed traces, it stays stable and violates no constraints at an $\ell$ at least 2× smaller, or at a deadline at least 2× tighter, than the baseline needs. It must also have closed-loop cost no worse than 5% above that baseline's cost at matched $\ell$.
Two ablations isolate the key ingredient. The first uses the same tiered protocol but a depth $d$ chosen at random rather than from $\rho$. The second inverts the tiers, keeping far stages fresh and near stages stale. If the inverted version performs as well as the correct one, the sensitivity-decay story is wrong.
Why not just…?
Why not just use uniform asynchronous ADMM with a good warm start? This is the real threat. Warm-starting from the shifted previous plan already makes far-future stages stale by roughly one sampling period, so uniform asynchrony may capture most of the benefit without any tiering. We will settle the question directly. The claim fails if uniform asynchrony matches tiering across delay distributions and horizon lengths. The claim survives if the gap grows with horizon length $N$ and with the heaviness of the delay tail, as $\bar\tau_\rho$ predicts, and if the gap closes when $\rho$ is pushed toward 1 by weakening controllability.
Why not just shrink the stepsize by the maximum delay? With a maximum delay of 160 and 95% of delays under 40 (Asynchronous Distributed Optimization With Delay-free Parameters), scaling the stepsize by $1/\tau_{\max}$ makes almost no progress within $\ell\le 30$ iterations. We include this setting as an additional baseline to show the collapse numerically rather than assert it.
Why not just slow the sampling period or centralize? The hovercraft experiments already show the costs. Slower sampling leaves the controller acting on outdated state and reduces agility. Offboard central computation tracked better but depends on a single node and on all agents reporting to it. We will report a centralized upper bound as a reference, not as a competitor, and we will sweep the sampling period to show where the distributed advantage disappears.
Why not just shorten the horizon so that delays matter less? On the platoon benchmark, shortening the horizon from $N=10$ to $N=5$ cut solve time from about 6.46 s to about 0.55 s but raised control cost (Distributed model predictive control without terminal cost). Tiering is designed to keep the long horizon while paying delay costs only on the short near-term part, and we will compare against the short-horizon controller at equal wall-clock budget.
Proposed Experiments
We will use three benchmarks from the file. The first is the three-agent double-integrator formation with distance constraints (Belgioioso et al.), where we can compute certified and empirical $\ell^*$. The second is the one-leader, three-follower vehicle platoon, with 40 m spacing, 20 m/s cruise, and speed limits of [5, 25] m/s (Liu et al.); we extend its horizon to $N=20$ and $N=40$ to stress the long-horizon regime. The third is a simulated four-hovercraft formation with a 50 ms deadline modeled on Geyer et al.. Delay traces are drawn from bounded uniform, time-varying jitter, and heavy-tailed distributions calibrated to the reported shape of a 95th percentile near 40 and a maximum of 160. Metrics are the empirical minimum stable $\ell$, constraint violations per 1,000 steps, closed-loop cost relative to the centralized optimum, and the ratio of certified to empirical $\ell^*$.
Three checks decide the question. First, the empirical stable $\ell$ should track $\bar\tau_\rho$ and should not track $\tau_{\max}$: we hold $\bar\tau_\rho$ fixed while increasing the tail maximum, and the required $\ell$ should stay flat under tiering but rise under the baselines. Second, the advantage of tiering over uniform asynchrony should grow with $N$. Third, the inverted-tier ablation should be clearly worse. If the first check fails, the discounted-delay theory is wrong, and the contribution reduces to an empirical protocol.
References
- Exponential Decay in the Sensitivity Analysis of Nonlinear Dynamic Programming
- Stability and Robustness of Distributed Suboptimal Model Predictive Control
- Asynchronous splitting design for Model Predictive Control
- Cooperative Distributed Model Predictive Control for Embedded Systems: Experiments with Hovercraft Formations
- Delay-agnostic Asynchronous Distributed Optimization
- Asynchronous Distributed Optimization With Delay-free Parameters
- Delay-agnostic Asynchronous Coordinate Update Algorithm
- DTAC-ADMM: Delay-Tolerant Augmented Consensus ADMM-based Algorithm for Distributed Resource Allocation
- A Generalized Stopping Criterion for Real-Time MPC with Guaranteed Stability
- Distributed model predictive control without terminal cost under inexact distributed optimization
- Closed-Loop Analysis of ADMM-Based Suboptimal Linear Model Predictive Control