An Approximate Set Membership Approach to Resilient Multi-Robot Communication
Nicholas Smith, Jen Jen Chung, Graeme Best
AI summary
Problem
Multi-robot coordination fails under real-world bandwidth limits and frequent message dropouts, as traditional reliable or compressed sharing either saturates networks or loses critical data.
Approach
Robots encode their observed map data into compact Bloom filters, apply unique random salts to decorrelate them, and stack multiple filters to probabilistically verify shared observations and suppress false positives.
Key results
- Reduces communication cost by up to 6× compared to exact map sharing
- Maintains team exploration efficiency close to exact methods across varying false-positive rates
- Sustains near-optimal performance under severe network degradation and high packet-loss rates
- Enables reliable frontier generation and coordinated exploration without overwhelming bandwidth
Why it matters
Enables reliable, bandwidth-efficient multi-robot coordination in degraded or resource-constrained environments where traditional communication fails.
Abstract
Effective communication is critical for coordinat- ing multi-robot teams, yet practical deployments often face severe bandwidth constraints and frequent message loss. This paper presents a communication protocol that leverages Bloom filters to enable efficient, approximate set membership queries in multi-robot systems. Bloom filters offer a tunable trade- off between false positive rate and memory footprint, making them well suited for bandwidth-limited communication. To mitigate the effects of false positives, we introduce a salting strategy that decorrelates Bloom filters and enables stacking— the combination of membership queries across multiple filters. These stacked results are incorporated into each robot’s belief map, such that only sufficiently corroborated information influences frontier generation and exploration planning. We evaluate our proposed communication protocol in a multi- robot exploration task, where robots share information about their observed cells to enable efficient coverage. Our results demonstrate that compared to exact methods, our Bloom filter- based protocol reduces communication cost by up to 6× while maintaining team exploration performance, even under severe communication dropouts.