Shifted Messages: Receding-Horizon Warm Starts for Decentralized Discrete Coordination

When many robots or vehicles must make discrete choices together, such as who goes first through an intersection, which side of an obstacle each one takes, or when to change lanes, the number of possible joint choices grows exponentially. With $n$ agents each choosing among $d$ options at each of $H$ future steps, there are $d^{nH}$ joint plans. A standard workaround is a coordination graph: a sparse network whose edges link only agents that can actually interfere with each other. Agents then pick actions by passing messages along its edges, using Max-Plus, a message-passing algorithm in which each message summarizes how good each of an agent's options looks to its neighbor. In a real controller, however, this message passing starts over at every control step, has to run to convergence within one sampling period, and assumes no message is ever lost. This note proposes to treat the discrete coordination problem the way receding horizon control treats a trajectory. Receding horizon control repeatedly plans over a short future window, executes only the first step, and replans. Here, the messages computed at the previous step are shifted forward one step in time and reused as the starting point for the next solve.

The claim is that shifted messages turn decentralized discrete coordination into an anytime procedure: a solve that returns a usable answer whenever it is stopped. One or two message rounds per control step would then be enough. A dropped packet would degrade gracefully, because the receiving agent falls back on a one-step-stale shifted message rather than on nothing. If this holds, discrete multi-agent coordination could run inside a real-time decentralized control loop over lossy networks. Current systems cannot do that. They either keep the discrete layer small and synchronous, or drop discrete choices entirely.

Core Claim and Positioning

Closed-loop replanning is known to be forgiving of imperfect plans. Rolling optimization tolerates forecast errors with far fewer scenarios than worst-case bounds require (Micheli et al.), and noisy lookahead inside a rolling horizon provably narrows the gap to optimal compared with myopic decisions (Bellman-Jensen Gap in Rolling Horizon Optimization). These results motivate the proposal: if replanning corrects errors, the discrete solver at each step need not be exact, provided it starts somewhere good. The contribution is to supply that starting point for discrete message passing, and to show that the resulting truncated, stale-tolerant solver matches fully converged coordination in closed loop.

The closest system is LCDMC. It builds a coordination graph among vehicles whose projected paths cross, runs Max-Plus to choose one of three speed actions per vehicle, and hands the result to a receding-horizon learned controller that only tracks it. The two layers are disconnected. The horizon never informs the discrete choice, message passing is cold-started every step, and communication is assumed perfect.

Factored Online Planning in Many-Agent POMDPs factors search over coordination graphs and scales to 64 agents on FireFightingGraph. Its planner is centralized, however, and restarts every step.

NonZero and MALinZero compress joint-action search, the former through pairwise interaction terms and the latter through a linear-bandit model. Both reinitialize from the current state at each node, run on one central machine, and never touch physical dynamics.

On the continuous side, Distributed Stochastic Search for Multi-Agent MPC and Sampling-Based Optimization for Multi-Agent MPC decompose multi-agent trajectory optimization with consensus ADMM, a method in which neighbors iteratively agree on shared copies of each other's plans. This scales to 196 vehicles, but only over continuous sampling distributions. This proposal reuses their local sampling optimizer as the thing that scores discrete edge choices. It differs from all of this work in placing the temporal warm start inside the discrete, decentralized solver itself.

Research Program

Each agent $i$ holds a discrete mode sequence $a_i = (a_i^1,\dots,a_i^H)$ over the horizon, for example a passing order, a yield or go decision, or a lane or homotopy choice. The team objective factors over the current coordination graph $G_t$:

$$\max_{a} \; \sum_{i} f_i(a_i; x_t) + \sum_{(i,j)\in G_t} f_{ij}(a_i, a_j; x_t).$$

Here $x_t$ is the measured state at step $t$. The local term $f_i$ is the negative cost of agent $i$'s own continuous plan given its modes. The pairwise term $f_{ij}$ scores conflicts between neighbors $i$ and $j$. Each agent computes $f_i$ and its share of $f_{ij}$ locally, by running a small sampling-based continuous optimizer, in the style of the stochastic-search MPC papers above, conditioned on a candidate mode pair. The continuous horizon therefore produces the discrete payoffs; it is not just a follower.

The warm start works as follows. After solving at step $t$, the message $\mu_{j\to i}$ that $j$ sent $i$ is a table over $i$'s mode sequences. At step $t+1$ it is shifted: its dependence on the executed first mode is marginalized out, and the new final horizon slot is initialized from the local term. When $G_{t+1}$ gains an edge, that edge starts with a zero message. When an edge disappears, its messages are simply dropped. This is a local update rule in the spirit of the plug-and-play protocol of Riverso et al., where adding a subsystem requires redesign only by its immediate neighbors. Each step then runs $R$ rounds of damped Max-Plus, with $R$ fixed and small. Any message that fails to arrive is replaced by the receiver's shifted copy.

The analysis asks when the shifted fixed point is close to the new one. We expect this to hinge on how many edges change per step and on how much the payoffs $f_{ij}$ drift between consecutive states. We will measure both quantities and report how closed-loop quality degrades with each, rather than claim a convergence proof; Max-Plus on graphs with cycles is not guaranteed to converge.

To stress the combinatorial side we will go well beyond LCDMC's three actions. We use up to 15 modes per agent (5 speed levels crossed with a 3-way yield, lane or homotopy choice) and horizons of 3 to 5 discrete slots.

Baselines

The naive reference is independent planning. Each agent runs the same local sampling MPC with the same compute and no messages, treating neighbors' last broadcast trajectories as fixed obstacles. The file's evidence suggests this fails badly: independent learning in the LCDMC intersections collided 22.8% to 26% of the time (LCDMC). Beating it means a large reduction in collisions at equal per-step compute.

The strongest discrete competitor is cold-start Max-Plus over the same coordination graph and the same local payoffs. This is LCDMC's high-level mechanism, run to convergence or to a generous round cap, and it is the method whose timing budget we claim to remove. On LCDMC's own simulator the reported numbers for LCDMC are a 0% collision rate and a T-junction clearance time of approximately 7.4 seconds, against 8.8 seconds for independent learning (LCDMC). We will reimplement that simulator from the paper's description, first reproduce these figures with three actions, and then enlarge the action set. Beating this baseline means matching its collision rate and clearance time with $R \le 2$ rounds per step, and degrading less than it does as packet loss rises.

The strongest continuous competitor is distributed stochastic search with Gaussian-mixture sampling distributions (Distributed Stochastic Search for Multi-Agent MPC). On the 64-agent Dubins-car obstacle task it reports 100% task completion with zero collisions, where distributed IPOPT, a standard gradient-based nonlinear solver, found no feasible solution. It will get the same 1,024-sample-per-agent budget, the same number of communication rounds per step, and the same hyperparameter search budget as our method.

We will also run centralized factored planning (Galesloot et al.) on FireFightingGraph. There the reported result is scaling to 64 agents while standard POMCP fails beyond 10. No reported return value was found on Lacuna for FireFightingGraph, so we will rerun it.

Two ablations isolate the key ingredient. The first warm-starts only the previous decision, reusing last step's chosen modes as the initial assignment while cold-starting the messages. The second is cold messages with stale-copy fallback. Together they separate "remember what we chose" from "remember what neighbors believed."

Why not just…?

Why not just keep last step's discrete decision and re-run Max-Plus? This is the most serious threat, because holding the previous plan is a cheap and familiar warm start. Its weakness is that the previous plan is a single point. Max-Plus messages carry each neighbor's ranking of all alternatives, so when conditions change they should allow a switch to a different joint mode without re-deriving everything from scratch. The decision-only ablation tests exactly this. If it matches shifted messages at $R \le 2$ under topology change and packet loss, we will report that the simpler method suffices and that the message tables add nothing.

Why not just let Gaussian-mixture sampling represent the discrete choices? Mixture components can capture passing left versus right. However, each agent's components are chosen independently, and consensus ADMM agrees on continuous trajectory copies rather than on which agent yields. We therefore expect it to oscillate or deadlock at crossings where several choices are symmetric. The file offers only indirect evidence for this: the 24-agent blocked quadcopter task reached just 25% completion (Sampling-Based Optimization for Multi-Agent MPC). Our Dubins task with discrete homotopy choices and symmetric crossings is designed to settle the question. We will not claim superiority on the original obstacle task, where this method is already at 100%.

Why not just run a centralized joint-action search such as NonZero? Compressed centralized search reaches $10^8$ joint actions on MatGame with a 14% gain over baselines (NonZero). But it needs every agent's state at one machine within each control period, which is the communication bottleneck decentralization exists to avoid. On the TurtleBot testbed, latencies of tens of milliseconds were already significant (Experimental Validation of Distributed Receding Horizon Motion Planning). We will include a centralized upper reference with perfect communication to measure the optimality gap our method pays.

Proposed Experiments and Decisive Checks

We will use three testbeds. The first is the reimplemented LCDMC intersections: basic and complex T-junctions and a high-density cross intersection. The second is the 64-agent Dubins formation through obstacles, extended with discrete homotopy and passing-order choices. The third is FireFightingGraph, where decentralized warm-started Max-Plus is compared with centralized factored planning. The metrics are collision rate, completion rate, clearance time, message rounds and bytes per step, and wall-clock time per step. Each is reported as a function of packet drop rate (0% to 30%), added latency of up to 100 milliseconds, and the fraction of coordination-graph edges that change per step.

The decisive check is a curve of closed-loop collision rate and clearance time against message rounds per step, with one line each for shifted messages, the decision-only ablation, and cold-start Max-Plus. The proposal succeeds if shifted messages at one or two rounds match cold-start at convergence and stay flat as packet loss rises while cold-start degrades. It fails if the decision-only ablation tracks it closely. A second check targets the known weakness of pairwise models (NonZero): we deliberately build three-way symmetric deadlocks at the cross intersection and report how often all pairwise methods, including ours, stall. That result will be stated as a limitation, not hidden.