Directed Graph Topology Preservation in Multi-Robot Systems With Limited Field of View Using Control Barrier Functions

Filippo Bertoncelli, Vivek Radhakrishnan, Mattia Catellani, Giuseppe Loianno, Lorenzo SabattiniIEEE Access 2024 · OpenReview

Abstract

This paper addresses the crucial challenge of maintaining the directed graph topology in multi-robot systems, particularly when operating under limited field-of-view constraints and with a lack of communication among robots. Traditional methods for multi-robot coordination rely heavily on inter-robot communication, which may not always be feasible, particularly in constrained or hostile environments. Our work presents a novel distributed control algorithm that leverages Control Barrier Functions (CBFs) to maintain the graph topology of a multi-robot system based solely on local, onboard sensor data. This approach is particularly beneficial in situations where external communication channels are disrupted or unavailable. The key contributions of this research are threefold: First, we design a novel control algorithm that efficiently maintains the graph topology in multi-robot systems using CBFs, which operate on neighbor detection data. Second, we perform an experimental evaluation of the algorithm, demonstrating its efficacy in controlling the flight of a team of drones using only local robot data. Third, we apply our methodology to a distributed coverage control scenario, showing that our approach can effectively manage a multi-robot system using only local information.

Introduction

Most multi-robot coordination strategies rely on a steady stream of communication between agents. However, in "denied" environments—such as underwater, underground, or hostile electronic warfare zones—external communication channels can be disrupted or entirely unavailable.

In these scenarios, robots must rely on onboard sensors like cameras or LiDAR to track their neighbors. The problem is that these sensors have a limited Field of View (FOV). If a neighbor moves out of sight, the "edge" in the robot network graph is broken. For tasks like distributed coverage or formation flight, losing these connections can lead to system instability, loss of coordination, or catastrophic collisions. This research tackles the challenge of topology preservation: ensuring that once a robot "sees" a neighbor, it modifies its own movement to keep that neighbor within its FOV and at a safe distance, all without needing to talk to that neighbor.

Methodology

The core of the solution is a Control Barrier Function (CBF) integrated into a Quadratic Programming (QP) optimization framework. This allows for a distributed control law that respects geometric constraints.

  1. Safety Set Definition: The authors define a "safe set" for each robot. For a neighbor to be considered "safe," it must stay within a triangular angular sector (the FOV) and beyond a minimum safety distance to avoid collisions.
  2. The CBF Controller: The controller takes a "desired" velocity from a high-level task (like moving toward a target) and minimally modifies it. It solves an optimization problem: "Find the velocity closest to what I want to do, provided it doesn't push my neighbors out of my sight or cause a crash."
  3. Worst-Case Assumption: Since robots cannot communicate, they do not know their neighbors' intentions or velocities. To remain safe, the algorithm assumes a conservative approach: it acts as if every neighbor is trying to leave the FOV at maximum speed.
  4. Cubic Dampening: Instead of a standard linear approach, the authors use a cubic function within the CBF. This creates a "dampening" effect, slowing the robot's relative motion more smoothly as a neighbor approaches the edge of the FOV.
Geometric representation of a robot's limited field of view (FOV) and its neighbors.

Key Insights and Ideas

  • Distributed Responsibility: The preservation of the global graph topology is achieved locally. If every robot ensures its outgoing edges (the neighbors it sees) are maintained, the entire network remains connected.
  • Smoothness via Cubic Functions: One of the primary innovations is the use of cubic Class $\mathcal{K}$ functions. Standard CBFs can sometimes lead to jerky, "bang-bang" control near boundaries. The cubic formulation allows for much smoother transitions, which is critical for stable drone flight.
  • Handling Anisotropy: Most connectivity research assumes "disk-based" sensing where a robot sees everything in a circle around it. This paper explicitly models the anisotropic nature of real sensors (the cone-shaped FOV), which is a much more realistic constraint for camera-based systems.

Experimental Results

The authors validated their approach through numerical simulations and real-world experiments conducted at the NYU Agile Robotics and Perception Lab (ARPL). They used a fleet of three quadrotors equipped with Qualcomm Snapdragon Flight Pro boards. A motion-capture system was used to emulate neighbor detection data, which was then filtered to respect the simulated 100° FOV of the drones.

Experimental setup with three quadrotors maintaining connectivity through local sensing and FOV constraints.
  • Collision Avoidance in Coverage Tasks: In a distributed coverage test without CBFs, drones crashed because they lacked information about neighbors behind them. With the CBF controller, the drones automatically entered a "circling" pattern to keep each other in sight, successfully completing the coverage task without incident.
  • Minimal Task Interference: The optimization-based approach proved to be "minimally invasive." Drones followed their primary mission objectives until a neighbor reached the very edge of the FOV, at which point the CBF took over to maintain the connection.
  • Real-Time Performance: The algorithm is computationally efficient, with an average solution time of just 0.4 ms on onboard hardware, making it highly suitable for high-speed aerial robotics.

Conclusion and Future Work

While the current model successfully maintains topology in a 2D plane, real-world drone applications often require 3D maneuvering. Furthermore, while the control was onboard, neighbor detection was emulated using motion-capture data. Future work will focus on moving to purely vision-based detection using onboard cameras and deep learning-based object trackers. Additionally, the "worst-case" velocity assumption for neighbors, while safe, can be overly restrictive; future iterations could involve estimating neighbor velocities to allow for more agile maneuvers while maintaining the same safety guarantees.

Summary updated

Abstract

This paper addresses the crucial challenge of maintaining the directed graph topology in multi-robot systems, particularly when operating under limited field-of-view constraints and with a lack of communication among robots. Traditional methods for multi-robot coordination rely heavily on inter-robot communication, which may not always be feasible, particularly in constrained or hostile environments. Our work presents a novel distributed control algorithm that leverages Control Barrier Functions (CBFs) to maintain the graph topology of a multi-robot system based solely on local, onboard sensor data. This approach is particularly beneficial in situations where external communication channels are disrupted or unavailable. The key contributions of this research are threefold: First, we design a novel control algorithm that efficiently maintains the graph topology in multi-robot systems using CBFs, which operate on neighbor detection data. Second, we perform an experimental evaluation of the algorithm, demonstrating its efficacy in controlling the flight of a team of drones using only local robot data. Third, we apply our methodology to a distributed coverage control scenario, showing that our approach can effectively manage a multi-robot system using only local information.
BibTeX
@inproceedings{bertoncelli2024directed,
  author = {Filippo Bertoncelli and Vivek Radhakrishnan and Mattia Catellani and Giuseppe Loianno and Lorenzo Sabattini},
  title = {{Directed Graph Topology Preservation in Multi-Robot Systems With Limited Field of View Using Control Barrier Functions}},
  booktitle = {IEEE Access},
  year = {2024},
  url = {https://openreview.net/forum?id=Vo9fuZaf6X},
}
Figure