Search

Controllers for dynamical systems that operate in safety-critical settings must account for stochastic disturbances. Such disturbances are often modeled as process noise in a dynamical system, and common assumptions are that the underlying distributions are known and/or Gaussian. In practice, however, these assumptions may be unrealistic and can lead to poor approximations of the true noise distribution. We present a novel controller synthesis method that does not rely on any explicit representation of the noise distributions. In particular, we address the problem of computing a controller that provides probabilistic guarantees on safely reaching a target, while also avoiding unsafe regions of the state space. First, we abstract the continuous control system into a finite-state model that captures noise by probabilistic transitions between discrete states. As a key contribution, we adapt tools from the scenario approach to compute probably approximately correct (PAC) bounds on these transition probabilities, based on a finite number of samples of the noise. We capture these bounds in the transition probability intervals of a so-called interval Markov decision process (iMDP). This iMDP is, with a user-specified confidence probability, robust against uncertainty in the transition probabilities, and the tightness of the probability intervals can be controlled through the number of samples. We use state-of-the-art verification techniques to provide guarantees on the iMDP and compute a controller for which these guarantees carry over to the original control system. In addition, we develop a tailored computational scheme that reduces the complexity of the synthesis of these guarantees on the iMDP. Benchmarks on realistic control systems show the practical applicability of our method, even when the iMDP has hundreds of millions of transitions., Comment: To appear in the Journal of Artificial Intelligence Research (JAIR). arXiv admin note: text overlap with arXiv:2110.12662

Discarding constraints in scenario optimization, a technique known as the sampling-and-discarding scheme, allows the decision maker to trade feasibility to performance. Recently, a removal scheme with a less conservative bound on the constraint violation probability of the final decision has been proposed. In this letter, we further contribute to the theoretical properties of such a scheme by extending the number of discarded scenarios to be arbitrary, as opposed to an integer multiple of the dimension of the decision space. There are two facets to the results of this paper. On the one hand, our feasibility guarantees outperform the standard “sampling-and-discarding” bound in the literature. On the other hand, we highlight an inherent property of the discarding mechanism, namely, the fact that removing a number of scenarios that is not an integer multiple of the dimension of the decision space is likely to introduce additional conservatism.

Mathematical optimisation plays a crucial role in providing efficient solutions to modern engineering applications. Despite enormous advances in the past decades, some of these applications involve solving optimisation problems that may not be computationally tractable or that call for new theoretical advancements. Hence, obtaining robust and scalable methods and developing new analytic tools to optimisation problems is of paramount importance. This thesis addresses some of the main challenges when solving optimisation programs, namely, scalability, the presence of integer decision variables and the presence of uncertainty. Scalability throughout this thesis is achieved by means of distributed computation. Technological advancements that lead to the increase of computational devices per capita have attracted research on the development of algorithms that can exploit such a distributed and unstructured computational power to solve large-scale optimisation problems. In this context, multi-agent optimisation has emerged, as it enables distributed computation by allowing devices (or agents) to communicate over a network. This thesis proposes an algorithmic scheme based on subgradient averaging to perform multi-agent optimisation. Some optimisation problems are computationally intractable due to the presence of integer variables. Optimising over integers is, in general, hard due to the lack of polynomial-time algorithms to obtain an optimal solution. In fact, some well-known NP-hard problems can be cast as optimisation programs involving integer decision variables. In this thesis we investigate the so-called actuator placement problem and show that a particular instance of this problem, despite being an integer program can be solved exactly by means of a convex relaxation. We also link such a relaxation to the multi-agent optimisation framework explored previously, showing how distributed schemes can be leveraged to obtain the optimal solution. Other challenging optimisation problems arise with the presence of uncertain constraints. Indeed, even the well-studied class of linear optimisation problems may require theoretical and algorithmic advancements under this type of constraints. Uncertain constraints represent our lack of knowledge about the underlying phenomena and appear in several applications, including the optimal power flow problem under renewable energy generation, robotics, and transportation applications. Motivated by this fact, the last part of this thesis focuses on a randomised approximation to chance-constrained optimisation problems. We show a new theoretical bound on the probability of constraint violation that can improve the conservatism with respect to the state-of-the-art.

The so-called scenario approach offers an efficient framework to address uncertain optimisation problems with uncertainty represented by means of scenarios. The sampling-and-discarding approach within the scenario approach literature allows the decision maker to trade feasibility to performance. We focus on a removal scheme composed by a cascade of scenario programs that removes at each stage a superset of the support set associated to the optimal solution of each of these programs. This particular removal scheme yields a scenario solution with tight guarantees on the probability of constraint violation; however, existing analysis restricts the number of discarded scenarios to be a multiple of the dimension of the optimisation problem. Motivated by this fact, this paper presents pathways to extend the theoretical analysis of this removal scheme. We first provide an extension for a restricted class of scenarios programs for which tight bounds can be obtained, and then we provide a conservative bound on the probability of constraint violation that is valid for any scenario program and an arbitrary number of removed scenarios, which is, however, not tight.

International audience

We describe a dominantly inherited β-thalassemia intermedia phenotype observed in a five-generation Portuguese family. Carriers are characterized by moderate anemia, hypochromia, microcytosis, elevated hemoglobin (Hb)A2 and HbF levels, splenomegaly, hepatomegaly, and inclusion bodies in pheripheral red blood cells after splenectomy. The molecular basis of this condition is a small deletion within the 5′ consensus splicing sequence of the second intron of the β-globin gene, IVS-II-4,5 (-AG). Reticulocyte RNA studies performed by reverse transcription-polymerase chain reaction (RT-PCR) and primer extension analysis showed three abnormally processed transcripts, which, upon sequencing, were shown to correspond to (1) skipping of exon 2, and (2) activation of two cryptic splice sites (between codons 59/60, and at IVS-II-47). In vitro translation studies of these patients' reticulocyte RNA have shown that at least one of these aberrant mRNA species is translated into an abnormally elongated peptide whose cytotoxic properties could, in part, be causing the atypical dominant mode of inheritance observed in this family. We suggest that this elongated β chain is unable to combine with an α-globin chain to form a functional Hb molecule. Its degradation would, then, exhaust the proteolytic defense mechanism of the erythroid precursors, leading to inefficient proteolysis of the free α chains in excess.

We consider a multi-agent setting with agents exchanging information over a possibly time-varying network, aiming at minimising a separable objective function subject to constraints. To achieve this objective we propose a novel subgradient averaging algorithm that allows for non-differentiable objective functions and different constraint sets per agent. Allowing different constraints per agent simultaneously with a time-varying communication network constitutes a distinctive feature of our approach, extending existing results on distributed subgradient methods. To highlight the necessity of dealing with a different constraint set within a distributed optimisation context, we analyse a problem instance where an existing algorithm does not exhibit a convergent behaviour if adapted to account for different constraint sets. For our proposed iterative scheme we show asymptotic convergence of the iterates to a minimum of the underlying optimisation problem for step sizes of the form η k + 1 , η > 0 . We also analyse this scheme under a step size choice of η k + 1 , η > 0 , and establish a convergence rate of O ( ln k k ) in objective value. To demonstrate the efficacy of the proposed method, we investigate a robust regression problem and an l 2 regression problem with regularisation .

We consider a multi-agent setting with agents exchanging information over a network to solve a convex constrained optimisation problem in a distributed manner. We analyse a new algorithm based on local subgradient exchange under undirected time-varying communication. First, we prove asymptotic convergence of the iterates to a minimum of the given optimisation problem for time-varying step-sizes of the form $c(k) = \frac{\eta }{{k + 1}}$, for some η > 0. We then restrict attention to step-size choices $c(k) = \frac{\eta }{{\sqrt {k + 1} }},\eta > 0$, and establish a convergence of $\mathcal{O}\left( {\frac{{\ln (k)}}{{\sqrt k }}} \right)$ in objective value. Our algorithm extends currently available distributed subgradient/proximal methods by: (i) accounting for different constraint sets at each node, and (ii) enhancing the convergence speed thanks to a subgradient averaging step performed by the agents. A numerical example demonstrates the efficacy of the proposed algorithm.