TL;DR
This paper introduces MemoryMesh, a novel system for coordinating ground and aerial robots in search-and-rescue missions. It achieves efficient, large-scale exploration by combining delta-encoded map sharing with a lightweight goal-broadcast protocol, drastically reducing communication overhead while maintaining high performance.
What Problem Does This Paper Address?
Coordinating multiple robots, especially heterogeneous teams like drones and ground vehicles, for tasks like search-and-rescue in disaster zones is crucial. However, real-world environments often have severely degraded communication infrastructure, making it impractical to share full sensor data or detailed maps between robots. This communication bottleneck leads to a trade-off: either robots explore independently, leading to redundant coverage and missed targets, or they attempt coordination with high communication costs, which is often infeasible. The paper aims to bridge this gap by enabling effective coordination with minimal communication.
Methods
MemoryMesh is built upon a decentralized, peer-to-peer architecture where each agent maintains its own local spatial memory map. The core innovations are:
- Shared Spatial Memory Map: Each agent stores a map of explored regions, including cell states (free, wall, target, unknown), observation confidence, timestamp, and the identity of the observing agent. This map is updated via a confidence-weighted merge rule that prioritizes more recent or confident observations, resolving conflicts deterministically.
- Delta-Encoded Map Sharing with Goal Broadcast: Instead of sending full maps, agents broadcast compact updates containing only newly observed cells (delta-encoded) and their current navigation goal (a single frontier coordinate). This goal broadcast adds minimal overhead (8 bytes per agent per message) but is key for coordination.
- Role-Aware Task Allocation: A scoring function guides agents towards frontiers. This function incorporates:
- Information Gain: Prioritizing frontiers with more unknown cells.
- Travel Cost: Minimizing distance to the frontier.
- Goal Exclusion Zones: Penalizing frontiers too close to other agents' announced goals, preventing redundant exploration.
- Persistent Goal Pursuit: Agents commit to a goal for a set number of timesteps (
Treplan) to reduce oscillation. - Role-Specific Biases: Drones are biased towards open areas (high information gain), while ground robots are biased towards wall-dense areas (better for detailed inspection).
- Robustness Mechanisms: Includes confidence-weighted merging for sensor noise and a mechanism to revisit stale regions if no new frontiers are found.
Datasets
The paper uses a 2D grid-world simulator with simulated sensor noise, partial observability, and occlusions. The evaluation is performed on two map sizes:
- 80x80 grids with 20 hidden targets, run for 200 timesteps.
- 150x150 grids with 40 hidden targets, run for 300 timesteps. These are not new datasets but rather simulated environments designed to test the system's performance under realistic constraints.
Key Insights and Ideas
- Goal Broadcast is King for Coordination: The
DeltaMapShareGoalsbaseline, which only adds goal broadcasting and exclusion to delta-encoding, performs exceptionally well, often matching or exceeding the full MemoryMesh system on key metrics like target discovery. This highlights the power of simple, low-bandwidth coordination signals. - Role-Aware Scoring is Nuanced: While intended to leverage complementary robot capabilities, the role-specific biases can sometimes hinder performance on compact maps by steering agents away from productive frontiers. This suggests specialization is more beneficial in larger, more complex environments.
- Communication Efficiency is Achieved: MemoryMesh and its variants achieve massive communication savings (over 99.5% reduction compared to full map sharing) while using only about 100 KB of communication for an entire 80x80 episode.
- Robustness to Real-World Imperfections: The system gracefully handles sensor noise and, remarkably, shows zero degradation in target discovery even with up to 40% packet loss, thanks to its decentralized, persistent local memory.
Key Results
- 80x80 Maps:
DeltaMapShareGoals(goal broadcast + exclusion) found all 20 targets with the fastest discovery time (62.6 steps) and highest coverage (0.986), using only 100 KB of communication.
- MemoryMesh achieved the lowest path overlap (1.1%), indicating excellent spatial separation.
- 150x150 Maps:
- MemoryMesh achieved the highest coverage (0.698), slightly ahead of
DeltaMapShareGoals(0.695).
- MemoryMesh achieved the highest coverage (0.698), slightly ahead of
DeltaMapShareGoalsstill had the fastest discovery time (131.0 steps) and best separation (128.1 cells).- Communication costs remained low for delta-encoded methods (around 208 KB for 150x150 maps).
- Robustness:
- Target discovery degraded only slightly with up to 20% sensor noise.
- Packet loss up to 40% had zero impact on target discovery.
- UAV occlusion showed stable performance, with moderate occlusion even slightly improving ground robot exploration.
Limitations and Future Work
- Limitations:
- The evaluation is in a 2D grid-world simulator, simplifying real-world challenges like continuous motion and 3D environments.
- The role bonus parameters might need tuning for different environment scales, as they can sometimes hurt discovery on compact maps.
- The pairwise exclusion mechanism degrades with 4 or more agents.
- The conflict resolution is a simple confidence-then-recency rule.
- Future Work:
- Extend to 3D simulators for more realistic SAR scenarios.
- Learn scoring weights and exclusion radii via multi-agent reinforcement learning.
- Adapt the exclusion mechanism for larger teams.
- Incorporate semantic object hypotheses into memory entries.
- Develop more sophisticated Bayesian fusion for conflict resolution.
- Explore predictive coordination by reformulating information gain as probabilistic uncertainty and using short-horizon trajectory predictions.
Summary updated