AFOSR: Networked Adversarially-Resilient Reconfigurable Operations in Obstacle Worlds
NARRO²W SPACE: Networked Adversarially-Resilient Reconfigurable Operations in Obstacle Worlds for Safe Planning and Attack-tolerant Control and Estimation, funded by the AFOSR Complex Networks program.
Teams of robots that coordinate over a wireless network are vulnerable to adversaries that inject malicious information, for example by sharing false mission parameters to steer the team off course. Resilient consensus algorithms can filter out such information, but only if the communication graph is sufficiently robust (in the sense of r- and (r, s)-robustness) relative to the number of adversaries. Most existing results assume a static or slowly varying network. Far less is known about how to maintain, or gracefully relax, graph robustness when robots move through narrow spaces where obstacles and communication range constrain which formations, and therefore which graphs, are feasible.
This project develops planning, control, and estimation methods that let multi-robot networks reconfigure in time and space while keeping a guaranteed level of resilience:
- Resilient network structure: characterizing robust communication topologies, including the sparsest graphs that achieve maximal robustness.
- Adversarially-resilient control barrier functions: encoding resilience requirements (r- and strong r-robustness) together with safety constraints such as collision and obstacle avoidance, so that robots preserve robust communication while moving safely.
- Adaptive resilience: adjusting resilience levels on the fly, and relaxing them in a principled way when needed, based on updated knowledge of the environment and the adversaries, while guaranteeing a minimum tolerance to attacks.
- Resilient consensus and learning: leader–follower consensus and distributed decision making that remain correct in time-varying graphs with Byzantine agents.
Algorithms are evaluated in simulation and in experiments with ground and aerial robots in the Ford Robotics Building and M-Air at the University of Michigan.
Papers
- Partial Resilient Leader-Follower Consensus in Time-Varying GraphsThis work studies resilient leader-follower consensus with a bounded number of adversaries. Existing approaches typically require robustness conditions of the entire network to guarantee resilient consensus. However, the behavior of such systems when these conditions are not fully met remains unexplored. To address this gap, we introduce the notion of partial leader-follower consensus, in which a subset of non-adversarial followers successfully tracks the leader’s reference state despite insufficient robustness. We propose a novel distributed algorithm - the Bootstrap Percolation and Mean Subsequence Reduced (BP-MSR) algorithm --- and establish sufficient conditions for individual followers to achieve consensus via the BP-MSR algorithm in arbitrary time-varying graphs. We validate our findings through simulations, demonstrating that our method guarantees partial leader-follower consensus, even when standard resilient consensus algorithms fail.
- Distributed Resilience-Aware Control in Multi-Robot NetworksEnsuring resilient consensus in multi-robot systems with misbehaving agents remains a challenge, as many existing network resilience properties are inherently combinatorial and globally defined. While previous works have proposed control laws to enhance or preserve resilience in multi-robot networks, they often assume a fixed topology with known resilience properties, or require global state knowledge. These assumptions may be impractical in physically-constrained environments, where safety and resilience requirements are conflicting, or when misbehaving agents corrupt the shared information. In this work, we propose a distributed control law that enables each robot to guarantee resilient consensus and safety during its navigation without fixed topologies using only locally available information. To this end, we establish a new sufficient condition for resilient consensus in time-varying networks based on the degree of non-misbehaving or normal agents. Using this condition, we design a Control Barrier Function (CBF)-based controller that guarantees resilient consensus and collision avoidance without requiring estimates of global state and/or control actions of all other robots. Finally, we validate our method through simulations.
- Combinatorial Control Barrier Functions: Nested Boolean and p-Choose-r Compositions of Safety ConstraintsThis letter investigates the problem of composing multiple control barrier functions (CBFs)—and matrix control barrier functions (MCBFs)—through logical and combinatorial operations. Standard CBF formulations naturally enable conjunctive (AND) combinations, but disjunctive (OR) and more general logical structures introduce nonsmoothness and possibly a combinatorial blow-up in the number of logical combinations. We introduce the framework of combinatorial CBFs that addresses p-choose-r safety specifications and their nested composition. The proposed framework ensures safety for the exact safe set in a scalable way, using the original number of primitive constraints. We establish theoretical guarantees on safety under these compositions, and we demonstrate their use on a patrolling problem in a multi-agent system.
- Reformulations of Quadratic Programs for Lipschitz ContinuityOptimization-based controllers often lack regularity guarantees, such as Lipschitz continuity, when multiple constraints are present. When used to control a dynamical system, these conditions are essential to ensure the existence and uniqueness of the system's trajectory. Here we propose a general method to convert a cf{QP} into a cf{SOCP}, which is shown to be Lipschitz continuous. Key features of our approach are that (i)~the regularity of the resulting formulation does not depend on the structural properties of the constraints, such as the linear independence of their gradients; and (ii)~it admits a closed-form solution under some assumptions, which is not available for general cp{QP} with multiple constraints, enabling faster computation. We support our method with rigorous analysis and examples.
- Maintaining Strong r-Robustness in Reconfigurable Multi-Robot Networks using Control Barrier FunctionsIn leader-follower consensus, strong r-robustness of the communication graph provides a sufficient condition for followers to achieve consensus in the presence of misbehaving agents. Previous studies have assumed that robots can form and/or switch between predetermined network topologies with known robustness properties. However, robots with distance-based communication models may not be able to achieve these topologies while moving through spatially constrained environments, such as narrow corridors, to complete their objectives. This paper introduces a Control Barrier Function (CBF) that ensures robots maintain strong r-robustness of their communication graph above a certain threshold without maintaining any fixed topologies. Our CBF directly addresses robustness, allowing robots to have flexible reconfigurable network structure while navigating to achieve their objectives. The efficacy of our method is tested through various simulation and hardware experiments # bib entry (optional). the |- is used to allow for multiline entry.
- Construction of the Sparsest Maximally r-Robust GraphsIn recent years, the notion of r-robustness for the communication graph of the network has been introduced to address the challenge of achieving consensus in the presence of misbehaving agents. Higher r-robustness typically implies higher tolerance to malicious information towards achieving resilient consensus, but it also implies more edges for the communication graph. This in turn conflicts with the need to minimize communication due to limited resources in real-world applications (e.g., multi-robot networks). In this paper, our contributions are twofold. (a) We provide the subgraph structures and tight lower bounds on the number of edges required for graphs with a given number of nodes to reach the maximum robustness. (b) We then use the results of (a) to introduce two classes of graphs that utilize the least number of edges to maintain maximum robustness. Our work is validated through a series of simulations.