Don’t Fire Together: Desynchronised Communication Scheduling for Bandwidth-Limited Multi-Robot Exploration

Cooperative multi-robot exploration relies on a shared belief over teammates’ poses and maps, but bandwidth-limited radios refresh that belief only intermittently. We identify a failure mode beyond simply sending fewer messages: when robots broadcast on a common schedule, the shared belief goes stale in phase, the learned explorer acts on the same outdated information across the team, and robots herd toward the same frontiers. We call this the synchrony tax and show it is controllable at test time, without retraining. A scheduling layer over a frozen graph-attention policy fixes each robot’s broadcast rate and changes only the phase of transmissions, cutting travel by 9.8% and sensing overlap by 13.2% (independent replications reach −12.9%). The primary contributing factor is a higher peak (not mean) team staleness, which a staleness-to-overlap bound links to redundant coverage; the benefit accordingly disappears on planners that barely use the shared belief. OW-Desync, a budget-constrained activation policy, carries even staggering to range-limited, heterogeneous channels, improving the freshness it controls while matching staggering on the task. Four-robot experiments over real WiFi reproduce the timing-to-staleness stage of the mechanism at a matched rate: across five repeated paired trials, staggering cuts the measured peak team staleness by 37% (all pairs concordant, within 1.5% of the predicted optimum) with the mean unchanged.