Introduction
Multi-robot coverage control is a fundamental problem in robotics, focusing on the optimal distribution of agents to monitor or explore a given area. The standard approach, Centroidal Voronoi Tessellation (CVT), requires robots to partition a workspace into Voronoi cells and move toward their respective centroids. However, a significant limitation of traditional CVT is its reliance on a Global Frame of Reference (FoR), such as GPS. In environments where GPS is unavailable—such as underground facilities, dense urban canyons, or extra-terrestrial terrains—maintaining a shared global coordinate system is often impossible.
This paper introduces the Anchor-Oriented Coverage (AOC) strategy, a decentralized approach that enables multi-robot teams to achieve optimal coverage using only local sensing and a shared environmental landmark, or "anchor."
The Challenge of Global Coordination
In a typical coverage scenario, robots must agree on the boundaries of the workspace to avoid gaps or redundant overlaps. Without a global map, individual robots may perceive the workspace differently due to sensor noise and varying perspectives. This lack of consensus prevents the formation of a cohesive Voronoi tessellation. The challenge lies in enabling a distributed team to converge on a unified spatial understanding using only relative local data.
The AOC Framework
The AOC framework shifts the coordination paradigm from a global map to a localized, anchor-centric model. The methodology consists of four primary components:
- Anchor Identification: The system utilizes a single environmental feature—an "anchor"—that is detectable by all robots in the team. This anchor could be a static landmark, a signal source like a Wi-Fi Access Point, or even a designated lead robot. Each agent estimates the anchor's position within its own local coordinate system.
- Distributed Boundary Consensus: To ensure all robots operate within the same perceived workspace, the authors implement a distributed consensus algorithm. Robots communicate with immediate neighbors to agree upon a common workspace radius ($r^*$) and orientation ($\theta^*$) relative to the anchor.
- Localized Voronoi Partitioning: With a shared boundary established, robots transform the relative positions of their neighbors into their own local frames, using the anchor as the origin. This allows for the calculation of Voronoi cells without any knowledge of absolute global coordinates.
- Decentralized Control Law: The robots employ a modified version of Lloyd’s algorithm. By calculating the centroid of their localized Voronoi cells and moving toward them, the swarm achieves optimal coverage through purely local interactions.
Theoretical Foundations
A key contribution of this work is the mathematical proof that localized partitioning around a shared anchor is equivalent to global partitioning. The authors demonstrate that if the robots reach consensus on the workspace boundary, the resulting coverage configuration is identical to what would be achieved with a perfect global coordinate system.
Furthermore, the paper provides a Regret Analysis to evaluate the system's robustness against noise in anchor estimation. The analysis shows that the cumulative error, or "regret," grows at a sub-linear rate ($O(\sqrt{T})$). This theoretical bound ensures that the system remains stable and that the coverage performance converges over time, even in the presence of imperfect sensing.
Experimental Validation
The AOC strategy was rigorously tested using the Robotarium, a hybrid simulator and physical robotics testbed. The evaluation included:
- Scalability Tests: Simulations were conducted with swarms ranging from 4 to 50 robots in environments up to $50 \times 50m^2$. The results indicated that the AOC algorithm scales effectively, with the "cost" of coverage decreasing as robot density increases.
- Hardware Trials: Experiments on physical GRITSbots validated the algorithm's resilience to real-world factors such as communication delays and sensor noise.
- Comparative Analysis: AOC was compared against standard GPS-aided CVT. The results showed that AOC achieves performance parity with global methods once consensus is reached. Conversely, tests conducted without the consensus mechanism resulted in poor coverage and inconsistent partitioning, highlighting the necessity of the boundary agreement step.
Discussion and Future Work
The AOC method offers several advantages beyond GPS-independence. Because robots only share relative positions centered on an anchor, the approach inherently provides a degree of location privacy. Additionally, the anchor can be dynamic; if the anchor moves, the entire coverage "bubble" moves with it, facilitating applications like mobile surveillance or target tracking.
However, the current implementation assumes that the anchor is visible to all robots. In complex or vast environments, this may not be feasible. Future research will explore multi-anchor settings, where robots can hand off reference points as they traverse larger areas, creating a chain of localized workspaces to maintain coverage across expansive, GPS-denied regions.
Conclusion
The Anchor-Oriented Coverage strategy provides a robust, scalable solution for multi-robot coordination in challenging environments. By leveraging local consensus and shared landmarks, the AOC framework bridges the gap between localized sensing and global optimization, offering a viable path forward for autonomous exploration and monitoring in GPS-denied zones.
Summary updated