More Like this

1. On the Characterization of Saddle Point Equilibrium for Security Games with Additive Utility

   https://doi.org/10.1007/978-3-030-64793-3_19  

   Emadi, Hamid; Bhattacharya, Sourabh (July 2020, GameSec Conference)

   In this work, we investigate a security game between an attacker and a defender, originally proposed in [6]. As is well known, the combinatorial nature of security games leads to a large cost matrix. Therefore, computing the value and optimal strategy for the players becomes computationally expensive. In this work, we analyze a special class of zero-sum games in which the payoff matrix has a special structure which results from the additive property of the utility function. Based on variational principles, we present structural properties of optimal attacker as well as defender’s strategy. We propose a linear-time algorithm to compute the value based on the structural properties, which is an improvement from our previous result in [6], especially in the context of large-scale zero-sum games. 

   more » « less
2. Adaptive Robust Model Predictive Control with Matched and Unmatched Uncertainty

   https://doi.org/10.23919/ACC53348.2022.9867457  

   Sinha, Rohan; Harrison, James; Richards, Spencer M.; Pavone, Marco (June 2022, American Control Conference)

   We propose a learning-based robust predictive control algorithm that compensates for significant uncertainty in the dynamics for a class of discrete-time systems that are nominally linear with an additive nonlinear component. Such systems commonly model the nonlinear effects of an unknown environment on a nominal system. We optimize over a class of nonlinear feedback policies inspired by certainty equivalent "estimate-and-cancel" control laws pioneered in classical adaptive control to achieve significant performance improvements in the presence of uncertainties of large magnitude, a setting in which existing learning-based predictive control algorithms often struggle to guarantee safety. In contrast to previous work in robust adaptive MPC, our approach allows us to take advantage of structure (i.e., the numerical predictions) in the a priori unknown dynamics learned online through function approximation. Our approach also extends typical nonlinear adaptive control methods to systems with state and input constraints even when we cannot directly cancel the additive uncertain function from the dynamics. Moreover, we apply contemporary statistical estimation techniques to certify the system’s safety through persistent constraint satisfaction with high probability. Finally, we show in simulation that our method can accommodate more significant unknown dynamics terms than existing methods. 

   more » « less
3. Control Barrier Functions for Complete and Incomplete Information Stochastic Systems

   https://doi.org/https://doi.org/10.23919/ACC.2019.8814901  

   Clark, A. (January 2019, American Control Conference (ACC))

   Real-time controllers must satisfy strict safety requirements. Recently, Control Barrier Functions (CBFs) have been proposed that guarantee safety by ensuring that a suitablydefined barrier function remains bounded for all time. The CBF method, however, has only been developed for deterministic systems and systems with worst-case disturbances and uncertainties. In this paper, we develop a CBF framework for safety of stochastic systems. We consider complete information systems, in which the controller has access to the exact system state, as well as incomplete information systems where the state must be reconstructed from noisy measurements. In the complete information case, we formulate a notion of barrier functions that leads to sufficient conditions for safety with probability 1. In the incomplete information case, we formulate barrier functions that take an estimate from an extended Kalman filter as input, and derive bounds on the probability of safety as a function of the asymptotic error in the filter. We show that, in both cases, the sufficient conditions for safety can be mapped to linear constraints on the control input at each time, enabling the development of tractable optimization-based controllers that guarantee safety, performance, and stability. Our approach is evaluated via simulation study on an adaptive cruise control case study. 

   more » « less
4. Towards Robust Data-Driven Control Synthesis for Nonlinear Systems with Actuation Uncertainty

   https://doi.org/10.1109/CDC45484.2021.9683511  

   Taylor, Andrew J.; Dorobantu, Victor D.; Dean, Sarah; Recht, Benjamin; Yue, Yisong; Ames, Aaron D. (December 2021, 2021 60th IEEE Conference on Decision and Control (CDC))

   Modern nonlinear control theory seeks to endow systems with properties such as stability and safety, and has been deployed successfully across various domains. Despite this success, model uncertainty remains a significant challenge in ensuring that model-based controllers transfer to real world systems. This paper develops a data-driven approach to robust control synthesis in the presence of model uncertainty using Control Certificate Functions (CCFs), resulting in a convex optimization based controller for achieving properties like stability and safety. An important benefit of our framework is nuanced data-dependent guarantees, which in principle can yield sample-efficient data collection approaches that need not fully determine the input-to-state relationship. This work serves as a starting point for addressing important questions at the intersection of nonlinear control theory and non-parametric learning, both theoretical and in application. We demonstrate the efficiency of the proposed method with respect to input data in simulation with an inverted pendulum in multiple experimental settings. 

   more » « less
5. Synthesis of Distributed Agreement-Based Systems with Efficiently-Decidable Verification

   https://doi.org/10.1007/978-3-031-30820-8_19  

   Jaber, Nouraldin; Wagner, Christopher; Jacobs, Swen; Kulkarni, Milind; Samanta, Roopsha (April 2023, Tools and Algorithms for the Construction and Analysis of Systems)

   Distributed agreement-based (DAB) systems use common distributed agreement protocols such as leader election and consensus as building blocks for their target functionality. While automated verification for DAB systems is undecidable in general, recent work identifies a large class of DAB systems for which verification is efficiently-decidable. Unfortunately, the conditions characterizing such a class can be opaque and non-intuitive, and can pose a significant challenge to system designers trying to model their systems in this class. In this paper, we present a synthesis-driven tool, CINNABAR, to help system designers building DAB systems ensure that their intended designs belong to an efficiently-decidable class. In particular, starting from an initial sketch provided by the designer, CINNABAR generates sketch completions using a counterexample-guided procedure. The core technique relies on compactly encoding root-causes of counterexamples to varied properties such as efficient-decidability and safety. We demonstrate CINNABAR ’s effectiveness by successfully and efficiently synthesizing completions for a variety of interesting DAB systems including a distributed key-value store and a distributed consortium system. 

   more » « less