Range Limited Coverage Control using Air-Ground Multi-Robot Teams

Max Rudolph, Sean Wilson, Magnus EgerstedtICRA 2021 · DOI · OpenReview

TL;DR

This paper introduces a novel extension to Lloyd's algorithm for coverage control in multi-robot systems with heterogeneous sensing capabilities. By combining the broad, coarse sensing of aerial robots with the precise, local sensing of ground robots, the system can effectively map and cover domains with unknown, non-uniform densities, outperforming traditional methods.

What Problem Does This Paper Address?

Traditional coverage control algorithms, often based on Lloyd's algorithm, assume a homogeneous team of robots with similar sensing capabilities. This works well when all robots can perceive the environment with similar fidelity. However, in real-world scenarios, teams are often heterogeneous, with robots possessing vastly different sensing ranges and resolutions (e.g., drones vs. ground robots). Applying standard Lloyd's algorithm to such systems is suboptimal because it doesn't effectively leverage the strengths of each robot type. Specifically, ground robots with limited sensing range struggle to cover large or complex domains, while aerial robots with broad but coarse sensing might not provide the detailed coverage needed. This paper addresses the challenge of fusing information from these disparate sensing capabilities to achieve efficient and effective coverage of domains with unknown, non-uniform density distributions.

Methods

The core contribution is an extension to Lloyd's algorithm that integrates information from a heterogeneous team of aerial and ground robots. The approach works as follows:

  • Heterogeneous Team Composition: The system comprises aerial robots with high-range, low-resolution sensors and ground robots with low-range, high-resolution sensors.
  • Aerial Robot Role: Aerial robots survey the entire domain from above, estimating the density function and identifying regions of interest. They perform a standard Lloyd's algorithm on their aerial domain, creating Voronoi cells. Within each aerial cell, they estimate the proportion of the total density and the number of ground robots present.
  • Ground Robot Role: Ground robots operate within their limited sensing range. They receive "cell weights" from the aerial robots, which indicate whether an aerial cell has an underabundance or overabundance of ground robots.
  • Extended Lloyd's Algorithm: The ground robots use a modified control law that balances two components:
  • Local Coverage: A traditional Lloyd's algorithm component that drives robots to the centroid of their local Voronoi cells for fine-grained coverage.
  • Global Distribution: A new component that uses the aerial robots' cell weights to distribute ground robots globally across the domain, directing them towards aerial cells that are under-robotized.
  • Stability Proof: The authors provide a proof demonstrating the asymptotic stability of their extended algorithm, showing that the cell weights converge to zero, effectively reducing the control law to the standard Lloyd's algorithm as the system reaches equilibrium.

Datasets

The paper does not use pre-existing datasets for training or evaluation. Instead, it relies on:

  • Simulations: The proposed algorithm is evaluated in simulation using a custom-defined bimodal Gaussian distribution for the domain's density.
  • Robotarium Testbed: Experiments are conducted on the Robotarium, a remotely accessible, multi-robot testbed, using a similar bimodal Gaussian density.

Key Insights and Ideas

  • Synergy of Heterogeneity: The most significant insight is that combining robots with complementary sensing capabilities (broad/coarse vs. narrow/fine) can achieve superior coverage performance compared to homogeneous teams, especially in complex environments.
  • Bridging Global and Local: The method effectively bridges the gap between global environmental awareness (provided by aerial robots) and local, high-fidelity sensing (provided by ground robots). This allows for intelligent global distribution guided by coarse environmental features.
  • Parameter-less Extension: The proposed extension to Lloyd's algorithm is "parameter-less," meaning it doesn't require explicit tuning of parameters related to the density function or robot sensing ranges, making it more robust and adaptable.
  • Dynamic Re-distribution: The cell weighting mechanism allows for dynamic re-distribution of ground robots, ensuring that under-covered areas are addressed while avoiding over-coverage.

Key Results

  • Improved Coverage: Simulations and experiments show that the proposed heterogeneous coverage control algorithm achieves a final cost (a measure of coverage quality) comparable to or better than standard Lloyd's algorithm, even when the standard algorithm assumes unlimited sensing range.
  • Performance Comparison: The proposed algorithm significantly outperforms a range-limited homogeneous team using standard Lloyd's algorithm, demonstrating the benefit of the aerial-ground robot collaboration.
  • Stability: The algorithm is proven to be asymptotically stable, ensuring that the robots will eventually reach a stable coverage configuration.
  • Robotarium Validation: The algorithm's effectiveness is validated on a physical multi-robot testbed, demonstrating its practical applicability.

Limitations and Future Work

  • Discrete Robot Positions: The paper acknowledges that the discrete nature of robot positions can lead to oscillations. A modification to the cell weight calculation is introduced to mitigate this, but it's noted that the ideal distribution might never be perfectly achieved.
  • Communication Bandwidth: While not a primary focus, the paper briefly mentions that increasing the number of ground robots can increase communication bandwidth requirements for aerial robots.
  • Ratio of Robots: The performance is shown to be sensitive to the ratio of aerial to ground robots. An appropriate ratio is crucial for optimal performance.
  • Future Work: The authors suggest exploring more complex density functions and investigating how to dynamically adjust the ratio of aerial to ground robots for optimal performance. Further research could also focus on optimizing communication protocols and handling more complex environmental features.

Summary updated

Abstract

In this paper, we investigate how heterogeneous multi-robot systems with different sensing capabilities can observe a domain with an apriori unknown density function. Common coverage control techniques are targeted towards homogeneous teams of robots and do not consider what happens when the sensing capabilities of the robots are vastly different. This work proposes an extension to Lloyd's algorithm that fuses coverage information from heterogeneous robots with differing sensing capabilities to effectively observe a domain. Namely, we study a bimodal team of robots consisting of aerial and ground agents. In our problem formulation we use aerial robots with coarse domain sensors to approximate the number of ground robots needed within their sensing region to effectively cover it. This information is relayed to ground robots, who perform an extension to the Lloyd's algorithm that balances a locally focused coverage controller with a globally focused distribution controller. The stability of the Lloyd's algorithm extension is proven and its performance is evaluated through simulation and experiments using the Robotarium, a remotely-accessible, multi-robot testbed.
BibTeX
@inproceedings{rudolph2021range,
  author = {Max Rudolph and Sean Wilson and Magnus Egerstedt},
  title = {{Range Limited Coverage Control using Air-Ground Multi-Robot Teams}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2021},
  doi = {10.1109/icra48506.2021.9561706},
}
Figure