Collective Ranking of Environmental Signals through Gaussian Belief Propagation in a Patrolling Robot Swarm
Published in DARS 2026 - Tokyo, Japan, 2026
This paper is currently Under Review.
Multi-robot patrolling (MRP) requires a team to visit all areas of an environment at regular intervals, typically minimising idleness. A practical extension, motivated by security and environmental monitoring, is to additionally form a collective ranking of all patrol locations by some measured signal, a generalisation of the best-of-n problem to the many-option, continuous-valued regime. We observe that the patrol graph admits a natural dual interpretation: it is simultaneously the topology that dictates agent movement and a factor graph over which spatial beliefs can be propagated. Exploiting this equivalence, we apply Gaussian Belief Propagation (GBP), a graph based algorithm, to collective ranking using unary measurement factors at visited nodes and pair-wise smoothness factors along patrol edges. We compare GBP against simple and visit-count-weighted averaging across a range of sensor-noise conditions in simulation, and validate the approach on four Leo Rovers tracking a propagating radio signal in an office lobby. GBP outperforms both baselines on ranking accuracy, mean squared error, and time to consensus. Crucially, as noise increases and the task becomes harder, GBP degrades gracefully in simulation while both averaging methods collapse. Hardware trials reproduce the same performance ordering on a real propagating radio signal, supporting the practical relevance of the simulated results.
Recommended citation: Madin, Z. R., Lawry, J., and Hunt, E. R. (2026). "Collective Ranking of Environmental Signals through Gaussian Belief Propagation in a Patrolling Robot Swarm" The 18th International Symposium on Distributed Autonomous Robotic Systems (DARS '26), Tokyo, Japan. (Under Review).