Minimum Sufficient Communication for Independent Behaviour Tree Robot Teams

Sherry Jiang, Oliver ObstarXiv 2026 · arXiv

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:

  1. Message Content ($S$): Eight different rules determining what is sent (e.g., task completion, ownership claims, intent, or full status updates).
  2. 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.

Figure 2: Detailed-stage frontiers with an explicit policy-colour legend. Each point is a tested arm and the black step is the running maximum of observed success. The dashed line is the observed full-state success minus 0.05. Shading is the running envelope of paired-bootstrap bounds shifted by the observed reference mean. The horizontal axis uses a symmetric logarithmic scale with a linear region near zero.

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.
Table 4: Summary of the cheapest passing communication policies for each tested condition.

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

Abstract

We present an experimental framework for determining sufficient communication in robot teams running fixed, independent Behaviour Trees with private blackboards. Within a declared policy family, we vary message content and admission frequency and measure traffic in recipient-weighted bits per robot decision. A dense sweep identifies candidate policies for comparison with full-state communication. We retest selected candidates and the reference on fresh, paired scenarios, using one-sided simultaneous confidence bounds to assess whether success remains within five percentage points of the full-state reference. The bounds also assess whether tested cheaper policies can be ruled out as insufficient. Depending on the evidence, the framework reports an exact minimum, a positive bracket, a sufficient upper bound, or an unresolved boundary. Experiments with eight content policies across four warehouse conditions identify zero communication as the exact minimum under low contention. In the scaled condition, the no-release policy at gate $q=0.992222$ is confirmed sufficient, achieving 96.33% success at an estimated rate of 738.55 bits per robot decision, or 0.544% of full-state traffic. The positive minimum remains unresolved. These claims apply only to the declared policy family, sampled gate values and operating conditions.
BibTeX
@misc{jiang2026minimum,
  author = {Sherry Jiang and Oliver Obst},
  title = {{Minimum Sufficient Communication for Independent Behaviour Tree Robot Teams}},
  year = {2026},
  eprint = {2610.38176},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.38176},
}
Figure