Committed Plans as Messages: Distilling Multi-Agent Path Planners Under Random Network Delay

Robots that plan paths in a shared warehouse or swarm usually learn by copying a central planner that sees the whole map. During training they imitate it. At run time each robot acts alone, using a small local view plus messages from nearby robots. In real wireless networks those messages arrive late by a random amount, sometimes out of order, sometimes not at all. Today's learned planners assume messages arrive instantly. Policies that use no messages avoid the problem but get stuck in dense traffic.

We propose a simple change to what robots send and when they decide. Each robot commits to its next $H$ moves and broadcasts that locked plan with a timestamp. A message that arrives late is then still exactly correct: the receiver uses the message's age to look up the right step of the sender's plan. Random communication delay becomes a fixed, self-imposed decision delay of $H$ steps, a setting that imitation learning already handles well. The research question is whether this trade, giving up some reaction speed in exchange for messages that never go stale within $H$ steps, beats learning to cope with stale messages directly.

Core Claim

The idea rests on one finding from single-agent delayed control. Addressing Signal Delay in Deep Reinforcement Learning shows that predicting the present state from a delayed observation breaks down when the delay fluctuates. Appending the agent's own recently issued, not-yet-executed actions to its input holds up much better. Delayed Reinforcement Learning by Imitation (DIDA) builds on that input. It trains an expert without delay, then uses DAgger (dataset aggregation: repeatedly roll out the student, ask the expert to label the states the student visits, and retrain) to teach a delayed student. The student sees the last known state plus its own pending actions. DIDA assumes a fixed delay and a single agent, and lists random delay as open work.

In a team, the missing piece is the other robots' pending actions. Our claim is that these should be broadcast explicitly as locked commitments. If a robot always fixes its action $H$ steps ahead, then any received plan of age $a < H$ tells the receiver exactly what the sender will do now and for the next $H-a$ steps. No prediction is needed.

The student's information is then corrupted only by messages whose total age, summed over relay hops and including losses, reaches $H$. We therefore expect performance to depend on the tail probability $P(a \ge H)$ of the delay distribution, not on its mean. A network with a large average delay but a short tail should barely hurt committed-plan policies. Standard state-sharing graph policies should degrade roughly with mean message age. This prediction is the main thing the experiments test.

Research Program

Student policy. The student follows the decentralized multi-robot path planner of Graph Neural Networks for Decentralized Multi-Robot Path Planning. That planner combines a convolutional encoder over a local occupancy grid with $K$ rounds of message passing among neighboring robots, a graph neural network (GNN). Its authors name latency and packet loss as unaddressed, and we take that up directly. We make three changes to the message content and the decision timing:

  1. Each robot keeps a buffer holding the most recent plan received from each robot within $K$ hops, with its send time. Relayed plans carry their original timestamp.
  2. At each step the receiver shifts every buffered plan by its age, so all buffered plans line up with the current time. Expired entries are masked and their age is supplied as an input.
  3. The policy outputs only the action at slot $t+H$. Slots $t+1$ through $t+H-1$ are already locked.

The aligned plans of distant robots extend the robot's view beyond its local grid. This takes the role that attention over neighbor features plays in SILLM. Here, though, the features are the senders' own commitments rather than features computed at a single shared time.

Teacher and labels. The teacher is a centralized search solver: Conflict-Based Search (CBS) on small maps, and Explicit Estimation CBS (EECBS) on dense maps, as in HiMAP. Following DIDA, labels are assigned in hindsight. The student's choice for slot $t+H$ is supervised with the teacher's action on the true global state at $t+H$, collected inside DAgger rollouts under randomized network conditions.

We test one teacher variant that we expect to matter. A plain zero-delay teacher assumes every robot can change course instantly. A commitment-aware teacher instead re-solves with all robots' locked slots fixed as constraints. Its labels are therefore always achievable by a robot that must honor its own commitments. Comparing the two teachers tells us whether achievable labels improve imitation.

Safety valve. Rigid commitments can trap robots in situations the plan did not anticipate. A local shield may therefore break a commitment when a collision is imminent. The shield follows the conflict-resolution fallback SILLM uses (CS-PIBT, a collision-shielded version of the PIBT priority planner), and a broken commitment is broadcast. We report how often commitments are broken, because a high rate would mean the trade does not work.

Choosing $H$. We study $H$ as the central knob. Small $H$ keeps robots reactive but lets more messages expire. Large $H$ makes messages reliable but delays every decision. One analysis checks whether the best $H$ follows a quantile of the per-hop delay distribution scaled by hop count, which the argument above predicts.

Network simulation. The simulator draws an independent delay for every link and hop. We use three delay distributions: geometric, uniform over 1–5 steps (the jitter range used by Li et al.), and heavy-tailed. We also add independent packet loss and allow out-of-order delivery.

Baselines

Communication-free reference. HiMAP-style local imitation with a 9×9 view and its four inference-time heuristics. It cannot be hurt by network delay and is the "ignore the network" reference. HiMAP reports a success rate between 60% and 70% on 80×80 maps with 512 agents. We retrain it with the same EECBS data and the same compute budget. Matching it at zero delay and beating it under delay is the minimum the proposal must show.

Strongest competitor: delay-randomized message passing. The $K$-hop GNN of Li et al., retrained with DAgger under the same randomized delays, with each message's age supplied as an input and robots sharing current state features rather than plans. This is the obvious way to make existing learned planners delay-robust, so it is the competitor that matters most. The file reports that $K=2$ or $K=3$ far outperformed $K=1$, but gives no success-rate number. No reported result found on Lacuna for any learned MAPF planner under stochastic communication latency, so all latency numbers will be produced here. It receives the same teacher, DAgger iterations, $K$, parameter count, and hyperparameter search budget as our method.

Extrapolation baseline. The same graph network, but receivers extrapolate each neighbor's last reported position forward by the message age. This is a discrete analogue of the first-order feature extrapolation in FFNet. A learned variant instead predicts offsets, in the spirit of TraF-Align. Both test the forward-prediction approach that cooperative perception relies on.

Classical reference. MAPF-DP plans centrally for robots whose moves are randomly delayed. It uses a minimal-communication execution policy that cut messages from over 23,000 to about 267 for 35 agents, and its solver (AME) scaled to 150 warehouse agents. We run it on its own 30×30 grids as a reference for message count and success rate, not as a scalable competitor.

Ablations. Two ablations isolate the key ingredient:

  1. Plans without locking. Robots broadcast their intended next $H$ moves but may change them freely. This tests whether locking, and not just the richer message, is what helps.
  2. Plain teacher instead of commitment-aware teacher. This tests whether achievable labels matter.

What counts as winning. Our method beats the delay-randomized GNN if two things hold. First, its success rate degrades less as the delay tail grows, at matched mean delay. Second, at zero delay it gives up no more than a few points of success and makespan (the time until the last robot reaches its goal).

Why not just…?

Why not just train the existing graph planner under randomized delays and let it learn? This is the real threat. Domain randomization combined with DAgger might be enough. The argument against it is indirect: Li et al. found that learned representations do not reliably undo variable-age information in single-agent control. That evidence does not settle the multi-agent case, and our main comparison is built to settle it. We vary tail heaviness at fixed mean delay. If the randomized baseline stays flat as the tail grows, or the no-locking ablation matches full commitment, the core claim fails and we will report that.

Why not just drop communication, as HiMAP does? That removes all delay vulnerability, but HiMAP's success rate stops at 60–70% in dense maps. Without its heuristics, success fell toward zero as density grew. In flocking, Tolstaya et al. found that one-hop controllers fragmented the swarm while three- to four-hop controllers matched the central expert. Our experiments include the delay level at which communication-free policies overtake each communicating method. That crossover is a useful number in its own right.

Why not just predict where neighbors are now? Forward prediction compounds errors under jitter in single-agent control (Li et al.). FFNet's authors note that linear extrapolation fails for sharp turns and long delays, and grid paths are full of sharp turns. Prediction might still work at short delays, so we run the extrapolation baselines across the full range of delays.

Proposed Experiments

Benchmarks. We use three map families:

  1. The 20×20 grids with 10% obstacles from Li et al., with CBS as the teacher.
  2. HiMAP's dense 40×40 and 80×80 maps with 30% obstacles, with EECBS as the teacher, training on up to 64 agents and testing generalization to larger teams.
  3. The MAPF-DP 30×30 random and warehouse grids, for comparison with the classical method.

Metrics. Success rate, makespan relative to the teacher, collision count, deadlock rate, commitment-break rate, and messages per agent per step.

Decisive check. For delay distributions with matched mean and increasing tail mass, we plot success rate against $P(a \ge H)$ and against mean age. The claim holds if committed-plan policies line up on $P(a \ge H)$ while the delay-randomized GNN lines up on mean age.

Secondary checks.

  1. Sweep $H$ to locate the reactivity-versus-reliability optimum and test whether it follows the delay quantile.
  2. Run the teacher ablation to see whether commitment-aware labels reduce shield interventions.
  3. Increase packet loss until commitments expire routinely, to find where the approach breaks.