Search

This paper addresses a structural design problem in control systems, and explicitly takes into consideration the possible application to large-scale systems. More precisely, we aim to determine and characterize the minimum number of manipulated state variables ensuring structural controllability of switched linear continuous-time systems. Towards this goal, we provide a new necessary and sufficient condition that leverages both graph-theoretic and algebraic properties required to ensure feasibility of the solutions. With this new condition, we show that a solution can be determined by an efficient procedure, i.e., polynomial in the number of state variables. In addition, we also discuss the switching signal properties that ensure structural controllability and the computational complexity of determining these sequences. In particular, we show that determining the minimum number of modes that a switching signal requires to ensure structural controllability is NP-hard. [ABSTRACT FROM AUTHOR]

Fifty years ago, control and computing were part of a broader system science. After a long period of separate development within each discipline, embedded and hybrid systems have challenged us to re-unite the, now sophisticated theories of continuous control and discrete computing on a broader system theoretic basis. In this paper, we present a framework of system approximation that applies to both discrete and continuous systems. We define a hierarchy of approximation metrics between two systems that quantify the quality of the approximation, and capture the established notions in computer science as zero sections. The central notions in this framework are that of approximate simulation and bisimulation relations and their functional characterizations called simulation and bisimulation functions and defined by Lyapunov-type inequalities. In particular, these functions can provide computable upper-bounds on the approximation metrics by solving a static game. Our approximation framework will be illustrated by showing some of its applications in various problems such as reachability analysis of continuous systems and hybrid systems, approximation of continuous and hybrid systems by discrete systems, hierarchical control design, and simulation-based approaches to verification of continuous and hybrid systems. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we present a new approach for hierarchical control based on the recent notions of approximate simulation and simulation functions, a quantitative version of the simulation relations. Given a complex system that needs to be controlled and a simpler abstraction, we show how the knowledge of a simulation function allows us to synthesize hierarchical control laws by first controlling the abstraction and then lifting the abstract control law to the complex system using an interface. For the class of linear control systems, we give an effective characterization of the simulation functions and of the associated interfaces. This characterization allows us to use algorithmic procedures for their computation. We show how to choose an abstraction for a linear control system such that our hierarchical control approach can be used. Finally, we show the effectiveness of our approach on an example. [Copyright &y& Elsevier]

Abstract: Graph matching is a fundamental problem that arises frequently in the areas of distributed control, computer vision, and facility allocation. In this paper, we consider the optimal graph matching problem for weighted graphs, which is computationally challenging due the combinatorial nature of the set of permutations. Contrary to optimization-based relaxations to this problem, in this paper we develop a novel relaxation by constructing dynamical systems on the manifold of orthogonal matrices. In particular, since permutation matrices are orthogonal matrices with nonnegative elements, we define two gradient flows in the space of orthogonal matrices. The first minimizes the cost of weighted graph matching over orthogonal matrices, whereas the second minimizes the distance of an orthogonal matrix from the finite set of all permutations. The combination of the two dynamical systems converges to a permutation matrix, which provides a suboptimal solution to the weighted graph matching problem. Finally, our approach is shown to be promising by illustrating it on nontrivial problems. [Copyright &y& Elsevier]

Abstract: In this paper, we define the notion of approximate bisimulation relation between two continuous systems. While exact bisimulation requires that the observations of two systems are and remain identical, approximate bisimulation allows the observations to be different provided the distance between them remains bounded by some parameter called precision. Approximate bisimulation relations are conveniently defined as level sets of a so-called bisimulation function which can be characterized using Lyapunov-like differential inequalities. For a class of constrained linear systems, we develop computationally effective characterizations of bisimulation functions that can be interpreted in terms of linear matrix inequalities and optimal values of static games. We derive a method to evaluate the precision of the approximate bisimulation relation between a constrained linear system and its projection. This method has been implemented in a Matlab toolbox: MATISSE. An example of use of the toolbox in the context of safety verification is shown. [Copyright &y& Elsevier]

Abstract: Trajectory generation for nonlinear control systems is an important and difficult problem. In this paper, we provide a constructive method for hierarchical trajectory refinement. The approach is based on the recent notion of -related control systems. Given a control affine system satisfying certain assumptions, we construct a -related control system of smaller dimension. Trajectories designed for the smaller, abstracted system are guaranteed, by construction, to be feasible for the original system. Constructive procedures are provided for refining trajectories from the coarser to the more detailed system. [Copyright &y& Elsevier]

The notion of bisimulation in theoretical computer science is one of the main complexity reduction methods for the analysis and synthesis of labeled transition systems. Bisimulations are special quotients of the state space that preserve many important properties expressible in temporal logics, and, in particular, reachability. In this paper, the framework of bisimilar transition systems is applied to various transition systems that are generated by linear control systems. Given a discrete-time or continuous-time linear system, and a finite observation map, we characterize linear quotient maps that result in quotient transition systems that are bisimilar to the original system. Interestingly, the characterizations for discrete-time systems are more restrictive than for continuous-time systems, due to the existence of an atomic time step. We show that computing the coarsest bisimulation, which results in maximum complexity reduction, corresponds to computing the maximal controlled or reachability invariant subspace inside the kernel of the observations map. These results establish strong connections between complexity reduction concepts in control theory and computer science. [Copyright &y& Elsevier]

Given a control system and a desired property, an abstracted system is a reduced system that preserves the property of interest while ignoring modeling detail. In previous work, abstractions of linear and nonlinear control systems were considered while preserving reachability properties. In this paper, we consider the abstraction problem for Hamiltonian control systems, where, in addition to the property of interest we also preserve the Hamiltonian structure of the control system. We show how the Hamiltonian structure of control systems can be exploited to simplify the abstraction process. We then focus on local accessibility preserving abstractions, and provide conditions under which local accessibility properties of the abstracted Hamiltonian system are equivalent to the local accessibility properties of the original Hamiltonian control system. [Copyright &y& Elsevier]

Recent control trends are increasingly relying on communication networks and wireless channels to close the loop for Internet-of-Things applications. Traditionally these approaches are model-based, i.e., assuming a network or channel model they are focused on stability analysis and appropriate controller designs. However the availability of such wireless channel modeling is fundamentally challenging in practice as channels are typically unknown a priori and only available through data samples. In this work we aim to develop algorithms that rely on channel sample data to determine the mean square stability and performance of networked control tasks. In this regard our work is the first to characterize the amount of channel modeling that is required to answer such a question. Specifically we examine how many channel data samples are required in order to answer with high confidence whether a given networked control system is stable or not. This analysis is based on the notion of sample complexity from the learning literature and is facilitated by concentration inequalities. Moreover we establish a direct relation between the sample complexity and the networked system stability margin, i.e., the underlying packet success rate of the channel and the spectral radius of the dynamics of the control system. This illustrates that it becomes impractical to verify stability under a large range of plant and channel configurations. We validate our theoretical results in numerical simulations. [ABSTRACT FROM AUTHOR]

Interferences arising between wireless sensor–actuator systems communicating over shared wireless channels impact closed loop control performance. We design interference-aware channel access policies where the total transmit power of the sensors is minimized while desired control performance is guaranteed for each involved control loop. Control performance is abstracted as an expected decrease rate of a Lyapunov function for each loop. We prove that the optimal channel access policies are decoupled so that, intuitively, each sensor balances the gains from transmitting to its actuator with the negative interference effect on all other control loops. Moreover the optimal policies are of a threshold nature with respect to channel conditions, that is, a sensor transmits only under favorable local fading conditions. Finally, the optimal policies can be computed by a distributed iterative procedure which does not require coordination between the sensors. [ABSTRACT FROM AUTHOR]

This paper addresses the design of finite-dimensional feedback control laws for linear discrete-time fractional-order systems with additive state disturbance. A set of sufficient conditions are provided to guarantee convergence of the state trajectories to an ultimate bound around the origin with size increasing with the magnitude of the disturbances. Performing a suitable change of coordinates, the latter result can be used to design a controller that is able to track reference trajectories that are solutions of the unperturbed fractional-order system. To overcome the challenges associated with the generation of such solutions, we address the practical case where the references to be tracked are generated as a solution of a specific finite-dimensional approximation of the original fractional-order system. In this case, the tracking error trajectory is driven to an asymptotic bound that is increasing with the magnitude of the disturbances and decreases with the increment in the accuracy of the approximation. The proposed controllers are finite-dimensional, in the sense that the computation of the control input only requires a finite number of previous state and input vectors of the system. Numerical simulations illustrate the proposed design methods in different scenarios. [ABSTRACT FROM AUTHOR]

In this paper, we establish a zero-sum, hybrid state stochastic game model for designing defense policies for cyber-physical systems against different types of attacks. With the increasingly integrated properties of cyber-physical systems (CPS) today, security is a challenge for critical infrastructures. Though resilient control and detecting techniques for a specific model of attack have been proposed, to analyze and design detection and defense mechanisms against multiple types of attacks for CPSs requires new system frameworks. Besides security, other requirements such as optimal control cost also need to be considered. The hybrid game model we propose contains physical states that are described by the system dynamics, and a cyber state that represents the detection mode of the system composed by a set of subsystems. A strategy means selecting a subsystem by combining one controller, one estimator and one detector among a finite set of candidate components at each state. Based on the game model, we propose a suboptimal value iteration algorithm for a finite horizon game, and prove that the algorithm results an upper bound for the value of the finite horizon game. A moving-horizon approach is also developed in order to provide a scalable and real-time computation of the switching strategies. Both algorithms aim at obtaining a saddle-point equilibrium policy for balancing the system’s security overhead and control cost. The paper illustrates these concepts using numerical examples, and we compare the results with previously system designs that only equipped with one type of controller. [ABSTRACT FROM AUTHOR]

Abstract: Gene regulatory networks capture the interactions between genes and other cell substances, resulting from the fundamental biological process of transcription and translation. In some applications, the topology of the regulatory network is not known, and has to be inferred from experimental data. The experimental data consist of expression levels of the genes, which are typically measured as mRNA concentrations in micro-array experiments. In a so-called genetic perturbation experiment, small perturbations are applied to equilibrium states and the resulting changes in expression activity are measured. This paper develops novel algorithms that identify a sparse and stable genetic network that explains data obtained from noisy genetic perturbation experiments. Our identification algorithm is based on convex relaxations of the sparsity and stability constraints and can also incorporate a variety of prior knowledge of the network structure. Such knowledge can be either qualitative, specifying positive, negative or no interactions between genes, or quantitative, specifying a range of interaction strengths. Our approach is applied to both synthetic and experimental data, obtained for the SOS pathway in Escherichia coli, and the results show that the stability specification not only ensures consistency with the steady-state assumptions, but also significantly increases the identification performance. Since the method is based on convex optimization, it can be efficiently applied to large scale networks. [Copyright &y& Elsevier]

Abstract: In this paper, we address the temporal logic motion planning problem for mobile robots that are modeled by second order dynamics. Temporal logic specifications can capture the usual control specifications such as reachability and invariance as well as more complex specifications like sequencing and obstacle avoidance. Our approach consists of three basic steps. First, we design a control law that enables the dynamic model to track a simpler kinematic model with a globally bounded error. Second, we built a robust temporal logic specification that takes into account the tracking errors of the first step. Finally, we solve the new robust temporal logic path planning problem for the kinematic model using automata theory and simple local vector fields. The resulting continuous time trajectory is provably guaranteed to satisfy the initial user specification. [Copyright &y& Elsevier]