اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدSampling-Based Resolution-Complete Algorithms for Safety Falsification of Linear Systems
36
0
0.0
(
0
)
تأليف
Amit Bhatia
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper, we describe a novel approach for checking safety specifications of a dynamical system with exogenous inputs over infinite time horizon that is guaranteed to terminate in finite time with a conclusive answer. We introduce the notion of resolution completeness for analysis of safety falsification algorithms and propose sampling-based resolution-complete algorithms for safety falsification of linear time-invariant discrete time systems over infinite time horizon. The algorithms are based on deterministic incremental search procedures, exploring the reachable set for feasible counter examples to safety at increasing resolution levels of the input. Given a target resolution of inputs, the algorithms are guaranteed to terminate either with a reachable state that violates the safety specification, or prove that no input exists at the given resolution that violates the specification.
قيم البحث
اقرأ أيضاً
In this work, we perform safety analysis of linear dynamical systems with uncertainties. Instead of computing a conservative overapproximation of the reachable set, our approach involves computing a statistical approximate reachable set. As a result,
the guarantees provided by our method are probabilistic in nature. In this paper, we provide two different techniques to compute statistical approximate reachable set. We have implemented our algorithms in a python based prototype and demonstrate the applicability of our approaches on various case studies. We also provide an empirical comparison between the two proposed methods and with Flow*.
This paper proposes a data-driven framework to solve time-varying optimization problems associated with unknown linear dynamical systems. Making online control decisions to regulate a dynamical system to the solution of an optimization problem is a c
entral goal in many modern engineering applications. Yet, the available methods critically rely on a precise knowledge of the system dynamics, thus mandating a preliminary system identification phase before a controller can be designed. In this work, we leverage results from behavioral theory to show that the steady-state transfer function of a linear system can be computed from data samples without any knowledge or estimation of the system model. We then use this data-driven representation to design a controller, inspired by a gradient-descent optimization method, that regulates the system to the solution of a convex optimization problem, without requiring any knowledge of the time-varying disturbances affecting the model equation. Results are tailored to cost functions satisfy the Polyak-L ojasiewicz inequality.
We propose a Thompson sampling-based learning algorithm for the Linear Quadratic (LQ) control problem with unknown system parameters. The algorithm is called Thompson sampling with dynamic episodes (TSDE) where two stopping criteria determine the len
gths of the dynamic episodes in Thompson sampling. The first stopping criterion controls the growth rate of episode length. The second stopping criterion is triggered when the determinant of the sample covariance matrix is less than half of the previous value. We show under some conditions on the prior distribution that the expected (Bayesian) regret of TSDE accumulated up to time T is bounded by O(sqrt{T}). Here O(.) hides constants and logarithmic factors. This is the first O(sqrt{T} ) bound on expected regret of learning in LQ control. By introducing a reinitialization schedule, we also show that the algorithm is robust to time-varying drift in model parameters. Numerical simulations are provided to illustrate the performance of TSDE.
The statistical analysis of Randomized Numerical Linear Algebra (RandNLA) algorithms within the past few years has mostly focused on their performance as point estimators. However, this is insufficient for conducting statistical inference, e.g., cons
tructing confidence intervals and hypothesis testing, since the distribution of the estimator is lacking. In this article, we develop an asymptotic analysis to derive the distribution of RandNLA sampling estimators for the least-squares problem. In particular, we derive the asymptotic distribution of a general sampling estimator with arbitrary sampling probabilities. The analysis is conducted in two complementary settings, i.e., when the objective of interest is to approximate the full sample estimator or is to infer the underlying ground truth model parameters. For each setting, we show that the sampling estimator is asymptotically normally distributed under mild regularity conditions. Moreover, the sampling estimator is asymptotically unbiased in both settings. Based on our asymptotic analysis, we use two criteria, the Asymptotic Mean Squared Error (AMSE) and the Expected Asymptotic Mean Squared Error (EAMSE), to identify optimal sampling probabilities. Several of these optimal sampling probability distributions are new to the literature, e.g., the root leverage sampling estimator and the predictor length sampling estimator. Our theoretical results clarify the role of leverage in the sampling process, and our empirical results demonstrate improvements over existing methods.
Finding solutions to systems of linear equations is a common prob-lem in many areas of science and engineering, with much potential for a speedup on quantum devices. While the Harrow-Hassidim-Lloyd (HHL) quantum algorithm yields up to an exponential
speed-up over classical algorithms in some cases, it requires a fault-tolerant quantum computer, which is unlikely to be available in the near term. Thus, attention has turned to the investigation of quantum algorithms for noisy intermediate-scale quantum (NISQ) devices where several near-term approaches to solving systems of linear equations have been proposed. This paper focuses on the Variational Quantum Linear Solvers (VQLS), and other closely related methods. This paper makes several contributions that include: the first application of the Evolutionary Ansatz to the VQLS (EAVQLS), the first implementation of the Logical Ansatz VQLS (LAVQLS), based on the Classical Combination of Quantum States (CQS) method, the first proof of principle demonstration of the CQS method on real quantum hardware and a method for the implementation of the Adiabatic Ansatz (AAVQLS). These approaches are implemented and contrasted.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
