Resilient Consensus via Voronoi Communication Graphs

Kelsey Saulnier, Lifeng Zhou, George J. Pappas, Vijay KumararXiv 2022 · OpenReview

TL;DR

This paper tackles the challenge of ensuring reliable consensus among robots in a team, even when some robots act maliciously or malfunction. They demonstrate that a communication graph derived from Voronoi tessellations naturally provides resilience against a single rogue robot, and show how to enhance this graph to handle multiple adversaries, making resilient consensus more practical for real-world robotic systems.

What Problem Does This Paper Address?

In multi-robot systems, consensus algorithms are crucial for enabling robots to agree on shared information, like estimates of global variables. However, these algorithms are vulnerable to "non-cooperative" robots – those that intentionally provide incorrect data or fail to update properly. This can lead the entire team astray, making the system unreliable. While algorithms like W-MSR exist to combat this, they rely on a strict graph connectivity property called "(r, s)-robustness," which is computationally expensive to verify, especially for dynamic robot teams. This paper addresses the need for practical, easily verifiable communication graph structures that inherently support resilient consensus.

Methods

The core of this work lies in analyzing and extending communication graph structures derived from Voronoi tessellations.

  • Voronoi Tessellation Graph (G△): The authors leverage the graph formed by connecting neighboring robots in a Voronoi tessellation. They prove that this graph, when used with the W-MSR consensus algorithm (with parameter F=1), is inherently (2,2)-robust, making it resilient to a single non-cooperative robot under the F-global threat model. This is significant because it bypasses the need for explicit (r, s)-robustness verification.
  • Enhanced Voronoi Graph (G△2): To handle more than one non-cooperative robot, they propose an enhancement: connecting "two-hop neighbors" in the Voronoi graph. This creates G△2, which is proven to be (3,3)-robust, enabling resilience against two non-cooperative robots under the F-global threat model or one under the F-local threat model.
  • Generalization: They also suggest a roadmap for further enhancing the graph (G△k) by connecting k-hop neighbors, indicating a path towards arbitrary levels of resilience.

Datasets

Not discussed in the paper. The paper focuses on theoretical proofs and simulations using synthetic robot formations and environments.

Key Insights and Ideas

  • Voronoi Graphs as a Natural Fit for Resilience: The paper highlights that a commonly used communication structure in robotics (Voronoi tessellations) has inherent properties that make it suitable for resilient consensus, simplifying its adoption.
  • Bypassing NP-Complete Verification: By proving that Voronoi-based graphs possess specific (r, s)-robustness properties, the paper offers a practical alternative to the computationally intractable verification of this property for arbitrary graphs.
  • Hierarchical Resilience: The proposed method of connecting k-hop neighbors provides a clear, systematic way to increase the resilience of the communication graph, offering a tunable mechanism for dealing with increasing numbers of adversarial robots.
  • Trade-offs in Connectivity and Resilience: The simulations demonstrate that while increased connectivity (like in G△2) generally improves resilience, it can also lead to faster convergence in cooperative scenarios. However, if the W-MSR parameter F is not matched to the number of non-cooperative robots, even highly connected graphs can fail.

Key Results

  • The communication graph formed by connecting neighbors in a Voronoi tessellation (G△) is proven to be (2,2)-robust, allowing W-MSR with F=1 to reject a single non-cooperative robot.
  • Enhancing G△ by connecting two-hop neighbors (G△2) results in a (3,3)-robust graph, capable of rejecting two non-cooperative robots (F-global threat) or one (F-local threat).
  • Simulations across various scenarios (distributed parameter estimation, polygon rendezvous, map consensus) demonstrate the effectiveness of G△ and G△2 in achieving resilient consensus, contrasting their performance with plain consensus and showing how they enable full exploration or safe convergence despite adversarial robots.
  • Numerical studies suggest a linear increase in (r, s)-robustness with the number of hops connected, indicating a scalable method for graph enhancement.

Limitations and Future Work

  • Computational Complexity for High Robustness: While the paper provides a method for enhancing robustness, the explicit verification of (r, s)-robustness remains computationally expensive for large graphs, limiting its direct application in real-time for very complex scenarios.
  • Scalability of Proofs: The proofs for higher levels of robustness (e.g., for G△k with k>2) become increasingly complex.
  • Future Work: The authors suggest exploring the application of resilient consensus to tasks like distributed filtering and target tracking. They also propose investigating the interaction between Voronoi partitioning algorithms and the construction of resilient communication graphs, as well as examining the effect of using W-MSR with resilient graphs in distributed Kalman filters.

Summary updated

Abstract

Consensus algorithms form the foundation for many distributed algorithms by enabling multiple robots to converge to consistent estimates of global variables using only local communication. However, standard consensus protocols can be easily led astray by non-cooperative team members. As such, the study of resilient forms of consensus is necessary for designing resilient distributed algorithms. W-MSR consensus is one such resilient consensus algorithm that allows for resilient consensus with only local knowledge of the communication graph and no a priori model for the data being shared. However, the verification that a given communication graph meets the strict graph connectivity requirement makes W-MSR difficult to use in practice. In this paper, we show that a commonly used communication graph structure in robotics literature, the communication graph built based on the Voronoi tessellation, automatically results in a sufficiently connected graph to reject a single non-cooperative team member. Further, we show how this graph can be enhanced to reject two non-cooperative team members and provide a roadmap for modifications for further resilience. This contribution will allow for the easy application of resilient consensus to algorithms that already rely on Voronoi-based communication such as distributed coverage and exploration algorithms.
BibTeX
@misc{saulnier2022resilient,
  author = {Kelsey Saulnier and Lifeng Zhou and George J. Pappas and Vijay Kumar},
  title = {{Resilient Consensus via Voronoi Communication Graphs}},
  year = {2022},
  eprint = {2209.04381},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2209.04381},
}
Figure