Collective Ranking of Environmental Signals

Collective Ranking of Environmental Signals

through Gaussian Belief Propagation in a

Patrolling Robot Swarm

Zachary R. Madin, Connor York, Jonathan Lawry, Edmund R. Hunt

University of Bristol

27th October 2026 - DARS 2026

Note: Hello all I’m Zachary Madin, the main author on the paper entitled Collective Ranking of Environmental Signals through Gaussian Belief Propagation in a Patrolling Robot Swarm. I’ll give a brief discussion of the paper and our findings, as well as the limitations and what we are working on next to examine some of those. Then I’ll be happy to take any questions you may have.

Motivation

• Multiple Security Robotic Agents

• Persistent monitoring

• Consensus of detection

• Spatial distribution of signal

Background

- Abstract map into a graph - Patrol algorithms to visit areas (TSP) - Collective belief system - Realistic problem for autonomous swarm - Patrolling "half" of the problem - Sampling second half

From Detection to Collective Ranking

• Prior work: consensus on binary anomaly flags during patrol
• Now: continuous signal, rank all patrol nodes by severity
• Generalises best-of-n to many options (40 nodes, 8 robots)

Patrol Graph => Factor Graph

• The patrol graph already defines where robots move
• Reuse the same graph to define how beliefs propagate
• Nodes = variables, edges = smoothness factors, visits = measurements

Note: SUGGESTED SLIDE. This dual-purpose use of the patrol graph is stated as the key contribution of the paper (Sec. 1) but is not currently stated explicitly in the talk.

Distributed Environmental Monitoring

Note: We focus on the measurement and belief fusion. We utilise patrolling as the manner in which robots navigate the environment and determine where to visit next.

Patrolling algorithms

- Method to cover an area - Repeatedly sample an environment - Distribute effort across swarm - Leading algorithms

Algorithms - CGG vs SEBS

• CGG: cyclic, Hamiltonian-cycle style traversal of the graph
• SEBS: Bayesian estimate of idleness, local utility-driven choice
• Both strong performers in our 10-algorithm comparison^[16]

Note: SUGGESTED SLIDE. The “Leading algorithms” bullet does not name the two algorithms used; the paper (Sec. 2.1) justifies the choice of CGG and SEBS as a principled contrast.

Robot Patrolling

Fusion approaches

• Naïve simple averaging

• Visit-weighted averaging

• Spatial inference

Averaging Baselines

\(\hat{z}_i = \frac{\sum_r v_i^r \hat{z}_i^r}{\sum_r v_i^r}\)

• $\hat{z}_{i}^{r}$: Averaged node $i$ value for robot $r$
• $v^{r}_{i}$: Node $i$ visit count of robot $r$
• Simple mean: $v_i^r = 1$ for all robots
• Each node treated independently, graph edges ignored

Note: SUGGESTED SLIDE. Eq. 1 of the paper. Makes clear why the baselines cannot exploit spatial correlation.

Why not Gaussian Processes?

• GP inference inverts the full covariance: $O(n^3)$ time, $O(n^2)$ memory
• Grows with every measurement
• Hard to decentralise across a swarm
• GBP: local messages, incremental updates

Note: SUGGESTED SLIDE. Paper Sec. 1 and 2.2: the motivation for choosing GBP over the standard spatial-modelling approach.

Gaussian Belief Propagation

• Measurements across graph

• [Image of factor graph]

Gaussian Belief Propagation

Note: Robots patrol and each visit adds a unary measurement factor at that node. Neighbouring nodes then exchange Gaussian messages along the smoothness factors on each edge, so beliefs sharpen incrementally without any central processor. Node 12 is never visited but its belief is still inferred from its neighbour.

GBP Formulation

• Unary factors: measurement $z$ with precision $1/\sigma_m^2$
• Pairwise factors: $x_i - x_j = 0$, precision from edge weight
• Canonical form: $\Lambda = \Sigma^{-1}$, $\eta = \Lambda \mu$
• Loopy graph: damped messages, $\alpha = 0.25$

Note: SUGGESTED SLIDE. Paper Sec. 2.5. The talk currently has no slide on how the factors are constructed or on loopy BP and damping, which are likely to come up in questions.

Measurable Hardness

• Best-of-N literature approaches
• Minimal literature on establishing difficulty^[1]

Measurable Hardness

Measurable Hardness

Note: Severity values are assigned to nodes by radial distance from a simulated emitter, so nearby nodes are correlated, mirroring a real propagating signal.

Simulation Setup

- Python 2D grid-world simulator, "Cumberland" map (40 nodes) - 8 robots, 20 runs per algorithm and fusion combination - Consensus when inter-agent std $\sigma_{inter} < \varepsilon$ at every node - Global communication: range had no effect above a minimum threshold

Note: SUGGESTED SLIDE. Paper Sec. 3.2 and 4. Consensus criterion and the justification for global communication are not in the talk.

Experimental Conditions

2 × 3 = 6 combinations, 20 runs each

Note: Every patrolling algorithm is paired with every fusion approach. Fusion does not drive robot movement, so the patrolling algorithm decides where data is collected and the fusion approach decides how it is combined.

Results - Metrics

• Mean Squared Error
  • Summed squared error over all agents and nodes
• Spearman Ranking
  • $\rho$: swarm ordering vs ground-truth ordering
• Consensus time
  • Steps until estimates agree across agents
• Speed-accuracy trade off

Note: Paper Sec. 4.1. Metrics motivated by the three-metric framework of Shan and Mostaghim.

Results Takeaways

• Gaussian Belief Propagation out-performs others

• SEBS performs better than CGG

• CGG suffers more from a harder problem

Note: CGG suffers more from harder problem, perhaps due to uniformity of visit spread.

Robustness to Noise

• Above ~25% mis-ordering, both averaging methods collapse
• GBP degrades gracefully, even at 45%
• Noisy or rarely visited nodes borrow strength from neighbours

Note: SUGGESTED SLIDE. This is the headline (“Crucially…”) result of the abstract and Sec. 4.2, but it is not stated explicitly in the current takeaways.

Robot Trials

• Four robots
• Radio signal
• Simple & weighted averaging
• Gaussian Belief Propagation

Hardware Setup

• 4 Leo Rovers: LiDAR, SLAM and navigation, XBee S2C receiver
• XBee transmitter: 2.4 GHz, +5 dBm, 20 Hz, RSSI measured
• Office lobby 20 x 14 m, 14 nodes, at most 5 m apart
• 10 SEBS trials; all three fusions run on the same trial data

Note: SUGGESTED SLIDE. Paper Sec. 5.1. The fact that fusion does not drive behaviour, so all methods are compared on identical data, is an important methodological point.

Results - Performance

Note: MSE is in dBm squared here, so it cannot be compared in absolute terms with simulation; only the ordering of methods is comparable. The same ordering holds despite multipath, occlusion and hardware noise.

Why Does GBP Hold Up?

• Averaging: each node independent, locks onto locally dominant beliefs
• GBP: graph structure acts as a constraint, not just consensus
• Consistent with Shan and Mostaghim on correlated options

Note: SUGGESTED SLIDE. Paper Sec. 6 discussion linking results to the collective-decision literature.

Limitations & Future Work

• Simple spatial model
• Comparison to other spatial inference
• Assumption about signal propagation

• Communication range investigation

• Adversarial patrol / Adaptive sampling
• Position uncertainty as joint problem
• Complex propagation patterns
• Adaptive sampling

Note: The selection of the model for GBP requires some prior knowledge about the propagation pattern. In this study we didn’t examine the performance against more complex propagation patterns. While the naïve approaches that do not consider the spatial correlations may perform better than the current implementation of GBP, there exists the possibility to choose a more sophisticated correlation model for the node correlation that feeds into the inference algorithm.

Takeaways

• Spatial inference outperforms naïve approaches

• Selection of patrolling algorithms matters

• Metric of interest changes selection

• GBP costs more computation per update

Acknowledgements

• ZRM: University of Bristol PhD Scholarship

• CY: UK FCDO Services

• ERH: Royal Academy of Engineering Research Fellowship

• Simulations: University of Bristol Self-Service Cloud

Questions?

Thank you!

zachary.madin@bristol.ac.uk

Note: I’ll now take questions, and here are some links for my paper and my Github if you want to stay in touch