State constrained reachability for stochastic hybrid systems

Many control problems can be formulated as driving a system to reach some target states while avoiding some unwanted states. We study this problem for systems with regime change operating in uncertain environments. Nowadays, it is a common practice to model such systems in the framework of stochastic hybrid system models. In this casting, the problem is formalized as a mathematical problem named state constrained stochastic reachability analysis. In the state constrained stochastic reachability analysis, this probability is computed by imposing a constraint on the system to avoid the unwanted states. The scope of this paper is twofold. First we define and investigate the state constrained reachability analysis in an abstract mathematical setting. We define the problem for a general model of stochastic hybrid systems, and we show that the reach probabilities can be computed as solutions of an elliptic integro-differential equation. Moreover, we extend the problem by considering randomized targets. We approach this extension using stochastic dynamic programming. The second scope is to define a developmental setting in which the state constrained reachability analysis becomes more tractable. This framework is based on multilayer modelling of a stochastic system using hierarchical viewpoints. Viewpoints represent a method originated from software engineering, where a system is described by multiple models created from different perspectives. Using viewpoints, the reach probabilities can be easily computed, or even symbolically calculated. The reach probabilities computed in one viewpoint can be used in another viewpoint for improving the system control. We illustrate this technique for trajectory design.     

Output controllability and optimal output control of positive fractional order linear discrete system with multiple delays in state, input and output

The article concerns output controllability and optimal output control of positive fractional order discrete linear systems with multiple delays in state, input and output. Necessary and sufficient conditions for output reachability (output controllability from zero initial conditions) and null output controllability (output controllability to zero final output) are given and proven. We also prove that the positive system is output controllable if it is output reachable and null output controllable with the output reachability index is equal or less than the null output controllability index. Sufficient conditions for the solvability of the optimal output control problem are given. Numerical examples are presented to illustrate the theoretical results.     

Falsification of hybrid systems with symbolic reachability analysis and trajectory splicing

The falsification of a hybrid system aims at finding trajectories that violate a given safety property. This is a challenging problem, and the practical applicability of current falsification algorithms still suffers from their high time complexity. In contrast to falsification, verification algorithms aim at providing guarantees that no such trajectories exist. Recent symbolic reachability techniques are capable of efficiently computing linear constraints that enclose all trajectories of the system with reasonable precision. In this paper, we leverage the power of symbolic reachability algorithms to improve the scalability of falsification techniques. Recent approaches to falsification reduce the problem to a nonlinear optimization problem. We propose to reduce the search space of the optimization problem by adding linear state constraints obtained with a reachability algorithm. An empirical study of how varying abstractions during symbolic reachability analysis affect the performance of solving a falsification problem is presented. In addition, for solving a falsification problem, we propose an alternating minimization algorithm that solves a linear programming problem and a non-linear programming problem in alternation finitely many times. We showcase the efficacy of our algorithms on a number of standard hybrid systems benchmarks demonstrating the performance increase and number of falsifyable instances.     

Partial Differential Equation for Evolution of Star-Shaped Reachability Domains of Differential Inclusions

The problem of reachability for differential inclusions is an active topic in the recent control theory. Its solution provides an insight into the dynamics of an investigated system and also enables one to design synthesizing control strategies under a given optimality criterion. The primary results on reachability were mostly applicable to convex sets, whose dynamics is described through that of their support functions. Those results were further extended to the viability problem and some types of nonlinear systems. However, non-convex sets can arise even in simple bilinear systems. Hence, the issue of nonconvexity in reachability problems requires a more detailed investigation. The present article follows an alternative approach for this cause. It deals with star-shaped reachability sets, describing the evolution of these sets in terms of radial (Minkowski gauge) functions. The derived partial differential equation is then modified to cope with additional state constraints due to on-line measurement observations. Finally, the last section is on designing optimal closed-loop control strategies using radial functions.     

Constructing the reachability set for a control problem with phase constraints

A method is proposed for describing the reachability set in a phase-constrained control problem. Sufficient conditions are obtained when the reachability set in a phase-constrained control problem is the intersection of two sets: the reachability set for the corresponding problem without phase constraints and the set of phase constraints. __________ Translated from Nelineinaya Dinamika i Upravlenie, No. 4, pp. 397–399, 2004.     

Time-constrained temporal logic control of multi-affine systems

In this paper, we consider the problem of controlling a dynamical system such that its trajectories satisfy a temporal logic property in a given amount of time. We focus on multi-affine systems and specifications given as syntactically co-safe linear temporal logic formulas over rectangular regions in the state space. The proposed algorithm is based on estimating the time bounds for facet reachability problems and solving a time optimal reachability problem on the product between a weighted transition system and an automaton that enforces the satisfaction of the specification. A random optimization algorithm is used to iteratively improve the solution.     

Interval techniques for enclosures of regions of reachability and controllability and for guaranteed state and parameter estimation of dynamical systems

Interval techniques are a powerful means for calculation of enclosures of the regions of reachability and controllability of dynamical systems with uncertainties during analysis and design of controllers. In this contribution, both discrete-time and continuous-time dynamical systems are considered. Using suitable algorithms, guaranteed state enclosures can be determined for systems with uncertain parameters, uncertain initial conditions, nonlinearities, and time-varying characteristics. Although both uncertain system parameters and bounded control variables are assumed to be represented by interval boxes in the following, they have to be distinguished in reachability and controllability analysis. Typically, robustness specifications for controllers of dynamical systems are given in terms of bounds on the system's time response which must not be violated for any possible operating condition. Hence, reachability as well as controllability of states have to be proven for all possible parameter values but for at least one admissible control sequence. Robust control strategies for nonlinear systems usually rely on knowledge of all current states. However, the complete state vector is not always directly accessible for measurement. In this case, observers are applicable to reconstruct non-measurable state variables. Furthermore, they can reduce the uncertainties of the measured quantities by model-based recursive computation of estimates and fusion of information gathered by different measurement devices. If guaranteed bounds of all uncertain parameters of a dynamical system (including the sensor characteristics) and conservative bounds of all disturbances can be specified, the presented interval observer provides guaranteed enclosures of all reachable states. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Stability analysis of probabilistic Boolean networks with switching topology

This paper investigates the set stability of probabilistic Boolean networks (PBNs) with switching topology. To deal with this problem, two novel concepts, set reachability and the largest invariant set family, are defined. By constructing an auxiliary system, the necessary and sufficient conditions for verifying set reachability are given and the calculation method for the largest invariant set family is obtained. Based on these two results, an equivalent condition of set stability is derived, which can be used to determine whether a PBN with switching topology can be stabilized to a given set. In addition, the design method of switching signal is proposed by combining the characteristic of the largest invariant set family, and a numerical example is reported to demonstrate the efficiency of presented approach.     

On weak and strong reachability and controllability of infinite-dimensional linear systems

The notions of reachability and controllability generalize to infinite-dimensional systems in two different ways. We show that the strong notions are equivalent to finite-time reachability and controllability. For discrete systems in Hilbert space, we get simple relations generalizing the Kalman conditions. In the case of a continuous system in Hilbert space, weak reachability is equivalent to the weak reachability of a related discrete system via the Cayley transform.This research was partially supported by the Batsheva de Rothschild Fund for the Advancement of Science and Technology.     

Reachability realization and stabilizability of switched linear discrete-time systems

In this paper, the reachability realization of a switched linear discrete-time system, which is a collection of linear time-invariant discrete-time systems along with some maps for “switching” among them, is addressed. The main contribution of this paper is to prove that for a switched linear discrete-time system, there exists a basic switching sequence such that the reachable (controllable) state set of this basic switching sequence is equal to the reachable (controllable) state set of the system. Hence, the reachability (controllability) can be realized by using only one switching sequence. We also discuss the stabilizability of switched systems, and obtain a sufficient condition for stabilizability. Two numeric examples are given to illustrate the results.     

Comparison principle for equations of the Hamilton-Jacobi type in control theory

This paper deals with the comparison principle for the first-order ODEs of the Hamilton-Jacobi-Bellman and Hamilton-Jacobi-Bellman-Isaacs type which describe solutions to the problems of reachability and control synthesis under complete as well as under limited information on the system disturbances. Since the exact solutions require fairly complicated calculation, this paper presents the upper and lower bounds to these solutions, which in some cases may suffice for solving such problems as the investigation of safety zones in motion planning, verification of control strategies or of conditions for the nonintersection of reachability tubes, etc. For systems with original linear structure it is indicated that present among the suggested estimates are those of ellipsoidal type, which ensure tight approximations of the convex reachability sets as well as of the solvability sets for the problem of control synthesis.     

Dynamic programming for stochastic target problems and geometric flows

Given a controlled stochastic process, the reachability set is the collection of all initial data from which the state process can be driven into a target set at a specified time. Differential properties of these sets are studied by the dynamic programming principle which is proved by the Jankov-von Neumann measurable selection theorem. This principle implies that the reachability sets satisfy a geometric partial differential equation, which is the analogue of the Hamilton-Jacobi-Bellman equation for this problem. By appropriately choosing the controlled process, this connection provides a stochastic representation for mean curvature type geometric flows. Another application is the super-replication problem in financial mathematics. Several applications in this direction are also discussed. Received October 24, 2000 / final version received July 24, 2001?Published online November 27, 2001     

Analysis of multi-stage open shop processing systems

We study algorithmic problems in multi-stage open shop processing systems that are centered around reachability and deadlock detection questions. We characterize safe and unsafe system states. We show that it is easy to recognize system states that can be reached from the initial state (where the system is empty), but that in general it is hard to decide whether one given system state is reachable from another given system state. We show that the problem of identifying reachable deadlock states is hard in general open shop systems, but is easy in the special case where no job needs processing on more than two machines (by linear programming and matching theory), and in the special case where all machines have capacity one (by graph-theoretic arguments).     

Observability of hybrid discrete-continuous systems

We study the statement and solvability of observability problems in linear stationary hybrid discrete-continuous dynamical systems. Necessary and sufficient observability conditions expressed directly via the system parameters are derived. We consider linear observability problems and the dual controllability and reachability problems. The problem of computing the minimum number of inputs for which the system has a given observability is discussed. An example illustrating the results is presented.     

Some remarks on Boolean control systems: Controllability domains and realization theory

We construct a theory of realizations and controllability domains for linear stationary systems in the category of finitely generated free semimodules over a Boolean semiring. We show that the classical realization theorems cannot be generalized to this case, and we prove some incomplete analogs of these theorems. We analyze the structure of controllability domains and the reachability and observability characteristics. In particular, we define a geometric object representing the reachability properties of a system, namely, the generalized reachability topology on the state space.     

Stabilization of stationary affine control systems with discrete time

We obtain new sufficient conditions for the local and global asymptotic stabilization of the zero solution of a nonlinear affine control system with discrete time and with constant coefficients by a continuous state feedback. We assume that the zero solution of the free system is Lyapunov stable. For systems with linear drift, we construct a bounded control in the problem of global asymptotic state and output stabilization. Corollaries for bilinear systems are obtained.     

Algebraic Properties and Design of Sampling Rates in Hybrid Linear Systems Under Multirate Sampling

This paper addresses the investigation of the reachability, observability and stabilizability properties of hybrid linear systems under multirate sampling. Technical results guaranteeing such properties at sampling instants and in between samples are formulated and proved. It is shown that the above properties can be investigated in terms of ranks of real or complex matrices if the system parameters are periodic or constant. The freedom in the choice of the sampling rates is finally used, under observability and exponential stability conditions, in the context of a optimal worst-case design. Two numerical examples are given. The first one is related to the design of such sampling rates for all possible choices of the inputs in a worst-case design context by using loss functions involving linear combinations of the L ₂ and induced l ₂ norms. The second one considers the choice of the sampling rates for an optimal transmission of possible rounding or measurement errors in the reachability problem.     

纯增益反馈控制律在MF模型中的应用研究

给出蒙代尔-弗莱明模型的动态表述,并证明蒙代尔-弗莱明模型的动态系统具有能控性、能达性、能观性等结构特征.在蒙代尔-弗莱明模型动态系统的基础上对开放经济条件下宏观经济模型的供需均衡问题转化为宏观经济政策的控制律设计问题,得出开放经济条件下宏观经济政策的纯增益反馈控制律的解析解并且对控制律的解析解的政策含义作出阐述.本文...     

Global controllability and computation of controls in nonlinear systems

The authors consider the problem of constructing an admissible open-loop control of bounded energy steering a nonlinear system from a given initial state to a given final state under the condition that the first-approximation system is completely controllable. The convergent iterative procedure for computing an admissible control is verified. It is shown that a nonlinear system locally controllable with respect to the first approximation becomes globally completely controllable for any boundary conditions from the stability region if the initial nonlinear system is stabilizable up to the asymptotic stability in the large and in the whole and the nonlinear terms either satisfy the global Cauchy-Lipschitz condition or are polynomials of a certain degree in state coordinates with arbitrary coefficients. The nonlinear system of algebraic equations to computation of whose solutions the problem of constructing the admissible control reduces is indicated. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 26, Nonlinear Dynamics, 2005.