TL;DR
This paper introduces a rigorous experimental framework to find the "minimum sufficient communication" for multi-robot teams. By systematically varying message content and transmission frequency, the authors demonstrate that robot teams can maintain near-peak performance (within 5% of a full-state broadcast baseline) while using as little as 0.5% of the original communication traffic.
What Problem Does This Paper Address?
In multi-robot systems, communication is a double-edged sword. While sharing information helps robots coordinate and avoid redundant work, it comes with costs: energy consumption, bandwidth limits, and network congestion.
Most research focuses on how to communicate better or learning what to say. However, there is a lack of formal methods to determine the absolute minimum amount of information required for a specific team to succeed. The authors address this by asking: What is the cheapest communication policy that keeps a team's success rate within a tolerable loss of the "gold standard" (full-state communication)?
Methods
The authors study robot teams where each robot runs an independent Behaviour Tree (BT) with a private "blackboard" (local memory). The robots' decision-making logic remains fixed, while the communication protocol is varied along two axes:
- Message Content ($S$): Eight different rules determining what is sent (e.g., task completion, ownership claims, intent, or full status updates).
- Admission Gate ($q$): A probability filter $q \in [0, 1]$ that controls how often eligible messages are actually transmitted.
To find the minimum, the framework uses a staged experimental design:
- Exploration: A dense sweep of policies and gate values to identify a "frontier" of best-performing low-rate candidates.
- Confirmation: Promising candidates are retested on entirely fresh scenarios.
- Statistical Rigor: The authors use one-sided simultaneous confidence bounds (Clopper-Pearson) to ensure that a policy is truly "sufficient" (not just lucky in a few simulations) compared to the full-state reference.
Communication cost is measured in recipient-weighted application bits per robot decision, providing a hardware-agnostic way to quantify traffic.
Datasets
The framework was evaluated in a simulated 2D warehouse environment where robots must complete stationary service tasks. The authors defined four distinct operating conditions to test the limits of their approach:
- Baseline: 4 robots, 12 tasks, reliable channel.
- Low Contention: Each robot has a unique capability, meaning they never compete for the same tasks.
- Lossy: A challenging environment with 10% message loss and increased communication delay.
- Scaled: A larger environment with 8 robots and 24 tasks to test how coordination requirements grow with team size.
Key Insights and Ideas
- Claims are King: In most scenarios, simply announcing which task a robot intends to do (a "claim") provides the bulk of coordination benefits. It prevents other robots from wasting time traveling to the same spot.
- Releases are Often Redundant: Interestingly, sending a message when a robot gives up a task ("release") was often unnecessary if task completion was deterministic.
- Lossy Channels Need Redundancy: In the "Lossy" condition, sparse event-based messages (like a single claim) weren't enough. The team performed better with "heartbeat" style updates that repeated state information, compensating for dropped packets.
- Timing Matters More Than Average Rate: The authors performed a "token-bucket" stress test, limiting burstiness. They found that even if two policies have the same average bit rate, the one that allows messages to be sent exactly when a decision is made performs significantly better.
Key Results
The framework successfully identified sufficient policies that drastically reduced traffic:
- Zero Communication is Sufficient: In the "Low Contention" case, the framework proved that $R^* = 0$. Because robots didn't compete for tasks, they didn't need to talk at all to match the full-state reference.
- Massive Reductions in Scaled Teams: In the "Scaled" condition, a "no-release" policy at a high gate value ($q \approx 0.99$) achieved 96.33% success while using only 738.55 bits per decision. This represents just 0.544% of the traffic generated by full-state communication.
- Baseline Efficiency: For the baseline warehouse, sufficiency was reached at just 1.13% of full-state traffic.
Limitations and Future Work
- Policy Family Constraints: The "minimum" found is only the minimum within the tested family of eight policies. A more clever encoding or a learned protocol might find even lower rates.
- Domain Specificity: The results are currently limited to warehouse-style tasks. The authors note that tasks requiring simultaneous coalitions (e.g., two robots lifting one heavy object) would likely change the communication requirements.
- Simulation vs. Reality: The simulation omits real-world network effects like radio congestion, signal interference, and jitter, which would be critical for a physical deployment.
- Fixed Controllers: The study holds the Behaviour Tree structure constant. Future work could explore how changing the robot's logic itself might further lower the communication threshold.
Summary updated