CS Paper Radar

Collective Ranking of Environmental Signals through Gaussian Belief Propagation in a Patrolling Robot Swarm

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

cs.RO ·submitted 2026-08-18 12:06 UTC · v1

Abstract

Multi-robot patrolling 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 pairwise 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. We find that as noise increases and the task becomes harder, GBP degrades gracefully in simulation while both averaging methods degrade substantially. Hardware trials reproduce the same performance ordering on a real propagating radio signal, supporting the practical relevance of the simulated results.

Closest papers

Nearest neighbours by meaning across the whole index.

Multi-robot Learning-based Informative Path Planning Using Spatio-Temporal Gaussian Process Kalman Filter

cs.RO ·2026-08-31 ·Muqing Cao, Yunwoo Lee, Junbin Yuan, Lorenzo Schenk, Sebastian Scherer
publishedcode/data similarity 0.65
Abstract · IEEE RA-L accepted

Multi-robot informative path planning (IPP) for persistent target monitoring requires robots to reason about spatial uncertainty, temporal evolution, and practical sensing and communication constraints. Recent learning-based multi-robot IPP methods use Gaussian Processes (GPs) for target uncertainty, but often rely on simplified sensing models and centralized belief updates. We propose a grid-based spatio-temporal GP-Kalman filtering framework for learning-based multi-robot IPP. Instead of maintaining one GP per target, we represent anonymous target presence as a single latent field over a discrete workspace grid. The proposed recursive update assimilates footprint-level camera measurements and supports arbitrary fields of view and range-dependent noise. A GP-derived temporal process update inflates uncertainty over time to account for moving targets. For decentralized deployment, each robot maintains its own mapper and exchanges fixed-size belief summaries rather than raw measurements. Received beliefs are fused using diagonal covariance intersection to remain conservative under unknown inter-robot correlations. We integrate the mapper with a reinforcement-learning policy for graph-based neighbor selection. In simulation, the centralized deployment improves target visitation and attains about 20% lower posterior target uncertainty than learning-based and classical auction/coverage baselines, a large share of which stems from the belief representation itself. A real-world two-UAV experiment demonstrates transfer to outdoor multi-robot search over a large field (>7000 m^2). Code is available at https://github.com/caomuqing/multirobot-ipp.

0.39

Gaussian Processes for Modelling Spatial Fields with Robot Swarms

cs.RO ·2026-09-15 ·Guillermo Legarda Herranz, Gianpiero Francesca, Mauro Birattari
similarity 0.65
Abstract

Robot swarms, by virtue of their decentralised architecture, are a natural tool for scalable, robust modelling of spatial fields, such as water temperature, wind velocity, or terrain elevation. However, existing methods rely on external positioning systems that allow each robot to determine its own position in space. Here, we introduce location-unaware Gaussian process regression (LU-GPR) as a solution to the modelling of spatial fields in the absence of such positioning systems. LU-GPR allows each robot to infer the posterior mean and variance of the field in space, while simultaneously agreeing on a common frame of reference with its peers, using only local sensing and communication. We propose an online algorithm that allows each robot to consistently infer local estimates as its local frame of reference converges to the common one. By means of a product of experts model, each robot also combines the estimates of its peers with its own to obtain a global model. Our results show that LU-GPR scales well with the number of robots and is robust to limited communication ranges. We also demonstrate how it can be used in real-world monitoring scenarios to estimate the flow of an evacuating crowd.

0.24

DGF-Asym: Adaptive Peer Weighting for Collective Estimation under Noisy and Faulty Sensing

cs.RO cs.AI ·2026-11-17 ·Mohammad Nomaan Husain, Tanja Katharina Kaiser
similarity 0.60
Abstract

Collective estimation under unreliable sensing requires robots to adaptively balance personal observations and social information from peers. We propose DGF-Asym, a decentralized collective estimation method extending the DeGroot-Friedkin model with asymmetric peer weighting based on retrospective predictive performance. The method supports consensus formation without prior sensor-noise statistics or explicit fault models while keeping inter-robot communication asynchronous. We evaluate DGF-Asym in simulated collective navigation under noisy observations and time-varying sensor faults. Compared with three baselines, it produces more stable estimates and more reliably sustains the decision criterion, at the cost of longer decision times. However, overall performance depends on fault ratio, group size, and influence-threshold selection. Our results demonstrate the potential of adaptive peer weighting for stable model-free collective estimation under unreliable sensing.

0.25

Belief-Driven Search in Connectivity-Constrained Mobile Sensor Networks with Convergence Guarantees

eess.SY ·2026-10-28 ·George J. Ziavras, Ziqiao Zhang, Shreyas Sundaram, Christopher G. Brinton
theory similarity 0.59
Abstract · 8 pages, 6 figures, 2 tables. Extended version with full proofs

Multi-agent search and coverage is critical to autonomous exploration, search-and-rescue, and defense applications. This paper investigates settings where a mobile sensor network is tasked with coordinating to discover the position of a stationary target within a bounded region. We develop a Bayesian update scheme where agents iteratively combine local uncertainties derived from their sensor measurements through inverse variance weighting to get a better global understanding of where the target may be located given some prior belief. Network agents' trajectories are governed by a primal-dual gradient update rule that simultaneously minimizes the expected sensing uncertainty and enforces network connectivity among the agents. We prove that the belief converges to the target under mild planner conditions, with an explicit exponential rate of false-hypothesis rejection and a bound on expected search time. Simulation results show that we can successfully find the target and collapse belief to the ground truth target location while ensuring connectivity of our sensor network. They also empirically confirm our theoretical bounds and planner conditions. Finally, we compare against a naive lawnmower sweeping strategy, showing that our method locates the target more quickly when the prior is informative.

0.36

Stochastic Multi-Robot Monitoring on Graphs under Markovian Mobility

cs.DS ·2026-08-20 ·Walid Ben-Ameur, Tijani Chahed, Shamisa Nematollahi
theory similarity 0.59
Abstract

We study a stochastic multi-robot monitoring problem on a connected graph $G=(V,E)$, where each robot moves according to a Markov chain on $G$ and monitors the closed neighborhood of its current vertex. The performance of $r$ robots is evaluated in steady state via two objectives: average-case coverage (the expected number of covered vertices) and worst-case coverage (the minimum coverage probability over all vertices). We consider three models: independent homogeneous strategies, where all robots share the same stationary distribution; independent heterogeneous strategies, where robots use different stationary distributions; and centralized strategies, allowing arbitrary correlations between robot locations. For the heterogeneous model, we prove that maximizing average coverage is NP-hard even for two robots, and that replicating an easy-to-compute optimal homogeneous strategy yields a \(\left(1-\left(1-\frac{1}{r}\right)^r\right)\)-approximation for both objective functions in the heterogeneous setting; moreover, no polynomial-time algorithm can achieve a ratio better than \(1-\nicefrac{1}{e}\) unless \(\text{P}=\text{NP}\). Centralized strategies can exploit correlations to reduce redundancy. We develop a hierarchy of approximation factors: for any positive integer \(r'\le r\), writing \(r=hr'+b\) with \(0\le b<r'\), block coordination yields a \(1-\left(1-\frac{r'}{r}\right)^h\left(1-\frac{b}{r}\right)\) approximation for both objectives. We also establish NP-hardness and a tight \(1-\nicefrac{1}{e}\) inapproximability bound. Moreover, we prove diminishing-returns properties with respect to the number of robots: a non-increasing-ratio property holds for the average-case objective in all settings, but not for the heterogeneous worst-case objective.

0.29

Lightweight Change Detection for Adaptive Collective Perception in Dynamic Environments

cs.RO ·2026-10-25 ·Thiemen Siemensma, Tiago Travassos, Jiacheng Zhang, Bahar Haghighat
benchmark similarity 0.58
Abstract

Swarm robotics enables scalable inspection through collective perception, where robots infer environmental properties from distributed observations. A common benchmark considers robots exploring black-white tiled environments and determining the majority tile type. While most work studies static environments, dynamic environments remain underexplored. We study collective perception in dynamic environments where the tile proportion and the spatial correlation of surface patterns may change over time. To enable implementation on resource-constrained robots, we integrate a lightweight change detection mechanism into a Bayesian collective decision-making framework that resets robot beliefs when distribution shifts are detected. The proposed detector requires constant memory and constant per-sample computation, unlike two recent competitive approaches that store the full sample stream, making it suitable for memory-constrained robots. We further introduce a method that detects spatially correlated sampling and adapts sampling intervals online to mitigate correlation effects. Our simulation results in Webots show competitive change detection delays, more consistent precision across communication settings, and improved decision accuracy under changing spatial correlations.

0.30

Belief-Aware Multi-Agent Path Finding under Map Uncertainty

cs.AI cs.MAcs.RO ·2026-09-30 ·Viraj Parimi, Shao-Hung Chan, Han Zhang, Jingkai Chen, Brian Williams
similarity 0.56
Abstract · Under review

Multi-Agent Path Finding (MAPF) aims to find collision-free paths for multiple agents in a shared environment. Classical MAPF assumes that all static obstacles are known in advance, but real-world environments can change unexpectedly due to fallen objects, spills, or other local disturbances. When such changes are spatially correlated, an observation can inform traversability estimates beyond the observed location. Prior approaches address uncertainty in traversability through contingent plans or replanning based on direct observations, but do not leverage this spatial dependence to infer the traversability of nearby unobserved locations. As a result, they cannot use one observation to anticipate nearby unobserved obstacles that may cause costly rerouting later. We focus on Belief-Aware MAPF, where map discrepancies are fixed during execution but initially unknown, and observations can be informative beyond the observed location. We propose Multi-Agent Gaussian belief Inference for Coordination (MAGIC), a framework that updates a shared belief about traversability online based on agents' observations. MAGIC uses a Gaussian Markov Random Field and Gaussian Belief Propagation to approximately infer traversability and construct detour-aware costs for standard MAPF planners. Our experiments on MAPF benchmarks show that MAGIC reduces the executed sum of costs compared to existing approaches on 96.3% of instances, across several planner families and teams of up to 800 agents, demonstrating its applicability to large-scale MAPF problems.

0.23

Exact Fusion and Coordinated Exploration in Multi-Robot Active Inference

cs.RO cs.MA ·2026-09-15 ·Peng Wu, Mohsen Imani, Amidu Kamara, Md Tamzeed Islam, Seyede Fatemeh Ghoreishi +1 more
similarity 0.56
Abstract

Robot teams that learn a common environment model exchange belief summaries and plan by the expected information gain of their actions. Under conjugate exponential-family beliefs the shared belief is counted once per robot at two points: at fusion, the product of local posteriors counts the common prior $n$ times, and at planning, every robot scores its plan under the same belief and the team converges on the same unknown. Both errors are removed by adding evidence increments to the shared natural parameter, realized increments at fusion and expected increments at planning. The expected increment of a committed teammate gives the next robot its conditional gain; corrected gains sum to the joint gain, the redundancy removed equals the total correlation of the planned observation streams, and sequential commitment keeps the $1/2$ greedy guarantee. The expected increment is exact for Gaussian beliefs with fixed sampling paths and for Dirichlet beliefs under the novelty approximation of discrete active inference, whose team objective has a closed concave form within an explicit bound of the exact mutual information, and fails for finite hypothesis classes, where a short exact enumeration replaces it. Experiments on cooperative RockSample, foraging, and field monitoring show that fusion correction leaves exploration redundancy unchanged, anticipated evidence removes it, and sequential commitment recovers most of the value of centralized joint planning at cost linear in the team size.

0.22