Search

We extend the notion of Cantor-Kantorovich distance between Markov chains introduced by (Banse et al., 2023) in the context of Markov Decision Processes (MDPs). The proposed metric is well-defined and can be efficiently approximated given a finite horizon. Then, we provide numerical evidences that the latter metric can lead to interesting applications in the field of reinforcement learning. In particular, we show that it could be used for forecasting the performance of transfer learning algorithms., Comment: Presented at the 26th International Symposium on Mathematical Theory of Networks and Systems (Cambridge, UK)

Abstractions of dynamical systems enable their verification and the design of feedback controllers using simpler, usually discrete, models. In this paper, we propose a data-driven abstraction mechanism based on a novel metric between Markov models. Our approach is based purely on observing output labels of the underlying dynamics, thus opening the road for a fully data-driven approach to construct abstractions. Another feature of the proposed approach is the use of memory to better represent the dynamics in a given region of the state space. We show through numerical examples the usefulness of the proposed methodology., Comment: Submitted to IEEE Transactions on Automatic Control

This paper studies the controller synthesis problem for nonlinear control systems under linear temporal logic (LTL) specifications using zonotope techniques. A local-to-global control strategy is proposed for the desired specification expressed as an LTL formula. First, a novel approach is developed to divide the state space into finite zonotopes and constrained zonotopes, which are called cells and allowed to intersect with the neighbor cells. Second, from the intersection relation, a graph among all cells is generated to verify the realization of the accepting path for the LTL formula. The realization verification determines if there is a need for the control design, and also results in finite local LTL formulas. Third, once the accepting path is realized, a novel abstraction-based method is derived for the controller design. In particular, we only focus on the cells from the realization verification and approximate each cell thanks to properties of zonotopes. Based on local symbolic models and local LTL formulas, an iterative synthesis algorithm is proposed to design all local abstract controllers, whose existence and combination establish the global controller for the LTL formula. Finally, the proposed framework is illustrated via a path planning problem of mobile robots., Comment: 16 pages, 11 figures

We introduce Dionysos.jl, a modular package for solving optimal control problems for complex dynamical systems using state-of-the-art and experimental techniques from symbolic control, optimization, and learning. More often than not with Cyber-Physical systems, the only sensible way of developing a controller is by discretizing the different variables, thus transforming the control task into a purely combinatorial problem on a finite-state mathematical object, called an abstraction of this system. Although this approach offers a safety-critical framework, the available techniques suffer important scalability issues. In order to render these techniques practical, it is necessary to construct smarter abstractions that differ from classical techniques by partitioning the state-space in a non trivial way., Comment: Submitted to the Proceedings of the JuliaCon Conferences

We introduce the concept of memoryless concretization relation (MCR) to describe abstraction within the context of controller synthesis. This relation is a specific instance of alternating simulation relation (ASR), where it is possible to simplify the controller architecture. In the case of ASR, the concretized controller needs to simulate the concurrent evolution of two systems, the original and abstract systems, while for MCR, the designed controllers only need knowledge of the current concrete state. We demonstrate that the distinction between ASR and MCR becomes significant only when a non-deterministic quantizer is involved, such as in cases where the state space discretization consists of overlapping cells. We also show that any abstraction of a system that alternatingly simulates a system can be completed to satisfy MCR at the expense of increasing the non-determinism in the abstraction. We clarify the difference between the MCR and the feedback refinement relation (FRR), showing in particular that the former allows for non-constant controllers within cells. This provides greater flexibility in constructing a practical abstraction, for instance, by reducing non-determinism in the abstraction. Finally, we prove that this relation is not only sufficient, but also necessary, for ensuring the above properties., Comment: to appear in proc. of HSCC 2024

We propose a multi-scale approach for computing abstractions of dynamical systems, that incorporates both local and global optimal control to construct a goal-specific abstraction. For a local optimal control problem, we not only design the controller ensuring the transition between every two subsets (cells) of the state space but also incorporate the volume and shape of these cells into the optimization process. This integrated approach enables the design of non-uniform cells, effectively reducing the complexity of the abstraction. These local optimal controllers are then combined into a digraph, which is globally optimized to obtain the entire trajectory. The global optimizer attempts to lazily build the abstraction along the optimal trajectory, which is less affected by an increase in the number of dimensions. Since the optimal trajectory is generally unknown in practice, we propose a methodology based on the RRT* algorithm to determine it incrementally. Finally, we provide a tractable implementation of this algorithm for the optimal control of L-smooth nonlinear dynamical systems., Comment: 9 pages, 8 figures

Safety in the face of uncertainty is a key challenge in robotics. We introduce a real-time capable framework to generate safe and task-efficient robot motions for stochastic control problems. We frame this as a chance-constrained optimisation problem constraining the probability of the controlled system to violate a safety constraint to be below a set threshold. To estimate this probability we propose a Monte--Carlo approximation. We suggest several ways to construct the problem given a fixed number of uncertainty samples, such that it is a reliable over-approximation of the original problem, i.e. any solution to the sample-based problem adheres to the original chance-constraint with high confidence. To solve the resulting problem, we integrate it into our motion planner VP-STO and name the enhanced framework Chance-Constrained (CC)-VPSTO. The strengths of our approach lie in i) its generality, without assumptions on the underlying uncertainty distribution, system dynamics, cost function, or the form of inequality constraints; and ii) its applicability to MPC-settings. We demonstrate the validity and efficiency of our approach on both simulation and real-world robot experiments., Comment: 17 pages, 11 figures, submitted to IEEE Transactions on Robotics

Neural-based, data-driven analysis and control of dynamical systems have been recently investigated and have shown great promise, e.g. for safety verification or stability analysis. Indeed, not only do neural networks allow for an entirely model-free, data-driven approach, but also for handling arbitrary complex functions via their power of representation (as opposed to, e.g. algebraic optimization techniques that are restricted to polynomial functions). Whilst classical Lyapunov techniques allow to provide a formal and robust guarantee of stability of a switched dynamical system, very little is yet known about correctness guarantees for Neural Lyapunov functions, nor about their performance (amount of data needed for a certain accuracy). We thus formally introduce neural Lyapunov functions for the stability analysis of switched linear systems: we benchmark them on this paradigmatic problem, which is notoriously difficult (and in general Turing-undecidable), but which admits recently-developed technologies and theoretical results. Inspired by switched systems theory, we provide theoretical guarantees on the representative power of neural networks, leveraging recent results from the ML community. We additionally experimentally display how neural Lyapunov functions compete with state-of-the-art results and techniques, while admitting a wide range of improvement, both in theory and in practice. This study intends to improve our understanding of the opportunities and current limitations of neural-based data-driven analysis and control of complex dynamical systems., Comment: 13 pages, 8 figures

This paper presents novel stabilizability conditions for switched linear systems with arbitrary and uncontrollable underlying switching signals. We distinguish and study two particular settings: i) the \emph{robust} case, in which the active mode is completely unknown and unobservable, and ii) the \emph{mode-dependent} case, in which the controller depends on the current active switching mode. The technical developments are based on graph-theory tools, relying in particular on the path-complete Lyapunov functions framework. The main idea is to use directed and labeled graphs to encode Lyapunov inequalities to design robust and mode-dependent piecewise linear state-feedback controllers. This results in novel and flexible conditions, with the particular feature of being in the form of linear matrix inequalities (LMIs). Our technique thus provides a first controller-design strategy allowing piecewise linear feedback maps and piecewise quadratic (control) Lyapunov functions by means of semidefinite programming. Numerical examples illustrate the application of the proposed techniques, the relations between the graph order, the robustness, and the performance of the closed loop.

We prove a fundamental limitation on the efficiency of a wide class of Reinforcement Learning (RL) algorithms. This limitation applies to model-free RL methods as well as a broad range of model-based methods, such as planning with tree search. Under an abstract definition of this class, we provide a family of RL problems for which these methods suffer a lower bound exponential in the horizon for their interactions with the environment to find an optimal behavior. However, there exists a method, not tailored to this specific family of problems, which can efficiently solve the problems in the family. In contrast, our limitation does not apply to several types of methods proposed in the literature, for instance, goal-conditioned methods or other algorithms that construct an inverse dynamics model.

We propose a novel framework for the Lyapunov analysis of an important class of hybrid systems, inspired by the theory of symbolic dynamics and earlier results on the restricted class of switched systems. This new framework allows us to leverage language theory tools in order to provide a universal characterization of Lyapunov stability for this class of systems. We establish, in particular, a formal connection between multiple Lyapunov functions and techniques based on memorization and/or prediction of the discrete part of the state. This allows us to provide an equivalent (single) Lyapunov function, for any given multiple-Lyapunov criterion. By leveraging our language-theoretic formalism, a new class of stability conditions is then obtained when considering both memory and future values of the state in a joint fashion, providing new numerical schemes that outperform existing technique. Our techniques are then illustrated on numerical examples., Comment: To appear in SICON

In 1892, Lyapunov provided a fundamental contribution to stability theory by introducing so-called Lyapunov functions and Lyapunov equilibria. He subsequently showed that, for linear systems, the two concepts are equivalent. These concepts have since been extended to diverse types of dynamical systems, and in all settings the equivalence remains valid. However, this involves an often technical proof in each new setting where the concepts are introduced. In this article, we investigate a categorical framework where these results can be unified, exposing a single underlying reason for the equivalence to hold in all cases. First we define what is a dynamical system. Then we introduce the notion of a level-set morphism, which in turn allows us to define the concepts of a Lyapunov equilibrium and a Lyapunov function in a categorical setting. We conclude by a proof of their equivalence., Comment: 11 pages Submitted to Cahiers de topologie et g\'eom\'etrie diff\'erentielle

We consider the problem of automatically synthesizing a hybrid controller for non-linear dynamical systems which ensures that the closed-loop fulfills an arbitrary \emph{Linear Temporal Logic} specification. Moreover, the specification may take into account logical context switches induced by an external environment or the system itself. Finally, we want to avoid classical brute-force time- and space-discretization for scalability. We achieve these goals by a novel two-layer strategy synthesis approach, where the controller generated in the lower layer provides invariant sets and basins of attraction, which are exploited at the upper logical layer in an abstract way. In order to achieve this, we provide new techniques for both the upper- and lower-level synthesis. Our new methodology allows to leverage both the computing power of state space control techniques and the intelligence of finite game solving for complex specifications, in a scalable way.

We introduce an adaptive refinement procedure for smart, and scalable abstraction of dynamical systems. Our technique relies on partitioning the state space depending on the observation of future outputs. However, this knowledge is dynamically constructed in an adaptive, asymmetric way. In order to learn the optimal structure, we define a Kantorovich-inspired metric between Markov chains, and we use it as a loss function. Our technique is prone to data-driven frameworks, but not restricted to. We also study properties of the above mentioned metric between Markov chains, which we believe could be of application for wider purpose. We propose an algorithm to approximate it, and we show that our method yields a much better computational complexity than using classical linear programming techniques., Comment: This paper is an extended version of a CDC2023 submission

We present a data-driven framework based on Lyapunov theory to provide stability guarantees for a family of hybrid systems. In particular, we are interested in the asymptotic stability of switching linear systems whose switching sequence is constrained by labeled graphs, namely constrained switching linear systems. In order to do so, we provide chance-constrained bounds on stability guarantees, that can be obtained from a finite number of noisy observations. We first present a method providing stability guarantees from sampled trajectories in the hybrid state-space of the system. We then study the harder situation where one only observes the continuous part of the hybrid states. We show that in this case, one may still obtain formal chance-constrained stability guarantees. For this latter result we provide a new upper bound of general interest, also for model-based stability analysis, Comment: Submitted to Nonlinear Analysis: Hybrid Systems

This paper deals with learning stability of partially observed switched linear systems under arbitrary switching. Such systems are widely used to describe cyber-physical systems which arise by combining physical systems with digital components. In many real-world applications, the internal states cannot be observed directly. It is thus more realistic to conduct system analysis using the outputs of the system. Stability is one of the most frequent requirement for safety and robustness of cyber-physical systems. Existing methods for analyzing stability of switched linear systems often require the knowledge of the parameters and/or all the states of the underlying system. In this paper, we propose an algorithm for deciding stability of switched linear systems under arbitrary switching based purely on observed output data. The proposed algorithm essentially relies on an output-based Lyapunov stability framework and returns an estimate of the joint spectral radius (JSR). We also prove a probably approximately correct error bound on the quality of the estimate of the JSR from the perspective of statistical learning theory.

We propose a sample-based, sequential method to abstract a (potentially black-box) dynamical system with a sequence of memory-dependent Markov chains of increasing size. We show that this approximation allows to alleviating a correlation bias that has been observed in sample-based abstractions. We further propose a methodology to detect on the fly the memory length resulting in an abstraction with sufficient accuracy. We prove that under reasonable assumptions, the method converges to a sound abstraction in some precise sense, and we showcase it on two case studies.

We present a novel method for deciding whether a given n-dimensional ellipsoid contains another one (possibly with a different center). This method consists in constructing a particular concave function and deciding whether it has any value greater than -1 in a compact interval that is a subset of [0,1]. This can be done efficiently by a bisection algorithm method that is guaranteed to stop in a finite number of iterations. The initialization of the method requires O(n^3) floating-point operations and evaluating this function and its derivatives requires O(n). This can be also generalized to compute the smallest level set of a convex quadratic function containing a finite number of n-ellipsoids. In our benchmark with randomly generated ellipsoids, when compared with a classic method based on semidefinite programming, our algorithm performs 27 times faster for ellipsoids of dimension n=3 and 2294 times faster for dimension n=100. We illustrate the usefulness of this method with a problem in the control theory field., Comment: 8 Pages, 3 Figures, submitted to international conference

We study path-complete Lyapunov functions, which are stability criteria for switched systems, described by a combinatorial component (namely, an automaton), and a functional component (a set of candidate Lyapunov functions, called the template). We introduce a class of criteria based on what we call memory-based Lyapunov functions, which generalize several techniques in the literature. Our main result is an equivalence result: any path-complete Lyapunov function is equivalent to a memory-based Lyapunov function, however defined on another template. We show the usefulness of our result in terms of numerical efficiency via an academic example., Comment: Preprint, Submitted to ACC23

We present an algorithmic framework for the identification of candidate invariant subspaces for switched linear systems. Namely, the framework allows to compute an orthonormal basis in which the matrices of the system are close to block-triangular matrices, based on a finite set of observed one-step trajectories and with a priori confidence level. The link between the existence of an invariant subspace and a common block-triangularization of the system matrices is well known. Under some assumptions on the system, one can also infer the existence of an invariant subspace when the matrices are close to be block-triangular. Our approach relies on quadratic Lyapunov analysis and recent tools in scenario optimization. We present two applications of our results for problems of consensus and opinion dynamics; the first one allows to identify the disconnected components in a switching hidden network, while the second one identifies the stationary opinion vector of a switching gossip process with antagonistic interactions.

In this paper, we study the application of switched systems stability criteria to derive delay-dependent conditions for systems affected by both a constant and a time-varying delay. The main novelty of our approach lies on the use of path-complete Lyapunov techniques along with the proposition of a new modified functional to obtain convex analysis conditions while avoiding the need of computing a dwell time for each mode in a switched system representation, as usual in the \textit{switched approach} for time-delay systems. Furthermore, we leverage the developed analysis to obtain LMIs for the closed-loop stabilization of systems with time-varying sensor delays by means of an observer-based compensator. A numerical example illustrates the proposed methods., Comment: Accepted for presentation at the 61st Conference on Decision and Control (CDC) 2022, Cancun, Mexico

In this paper, we develop tools to establish almost sure stability of stochastic switched systems whose switching signal is constrained by an automaton. After having provided the necessary generalizations of existing results in the setting of stochastic graphs, we provide a characterization of almost sure stability in terms of multiple Lyapunov functions. We introduce the concept of lifts, providing formal expansions of stochastic graphs, together with the guarantee of conserving the underlying probability framework. We show how these techniques, firstly introduced in the deterministic setting, provide hierarchical methods in order to compute tight upper bounds for the almost sure decay rate. The theoretical developments are finally illustrated via a numerical example., Comment: Extended version of conference submission

Meta-learning is a line of research that develops the ability to leverage past experiences to efficiently solve new learning problems. Meta-Reinforcement Learning (meta-RL) methods demonstrate a capability to learn behaviors that efficiently acquire and exploit information in several meta-RL problems. In this context, the Alchemy benchmark has been proposed by Wang et al. [2021]. Alchemy features a rich structured latent space that is challenging for state-of-the-art model-free RL methods. These methods fail to learn to properly explore then exploit. We develop a model-based algorithm. We train a model whose principal block is a Transformer Encoder to fit the symbolic Alchemy environment dynamics. Then we define an online planner with the learned model using a tree search method. This algorithm significantly outperforms previously applied model-free RL methods on the symbolic Alchemy problem. Our results reveal the relevance of model-based approaches with online planning to perform exploration and exploitation successfully in meta-RL. Moreover, we show the efficiency of the Transformer architecture to learn complex dynamics that arise from latent spaces present in meta-RL problems.

We present a framework based on multiple Lyapunov functions to find probabilistic data-driven guarantees on the stability of unknown constrained switching linear systems (CSLS), which are switching linear systems whose switching signal is constrained by an automaton. The stability of a CSLS is characterized by its constrained joint spectral radius (CJSR). Inspired by the scenario approach and previous work on unconstrained switching systems, we characterize the number of observations needed to find sufficient conditions on the (in-)stability of a CSLS using the notion of CJSR. More precisely, our contribution is the following: we derive a probabilistic upper bound on the CJSR of an unknown CSLS from a finite number of observations. We also derive a deterministic lower bound on the CJSR. From this we obtain a probabilistic method to characterize the stability of an unknown CSLS., Comment: CDC2022 pre-print, 6 pages

We consider stability analysis of constrained switching linear systems in which the dynamics is unknown and whose switching signal is constrained by an automaton. We propose a data-driven Lyapunov framework for providing probabilistic stability guarantees based on data harvested from observations of the system. By generalizing previous results on arbitrary switching linear systems, we show that, by sampling a finite number of observations, we are able to construct an approximate Lyapunov function for the underlying system. Moreover, we show that the entropy of the language accepted by the automaton allows to bound the number of samples needed in order to reach some pre-specified accuracy., Comment: Extended abstract (4 pages), accepted final version

This paper studies the stabilization and safety problems of nonlinear time-delay systems. Following both Razumikhin and Krasovskii approaches, we propose novel control Lyapunov functions/functionals for the stabilization problem and novel control barrier functions/functionals for the safety problem. The proposed control Lyapunov and barrier functions/functionals extend the existing ones from the delay-free case to the time-delay case, and allow for designing the stabilizing and safety controllers in closed-form. Since analytical solutions to time-delay optimal control problems are hard to be achieved, a sliding mode control based approach is developed to merge the proposed control Lyapunov and barrier functions/functionals. Based on the sliding surface functional, a feedback control law is established to investigate the stabilization and safety objectives simultaneously. In particular, the properties of the sliding surface functional are analyzed, and further how to construct the sliding surface functional is discussed. Finally, the proposed approaches are illustrated via two numerical examples from the connected cruise control problem of automotive systems and the synchronization problem of multi-agent systems., Comment: 15 pages, 12 figures, accepted as Regular Paper by Automatica

This paper is concerned with objective value performance of the scenario approach for robust convex optimization. A novel method is proposed to derive probabilistic bounds for the objective value from scenario programs with a finite number of samples. This method relies on a max-min reformulation and the concept of complexity of robust optimization problems. With additional continuity and regularity conditions, via sensitivity analysis, we also provide explicit bounds which outperform an existing result in the literature. To illustrate the improvements of our results, we also provide a numerical example.

This paper treats the global stabilization problem of continuous-time switched affine systems that have rank-deficient convex combinations of their dynamic matrices. For these systems, the already known set of attainable equilibrium points has higher dimensionality than in the full-rank case due to the existence of what we define as singular equilibrium points. Our main goal is to design a state-dependent switching function to ensure global asymptotic stability of a chosen point inside this set with conditions expressed in terms of linear matrix inequalities. For this class of systems, global exponential stability is generally impossible to be guaranteed. Hence, the proposed switching function is shown to ensure global asymptotic and local exponential stability of the desired equilibrium point. The position control and the velocity control with integral action of a dc motor driven by an h-bridge fed via a boost converter are used for validation. This practical application example is composed of eight subsystems, and all possible convex combinations of the dynamic matrices are singular., Comment: 16 pages, 5 figures, forwarded to be published in Automatica

The problem of the optimal allocation (in the expected mean square error sense) of a measurement budget for particle filtering is addressed. We propose three different optimal intermittent filters, whose optimality criteria depend on the information available at the time of decision making. For the first, the stochastic program filter, the measurement times are given by a policy that determines whether a measurement should be taken based on the measurements already acquired. The second, called the offline filter, determines all measurement times at once by solving a combinatorial optimization program before any measurement acquisition. For the third one, which we call online filter, each time a new measurement is received, the next measurement time is recomputed to take all the information that is then available into account. We prove that in terms of expected mean square error, the stochastic program filter outperforms the online filter, which itself outperforms the offline filter. However, these filters are generally intractable. For this reason, the filter estimate is approximated by a particle filter. Moreover, the mean square error is approximated using a Monte-Carlo approach, and different optimization algorithms are compared to approximately solve the combinatorial programs (a random trial algorithm, greedy forward and backward algorithms, a simulated annealing algorithm, and a genetic algorithm). Finally, the performance of the proposed methods is illustrated on two examples: a tumor motion model and a common benchmark for particle filtering., Comment: 13 pages, 7 figures, 3 Tables

In this manuscript, we investigate symbolic abstractions that capture the behavior of piecewise-affine systems under input constraints and bounded external noise. This is accomplished by considering local affine feedback controllers that are jointly designed with the symbolic model, which ensures that an alternating simulation relation between the system and the abstraction holds. The resulting symbolic system is called a state-feedback abstraction and we show that it can be deterministic even when the original piecewise-affine system is unstable and non-deterministic. One benefit of this approach is the fact that the input space need not be discretized and the symbolic-input space is reduced to a finite set of controllers. When ellipsoidal cells and affine controllers are considered, we present necessary and sufficient conditions written as a semi-definite program for the existence of a transition and a robust upper bound on the transition cost. Two examples illustrate particular aspects of the theory and its applicability., Comment: 10 pages, 3 figures, accepted to IEEE CDC 2022

This paper studies optimal scheduling and resource allocation under allowable over-scheduling. Formulating an optimisation problem where over-scheduling is embedded, we derive an optimal solution that can be implemented by means of a new additive increase multiplicative decrease (AIMD) algorithm. After describing the AIMD-like scheduling mechanism as a switching system, we show convergence of the scheme, based on the joint spectral radius of symmetric matrices, and propose two methods for fitting an optimal AIMD tuning to the optimal solution derived. Finally, we demonstrate the overall optimal design strategy via an illustrative example., Comment: 8 pages, 4 figures, submitted to CDC2022. arXiv admin note: text overlap with arXiv:2112.00708

The dynamical behavior of switched affine systems is known to be more intricate than that of the well-studied switched linear systems, essentially due to the existence of distinct equilibrium points for each subsystem. First, under arbitrary switching rules, the stability analysis must be generally carried out with respect to a compact set with non-empty interior rather than to a singleton. We provide a novel proof technique for existence and outer approximation of attractive invariant sets of a switched affine system, under the hypothesis of global uniform stability of its linearization. On the other hand, considering dwell-time switching signals, forward invariant sets need not exist for this class of switched systems, even for stable ones. Hence, more general notions of stability/boundedness are introduced and studied, highlighting the relations of these concepts to the uniform stability of the linear part of the system under the same class of dwell-time switching signals. These results reveal the main differences and specificities of switched affine systems with respect to linear ones, providing a first step for the analysis of switched systems composed by subsystems not sharing the same equilibrium. Numerical methods based on linear matrix inequalities and sum-of-squares programming are presented and illustrate the developed theory., Comment: Submitted as a journal paper

In this paper, we present a geometric approach for computing controlled invariant sets for hybrid control systems. While the problem is well studied in the ellipsoidal case, this family is quite conservative for constrained or switched linear systems. We reformulate the invariance of a set as an inequality for its support function that is valid for any convex set. This produces novel algebraic conditions for the invariance of sets with polynomial or piecewise quadratic support function., Comment: 20 pages, 2 figures, submitted to Nonlinear Analysis: Hybrid Systems (NAHS). arXiv admin note: substantial text overlap with arXiv:2101.06990

This paper investigates, in the context of discrete-time switching systems, the problem of comparison for path-complete stability certificates. We introduce and study abstract operations on path-complete graphs, called lifts, which allow us to recover previous results in a general framework. Moreover, this approach highlights the existing relations between the analytical properties of the chosen set of candidate Lyapunov functions (the template) and the admissibility of certain lifts. This provides a new methodology for the characterization of the order relation of path-complete Lyapunov functions criteria, when a particular template is chosen. We apply our results to specific templates, notably the sets of primal and dual copositive norms, providing new stability certificates for positive switching systems. These tools are finally illustrated with the aim of numerical examples., Comment: 23 pages, 7 figures, submission

This paper studies the tracking control problem of networked and quantized control systems under both multiple networks and event-triggered mechanisms. Multiple networks are to connect the plant and reference system with decentralized controllers to guarantee their information transmission, whereas event-triggered mechanisms are to reduce the information transmission via multiple networks. In this paper, all networks are independent and asynchronous and have local event-triggered mechanisms, which are based on local measurements and determine whether the local measurements need to be transmitted. We first implement an emulation-based approach to develop a novel hybrid model for tracking control of networked and quantized control systems. Next, sufficient conditions are derived and decentralized event-triggered mechanisms are designed to ensure the tracking performance. Finally, a numerical example is given to illustrate the obtained results., Comment: Here is the 8-page version of the one accepted by ECC2021

The essence of distributed computing systems is how to schedule incoming requests and how to allocate all computing nodes to minimize both time and computation costs. In this paper, we propose a cost-aware optimal scheduling and allocation strategy for distributed computing systems while minimizing the cost function including response time and service cost. First, based on the proposed cost function, we derive the optimal request scheduling policy and the optimal resource allocation policy synchronously. Second, considering the effects of incoming requests on the scheduling policy, the additive increase multiplicative decrease (AIMD) mechanism is implemented to model the relation between the request arrival and scheduling. In particular, the AIMD parameters can be designed such that the derived optimal strategy is still valid. Finally, a numerical example is presented to illustrate the derived results., Comment: This work has been submitted to ACC2022

In this paper, we investigate the controller design problem for linear disturbed systems under signal temporal logic (STL) specifications imposing both spatial and temporal constraints on system behavior. We first implement zonotope-based techniques to partition the state space into finite cells, then propose an evaluation mechanism to rearrange the time constraints of the STL specification, and finally decompose the global STL formula into finite local STL formulas. In this way, each cell has a local control design problem, which is further formulated into a local optimization problem. To deal with each local optimization problem, we take advantage of the properties of zonotopes and reachability analysis to design local controller consisting of feedforward and feedback parts. By solving all local optimization problems, all local controllers are combined to guarantee the global STL specification. Finally, a numerical example is presented to illustrate the derived results., Comment: 8 pages, 4 figures, sumitted to American Control Conference 2022

We consider discrete-time switching systems composed of a finite family of affine sub-dynamics. First, we recall existing results and present further analysis on the stability problem, the existence and characterization of compact attractors, and the relations these problems have with the joint spectral radius of the set of matrices composing the linear part of the subsystems. Second, we tackle the problem of providing probabilistic certificates of stability along with the existence of forward invariant sets, assuming no knowledge on the system data but only observing a finite number of sampled trajectories. Some numerical examples illustrate the advantages and limits of the proposed conditions., Comment: 1 figure, paper submitted CDC2021

This paper addresses the problem of robust control of a linear discrete-time system subject to bounded disturbances and to measurement and control budget constraints. Using Q-parameterization and a polytope containment method, we prove that the co-design of an affine feedback controller, a measurement schedule and a control schedule can be exactly formulated as a mixed integer linear program with 2 binary variables per time step. As a consequence, this problem can be solved efficiently, even when an exhaustive search for measurement and control times would have been impossible in a reasonable amount of time., Comment: Published in the 60th IEEE Conference in Decision and Control (2021). 8 pages, 4 figures, 1 table

We study the algorithmic complexity of the problem of deciding whether a Linear Time Invariant dynamical system with rational coefficients has bounded trajectories. Despite its ubiquitous and elementary nature in Systems and Control, it turns out that this question is quite intricate, and, to the best of our knowledge, unsolved in the literature. We show that classical tools, such as Gaussian Elimination, the Routh--Hurwitz Criterion, and the Euclidean Algorithm for GCD of polynomials indeed allow for an algorithm that is polynomial in the bit size of the instance. However, all these tools have to be implemented with care, and in a non-standard way, which relies on an advanced analysis., Comment: To appear in Proceedings of 2021 60th IEEE Conference on Decision and Control (CDC)

This paper studies the controller synthesis problem for Linear Temporal Logic (LTL) specifications using (constrained) zonotope techniques. First, we implement (constrained) zonotope techniques to partition the state space and further to verify whether the LTL specification can be satisfied. Once the LTL specification can be satisfied, the next step is to design a controller to guarantee the satisfaction of the LTL specification for dynamic systems. Based on the verification of the LTL specification, an abstraction-based control design approach is proposed in this paper: a novel abstraction construction is developed first, then finite local abstract controllers are designed to achieve the LTL specification, and finally the designed abstract controllers are combined and refined as the controller for the original system. The proposed control strategy is illustrated via a numerical example from autonomous robots., Comment: 6 pages, 5 figures, CDC2021

We present a new data-driven method to provide probabilistic stability guarantees for black-box switched linear systems. By sampling a finite number of observations of trajectories, we construct approximate Lyapunov functions and deduce the stability of the underlying system with a user-defined confidence. The number of observations required to attain this confidence level on the guarantee is explicitly characterized. Our contribution is twofold: first, we propose a novel approach for common quadratic Lyapunov functions, relying on sensitivity analysis of a quasi-convex optimization program. By doing so, we improve a recently proposed bound. Then, we show that our new approach allows for extension of the method to Sum of Squares Lyapunov functions, providing further improvement for the technique. We demonstrate these improvements on a numerical example., Comment: to be published in the proceedings of the 7th IFAC Conference on Analysis and Design of Hybrid Systems (ADHS 2021)

A caveat to many applications of the current Deep Learning approach is the need for large-scale data. One improvement suggested by Kolmogorov Complexity results is to apply the minimum description length principle with computationally universal models. We study the potential gains in sample efficiency that this approach can bring in principle. We use polynomial-time Turing machines to represent computationally universal models and Boolean circuits to represent Artificial Neural Networks (ANNs) acting on finite-precision digits. Our analysis unravels direct links between our question and Computational Complexity results. We provide lower and upper bounds on the potential gains in sample efficiency between the MDL applied with Turing machines instead of ANNs. Our bounds depend on the bit-size of the input of the Boolean function to be learned. Furthermore, we highlight close relationships between classical open problems in Circuit Complexity and the tightness of these.

This paper tackles state feedback control of switched linear systems under arbitrary switching. We propose a data-driven control framework that allows to compute a stabilizing state feedback using only a finite set of observations of trajectories with quadratic and sum of squares (SOS) Lyapunov functions. We do not require any knowledge on the dynamics or the switching signal, and as a consequence, we aim at solving \emph{uniform} stabilization problems in which the feedback is stabilizing for all possible switching sequences. In order to generalize the solution obtained from trajectories to the actual system, probabilistic guarantees on the obtained quadratic or SOS Lyapunov function are derived in the spirit of scenario optimization. For the quadratic Lyapunov technique, the generalization relies on a geometric analysis argument, while, for the SOS Lyapunov technique, we follow a sensitivity analysis argument. In order to deal with high-dimensional systems, we also develop parallelized schemes for both techniques. We show that, with some modifications, the data-driven quadratic Lyapunov technique can be extended to LQR control design. Finally, the proposed data-driven control framework is demonstrated on several numerical examples., Comment: This is an extended version to the previous paper